3SUM
{{unsolved|計算機科學|是否存在一个算法，能够在O(n^{2-\epsilon}) （\epsilon>0）的时间复杂度内解决3SUM问题？}} 在计算复杂度理论中, 3SUM问题是指如下的问题：给定一个包含n个实数的集合，判断其中是否包含3个和为0的元素。问题也可以推广到一个更一般化的版本，rSUM，是要求判断集合中是否存在r个数的和为0。3SUM问题可以很容易地在O(n^2)的时间复杂度内解决。对于某些特化的计算模型，这已…
标签：#多项式时间问题
共 7 篇文章
最长公共子序列
最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的問題。这与查找最長公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。 定義 一个数列S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S称为已…
贝尔曼-福特算法
贝尔曼-福特算法（），求解单源最短路径问题的一种算法，由理查德·貝尔曼和小萊斯特·倫道夫·福特创立。有时候这种算法也被称为貝爾曼-福特-摩爾算法（Bellman–Ford–Moore algorithm），因为愛德華·F·摩爾也为这个算法的发展做出了贡献。它的原理是对图进行 |V|-1次松弛操作，得到所有可能的最短路径。其优于戴克斯特拉算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O (|V| |E|)。但算法可以…
最短路问题
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： 确定起点的最短路径问题 - 也叫单源最短路问题，即已知起始结点，求最短路径的问题。在边权非负时适合使用Dijkstra算法，若边权为负时则适合使用Bellman-ford算法或者SPFA算法。 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完…
匹配 (图论)
在图论中，一个图是一个匹配（或称独立边集）是指这个图之中，任意两条边都没有公共的顶点。这时每个顶点都至多连出一条边，而每一条边都将一对顶点相匹配。 严格定义 对于一个给定的图G=(V,E)，这幅图的一个匹配M是图G的一个子图（由原来的图的一部分顶点和一部分边构成的图），其中每两条边都不相邻（没有公共顶点）。在匹配图中，一个顶点连出的边数至多是一条。如果这个顶点连出一条边，就称这个顶点是已匹配的。 图G的一个极大匹配是指这样一个匹配，它不…
Floyd-Warshall算法
算法（），中文亦称弗洛伊德算法或佛洛依德算法，是解决任意两点间的最短路径的一种算法，可以正確處理有向圖或负权（但不可存在负权回路）的最短路径問題，同时也被用于计算有向图的传递闭包。 算法的时间复杂度為O(|V|^3)，空间复杂度为O(|V|^2)，其中V是点集。 原理 算法的原理是动态规划。 设D_{i,j,k}为从i到j的只以(1..k)集合中的节点为中间節点的最短路径的长度。 #若最短路径经过点k，则D_{i,j,k}=D_{i,k…
边覆盖
在图论中，图的边覆盖是指一组边的集合，且该集合满足图的每个顶点都在至少一条边上。在计算机科学中，最小边覆盖问题是寻找最小个数边的边覆盖问题。它是属于覆盖问题类的优化问题，可以在多项式时间内求解。 定义 正式来说，图G的边覆盖是指一组边的集合C ，其满足G中的每个顶点都至少在C中的一条边上。其被描述为集合C覆盖了G中的所有顶点。下图显示了两个图中边缘覆盖的示例。 : 最小边覆盖是指最小可能数量的边覆盖。边覆盖数\rho(G)是最小边覆盖的…