循环图中最长路径问题的优化
循环图中最长路径问题的优化
提问于 2010-11-23 02:30:38
在循环图中寻找最长路径存在哪些优化？
循环图中的最长路径已知是NP-完全的.什么样的优化或启发式可以使查找最长路径的速度比整个图的DFSing快？有什么概率方法吗？
我有一个具有特定性质的图表，但我正在寻找一般情况下的答案。链接到文件就太棒了。以下是部分答案：
- 确认它是循环的。非循环图中的最长路径很容易用动态规划来计算。
- 找出该图形是否为平面图(哪种算法最好？)如果是，您可能会看到它是块图、托勒密图还是仙人掌图，并应用本论文中的方法。
- 找出使用唐纳德·B·约翰逊算法 (Java实现)的简单循环数。您可以通过删除简单循环中的边缘，将任何循环图更改为无圈图。然后可以运行在维基百科页面上找到的动态编程解决方案。为了完整，您必须对每个周期执行N次，其中N是周期的长度。因此，对于整个图，必须运行DP解决方案的次数等于所有循环长度的乘积。
- 如果您必须对整个图进行DFS，您可以通过预先计算每个节点的“可达性”来修剪一些路径。这种可达性主要适用于有向图，即每个节点可以不重复到达的节点数。这是该节点可能存在的最长路径。有了这些信息，如果您的当前路径加上子节点的可达性小于您已经找到的最长路径，则没有必要使用该分支，因为您不可能找到更长的路径。
回答 1
Stack Overflow用户
发布于 2010-11-24 06:58:10
下面是一个O(n*2^n)动态规划方法，对于20个顶点来说应该是可行的：
m(b, U) =以b结尾的任何路径的最大长度，并且只访问U中的(某些)顶点。
最初，设置m(b, {b}) = 0。
然后，m(b, U) = m(x, U - x) + d(x, b)在U中所有x上的最大值，使得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)在大约7s和需要约160 my (其中一半是为前任跟踪)。
(请不要评论使用固定大小的数组.)在实际程序中使用malloc() (或者更好的是C++ vector<int>)。我就是这样写的，这样事情就更清楚了。)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4252215
复制相关文章
相似问题
腾讯云开发者
