5

対称隣接行列があることが保証されている場合、Floyd-Warshallの実行時間の定数係数を下げる最適化はありますか？

4

2 に答える 2

13

いくつか考えた後、私は思いついた：

for (int k = 0; k < N; ++k)
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= i; ++j)
            dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

もちろん、私たちは両方ともそれが正しく、より速いことを示す必要があります。

正しさは、自明ではないフロイド・ウォーシャルの証明に依存しているため、証明するのが困難です。かなり良い証拠がここにあります：フロイド-ウォーシャル証明

入力行列は対称です。ここで、残りの証明は、修正されたFloyd-Warshallの証明を使用して、2つの内部ループの計算の順序は重要ではなく、グラフは各ステップの後で対称のままであることを示します。これらの条件の両方が真であることを示す場合、両方のアルゴリズムは同じことを行います。

からへのパス上の中間頂点としてセットからの頂点のみを使用して、からへdist[i][j][k]の距離として定義しましょう。ij{0, ..., k}ij

dist[i][j][k-1]iからまでのエッジの重みとして定義されjます。間にエッジがない場合、この重みは無限大と見なされます。

ここで、上記のリンクされた証明で使用されたものと同じロジックを使用します。

dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1])

今の計算でdist[i][k][k]（そして同様にdist[k][i][k]）：

dist[i][k][k] = min(dist[i][k][k-1], dist[i][k][k-1] + dist[k][k][k-1])

dist[k][k][k-1]負になることはできないので（またはグラフに負のループdist[i][k][k] = dist[i][k][k-1]がある）、これはを意味します。その場合dist[k][k][k-1] = 0は両方のパラメータが同じであるため、それ以外の場合はの最初のパラメータmin()が選択されます。

だから今、dist[i][k][k] = dist[i][k][k-1]計算するとき、それは彼らのパスで許可されているかどうかdist[i][j][k]は重要ではないからです。はの計算にのみ使用されるため、が計算されるまで行列に残ります。以上の場合、上記の場合が適用されます。dist[i][k]dist[k][j]kdist[i][j][k-1]dist[i][j][k]dist[i][j]dist[i][j][k-1]dist[i][j][k]ijk

したがって、計算の順序は重要ではありません。

dist[i][j] = dist[j][i]次に、アルゴリズムのすべてのステップの後でそれを示す必要があります。

dist[a][b] = dist[b][a]したがって、すべてaとの対称グリッドから始めbます。

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
           = min(dist[j][i], dist[k][i] + dist[j][k])
           = min(dist[j][i], dist[j][k] + dist[k][i])
           = dist[j][i]

したがって、私たちの割り当ては両方とも真であり、不変量を維持しdist[a][b] = dist[b][a]ます。したがってdist[i][j] = dist[j][i]、アルゴリズムのすべてのステップの後

したがって、両方のアルゴリズムで同じ正しい結果が得られます。

速度を証明するのは簡単です。内側のループは、通常呼び出される回数の半分強で呼び出されるため、関数の速度は約2倍になります。同じ回数を割り当てているため、少し遅くなりましたが、min()ほとんどの時間を費やしているので、これは問題ではありません。

私の証明に何か問題がある場合は、技術的であっても、遠慮なく指摘してください。修正を試みます。

編集：

ループを次のように変更することで、速度を上げてメモリの半分を節約できます。

for (int k = 0; k < N; ++k) {
    for (int i = 0; i < k; ++i)
        for (int j = 0; j <= i; ++j)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k]);
    for (int i = k; i < N; ++i) {
        for (int j = 0; j < k; ++j)
            dist[i][j] = min(dist[i][j], dist[k][i] + dist[j][k]);
        for (int j = k; j <= i; ++j)
            dist[i][j] = min(dist[i][j], dist[k][i] + dist[k][j]);
    }
}

これは、最適化されたアルゴリズムの上記のforループを分割するだけなので、それでも正しく、同じ速度になる可能性がありますが、メモリの半分を使用します。

アイデアをくれたChrisElionに感謝します。

于 2010-01-10T21:48:53.067 に答える
2

（ウィキペディアの記事の擬似コードの表記を使用）edgeCost行列が対称である場合、パス行列も各反復後に対称になると私は信じています（ただしテストはしていません）。したがって、各反復でエントリの半分を更新するだけで済みます。

下位レベルでは、マトリックスの半分を格納するだけで済み（d（i、j）= d（j、i）であるため）、使用するメモリの量を減らし、できればキャッシュミスの数を減らすことができます。同じデータに複数回アクセスします。

于 2010-01-10T21:40:51.393 に答える