前段时间借了本《算法设计》大致看完了，作个小结。

大的方向：分治与递归

发现这个是经典啊，递归是分治思想的实现方法。递归有两个方面，一个是递归方程，是设计分治问题的数学工具，于是就有主方法，主定理，这一块比较容易用来考试，像考研啊可能会比较喜欢这块内容，还有一个就是程序中的递归，这个需要技巧，先别乱用。

分治这条线下来，看最优问题中的两个常见范型，DP和贪心，她们的共同点是有最优子结构，怎么刻划最优子结构？就是递归方程，写成方程是最终目的，一开始可以简单表示，然后考虑需要考虑的量，然后转化成方程，有了递归方程再做程序，程序中不要用递归，而是打表，做备忘录或者直接递推，最后再由结果构造最优解，这样DP算法设计完毕。贪心的数学工具是拟阵，它是非空的，可遗传的，可独立扩充的一个二元集合，对拟阵有Greedy算法，这是有证明的算法，于是在贪心算法的具体问题上如果发现它满足拟阵的定义就可以直接运用贪心算法。贪心和DP的区别在于，贪心是从当前状态简单的做出最优判断，做状态转移，也可以看成是先排序（或大致有序）再一一进行选择，然后最优解就可以简单地构造出来，而DP是对当前状态进行一个计算，然后再构造最优集。贪心算法从理论上虽然不完美，但实际中有很重要的作用，像Dijkstra单源点最短路径算法，Prim算法等都是贪心。顺便提一下优先队列，这个数据结构可以用于最优问题中的选择算法，它可以动态的维护一个堆，而不是作相对费时的排序操作，而使算法性能提高很多。这一块分出来，叫面向数据结构的算法设计。此外，最优化问题远不仅如此，像LP等，那都是工科数学做的，应用方面多在工程上。

分治DP这一块有很多很多经典问题，有些问题本身都可以看成是算法设计范型，应用相当广泛，像LCS，归并，快排等。

递归这条线下来，看回溯法。回溯是王道啊。这里要了解解集和解集树的概念，在不是最优问题时或者没有最优子结构的最优问题里，就需要先构造解集树。这里和图论中的DFS有一些联系，实际上对图的一次DFS就是对它的某个生成树的遍历，其实质上也就是回溯。回溯就是先构造解的一部分，再决定是继续构造解还是退回，也就是回溯一词的本意。更广泛的来讲，回溯不仅限于DFS，DFS只是延深度方向延拓结点构造解，而回溯也可以延广度方向，或者是其它形式。理解了DFS，相当于理解了回溯的一大半，于是你就可以轻松的设计全排列、8皇后等问题。对回溯更进一步的了解，发现它是一种一般的搜索算法的设计思路，不管是求一个可行解还是没有最优子结构的最优构，都需要搜索。搜索算法可以简单的分成DFS和BFS和其它，也可以按启发式分，有非启发性的蛮力搜索和启发式搜索，像最优搜索，还有非常流行的A*，以及BB（Branch and Bound），这些思想说起来简单，但对具体问题还是很难于掌握的，它们在总的思想上是一致的，就是回溯，原始意义上的回溯，是指在发现当前构造了的一部分解无法继续构造下去，就是预先知道此路径走不通，也即此子树上没有目标解，那就回溯，其本质就是杀死活结点，常常也称作剪枝。另外还有一部分，人工智能上的搜索，A*算是其中一种常见的，像对弈算法中的Alpha_beta搜索等。DFS可以用程序中的递归进行设计，于是递归可以在这里放心大胆地使用，你会发现递归没那么神秘。

此外就还剩NP问题，这些现在只当是了解吧。世界上的问题，如果都转化成判定问题，就分为P类，NP是不是P的子集现在没有答案，但是从人类对它做过的努力，我觉得希望比较小。这些都是从问题的复杂性上分的，解决一个问题可以设计一个算法，算法有一个复杂性，算法的好坏与否就在于是否达到了问题本身的复杂性，比如全排列算法，它本身就是要操作O(n!)，那用回溯法设计的就已经很好了。

整个一条线贯穿整本书的，就是分治法，分治思想，整本书读厚再读薄，最后读成两个字，分治。

评论