尝试在循环图中找到最长路径存在哪些优化?
已知循环图中的最长路径是 NP 完全路径。哪些优化或启发式方法可以比对整个图进行 DFS 更快地找到最长路径?是否有任何概率方法?
我有一个具有特定特性的图表,但我正在寻找一般情况下的答案。链接到论文会很棒。这是部分答案:
确认它是循环的。非循环图中的最长路径很容易使用动态规划计算。
找出图形是否是平面的(哪种算法最好?)。如果是,您可能会查看它是 block 图、托勒密图还是仙人掌图,并应用 this paper 中的方法.
使用 Donald B Johnson's algorithm 找出有多少个简单循环(Java implementation)。您可以通过删除简单循环中的一条边,将任何有环图变成无环图。然后您可以运行在 the Wikipedia page 上找到的动态规划解决方案.为了完整起见,您必须为每个循环执行 N 次,其中 N 是循环的长度。因此,对于整个图,您必须运行 DP 解决方案的次数等于所有循环长度的乘积。
如果您必须对整个图进行 DFS,您可以通过提前计算每个节点的“可达性”来修剪一些路径。这个reachability,主要适用于有向图,是每个节点在不重复的情况下可以到达的节点数。它是从该节点可能的最长路径的最大值。有了这些信息,如果您当前的路径加上子节点的可达性小于您已经找到的最长路径,那么采用该分支就没有意义,因为您不可能找到更长的路径。
最佳答案
这是一个复杂度为 O(n*2^n) 的动态规划方法,对于最多 20 个顶点应该是可行的:
m(b, U)
= 以 b
结尾的任何路径的最大长度并且只访问 U
中的(部分)顶点.
最初,设置m(b, {b}) = 0
.
然后,m(b, U)
= m(x, U - x) + d(x, b)
的最大值总而言之x
在U
这样 x
不是 b
和一条边(x, b)
存在。为所有端点取这些值中的最大值 b
, 与 U
= V
(完整的顶点集)。这将是任何路径的最大长度。
以下 C 代码假定距离矩阵在 d[N][N]
中.如果您的图表未加权,您可以将对此数组的每次读取访问更改为常量 1
.在数组 p[N][NBITS]
中还计算了显示最佳顶点序列(可能不止一个)的回溯。 .
#define N 20
#define NBITS (1 << N)
int d[N][N]; /* Assumed to be populated earlier. -1 means "no edge". */
int m[N][NBITS]; /* DP matrix. -2 means "unknown". */
int p[N][NBITS]; /* DP predecessor traceback matrix. */
/* Maximum distance for a path ending at vertex b, visiting only
vertices in visited. */
int subsolve(int b, unsigned visited) {
if (visited == (1 << b)) {
/* A single vertex */
p[b][visited] = -1;
return 0;
}
if (m[b][visited] == -2) {
/* Haven't solved this subproblem yet */
int best = -1, bestPred = -1;
unsigned i;
for (i = 0; i < N; ++i) {
if (i != b && ((visited >> i) & 1) && d[i][b] != -1) {
int x = subsolve(i, visited & ~(1 << b));
if (x != -1) {
x += d[i][b];
if (x > best) {
best = x;
bestPred = i;
}
}
}
}
m[b][visited] = best;
p[b][visited] = bestPred;
}
return m[b][visited];
}
/* Maximum path length for d[][].
n must be <= N.
*last will contain the last vertex in the path; use p[][] to trace back. */
int solve(int n, int *last) {
int b, i;
int best = -1;
/* Need to blank the DP and predecessor matrices */
for (b = 0; b < N; ++b) {
for (i = 0; i < NBITS; ++i) {
m[b][i] = -2;
p[b][i] = -2;
}
}
for (b = 0; b < n; ++b) {
int x = subsolve(b, (1 << n) - 1);
if (x > best) {
best = x;
*last = b;
}
}
return best;
}
在我的 PC 上,这解决了一个 20x20 的完整图,边权重在 [0, 1000) 范围内随机选择,大约需要 7 秒,需要大约 160Mb(其中一半用于前导轨迹)。
(请不要评论使用固定大小的数组。在实际程序中使用 malloc()
(或更好,C++ vector<int>
)。我只是这样写的,这样事情会更清楚。)
关于algorithm - 循环图中最长路径问题的优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4252215/