这个问题是 NP 困难的(从哈密顿路径到您的问题有一个简单的简化,并且哈密顿路径搜索已知是 NP 困难的)。这意味着这个问题没有多项式解(除非 P = NP)。
如果您需要精确的解决方案,您可以使用动态规划(具有指数数量的状态):状态为(mask of visited vertices, last_vertex)
,该值是 true 或 false。过渡是添加一个不在原点中的新顶点mask
如果之间有一条边last_vertex
和新的顶点。它有O(2^n * n^2)
时间复杂度还是比O(n!)
回溯。
这是动态规划解决方案的伪代码:
f = array of (2 ^ n) * n size filled with false values
f(1 << start, start) = true
for mask = 0 ... (1 << n) - 1:
for last = 0 ... n - 1:
for new = 0 ... n - 1:
if there is an edge between last and new and mask & (1 << new) == 0:
f(mask | (1 << new), new) |= f(mask, last)
res = 0
for mask = 0 ... (1 << n) - 1:
if f(mask, end):
res = max(res, countBits(mask))
return res
关于从哈密顿路径简化到这个问题的更多信息:
def hamiltonianPathExists():
found = false
for i = 0 ... n - 1:
for j = 0 ... n - 1:
if i != j:
path = getLongestPath(i, j) // calls a function that solves this problem
if length(path) == n:
found = true
return found
这是一个 Java 实现(我没有正确测试,因此它可能包含错误):
/**
* Finds the longest path between two specified vertices in a specified graph.
* @param from The start vertex.
* @param to The end vertex.
* @param graph The graph represented as an adjacency matrix.
* @return The length of the longest path between from and to.
*/
public int getLongestPath(int from, int to, boolean[][] graph) {
int n = graph.length;
boolean[][] hasPath = new boolean[1 << n][n];
hasPath[1 << from][from] = true;
for (int mask = 0; mask < (1 << n); mask++)
for (int last = 0; last < n; last++)
for (int curr = 0; curr < n; curr++)
if (graph[last][curr] && (mask & (1 << curr)) == 0)
hasPath[mask | (1 << curr)][curr] |= hasPath[mask][last];
int result = 0;
for (int mask = 0; mask < (1 << n); mask++)
if (hasPath[mask][to])
result = Math.max(result, Integer.bitCount(mask));
return result;
}