循环图中最长路径问题的优化
试图找到循环图中最长的路径有哪些优化？
已知循环图中最长的路径是NP完全的。 什么优化或启发式算法可以比查找整个图表更快地找到最长的路径？ 有没有任何概率方法？
我有一个具有特定质量的图表，但在一般情况下我正在寻找这个答案。 链接到论文将是太棒了。 这是一个部分答案：
确认它是循环的。 非循环图中最长的路径很容易使用动态编程来计算。
找出图表是否平坦（哪种算法最好？）。 如果是的话，你可能会看到它是块图，托勒密图还是仙人掌图，并应用本文中找到的方法。
找出使用Donald B Johnson算法的多少个简单循环（Java实现）。 您可以通过删除简单循环中的边来将任何循环图变成非循环图。 然后，您可以运行维基百科页面上的动态编程解决方案。 为了完整性，您必须对每个循环执行N次，其中N是循环的长度。 因此，对于整个图表，您必须运行DP解决方案的次数等于所有周期长度的乘积。
如果您必须对整个图进行DFS，则可以通过提前计算每个节点的“可达性”来修剪某些路径。 这种主要适用于有向图的可达性是每个节点无需重复就可以到达的节点数量。 这是来自该节点的最长路径可能的最大值。 有了这些信息，如果您当前的路径加上子节点的可达性小于您已经找到的最长路径，那么采用该分支就没有意义了，因为您不可能找到更长的路径。
这是一个O（n * 2 ^ n）动态规划方法，对于20个顶点应该是可行的：
m(b, U) =以b结尾的任何路径的最大长度，并且只访问（某些） U的顶点。
最初，设置m(b, {b}) = 0 。
那么，对于U所有x ， m(b, U) = m(x, U - x) + d(x, b)最大值，使得x不是b并且存在边(x, b) 。 取所有终点b的这些值的最大值， U = V （全部顶点）。 这将是任何路径的最大长度。
以下C代码假设d[N][N]的距离矩阵。 如果图形未加权，则可以将对该数组的每个读访问权限更改为常量1 。 在数组p[N][NBITS]也计算显示最佳顶点序列（可能不止一个）的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，需要大约160Mb（其中一半用于前一曲线）。
（请不要使用固定大小的数组，在一个真正的程序中使用malloc() （或者更好，C ++ vector<int> ），我只是这样写的，所以事情会变得更清晰。