分治法

分治法 分治法是种经典的算法设计策略，这种策略简单来说就是先把原问题分成规模更小的子问题，再把子问题划分成更小的子问题…一直划分到子问题十分容易解决，然后就能倒过来解决原问题。数学中数列项的递推式就能看做是基于分治策略的算法，数学中的递推式很多时候都比通项式更容易找到和理解，分治算法相对于一些其他的算法很多时候也是这样。虽然分治策略本身不限定算法的物理实现形式，但通常默认分治算法是递归函数程序。 由于分支策略只是一个大的设计框架，所以不同问题的分治算法间的区别可以很大，且同一问题也可能有多种分治算法。但所有分治算法都是遵循如下3大步骤的(或者说能按这几大步骤设计)： 1) 分解子问题：需要拆分出几个子问题，这些子问题的输入应该怎么求得； 2) 解决子问题：解决上述这些子问题，并得到子问题的解；… 阅读全文

棋盘覆盖问题(chess cover problem)在\({2^k}\times {2^k}\)的棋盘格(\(k\)为正整数)中，其有1个确定位置的方格一开始是被覆盖的，现提供4种不同L型骨牌(如上图所示)。棋盘覆盖问题要求得到其中1种方案，用这4种骨牌覆盖所有方格，且覆盖是没有任何重叠的。 然后找该问题的分治算法，由于棋盘长宽相等且是2的幂，所以棋盘能拆成等大的4个象限，被覆盖的方格在某个象限里。这时考虑在中心位置选一种形状的骨牌放入1个，要求其刚好横跨另外3个没有被覆盖方格的象限。这时这4个象限每个都刚好有1个被覆盖的方格，这样就可把这4个象限当成“子棋盘”来递归的求解子问题，直到遇到\(2\times 2\)的“子棋盘”时，使用1个骨牌覆盖后就等于完全解决了这个子问题，而无需继续递归下去求更小规模的子问题。… 阅读全文

Strassen矩阵乘法             为更好的讨论算法本身，本文矩阵特指行列数相等(方阵)且都为2的幂的矩阵。矩阵乘法的定义是\((AB)_{ij} = \sum_{k=0}^n A_{ik}B_{kj}\)。使用定义直接求\(AB\)需要嵌套3层循环，如果\(AB\)是\(m\times m\)的，时间复杂度是\(O(m^3)\)。如何高效的做矩阵乘法是个重要的问题，计算机各领域都需要用到。目前计算机学者们虽未找到该算法足够“紧”的“理论下界”，但一直都在发明更优的具体算法，目前最快“斯坦福方法”代价为\(O(m^{2.373})\)，第一个快于\(O(m^3)\)的算法由德国数学家Strassen于1969年提出。 结合上述(1)和(2)找一种分治算法，(2)把方阵均分为四象限，把每个象限作为“子矩阵”。根据矩阵乘法定义，矩阵乘法可以正确转化成(2)等号右边的递归形式。分析这种算法的时间复杂度，其包含8个“子矩阵乘法”和4次加法，所有加法和其他操作的总代价等于遍历矩阵的\(O(m^2)\)。所以时间复杂度满足\(T(m)=8T(\frac{m}{2})… 阅读全文

汉诺塔问题(Hanoi Tower Problem)印度有一个古老的传说，在贝拿勒斯的圣庙里，一块黄铜板上插着三根宝石针。印度教主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是汉诺塔(如上图所示)。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭。而梵塔、庙宇和众生也都将同归于尽。 \(k\)层汉诺塔问题可以这样表述：“有\(a,b,c\)三个柱子，其中\(a\)有\(k\)片圆盘，圆盘的大小从上到下严格递增。允许一次移动一个圆盘到其他柱子，每次移动后所有柱子上的圆盘上面不能有更大的圆盘。问如何操作能把所有圆盘移动到\(c\)柱”。这里规定解为序列，序列元素是二元组\((X,Y)\)表示“从\(X\)柱移一片圆盘到\(Y\)柱”，那么解就是有顺序的一系列移动步骤。… 阅读全文

约瑟夫环问题传说在古罗马时期，罗马人占领乔塔帕特后，犹太士兵与约瑟夫不愿投降，于是约瑟夫提出一起自杀的方式：“所有人围成圈，从某人开始报数，每报到3该人自杀，然后再由下个人重新报数，直到所有人自杀”。但约瑟夫其实不想自杀，那他站在什么位置才能最后轮到他自杀？这就是约瑟夫环问题，也叫丢手绢问题。问题的解可用士兵编号来表示。 简单的算法是用环形链表模拟过程，但这里讨论复杂一点的分治算法。先用\(G(n,k)\)符号表示“共\(n\)个人，间隔为\(k\)(\(k=1\)表示下个人)的约瑟夫环问题”。对于\(G(n,k)\)，第一次士兵自杀后，问题转化为更小规模的\(G(n-1,k)\)，求解\(G(n-1,k)\)得到最后自杀的编号后，将其换算为问题\(G(n,k)\)对应的编号即可。进一步定义函数\(F(n,k)\)为“问题\(G(n,k)\)的解，其中士兵编号从0开始”，定义域满足\(n>0,k\geq… 阅读全文

最大连续子序列 最大连续子序列是“由原序列中连续元素构成的所有序列里，元素和最大的”，比如\([11, -4, 13, -5, 5,-1]\)的最大连续子序列有\([11,-4,13]\)和\([11,-4,13,-5,5]\)两个。这里规定空序列不能作为问题的输入，非空序列的最大连续子序列至少包含1个元素。那么对于全负序列，其最大连续子序列仅包含其中的最大值。然后来寻找其分治算法，设\(L=[0,…,n]\)为序列，将其尽量等长分为非空的\(L_1=L[0,…,k]\)与\(L_2=L[k+1,…,n]\)。如下情况至少成立1种： a) \(L\)存在可作为\(L_1\)最大连续子序列的最大连续子序列； b) \(L\)存在可作为\(L_2\)最大连续子序列的最大连续子序列；… 阅读全文

