ダイクストラ対。A*–パスファインディング
1. 序章
ダイクストラのアルゴリズムとA*は、グラフで最適なパスを検索するためのよく知られた手法です。 このチュートリアルでは、それらの類似点と相違点について説明します。
2. 最適なパスを見つける
AI探索問題では、ノードがAIエージェントの状態であるグラフがあり、エッジは、エージェントがある状態から別の状態に移行するために実行する必要のあるアクションに対応しています。 タスクは、開始状態から目標テストに合格する状態に至る最適なパスを見つけることです。
たとえば、開始状態はチェス盤上の駒の最初の配置であり、白が勝つ状態は検索の目標状態です。同じことが黒の目標状態にも当てはまります。
エッジにコストがあり、パスの合計コストがその構成エッジのコストの合計である場合、開始状態と目標状態の間の最適なパスは最も安価なパスです。ダイクストラのアルゴリズム、均一コスト検索、A*などのアルゴリズム。
3. ダイクストラのアルゴリズム
ダイクストラのアルゴリズムの入力には、グラフ、ソース頂点、およびターゲットノードが含まれます。 は頂点のセット、はエッジのセット、はエッジのコストです。 AI探索問題への接続は簡単です。 状態、開始状態に対応し、目標テストはに等しいかどうかをチェックしています。
ダイクストラは、グラフ内の頂点のセットである、を2つの互いに素で相補的なサブセットに分割します。
ダイクストラは、頂点がに移動するまで、各ステップで頂点をからに移動します。 の最小値でノードを削除することを選択します。 そのため、通常は優先キューです。
から削除するとき、アルゴリズムはすべての外向きのエッジを検査し、かどうかをチェックします。 もしそうなら、ダイクストラはより厳しい上限を見つけたので、それはに設定されます。 このステップは、リラックス操作と呼ばれます。
アルゴリズムの不変条件は、エッジを緩和してからに削除することを選択した場合は常に、からへの最適なパスのコストに等しいということです。
4. A *
AIでは、多くの問題の状態グラフが非常に大きいため、メインメモリに収まらないか、無限になります。 したがって、Dijkstraを使用して最適なパスを見つけることはできません。 代わりに、UCSを使用します。 論理的にはDijkstraと同等ですが、無限のグラフを処理できます。
ただし、UCSは均一なコストの波の中で状態を体系的に探索するため、必要以上に状態を拡張する可能性があります。 たとえば、UCSが、最適なパスコストを持ち、その直後の後続が求められている目標状態（最適なコスト）である状態に到達したと想像してみてください。 検索の性質上、UCSは、との間のパスコストがかかるすべての州を訪問した後にのみ目標に到達します。 問題は、そのような状態がたくさんあるかもしれないということです。
A *アルゴリズムは、このようなシナリオを回避することを目的としています。 それは、状態が最初からどれだけ離れているかだけでなく、それが目標にどれだけ近いかを考慮することによってそうします。後者のコストは不明です。確実に知るためには、見つける必要があります。すべてのノードと最も近い目標の間の最低コストのパス。これは、現在解決している問題と同じくらい難しい問題です。 したがって、最も近い目標に近いコストの多かれ少なかれ正確な見積もりのみを使用できます。
これらの推定値は、ヒューリスティックと呼ばれる関数を介して利用できます。そのため、UCSを非通知検索アルゴリズムと呼んでいる間、A*は通知されます。 後者は問題の定義のみを使用して問題を解決しますが、前者はヒューリスティックが提供する追加の知識を使用します。
4.1. 経験則
ヒューリスティックは、状態を受け取り、最も近い目標までの最適なパスのコストの推定値を出力する関数です。たとえば、状態が2Dマップ上のポイントを表す場合、ユークリッドとマンハッタンの距離は適切です。ヒューリスティックの候補：
ただし、ダイクストラとA *の違いは、ヒューリスティックの使用だけではありません。
4.2. フロンティア
A *は、フロンティアの順序のみがUCSと異なります。 UCSは、フロンティア内のノードをその値で並べ替えます。 これらは、開始状態からフロンティアノードの状態へのパスのコストを表します。 A *では、フロンティアをで注文します。 がフロンティアの任意のノードである場合、の値は、開始と目標を接続し、の状態を通過する最適なパスの推定コストとして解釈されます。
ここで、状態を入力として定義したが、検索ノードを指定したため、混乱が生じる可能性があります。 を定義できるため、違いは技術的なものにすぎません。
5. 仮定の違い
Dijkstraには2つの仮定があります。
- グラフは有限です
- エッジコストは負ではありません
ダイクストラはすべてのノードを最初に配置するため、最初の仮定が必要です。 2番目の仮定が当てはまらない場合は、ベルマンフォードアルゴリズムを使用する必要があります。 2つの仮定により、Dijkstraは常に終了し、最適なパスまたは開始状態から目標に到達できないという通知のいずれかを返します。
A*では違います。 アルゴリズムが常に終了するには、次の2つの前提条件が必要です。
- エッジには厳密に正のコストがあります
- 状態グラフが有限であるか、最初から目標状態に到達可能です
したがって、グラフのすべてのエッジが正であり、開始から目標までのパスがある場合、A*は無限のグラフを処理できます。 ただし、有限グラフでもゼロコストエッジがない場合があります。 さらに、最適なパスのみを返すようにA*が満たす必要のある追加の要件があります。 このようなアルゴリズムを最適と呼びます。
5.1. A*の最適性
まず、A *には、 Tree-Like Search（TLS）とGraph-Search（GS）の2つのフレーバーがあることに注意してください。 TLSは繰り返し状態をチェックしませんが、GSはチェックします。
繰り返される状態をチェックせず、TLS A *を使用する場合、アルゴリズムが最適であることが許容されるはずです。ヒューリスティックは、過大評価されない場合は許容可能であると言います。目標を達成するためのコスト。 したがって、が目標までの最適なパスの実際のコストである場合は、があれば許容されます。 許容できないヒューリスティックでさえ、私たちを最適なパスに導いたり、最適なアルゴリズムを提供したりする可能性がありますが、それを保証するものではありません。
繰り返しの状態を避けたい場合は、GS A *を使用し、それを最適化するには、一貫性のあるヒューリスティックを使用する必要があります。ヒューリスティックは、ノードとその子に対して次の条件を満たす場合、一貫性があります。 ：
ここで、は状態グラフのエッジのコストです。 一貫したヒューリスティックは常に許容されますが、その逆は必ずしも当てはまりません。
6. 探索木と探索輪郭
ダイクストラのアルゴリズムとA*はどちらも、グラフ上に探索木を重ね合わせます。 木の道はユニークなので、 検索ツリーの各ノードは、状態と状態へのパスの両方を表します。 したがって、どちらのアルゴリズムも、実行の各ポイントで開始状態からのパスのツリーを維持していると言えます。 ただし、ダイクストラとA *は、ツリーにノードを含める順序が異なります。
グラフ上に検索波面を描画することで違いを視覚化できます。 各ウェーブを、ツリーに追加されたときに範囲内のパスコストを持つノードのセットとして定義します。ここで、境界値を事前に選択します。 インクリメンタル値を適切に選択してウェーブを定義すると、グラフ内で検索がどのように進行するかがわかります。
6.1. ダイクストラ
探索木のルートはであり、そのノードはの頂点です。 不変であるため、ノードが最適なパスを表すことがわかります。 エッジの非負性の仮定は、からに移動するための最低コストのノードを選択するというポリシーとともに、ダイクストラの別のプロパティを保証します。 最適なパスのコストがかかるすべての状態を移動した後のみ、最適なパスのコストがかかる状態に移動できます。
したがって、ダイクストラの波を分離する等高線は、多かれ少なかれ均一な円のように見えます。
したがって、ダイクストラの探索木は、グラフによって誘発されたトポロジーのすべての方向に均一に成長します。
6.2. A *
UCSとDijskraはすべての方向に状態グラフ全体に広がり、均一な輪郭を持っていますが、A*は他の方向よりもいくつかの方向を優先します。 同じ値を持つ2つのノード間では、A*はより良い値を持つノードを優先します。 したがって、ヒューリスティックは、ゴール状態の方向に輪郭を伸ばします：
7. 複雑さの違い
ここでは、ダイクストラのアルゴリズムとA*の空間と時間の複雑さを比較します。
7.1. ダイクストラ
最悪の場合の時間計算量は、グラフのスパース性と実装するデータ構造によって異なります。 たとえば、密グラフでは、ダイクストラは各エッジを2回チェックするため、最悪の場合の時間計算量もです。
ただし、グラフがスパースの場合は、に匹敵しません。 フィボナッチヒープをとして使用すると、時間計算量はになります。
以来、スペースの複雑さはです。
7.2. A *
GS A *の時間と空間の複雑さは、状態グラフのサイズによって上から制限されます。 最悪の場合、A *はメモリを必要とし、ダイクストラやUCSと同様に時間計算量が大きくなります。 ただし、これは最悪のシナリオです。 実際には、A*の探索木はダイクストラやUCSの探索木よりも小さくなっています。 これは、ヒューリスティックは通常、ダイクストラが同じ問題で成長するツリーの大部分を剪定するためです。 これらの理由から、A *はフロンティアの有望なノードに焦点を合わせ、DijkstraやUCSよりも速く最適なパスを見つけます。
TLS A *の最悪の場合の時間はです。ここで、は分岐係数の上限であり、は最適なパスのコストであり、は最小のエッジコストです。 ただし、A *が到達するノードが少ないため、実際にはその効果的な複雑さはそれほど悪くありません。 同じことがTLSA*のスペースの複雑さにも当てはまります。
8. アルゴリズムの階層
ある意味で、DijkstraはA*のインスタンスです。 常に0を返す簡単なヒューリスティックを使用すると、A*はUCSになります。 ただし、UCSは、同じ探索木があるという意味でDijkstraと同等です。 したがって、ヒューリスティックとして使用するA*を使用してダイクストラをシミュレートできます。
9. 例
次のグラフで、ダイクストラとA*がとの間の最適なパスをどのように見つけるかを見てみましょう。
ダイクストラの探索木はグラフ全体に及びます。
ただし、次のヒューリスティック推定を使用する場合：
A *のツリーには、最適なパスのみが含まれます。
つまり、A *は不要なノードを拡張しません！
10. 概要
だから、ここにダイクストラ対の要約があります。 A*。
ご覧のとおり、A *の効率は、使用されるヒューリスティック関数のプロパティに由来します。 したがって、A *の実装には、高品質のヒューリスティックを設計する追加の手順が必要です。 グラフ全体で検索を効率的にガイドする必要がありますが、計算が軽量である必要があります。
11. 結論
この記事では、ダイクストラのアルゴリズムとA*について説明しました。 それらの違いを示し、後者が実際に速い理由を説明しました。
