Skip to content
検索結果に戻る

A*探索アルゴリズム

提唱者
Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
年
1968
種類
algorithm
系統
Graph Algorithms

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

A*探索アルゴリズムは、1968年にPeter E. Hart、Nils J. Nilsson、Bertram Raphaelによって開発された、ダイクストラ法(Dijkstra's algorithm)の利点とヒューリスティック誘導を組み合わせた最適な経路探索アルゴリズムです。これは、開始地点からの実際の距離と目標までの推定距離のバランスを取ることで、効率的に最短経路を見つけます。

手法の背後にある直感

A*は評価関数f(n) = g(n) + h(n)を使用します。ここで、g(n)は開始地点からノードnまでの実際のコスト、h(n)は目標までの残りのコストのヒューリスティック推定値です。最も低いf(n)値を持つノードを探索することにより、アルゴリズムは最適性を維持しながら(ヒューリスティックが許容可能な場合、つまり過大評価しない場合)、効率的に探索空間を目標に向かって狭めます。これにより、A*は情報のない探索手法よりも大幅に高速でありながら、最適な経路を見つけることが保証されます。

歴史学

Hart、Nilsson、Raphaelは1968年にA*を発表し、ダイクストラ法にヒューリスティック情報を追加することで、最適性を維持しながら探索効率を劇的に向上させることができることを実証しました。このアルゴリズムは、人工知能とオペレーションズリサーチの基礎となりました。その後の開発には、双方向A*、IDA*(反復深化)、およびさまざまなヒューリスティックの改善が含まれます。A*は、最新のゲームエンジンやロボット工学システムにおける経路探索の標準的な選択肢であり続けています。

使うべき場面

良好なヒューリスティック関数が利用可能なグラフで最適な経路を見つける必要がある場合にA*を適用します。これは、ゲーム、ロボット工学、経路計画において、情報に基づいた探索が計算量を大幅に削減できるため、特に効果的です。速度が重要でありながら最適性が要求される場合に使用します。信頼できるヒューリスティックがない場合は、代わりにダイクストラ法を使用してください。

限界と注意点

  • 最適性はヒューリスティック関数の許容可能性に依存する
  • 貧弱または許容不可能なヒューリスティックによるパフォーマンスの著しい低下
  • 広大な探索空間におけるメモリ使用量が多い(オープンセットとクローズドセットを維持するため)
  • 良好なヒューリスティック関数を設計するために明示的なドメイン知識が必要

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • ヒューリスティックが許容可能な場合の最適な経路探索
  • 良好なヒューリスティックが利用可能な場合、ダイクストラ法や幅優先探索よりも大幅に高速
  • 柔軟性:あらゆる許容可能なヒューリスティック関数で機能する
  • 単一目標の経路探索問題に適している
  • ゲーム、ロボット工学、ナビゲーションシステムにおける広範な実世界での検証

応用

  • ビデオゲームの経路探索:動的なゲーム環境におけるリアルタイムNPCナビゲーション
  • ロボットの動作計画:障害物を回避する自律ロボットの最適な経路計画
  • GPSナビゲーション:道路網と交通状況を考慮した効率的なルートの計算
  • パズル解決:15パズルなどの組み合わせ問題における最適な解の発見
  • ネットワークルーティング:リンク品質ヒューリスティックを使用した効率的なパケットルートの決定
  • バイオインフォマティクス:配列アラインメントとタンパク質構造予測の探索

使い方

使い方

1

開始ノードを持つオープンセットを作成し、そのg値(開始からのコスト)をゼロに設定し、ヒューリスティック関数を使用してh値を計算します。

2

オープンセットから最も低いf値を持つノードを選択し、その訪問されていない隣接ノードのf値を計算し、有望な隣接ノードをオープンセットに追加します。

3

目標が最も低いf値で到達されるまでノードの展開を続けます。これにより最適な経路が保証されます。親ポインタをたどって経路を再構築します。

よくある落とし穴

  • コストを過大評価する許容不可能なヒューリスティックを使用し、最適でない経路につながる
  • 問題に対して単純すぎる、または無関係なヒューリスティックを選択し、探索効率を低下させる
  • オープンセットの実装が非効率的(優先度付きキューを使用すべき)、ノード選択が遅くなる

よくある質問

許容可能なヒューリスティックとは何ですか、そしてなぜそれが重要ですか?

許容可能なヒューリスティックは、目標までの実際のコストを過大評価することはありません。この特性により、A*が最適な経路を見つけることが保証されます。ヒューリスティックが過大評価する場合、A*はより短い経路を見逃し、最適でない解を返す可能性があります。

問題に対する良好なヒューリスティックをどのように設計しますか?

良好なヒューリスティックは、ドメイン知識と問題構造に基づいています。グリッドベースの経路探索では、マンハッタン距離またはユークリッド距離がうまく機能します。より複雑な問題については、制約を緩和したり、パターンデータベースを使用して許容可能なヒューリスティックを計算することを検討してください。

A*とダイクストラ法の違いは何ですか?

どちらも最適な経路を見つけますが、A*はヒューリスティックを使用して目標への探索を優先するため、良好なヒューリスティックが利用可能な場合ははるかに高速です。ダイクストラはすべての方向に均一に探索し、ヒューリスティックが信頼できない場合はより安全です。

A*は最短経路を見つけることを保証できますか?

はい、ヒューリスティックが許容可能である(実際のコストを過大評価しない)場合、A*は最短経路を保証します。許容不可能なヒューリスティックの場合、最適性は保証されません。

関連する手法

参考文献

  1. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.

    DOI 文献を開く
    コピーしました。
  2. Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.

    ISBN:978-0-13-604259-4
    コピーしました。