算法 – 第 3 页 – JONY'S WORDPRESS

TRIE树

TRIE(前缀树/字典树)TRIE常用于存储和表示字符串的集合，并实现该集合上的增删字符串运算。其核心思想是用公共前缀表示字符串，比如abcd与abc的公共前缀是abc，当字符串间恰好没有公共前缀时，比如abc,edfg,czx构成的集合，那么其会存储3个前缀abc,edfg,czx。其常用于存储字符串构成的集合。其结构是这样的，Trie的根节点不存储字符，其他节点仅存储单个字符，且同一层节点无重复字符。节点有变量存储“颜色”，若某节点被“染色”说明从根到该节点的路径存储了一个字符串，除此之外Trie的叶节点肯定是“染色”的。下面讨论Trie的运算结构： 1）插入：首先查找根节点全部孩子节点，若找到待插入串首字符则进入该节点并重复该步骤，若没有则在该处新建节点并插入剩余字符，最终为叶节点染色。如果用哈希表/dict来记录每个节点的儿子，可以在\(O(1)\)时间完成当前层的查找，所以可以认为时间复杂度为字符数\(O(n)\)。… 阅读全文

STRASSEN矩阵乘法

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)背包问题

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

并查集与并查集森林

并查集(Union-find Disjoint Sets) 首先定义不相交集合数据结构(Disjoint-Sets Data Structure)，其首先是一个集合\(S = \{S_1,S_2,…,S_n \}\)，\(S\)中的元素也是集合，并且对于\(S\)中的任意两个元素\(S_x,S_y\)，都满足\(S_x\cap S_y=\emptyset\)。并查集则是带有特定运算的不相交集合数据结构，主要用于解决查询与合并的问题，由于\(S_x\)是可修改的，所以也称它们为动态集合。并查集运算的定义如下： 1) \(MAKE(x)\)：创建1个仅含元素\(x\)的动态集合，并把该动态集合加入到并查集中；是若干不相交动态集合组成的集合\(S = \{S_1,S_2,…S_n \}\)，不相交指任意两动态集合间无重复元素，从动态集合中任取一元素即可形成与该动态集合的单射。对并查集中的动态集合\(S_k\)而言，动态指\(S_k\)中的元素是从无到有通过\(S\)上定义的运算结构动态添加的，所以接下来讨论\(S\)上的运算结构：… 阅读全文

有向图与无向图

有向图与无向图数据结构中的图(Graph)是对数学分支图论(Graph Theory)中的图的表示，通常用二元组\(G=(V,E)\)定义图\(G\)，其中\(V\)是顶点的集合(顶点集)，\(E\)是边的集合(边集)。边集的元素也是二元组\((x,y)\)且\(x,y\)是\(V\)的元素，由于二元组包含\(x,y\)的序，若不关心\(x,y\)的序或用集合\(\{x,y\}\)表示边，则\(G\)是无向图，否则是有向图。一般按上图的方式“画”有向图和无向图。直观上图是对前面讨论过的树的推广，树不允许树边任意的加在两节点间，图边则没有这些限制，并且图中一般不会指定“树根”这样的顶点。所以图相比树会有更多更复杂的“边界情况”，给出与之相关的概念： 1) 重边：即重复的边。设\(u,v\)是图顶点，对于有向图，若存在2个以上的从\(u\)到\(v\)的边，则称从\(u\)到\(v\)有重边。对于无向图，若存在2个以上连接\(u\)和\(v\)的边，则称\(u\)与\(v\)间有重边。也就是边集中有“相同”的二元组；… 阅读全文

广度优先搜索

广度优先搜索(BFS) 之前所讨论的BFS是种“简化的”版本，而“通用的”BFS将作为其他图算法的框架，所以在通用BFS的执行途中需记录一些信息。算法导论中的BFS需要记录顶点颜色(白/灰/黑=未到达/已到达/已到达且所有邻接顶点已到达)。顶点的\(\pi\)为前驱顶点，\(d\)为前驱顶点的\(d+1\)(源点的\(d\)为0)。在这种定义下顶点入队时从白染灰，出队时从灰染黑。BFS结束后利用顶点的\(\pi\)可得到该BFS下源点与其可达顶点形成的BFS树，树中的顶点为黑色而其他未达的顶点为白色。 def bfs(graph,vertex): visited = [vertex,] queue = [vertex,] while queue: vertex = queue.pop(0) for v in graph.getVertices(vertex):… 阅读全文

深度优先搜索

深度优先搜索(DFS) 通用DFS的用途比通用BFS更广泛，DFS记录顶点颜色、前驱、变灰时间、变黑时间。顶点有三种色(白/灰/黑=未到达/已到达并开始当前顶点的子DFS/已到达且全部邻接顶点的子DFS结束亦即当前顶点的子DFS结束)。时间的定义是每次变色时间加一，其用于描述搜索的推进。顶点由白变灰意味着其子DFS的开始，该DFS会一直持续到该顶点变黑。任意子DFS在结束时比开始只会新增染黑的顶点。DFS往往要求访问完源点所有可达顶点后(此时根据可达顶点的前驱可得DFS树)，若顶点集尚有未达顶点，就从中选新源点在“当前时间”继续DFS(最终根据所有顶点的前驱可得DFS森林)。该要求意味在解决很多问题时从任意源点DFS不影响结果，而且往往需访问所有顶点。 def _dfs(graph,vertex,time,attr):… 阅读全文