Loading AI tools
来自维基百科,自由的百科全书
图论中的经典问题哈密顿路径问题(台湾作漢米頓路徑問題)(Hamiltonian path problem)与哈密顿环问题(台湾作漢米頓環問題)(Hamiltonian cycle problem)分别是来确定在一个给定的图上是否存在哈密顿路径(一条经过图上每个顶点的路径)和哈密顿环(一条经过图上每个顶点的环)。两个问题皆为NP完全。[1]
哈密顿环问题与哈密顿路径问题之间有着很简单的关系:
在一个阶数为的图中,可能成为哈密顿路径的顶点序列最多有有!个(在完全图的情况下恰好为!个),因此暴力搜索所有可能的顶点序列是非常慢的。 一个早期的在有向图上寻找哈密顿环的算法是Martello的枚举算法[3] 由Frank Rubin[4] 提供的搜索过程将图的边分为3种类型:必须在路径上的边、不能在路径上的边和未定边。在搜索的过程中,一个决策规则的集合将未定边进行分类,并且决定是否继续进行搜索。这个算法将图分成几个部分,在它们上问题能够被单独地解决。
另外,Bellman, Held, and Karp 的动态规划算法可以在O(n2 2n)时间内解决问题。在这个方法中,对每个顶点集和其中的每一个顶点 ,均做出如下的判定:是否有一条经过中每个顶点,并且在结束的路径,对于每一对和,当且仅当存在的邻居满足存在一条路径经过的所有顶点,并在上结束的路径时,存在路径经过中每个顶点,并且在结束。这个充要条件已经可以之前的动态规划计算中确认。[5][6]
Andreas Björklund通过容斥原理将哈密尔顿环的计数问题规约成一个更简单,圈覆盖的计数问题,后者可以被通过计算某些矩阵的行列式解决。通过这个方法,并通过蒙特卡洛算法,对任意阶图,可以在O(1.657n)时间内解决。对于二分图,这个算法可以被进一步提升至o(1.415n)。[7]
对于最大度小于等于3的图,一个回溯搜索的方法可以在 O(1.251n)时间内找到哈密顿环。[8]
哈密顿环和哈密顿路径也可以通过SAT 求解器找到。
哈密顿环和哈密顿路径问题是FNP问题,它的决定性问题是检测是否存在一条哈密顿环或哈密顿路径。有向图和无向图上的哈密顿环问题是卡普的二十一个NP-完全问题中的其中两个。对于一些特殊类型的图来说,它们仍然是NP完全的。例如:
然而,对于某些类型的图,哈密顿环和哈密顿路径问题可以在多项式时间内解决:
将以上提供的条件汇总起来,3-正则,3-定点连通的二分图是否总是存在哈密顿环这一问题仍然是开放的,在这个情况下这一问题不是NP完全的,详见Barnette猜想。
在所有顶点的度都是奇数的途中,一个与握手引理有关的结论说明对于任意一条边来说,经过它的哈密顿环的个数总是偶数,因此如果存在一条哈密顿环,则一定存在另一条 [17] 然而,找到第二条哈密顿换并不是一个简单的计算问题。Papadimitriou定义了一个复杂性类 PPA来描述这一类问题。 [18]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.