JONY

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)\)的解：… 阅读全文