algorithm - 循环图中最长路径问题的优化

在循环图中寻找最长路径有哪些优化？
循环图的最长路径是np完全的。什么样的优化或启发式可以使查找最长路径的速度快于对整个图的dfs操作？有概率方法吗？
我有一个具有特定性质的图表，但我正在寻找一般情况下的答案。链接到文件将是非常棒的。以下是部分答案：
确认它是循环的。非循环图中的最长路径很容易用动态规划计算。
找出图是否是平面的（哪种算法最好？）。如果是，您可以查看它是块图、托勒密图还是仙人掌图，并应用this paper中的方法。
找出使用Donald B Johnson's algorithm（Java implementation）的简单循环数。通过在简单循环中移除边，可以将任何循环图更改为非循环图。然后可以运行the Wikipedia page上的动态编程解决方案。为了完整起见，您必须为每个周期执行n次，其中n是周期的长度。因此，对于整个图，必须运行dp解决方案的次数等于所有循环长度的乘积。
如果必须dfs整个图，可以通过预先计算每个节点的“可达性”来修剪一些路径。这种可达性主要适用于有向图，它是指每个节点可以达到的节点数，而无需重复。这是该节点可能的最长路径。有了这些信息，如果您的当前路径加上子节点的可达性小于您已经找到的最长路径，那么使用该分支是没有意义的，因为您不可能找到更长的路径。

最佳答案

这里有一个o（n*2^n）动态规划方法，对于多达20个顶点来说应该是可行的：
m(b, U) =在b结束的任何路径的最大长度，并且只访问（部分）在U中的顶点。
最初，设置m(b, {b}) = 0。
然后，m(b, U)＝cc>在m(x, U - x) + d(x, b)中的所有x的最大值，使得U不是x，边缘b存在。对于所有端点(x, b)，使用这些值的最大值，使用b＝ccc>（顶点的全组）。这将是任何路径的最大长度。
下面的C代码假设U中有一个距离矩阵。如果图形未加权，则可以将对该数组的每个读取访问更改为常量V。在数组d[N][N]中还计算显示最佳顶点序列（可能有多个顶点）的回溯。

#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;
}

在我的电脑上，这解决了一个20x20的完整图形，其边权重在7秒内随机选择在[0，1000]范围内，需要大约160MB（其中一半用于前置跟踪）。
（请不要评论如何使用固定大小的数组。在实际的程序中使用1（或者更好，C++ +cc>）。我只是这样写的，这样事情就更清楚了。）