A
探索アルゴリズムは、グラフ上でスタート地点からゴール地点までの最短経路を見つけるための、強力なグラフ
探索アルゴリズムです。最良優先
探索を拡張した
アルゴリズムであり、各ノードへのコストとゴールまでの推定コストを組み合わせることで、効率的な
探索を実現します。
A
アルゴリズムの中核は、
ヒューリスティック関数と呼ばれる推定関数にあります。この関数は、任意のノードからゴールまでの距離を推定するもので、
探索の効率性を大きく左右します。
ヒューリスティック関数の設計は、対象となる問題に依存し、適切な関数の選択が重要となります。
例えば、2次元平面上の経路
探索では、ユークリッド距離が
ヒューリスティック関数として利用できます。これは、直線距離が実際の経路距離の妥当な近似となるためです。しかし、より複雑な問題、例えば15パズルやSTRIPSプランニングなどでは、マンハッタン距離、パターンデータベース、FF
ヒューリスティック、Merge-and-Shrink、Landmark-Cutなど、より高度な
ヒューリスティック関数の設計が必要となります。
A
アルゴリズムは、ヒューリスティック関数が常に0を返す場合、ダイクストラ法と同等の動作となります。これは、ヒューリスティック関数が探索に全く寄与しないことを意味します。逆に、ヒューリスティック関数が常に正確なゴールまでの距離を返す場合(パーフェクト・ヒューリスティクス)、Aアルゴリズムは迷うことなく最短経路を効率的に発見します。
現実的な問題では、パーフェクト・ヒューリスティクスを得ることは困難です。そのため、実際には、正確性と計算コストのバランスを考慮した
ヒューリスティック関数を設計する必要があります。不正確な
ヒューリスティック関数を使用した場合、
探索は非効率的になり、最悪の場合、解を発見できない可能性があります。しかし、A
アルゴリズムは完全性を備えているため、いずれは解を発見します。
A
アルゴリズムの歴史
A
アルゴリズムは、1968年にPeter E. Hart、Nils J. Nilsson、Bertram Raphaelの3人によって発表されました。その名前の由来は、論文中で許容的なアルゴリズムの集合をAと表し、その中で評価回数が最適なものをAと表記したことにあります。
A
アルゴリズムでは、スタートノードからあるノードnを経由してゴールノードに到達する経路のコストをf
(n)とします。これは、スタートノードからノードnまでのコストg(n)と、ノードnからゴールノードまでのコストh
(n)の和で表されます。しかし、これらの値を事前に知ることは不可能です。
そこで、Aアルゴリズムでは、これらの値を推定値g(n)とh(n)で置き換えます。g(n)は
探索過程で更新され、h(n)は
ヒューリスティック関数によって与えられます。このf(n) = g(n) + h(n)を評価することで、
探索を進めます。
A
アルゴリズムは、以下の手順で実装されます。
1. スタートノードを作成し、OPENリスト(
探索対象のノード)とCLOSEリスト(既に
探索済みのノード)を用意します。
2. スタートノードをOPENリストに追加します。
3. OPENリストが空であれば
探索は失敗です。
4. OPENリストの中でf(n)が最小のノードnを選択します。
5. nがゴールノードであれば
探索終了です。
6. nをCLOSEリストに移し、nに隣接するノードmに対して、f'(m)を計算します。
7. mの状態に応じて、OPENリストまたはCLOSEリストへの追加、更新を行います。
8. 3以降を繰り返します。
OPENリストとCLOSEリストの実装には、効率的なデータ構造の選択が重要です。通常は優先度付きキューが用いられますが、問題によっては、
ハッシュテーブルなどを組み合わせることで、より効率的な実装が可能です。
A
アルゴリズムの性質は、
ヒューリスティック関数h(n)の性質に大きく依存します。h(n)が常に真のゴール距離h
(n)以下である場合(許容的)、Aアルゴリズムは最適解を保証します。また、h(n)が無矛盾である場合も、最適解が保証されます。無矛盾な
ヒューリスティック関数は常に許容的です。さらに、支配関係にある
ヒューリスティック関数を使用することで、
探索効率の向上が期待できます。
部分問題への分割
複雑な問題を部分問題に分割して解くことで、効率が向上する場合があります。この場合、AND/OR木またはAND/ORグラフを用いた
探索が必要となります。AO
アルゴリズムやA0アルゴリズムは、それぞれ閉路のないAND/ORグラフ、閉路のあるAND/ORグラフに対するAアルゴリズムの拡張です。
まとめ
A*
探索アルゴリズムは、
ヒューリスティック関数を用いた効率的なグラフ
探索アルゴリズムです。様々な問題に適用可能であり、適切な
ヒューリスティック関数の設計がその効率に大きく影響します。部分問題への分割なども考慮することで、より複雑な問題にも対応できるようになります。