グラフ理論における最短経路問題
あるいは最短経路探索問題．
定義
- 入力：グラフ
、コスト関数
、始点
、終点
．
- 解：始点から終点への経路．すなわち、次を満たす頂点と辺の列
（ただし
）．
、
、
- 任意の
について
．
- 解のコスト：経路に含まれる各辺のコストの和．
- 出力：コスト最小の解．
文脈によっては、上記の頂点と辺の列から頂点のみ（あるいは辺のみ）を抜き出した列を経路と呼ぶことも多々あります．また、文脈によっては、最短経路のコストを求める問題や、始点とそれ以外の全頂点の間の最短経路のコストを求める問題を最短経路問題と呼ぶこともあります*1．
なお、解の最適性が不要な場合は単に経路探索問題といいます．また、単に経路があるかどうかを判定する問題を到達可能性問題といいます．
応用
経路を見つける問題というと迷路のソルバ（あるいは応用としてはカーナビや路線検索など）といった比較的小規模な用途にしか使えないように思えるかもしれませんが、実は、グラフ上の最短経路問題は計算機科学や人工知能における最も重要な問題の一つです．これは何故なら、状態空間が離散的かつ決定的な世界で初期状態を目標状態に遷移させる手順を求める問題は全て経路探索問題に帰着して解く事ができるからです．
もう少し噛み砕いて説明すると、例えばぐちゃぐちゃにされたルービックキューブが与えられたときに各面が整っている状態にキューブを戻す問題は経路探索問題に帰着することができます．
- キューブの各状態と頂点を対応させる．
- キューブAと、そのある列をある角度だけ回したときに得られるキューブBについて、Aに対応する頂点からBに対応する頂点に辺を張る．
- 全ての辺のコストを1とおく．
- 最初に与えられたキューブに対応する頂点を始点とする．
- 各面が整っているキューブに対応する頂点を終点とする．
同様に、例えば、スライディングタイルパズルや倉庫番なんかも経路探索問題に帰着できます．敵キャラの要素を無視すればゼルダの伝説のような謎解きゲームもいけるかもしれません．更に、パズルだけでなく、荷物を配送したりコンテナを整理したり機械を組み立てたりといったスケジューリング問題や、果ては人工衛星や火星探査機を操作して映像や物質を採集する問題も経路探索問題に帰着することができます（実際にNASAが過去にそのような研究を行っています）．
グラフ理論や理論計算機科学の世界では、経路探索問題や到達可能性問題が別の問題の子問題になる場合が数多くあるため、古くから盛んに研究されています．
一方、人工知能の世界では上記の「状態空間が離散的～」の問題は古典的プランニング問題と呼ばれ、やはり同様に古くから盛んに研究されています*2．人工知能研究では究極的には人間以上に何でもできるナニカを作ることが目標なので、色々な問題を経路探索に帰着できるという性質は非常に重要なわけです．
解法
メモリに載りきる大きさのグラフについての最短経路問題の解法としてはダイクストラ法やベルマン-フォード法が有名です．
しかし、上記のように別の問題を経路探索問題に帰着して解く場合にはグラフのサイズがとてつもなく巨大になることが普通なので、A*アルゴリズムやより専門化したアルゴリズムを使って、グラフのごく一部だけを探索してなるべく高速に解くことが試みられます*3．この場合には、グラフも必要な部分だけ逐次的に構築されます．
一方、理論の世界では計算時間を多少延ばしてもよいので使用メモリが少ないアルゴリズムを作ることも重要なのですが、2012年現在、これについてはほとんど研究が進んでいません．到達可能性問題については Reingold, 2008*4 あたりでグラフの辺に向きが無い場合に関する手法が提案されているのですが、向きがある場合については同様にほとんど結果がありません．
詳細は執筆予定の各アルゴリズムのページにて．
