[Edit] すみません、タグをつけ忘れていると自動投稿されないようです! 予約投稿で書き溜めてあるので、今後は気をつけて自動で公開されるようにします。
この記事では、Pearl (1984), AIMA 3rd ed. (2011) にならって、A*のより詳しい性質を少し紹介します。
前回チラリと触れたのは、$h$に関するdominanceやperfect heuristicsの議論です。前回話していなかったのですが、$h$の性質はA*にとって重要です。
ヒューリスティクスの許容性 Admissibility
Admissibility とは、べつにヒューリスティクスの懐が深いとか、ロバストだとか、そういうことではありません。まあいわば、そのヒューリスティクスが人間にとって「許せるほど正確か」という意味です。許容性の定義は以下のとおり:
Admissibility of h:
- $\forall n \in V ; \quad 0 \leq h(n) \leq h^*(n)$
つまり、真のコスト h* を 控えめに見積もる(underestimate) ような h は許容的なヒューリスティクスです。許容的なhを用いる限り、A*は常に最適解を返します。
前回用いた、地図におけるユークリッド距離ヒューリスティクス$h_e=||v_g-n||_2$は許容的です。三角不等式を用いて、hがh*を下回ることを証明したことを再確認してください。
なんだ、じゃあ地図の探索問題なんて終わったも同然じゃん
勘違いしてはいけないのは、1つのグラフ探索問題のクラスについて、許容的なヒューリスティクスは1つではないということです。例えば、
- 全ての非負コストグラフ探索問題において、 blind heuristics $h_0=0$ は許容的。
- 地図において、 x座標の差の絶対値 $h_x=|v_{gx}-n_x|$ は許容的。
- 地図において、 y座標の差の絶対値 $h_y=|v_{gy}-n_y|$ は許容的。
- 地図において、 $h_{xy}=\max{(h_x,h_y)}$ は許容的。
この場合、 $h_0 \leq h_x \leq h_{xy} \leq h_e$ というdominance relationship があります。
もしかすると、ユークリッド距離よりも正確な見積りの出来るヒューリスティクスがあるかもしれませんよ。(実は、実際の実装は知らないものの、そういうものは考えられます。詳細は二日後)
じゃあ、実用においても より正確なhをいつも使うのがいいんだよね?
じつはこれも正しくありません。なぜなら、正確なヒューリスティクスは計算に時間がかかるからです。
比較的小さいグラフなら、blind heuristics、つまりダイクストラ法が一番早い場合もあります。ただし、それは大規模な問題を解くことは出来ません。
非許容的なヒューリスティクスは使えない?
いえいえそんなことはありません。例えば:
- 地図において、マンハッタン距離 $h_{man}=||v_g-n||_1=h_x+h_y$ は非許容的。
ですが、解の最適性がそこまで重要でない問題ならば、これらの関数も使うことが出来ます。なぜなら、これらはある程度信頼できる見積もり値を与えてくれるので、最適ではないにせよ何らかの経路を返してくれるからです。
また、非許容的なヒューリスティクスには、過度な単純化により計算負荷が低いものがあります。例えば上のマンハッタン距離は、sqrtが必要になるユークリッド距離よりも計算が軽いです。
まとめ
A*の性質にまつわる基礎的な話をしました まる