algorithm - m 行 n 列の行列に対する Floyd-Warshall アルゴリズム

Question

迷路に Floyd–Warshall アルゴリズムを実装して、迷路内のある点から他のすべての点までの距離を計算しようとしています。何らかの理由でk、列と行の間の最大値に等しい a を使用すると、間違った答えが得られます。

k特定の迷路のすべての長さに対して正しい値でこれを解決する方法はありますか?

つまり、n×n 以外の行列に Floyd-Warshall アルゴリズムを使用する方法はありますか? つまり、am×n 行列の場合、m!= n?

Answer 1

いいえ。

Floyd-Warshallアルゴリズムの行列の目的について混乱しているようです。迷路の2つの場所i、jの場合、行列A [i、j]はエッジi-> jの重みを格納します（存在しない場合はおそらく無限大）。縁）。列と行の両方が場所を示します。非正方形行列の場合は無意味です。

サイズがMxNの長方形の迷路があり、すべての可能な場所が可能である場合、Floyd-Warshallアルゴリズムの（M * N）x（M * N）行列が必要です。あなたが4つの方向にしか行けないと仮定すると、これは本当にスペースの無駄です。

1つの頂点からの最短経路が必要な場合は 、ダイクストラのアルゴリズムを使用すると、はるかに高速になります。エッジに重みがない場合は、さらに適切に、プレーンBFSを使用します。

Answer 2

迷路が狭い通路の種類である場合 (これは非常に一般的であり、おそらくここではそうです)、各セルに頂点を持たせることは意味がありません。これは、各パスのコストが同じ (重み付けされていない) 絶対に不要な頂点を追加するためです。 .

グラフをモデル化する正しい方法は、各交点 (角ではなく) に頂点を割り当てることです。私はe。いずれかの時点で選択肢が 3 方向または 4 方向の間である場合、頂点を配置します。前後にしか移動できない場合は、頂点を割り当てないでください。

これにより、大きな迷路であってもかなりコンパクトな数の頂点が生成されます。

次に、頂点のペア間のパスの重みは、単純に 2 つの頂点間の孤立した直接パス上の正方形の数です。これは、頂点の最大 4 つの方向のそれぞれに進み、ホップ数を数えることで簡単に計算できます。

したがって、頂点とパスの重みから始めて、Floyd-Warshall が問題なく各ペア間の最短パス長を提供すると確信しています。

行列は NxN になります (MxN などではありません)。

編集:さらに、迷路が「狭い通路」の種類ではなく、通常は 4 つの方向すべてに進むことができる場合は、Floyd-Warshall またはグラフ アルゴリズムの代わりに、A* 検索またはシミュレートされたアニーリングまたはそのグローバル最適化のセットを使用します。アルゴリズム。(A*-search をお勧めします)

Answer 3

ウィキペディアの記事から、非正方行列でFloyd-Warshallを使用することは可能であるように思われます。アルゴリズムの詳細については、その方法を説明するのに十分な知識がありませんが、これからも見ていきます。

しかし、私が迷路について知っていることに基づいて、最初のステップは、1で表される点の壁以外の各「エッジ」と、無限大または非常に大きな数で表される各壁で迷路を表すグラフを生成することだと思います。 。

Answer 4

このアルゴリズムの問​​題の理由がわかりません。私の知る限り、そのアルゴリズムには行列のサイズに関する制限はありません (注: 任意のグラフを使用できます!)。

ウィキペディアの簡単な概要は、私の推測を裏付けています。

実装またはグラフの定義にバグがあるとしか思えません。また、負のサイクルはありますか？