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

Question

尝试在循环图中找到最长路径时存在哪些优化？

已知循环图中的最长路径是NP完全的.优化或启发式方法可以比DFS整个图表更快地找到最长的路径？有任何概率方法吗？

我有一个具有特定品质的图表,但我在一般情况下寻找答案.链接到论文会很棒.这是一个部分答案:

1. 确认它是循环的.使用动态编程可以轻松计算非循环图中最长的路径.

2. 找出图表是否是平面的(哪种算法最好？).如果是,你可能会看到,如果它是一个块图,托勒密图,或者仙人掌图形和应用中发现的方法本文.

3. 使用Donald B Johnson的算法(Java实现)找出有多少简单周期.您可以通过删除简单循环中的边来将任何循环图更改为非循环图.然后,您可以运行Wikipedia页面上的动态编程解决方案.为了完整性,您必须为每个循环执行N次,其中N是循环的长度.因此,对于整个图表,您必须运行DP解决方案的次数等于所有周期长度的乘积.

4. 如果必须对整个图进行DFS,则可以通过提前计算每个节点的"可达性"来修剪某些路径.这种可达性主要适用于有向图,是每个节点无需重复即可达到的节点数.它是该节点可能的最长路径的最大值.有了这些信息,如果您当前路径加上子节点的可达性小于您已经找到的最长路径,那么获取该分支是没有意义的,因为您找不到更长的路径是不可能的.

Answer 1

这是一个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]范围内随机选择,大约7s,需要大约160Mb(其中一半用于前一个跟踪).

(请注意,没有关于使用固定大小数组的评论.在真实程序中使用malloc()(或者更好的是,C++ vector<int>).我只是用这种方式编写它,所以事情会更清楚.)