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

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

我有一个具有特定质量的图，但我在寻找一般情况下的答案。链接到论文将是太棒了。下面是部分答案：

确认它是循环的。非循环图中最长的路径很容易使用动态编程来计算。
找出图表是否是平面的（哪种算法最好？）。如果是，您可能会看到它是块图，托勒密图还是仙人掌图，并应用this paper中的方法。
找出有多少个简单的周期使用Donald B Johnson's algorithm（Java implementation）。您可以通过删除简单循环中的边来将任何循环图变成非循环图。然后您可以运行the Wikipedia page上的动态编程解决方案。为了完整性，您必须对每个循环执行N次，其中N是循环的长度。因此，对于整个图表，您必须运行DP解决方案的次数等于所有周期长度的乘积。
如果必须DFS整个图形，可以通过提前计算每个节点的“可达性”来修剪一些路径。这种主要适用于有向图的可达性是每个节点无需重复就可以到达的节点数量。这是来自该节点的最长路径可能的最大值。有了这些信息，如果您当前的路径加上子节点的可达性小于您已经找到的最长路径，那么采用该分支就没有意义了，因为您不可能找到更长的路径。

2010-11-23 Craig Younkins

不（3 ）涉及到查找强连接组件？（http://en.wikipedia.org/wiki/Strongly_connected_component） - 如果没有，我会认为你可以对这些做些什么。我发现Tarjans算法很容易理解。 – Steve314 2010-11-23 02:49:56

我真的不知道如何识别强连接组件或顶点收缩有助于解决LPP，但我可能是错的。为了强制它成为一个非循环图，我相信你需要简单的循环（Johnson's），因为强连通组件中可能还有循环。 – 2010-11-23 03:37:50

这里是一个为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，这解决了与在范围[0，1000）中随机选择的约7秒的边权重20×完全图，并且需要大约160MB（的一半是用于前身迹线）。

（请，没有关于使用固定大小的数组的意见。在实际的程序中使用malloc()（或更好，但C++ vector<int>），我只是写了这样这样的事情会更清晰。）

来源

2010-11-24 06:58:10

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

回答

相关问题