A Formal Basis for the Heuristic Determination of Minimum Cost Paths¶
| Author: | Peter E. Hart, Nils Nillson, and Bertram Raphael |
|---|---|
| Year: | 1968 |
| Accepted: | IEEE Transactions on Systems Science and Cybernetics, July, 1968 |
| Link: | https://www.cs.auckland.ac.nz/courses/compsci709s2c/resources/Mike.d/astarNilsson.pdf |
contents
Introduction¶
The problem of finding paths through graphs¶
グラフ理論において最短経路を求める手法を, ここでは mathematical approach と heuristic approach に分けている.
- methematical approachというのは, 任意のグラフについての一般論を引き出そうとするアプローチのことを言おうとしているのだと思う. あらゆるグラフに対して最短経路を求められることが保証されている手法の解析など. 計算量の観点には配慮がないとか.
- heuristic approachというのは, グラフとして表現されている問題のdomainに関する特殊な知識を用いる手法のことであり, 計算効率を上げることを目的にしている. 枝狩りを用いるということだろう. heuristic approachを用いている手法は概して, 最短コストの経路を見つけられることが保証されていない.
この論文で提唱される方法は, 緩い仮定のもとで, 最短経路を保証する経路を求める際に走査するノードの数を最小化するという意味でoptimalであることを証明する.
最小コストを求めたい2つのノードが与えられた時に, 「その経路の実際の最短コストよりはギリギリ少し大きい」ような評価関数を見つけることができれば, それを使ってグラフを探査することで, 走査するノードの数を減らすことができる.
Some definitions about graphs¶
グラフ理論の教科書にのっているような定義が書かれている. ノードの集合 \(\{ n_i \}\) とエッジの集合 \(\{ e_{pq} \}\) があり, それぞれのエッジにはコストが定められている. また有向グラフである場合, \(e_{ij}\) と \(e_{ji}\) の値は異なる. エッジのコストの最小値を \(\delta\) としたとき, そのグラフを \(G_{\delta}\) と表す.
この論文で扱うようなアプリケーションにおいては, グラフの各エッジに対してコストが与えられていることはなく. その代わりimplicitlyにソースノード集合 \(S \in \{ n_j \}\) と, successor operator \(\Gamma\) が与えられている. \(\Gamma\) は各ノードに対して, 別のノードへのコストのリスト \(\{ n_j, c_{ij} \}\) を返す関数である. successor operatorを初期のノードリスト, そのsuccessor, 更にその先へと, これ以上新しいノードが見つからなくなるまで適用することで, グラフをexplicitlyに表現することもできる.
subgraph \(G_n\) は, \(\{ n_i \}\) の中のいずれかのノード \(n\) からsuccessor \(\Gamma\) を用いて「ひとつだけ伸ばして」作られるグラフのこと.
あるノードからそのpreferred goal nodeへの最短経路のコストを, \(h(n)\) と表記する.
An admissible searching algorithm¶
ノード \(n_i\) から \(n_j\) へのoptimal costのことを \(h(n_i, n_j)\) と表記する. これは \(n_i\) から \(n_j\) の間に最短コストの経路が存在している場合のその値である(連結でなければそもそも定義されないので).
一応この論文ではゴールとなるノードが複数ある場合を考えている. そのゴール集号のことを \(T\) , そのノードの中でもソースノードsからの最小コストが最も小さいノードのことをpreferred nodeと呼び, その時のコストのことを \(h(n)\) と呼ぶ. これは動的計画法で言うところの真の価値関数というところだろう.
Algorithms for finding minimum cost paths¶
ソースノードsからスタートして \(\Gamma\) を適用してsubgraph \(G_s\) を構築することを expand node と表現する.
ソースノードsから訪問した各ノードへの最短経路は, 次のようにして辿ることができる. successorにより, あるノードnへとエッジがexpandされた時, そのノードnに 向かう エッジの中で, ノードnへの累積コストが最も短くなるものを選ぶ. そしてノードnに, その最小累積コストとその時の親を格納する. この操作をgoal nodeのtに到達するまで続ける. そしてtからsへと逆向きに辿ればいい.
与えられたソースノードsからpreferred goalへのoptimal solutionを求められるアルゴリズムのことを admissible という. グラフが与えられた時に, そのノードを走査する順番や走査する必要のあるノードの数はアルゴリズムによって異なる. 次の章では admissible な解を得るためのノードを辿る順番について, その次の章で, 緩やかな仮定のもとで, その方法により, optimal pathを最も少ないノード数で見つけられることを示す.
Description of the algorithm¶
最短経路を探索する際に辿る必要のあるノード数を出来る限り少なくするためには, 次に走査する必要のあるノードについて, 出来る限り 知識あり の決定を行う必要がある. そのため, optimal pathを与える可能性のあるノードを無視してしまうとadmissibleな解を得ることができない.
評価関数として \(\hat{f}(n)\) を各ノードについて評価することができるとする. そしてその時点で \(\hat{f}(n)\) の値が最も小さいノードを次に expand するノードとして用いる.
| Search Algorithm A*: | |
|---|---|
- sを open list に入れて \(\hat{f}(s)\) を求める
- open list の中で最も \(\hat{f}(n)\) の値が小さいnを求める
- nを closed list に入れる. そしてnからsuccessor \(\Gamma\) を適用する(エッジを辿る). そしてその中でまだ closed list に入っていないものを open list に入れる. つまり open list に入っているノードは子を持たない 葉 であるか(まだ探索されていなかった)あるいはまだ探索の余地がある(更新される際にコストが下がった), そして closed list に入っているノードは 枝 になっている(基本的には探索の対象とはしない. 枝刈りの対象). そして各々の \(\hat{f}(n)\) を更新する.
- 一方 closed list に入っていたノードの中で, \(\hat{f}(n)\) が下がったものは, 再び open list に入れる. つまり上の手順で枝刈りされたけど(closed list に入れられたけど)再び探索対象に入れる.
- 手順1に戻る
The evaluation function¶
ソースノードsからゴールノードgへの最短経路を考えた時に, その中でノードnを通るという制約を加えた時の最短経路のコストを, \(f(n)\) と表記する. つまり \(f(s) = h(s)\) である. そしてｓからｇへの最短経路上に存在するノードｎについては, いずれも \(f(n) = f(s)\) を満たしている. そしてｓからｇへの最短経路上に存在しないノードについては \(f(n) > f(s)\) である. 各ノードについて \(f(n)\) を求めるためには動的計画法を厳密に行う必要があるが, その関数の近似関数 \(\hat{f}(n)\) を探索の途中の「次にどこから伸ばすか」を決めるための評価関数として用いるのは妥当そうである. 始点から探索を開始したのなら, その時点で各ノードについては
のようにして, 現時点でのすでに分かっている, 始点からのコスト \(g(n)\) とまだ未知の終点へのコスト関数 \(g(n)\) に分けることができる. 問題は \(h(n)\) として何を用いるかである.
初めに, もし \(\hat{f}(n)\) が \(h(n)\) の下界に属していれば, A*アルゴリズムはadmissibleであることを証明する.
The admissibility of A*¶
| Lemma1: |
|---|