(01)背包问题背包问题(Knapsack Problem)是一类著名的运筹学、应用数学的问题，其相关研究可追溯至1897年。其中最简单的背包问题是(01)背包问题。其可描述为“给定一个物品序列\([t_0,t_1…t_n]\)，序列中任意下标\(i\)的物品都有体积\(A_i\)和价值\(B_i\)两个指标，现有容积\(V\)的背包，问放入背包哪些物品能取到最大价值”。这个问题的解不一定唯一，这里规定解的格式为和物品序列等长的序列，序列下标\(i\)的元素能取的值是0/1，表示物品序列下标\(i\)的物品不放/放入背包。 然后找问题的分治算法，这里先用一个符号\(G(k,V)\)表示“对物品序列前\(k+1\)项构成的子序列\([t_0,t_1…t_k]\)，求一个能放入体积\(V\)背包的最大价值物品组合”。然后考虑如何用规模更小的若干个\(G\)构造出\(G(k,V)\)的一个解。这里先直接给出结论，按如下2种方式得到的物品组合，总价最大的其中一个可作为\(G(k,V)\)的解：… 阅读全文

比较排序排序算法(sorting)是一类非常重要的基础算法，高德纳在其著作《计算机程序设计艺术》的第3卷专门讨论排序与查找。排序算法一般被分为比较排序(comparison sort)与非比较排序两类来研究，其中比较排序是通过两两比较元素最终得到排序的算法。在设计实际应用的排序算法时通常会关注如下特性： 1）稳定性：比较结果相等的元素能够保持原本的次序； 2）原地性(in-place)：能够在原数据结构上完成排序而不是创建新数据结构存储排序结果；     对于实际应用中的比较排序程序，会根据问题规模选择算法、根据内存限制考虑利用外存、做并行计算(排序网络)等，这里不考虑。排序算法通常会尽量满足如下特性： 1）稳定：相等的元素维持原来的次序； 2）原地排序：在原存储结构（比如数组）上完成排序，而不是用新对象存储结果；… 阅读全文

选择问题 选择问题是求集合的第\(k\)小(第\(k\)大)元素。具体可表述为“给定乱序序列，求其递减排序序列中，下标为\(k-1\)的元素”。最容易想到的是直接用\(O(nlgn)\)分治排序对整个序列排序，另一种思路是遍历\(k\)次序列，每轮都求一个最大值的下标，每轮求的时候都避开之前已求出的下标，这样代价是\(O(nk)\)，如果\(k\)是常数就是\(O(n)\)，但如果\(k\)和\(n\)同阶就是\(O(n^2)\)。 这里看一种基于快速排序的算法，快速排序每次递归都会把序列分为左右两半，右半边的任意元素都大于等于左半边的任意元素。这时如果分别记录左半边和右半边的长度，就能确定第\(k\)小元素是在左半边还是右半边。接下来就不用像快排那样分别递归左半边和右半边，只需要递归两者中的其中一个。递归前需要把\(k\)换算，转换成表示“子问题”中的第\(k’\)小元素。… 阅读全文