騎士巡邏
騎士巡禮（）是指在按照国际象棋中骑士的规定走法走遍整个棋盘的每一个方格，而且每个网格只能夠经过一次。假若騎士能夠從走回到最初位置，則稱此巡禮為「封閉式巡禮」，否則，稱為「開放巡禮」。對於88棋盤，一共有26,534,728,821,064種封閉巡禮，有19,591,828,170,979,904種開放式巡禮。 由骑士巡禮引申出了一个著名的数学问题 ：骑士巡禮问题--找出所有的骑士巡禮路徑。編寫一個程式来找出骑士巡禮路徑經常在计算机系的学…
标签：#图算法
共 35 篇文章
极小化极大算法
Minimax算法（亦稱 MinMax or MM）又名极小化极大算法，是一种找出失败的最大可能性中的最小值（最小化最坏情况）的算法。 概述 Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法。而开始的时候总和为0。很多棋类游戏可以采取此算法，例如井字棋（tic-tac-toe）。 偽代碼 function minimax(no…
图神经网络
图神经网络（，簡稱GNNs）是一类专门设计用于输入为图的人工神经网络。，每个输入样本都是一个分子的图表示，其中原子形成节点，原子之间的化学键形成边。除了图表示之外，输入还包括每个原子的已知化学性质。因此，数据集样本的长度可能不同，这反映了分子中原子数量的变化以及它们之间键的数量的变化。该网络的最终任务是预测给定分子在特定医疗应用中的功效，例如消除大肠杆菌（E. coli）。 GNN的关键设计元素是使用“成对消息传递（pairwise m…
埃德蒙兹-卡普算法
计算机科学中，埃德蒙兹-卡普算法（）通过实现福特-富尔克森算法来计算网络中的最大流，其时间复杂度为O(VE^2)。该算法由在1970年最先提出，并由和理查德·卡普在1972年独立发表。 C++實作 以下是关于埃德蒙兹-卡普算法的C++语言描述： struct Main { struct Edge { int u, v, Capacity, Flow; Edge (int u, int v, int Capacity, int Flow)…
Alpha-beta剪枝
Alpha-beta剪枝是一种搜索算法，用以减少极小化极大算法（Minimax算法）搜索树的节点数。这是一种对抗性搜索算法，主要应用于机器游玩的二人游戏（如井字棋、象棋、围棋）。当算法评估出某策略的后续走法比之前策略的还差时，就会停止计算该策略的后续发展。该算法和极小化极大算法所得结论相同，但剪去了不影响最终决定的分枝。 历史 Allen Newell和Herbert A. Simon在1958年，使用了John McCarthy所谓的…
图的遍历
图的遍历问题分为四类： 遍历完所有的边而不能有重复，即所謂“欧拉路径问题”（又名一笔画问题）； 遍历完所有的顶点而没有重复，即所谓“哈密頓路径问题”。 遍历完所有的边而可以有重复，即所谓“中国邮递员问题”； 遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。 对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。 第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密顿图的性质。 算法 图的遍…
图同构
图同构（）描述的是图论中，两个图之间的完全等价关系。在图论的观点下，两个同构的图被当作同一个图来研究。 定义 一般定义 只有节点数目相同(即同阶)的两个图才有可能同构。两个简单图G和H称为是同构的，当且仅当存在一个将G的节点 1,\ldots,n 映射到H的节点1,\ldots,n的一一对应\sigma，使得G中任意两个节点i和j相连接，当且仅当H中对应的两个节点\sigma(i)和\sigma(j)相连接。同构可记作G\simeq H…
最长路径问题
在图论和理论计算机科学中，最长路径问题是指在给定的图中找出长度最长的简单路径。一条不具有任何重复顶点的路径被称为简单路径。无权图中路径的长度就是边的数量，而有权图中路径长度是边权重之和。不同的是，与此相反的最短路径问题（不含负权环）可以在多项式时间内解决。而最长路径问题是NP困难的，这意味着除非P = NP，否则对应于任意的图，没有办法在多项式时间内解决该问题。更强的结果表明这个问题也難以近似地得出答案。但是，有一个线性时间的方法可以用…
福特-富尔克森算法
福特-富尔克森方法（），又稱福特-富尔克森算法（），是一类计算网络流的最大流的贪心算法。之所以称之为“方法”而不是“算法”，是因为它寻找增广路径的方式并不是完全确定的，而是有几种不同时间复杂度的实现方式。它在1956年由小萊斯特·倫道夫·福特及德爾伯特·雷·富爾克森发表。“福特-富尔克森”这个名词通常也指代埃德蒙兹-卡普算法，这是一个特殊的福特-富尔克森算法实现。 算法的思想如下：只要有一条从源点（开始节点）到汇点（结束节点）的路径，在…
克鲁斯克尔演算法
克魯斯克爾演算法（）是一種用來尋找最小生成樹的演算法，由美國數學家約瑟夫·克魯斯克爾在1956年發表。用來解決同樣問題的還有普林演算法和等。三種演算法都是贪心算法的應用。和布盧瓦卡演算法不同的地方是，克魯斯克爾演算法在圖中存在相同權值的邊時也有效。 步骤 新建图G，G中拥有原图中相同的节点，但没有边 将原图中所有的边按权值从小到大排序 从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中 重複3…
戴克斯特拉算法
{{Infobox algorithm |class=搜索算法 |image=Dijkstra Animation.gif |caption = 戴克斯特拉算法运行演示（找到A，B之间的最短路），本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离。在演示过程中访问过的结点会被标为红色。 |data=图 堆/优先队列（算法优化） |best-time= |average-time= |SpaceComp=O(|E|+|V|)…
贝尔曼-福特算法
贝尔曼-福特算法（），求解单源最短路径问题的一种算法，由理查德·貝尔曼和小萊斯特·倫道夫·福特创立。有时候这种算法也被称为貝爾曼-福特-摩爾算法（Bellman–Ford–Moore algorithm），因为愛德華·F·摩爾也为这个算法的发展做出了贡献。它的原理是对图进行 |V|-1次松弛操作，得到所有可能的最短路径。其优于戴克斯特拉算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O (|V| |E|)。但算法可以…
霍普克洛夫特-卡普算法
霍普克洛夫特－卡普算法（Hopcroft Karp算法）是用來解決二分圖最大匹配問題的一種演算法。 在匈牙利算法中，我们每次寻找一条增广路来增加匹配集合M。可以证明，每次找增广路的复杂度是\mathcal{O}\left( \left|E\right| \right)，一共需要增广\mathcal{O}\left(\left|V\right|\right)次，因此总时间复杂度为\mathcal{O}\left(\left|V\right…
迭代深化深度优先搜索
迭代深化深度优先搜索 （iterative deepening depth-first search (IDS or IDDFS)）是对状态空间的搜索策略。它重复地运行一个有深度限制的深度优先搜索，每次运行结束后，它增加深度并迭代，直到找到目标状态。 IDDFS 与广度优先搜索有同样的时间复杂度，但空间复杂度更低。 IDDFS 第一次访问节点的累积顺序是广度优先的。 例子 對於這張圖，若使用標準的深度優先搜索（DFS），則演算法會在B、…
旅行推销员问题
旅行商问题（，縮寫：TSP）是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。问题内容为“给定一系列城市和每對城市之间的距离，求解访-{}-问每座城市一次并回到起始城市的最短回路。” TSP是与车辆路径问题的一种特殊情况。 作为计算复杂性理论中一个典型的判定性问题，TSP的一个版本是给定一个图和长度 L，要求回答图中是否存在比 L 短的回路（英语：circuit或tour）。该问题被划分为NP完全问题。已知TSP算法最…
最短路问题
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： 确定起点的最短路径问题 - 也叫单源最短路问题，即已知起始结点，求最短路径的问题。在边权非负时适合使用Dijkstra算法，若边权为负时则适合使用Bellman-ford算法或者SPFA算法。 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完…
迪尼茨算法
迪尼茨算法（）是在网络流计算最大流的强多项式复杂度的算法，设想由以色列计算机科学家在1970年提出。算法O(V^2 E)的时间复杂度类似于埃德蒙兹-卡普算法，其时间复杂度为O(VE^2)，迪尼茨算法与埃德蒙兹-卡普算法的不同之处在于它每轮算法都选择最短的可行路径进行增广。迪尼茨算法中采用高度标号（level graph）以及阻塞流（blocking flow）实现性能。 历史 迪尼茨在格奧爾吉·阿傑爾松-韋利斯基（AVL树的发明者之一）…
置信度传播
置信度传播（），又称为乘积和信息传递（），是在贝叶斯网络、马尔可夫随机场等概率图模型中用于推断的一种信息传递算法。在给定已观测节点时，可以用该算法高效地计算未观测节点的边缘分布。置信度传播在人工智能、信息论中十分常见，已成功应用于低密度奇偶检查码、Turbo码、自由能估计、等不同领域。 置信度传播由美国计算机科学家朱迪亚·珀尔于1982年提出。最初该算法的运用范围仅限于树，不久则扩展到。此后，研究者发现在一般的图中该算法是一种十分有用的…
科萨拉朱算法
科萨拉朱算法（），也被称为科萨拉朱—夏尔算法，是一个在线性时间内寻找一个有向图中的强连通分量的算法。阿尔佛雷德·艾侯，约翰·霍普克洛夫特和杰弗瑞·乌尔曼相信该算法来自于1978年撰写的一篇未发表论文之中。也独立发现了该算法并于1981年将其发表。该算法巧妙地利用了一个定理：「一个图的反向图和原图具有一样的强连通分量」。 简介 该算法主要用于枚举图中每一个强连通分量内的所有顶点。该算法可由以下四部分组成： 对有向图G取逆，得到G的反向图G…
激活扩散
激活扩散（）是一种搜索关联网络、生物和人工神经网络或语义网络的方法。这一搜索过程是通过给一组源节点（例如语义网络中的概念）贴上权重或“激活”来启动的，然后迭代地将激活传播或“扩散”到与源节点相连的其他节点。大多数情况下，这些“权重”是真实的数值，伴随激活在网络中的传播而逐渐衰减。当权重值是离散的时，这个过程通常被称为标记传递。激活可能来自不同的路径，由不同的标记识别，并在两个备用路径到达同一节点时终止。大脑研究表明，几个不同的大脑区域在…