15

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

已知循环图中的最长路径是 NP 完全的。哪些优化或启发式方法可以使找到最长路径比对整个图进行 DFS 更快？有没有概率方法？

我有一张具有特定品质的图表，但我正在寻找一般情况下的答案。链接到论文会很棒。这是部分答案：

  1. 确认它是循环的。使用动态规划很容易计算出无环图中的最长路径。

  2. 找出图形是否是平面的（哪种算法最好？）。如果是，您可能会查看它是块图、托勒密图还是仙人掌图，然后应用本文中找到的方法。

  3. 找出使用Donald B Johnson 算法（Java 实现）有多少个简单循环。您可以通过在一个简单的循环中删除一条边，将任何循环图变为非循环图。然后，您可以运行在Wikipedia 页面上找到的动态编程解决方案。为了完整起见，您必须为每个周期执行 N 次，其中 N 是周期的长度。因此，对于整个图形，您必须运行 DP 解决方案的次数等于所有循环长度的乘积。

  4. 如果必须对整个图进行 DFS，可以通过提前计算每个节点的“可达性”来修剪一些路径。这种可达性，主要适用于有向图，是每个节点在不重复的情况下可以到达的节点数。这是从该节点可能的最长路径的最大值。有了这些信息，如果您当前的路径加上子节点的可达性小于您已经找到的最长路径，那么采用该分支是没有意义的，因为您不可能找到更长的路径。

4

1 回答 1

6

这是一个 O(n*2^n) 动态规划方法，对于最多 20 个顶点应该是可行的：

m(b, U)= 任何路径的最大长度，其结束于b且仅访问 中的（部分）顶点U。

最初，设置m(b, {b}) = 0.

然后， =全部的m(b, U)最大值，这样不存在并且存在边。取所有端点的这些值中的最大值，使用= （完整的顶点集）。这将是任何路径的最大长度。m(x, U - x) + d(x, b)xUxb(x, b)bUV

以下 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 的完整图，其中边权重在大约 7 秒内随机选择在 [0, 1000) 范围内，并且需要大约 160Mb（其中一半用于前身跟踪）。

（请不要对使用固定大小的数组发表评论。在实际程序中使用malloc()（或者更好的是 C++ vector<int>）。我只是这样写的，这样事情会更清楚。）

于 2010-11-24T06:58:10.593 回答