回溯、贪心、DP的区别和联系

四大常用算法：分治、贪心、回溯、动态规划

回溯算法是个“万金油”。基本上能用跟动态规划、贪心解决的问题，都可以用回溯去解决。回溯算法相当于穷举搜索，穷举所有情况，然后得到最优解。不过回溯算法时间复杂度非常高，指数级的，只能解决小规模数据问题。对于大规模数据，执行效率就相当低。

void backtracking(参数) {

    if (终止条件) {

        存放结果;

        return;

    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {

        处理节点;

        backtracking(路径，选择列表); // 递归

        回溯，撤销处理结果

    }

}

动态规划算法高效，但并不是所有问题都可以用动态规划来解决，必须满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题上，动态规划和分治算法的区分很明显，分治算法分割成的子问题，不能有重复子问题，而动态规划则相反，之所以高效，就是因为回溯算法实现中存在大量重复子问题。DP问题一定是分阶段问题。动态规划其实就是一种遍历，但是他是带备忘录的遍历，对于前面算到的子问题，仅就不在计算而是直接查看备忘录

贪心算法算是动态规划的一种特殊情况。解决问题更加高效，代码实现更简洁，不过他解决问题也更加有限。他能解决的问题必须满足三个条件，最优子结构，无后效性和贪心选择性。其中，最优子结构和无后效性跟动态规划无异，贪心选择性，就是通过局部最优选择，能产生全局最优选择。每一个阶段，我们都选择当前最优的决策，所有阶段的决策完之后，最终由这些局部最优解构成全局最优解。

最优子结构：问题的整体最优解包含着它的子问题（某一个但不是全部子问题）的最优解。每一步贪心选完后会留下子问题，子问题的最优解和贪心选出来的解可以凑成原问题的最优解
贪心选择性：整体的最优解可通过一系列局部最优解达到。每一步贪心选出来的一定是原问题的最优解的一部分
无后效性：某阶段的状态旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整的总结，此前的历史只能通过当前的状态去影响过程未来的演变。

贪心VS动态规划

贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解则不作保留；

动态规划：全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有的局部最优解。

举例说明：也就是说，假如你要求第十步的最优解，那么第十步的最优解肯定与第九步的最优解有关，而第九步的最优解肯定与第八步的最优解有关。可以这么理解，贪心算法第十步的最优解得把前面九步的最优解都用上了，但是动态规划你需要求第十步的最优解，这个最优解可能只与第八步，第三步，第一步有关，与第九步没有关系，我们为什么选择第八步而不选择第九步呢？是因为我们在计算第十步的最优解的时候其实把1-9步的组合的情况都计算了，选择了其中最优的解，也就是第八步的解，其实第十步解的构成与第九步没有关系，动态规划相当于穷举了1-9步最优情况下的组合，选了其中最优的作为第十步的最优解，而贪心算法第十步的最优解肯定是由第九步构成的。

巴特西

回溯、贪心、DP的区别和联系

最新文章

热门文章