15

巡回グラフで最長パスを見つけようとするために、どのような最適化が存在しますか?

巡回グラフの最長経路は NP 完全であることが知られています。グラフ全体を DFS するよりも速く最長パスを見つけることができる最適化またはヒューリスティックは何ですか? 確率論的アプローチはありますか？

特定の性質を持つグラフがありますが、一般的なケースでこれに対する答えを探しています。論文へのリンクは素晴らしいでしょう。ここに部分的な答えがあります：

  1. 周期的であることを確認します。非巡回グラフの最長経路は、動的計画法を使用して簡単に計算できます。

  2. グラフが平面かどうかを調べます (どのアルゴリズムが最適か?)。そうである場合、それがブロック グラフ、プトレマイック グラフ、またはサボテン グラフであるかどうかを確認し、このペーパーに記載されている方法を適用します。

  3. Donald B Johnson のアルゴリズム( Java 実装)を使用して、単純なサイクルがいくつあるかを調べます。単純なサイクルでエッジを削除することにより、循環グラフを非循環グラフに変更できます。その後、ウィキペディアのページにある動的プログラミング ソリューションを実行できます。完全を期すために、各サイクルでこれを N 回実行する必要があります。ここで、N はサイクルの長さです。したがって、グラフ全体の場合、DP ソリューションを実行する必要がある回数は、すべてのサイクルの長さの積に等しくなります。

  4. グラフ全体を DFS する必要がある場合は、事前に各ノードの「到達可能性」を計算することで、いくつかのパスを削除できます。主に有向グラフに適用されるこの到達可能性は、各ノードが繰り返しなしで到達できるノードの数です。これは、そのノードからの最長パスの最大値です。この情報を使用して、現在のパスと子ノードの到達可能性を合わせたものが、既に見つけた最長パスよりも短い場合、より長いパスを見つけることは不可能であるため、その分岐を使用しても意味がありません。

4

1 に答える 1

6

これは、最大 20 個の頂点に対して実行可能な O(n*2^n) 動的計画法のアプローチです。

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 では、[0, 1000) の範囲でランダムに選択されたエッジの重みを持つ 20x20 の完全なグラフを約 7 秒で解決し、約 160Mb を必要とします (その半分は先行トレース用です)。

(固定サイズの配列の使用についてはコメントしないでください。実際のプログラムで使用malloc()(またはもっと良いのは C++ vector<int>) を使用してください。物事がより明確になるように、このように記述しました。)

于 2010-11-24T06:58:10.593 に答える