無向グラフの最短パス？

Question

だから私はこの（やや基本的な）質問がここにあると思った：

10x10パターンで配列されたサイズ100ノードのグラフがあるとします（チェスボードを考えてください）。グラフは無向であり、加重されていません。グラフを移動するには、3つのスペースを前方に移動し、1つのスペースを右または左に移動することが含まれます（チェスナイトがボードを横切って移動する方法と同様）。

固定された開始ノードを考えると、ボード上の他のノードへの最短パスをどのように見つけますか？

実行可能な動きであるノード間にエッジがあると想像しました。したがって、この情報を考えると、開始ノードから終了ノードまでの最短パスを見つけたいと思います。

私の最初の考えは、各エッジが重量1で重み付けされているということでした。ただし、グラフは無向であるため、Djikstrasは理想的な適合ではありません。したがって、深さの最初の検索の変更された形式を使用してそれを行うことにしました。

しかし、私の人生は、検索を使用して最短のパスを取得する方法を視覚化することはできませんでした。

私が試したもう1つのことは、スタートノードをルートとしてツリー形式にするグラフをルートとして配置し、次に浅い（最も低い行数）結果を選択することです。より大きなグラフでは機能しません。

誰かがこれについて私を正しい方向に向けるかもしれないアイデアを持っていますか？

どうもありがとうございました。

（グラフの視覚化を試みましたが、評判が少ないためにできませんでした）

Answer 1

グラフ内のエッジが特定の位置間の有効な動きのみを表している場合、Dijkstraを使用すると正常に機能します。ただし、グラフが加重されていないため、過剰になります。シンプルな幅最初の検索では、最適な答えが得られます。

Answer 2

ニコラスはすでに完璧な答えを提供しました。ただし、深さ最初の検索を使用するための元の試みに対処しましょう。

まず、Dijkstra（Nicholas Mancusoが指摘しているように、非加重ノードで正常に動作する）または記憶の指数関数的な無駄に発生する幅広い検索のいずれかです。しかし、彼らの利点は、最適なソリューションを見つけることが保証されている間、ノードを再拡張しないことです。残念ながら、彼らの制限は非常に重要であり、合理的にスケールアップすることを期待されるべきではありません。

問題の大規模なインスタンスを解決したい場合 反復的な深さの深さ 検索（IDFS）。最初の状態からの深度検索を発行するだけで、最大の深さを特定のしきい値に設定して$ d_ {max} $に設定します。ソリューションが見つからない場合は、固定定数$ k $によって最後の反復の深さを増やします。したがって、$ i $ -th Iterationでは、深さ$ d_ {max} + i times k $で深さfirst検索が起動されます（最初の反復は0になります）。 $ d_ {max} = k = 1 $の場合、ソリューションの深さでメモリ線形を使用しながら、最適なソリューションを見つけることが保証されます。

まあ、あなたは再吸収ノードを再拡張することはかなり悪い考えであると考えているかもしれません。全くない！これはメモリの線形消費を保証するものですが、全体的な実行時間を支配する反復が最後のものであるため、このアルゴリズムが$ frac {b} {b-1} $のオーバーヘッドで発生することを証明できます。 b $は効果的な分岐要因であり、これは明らかに、難しい問題に直面するときに考慮にかけられる非常に小さなペナルティです。

乾杯、