Help us understand the problem. What is going on with this article?

A*の理論モチョットデキル - 無矛盾なヒューリスティクス

More than 5 years have passed since last update.

許容的なヒューリスティクスよりも少し強い仮定として、 無矛盾 なヒューリスティクスというクラスのヒューリスティクスがあります。Consistentの訳ですが、Monotonicとも呼ばれるので、 単調な ヒューリスティックと訳してもいいのかもしれません。しかし、その意味するところは 無矛盾 のほうがわかりやすいかもしれません。個人的には、Consistencyの訳は 「一貫した」とか、「整合性」とか、いうのもあり得ると思うのですが、AIMAの日本語訳でこの訳が用いられているので、このバージョンを用います。

無矛盾でない (inconsistent) ヒューリスティクスを人間で例えると、言うことがコロコロ変わる信頼の置けない奴という意味です。ここを実感していただくために、まず、無矛盾なヒューリスティクスの定義と「単調」の意味を示して、それから「無矛盾」の意味を解説します。

「無矛盾」なヒューリスティクス : Consistent / Monotonic heuristics

Consistency of a heuristics $h$:

  • $\forall n \in V ; \forall m \in children(n) ;$
    • $h(n) \leq cost(n,m) + h(m)$

無矛盾なhは常に許容的です。証明は以下:

$n_0, n_1, ... n_g=v_g$ として、

  • $h(n_0) \leq cost(n_0,n_1) + h(n_1)$
  • $h(n_1) \leq cost(n_1,n_2) + h(n_2)$
  • ...
  • $h(n_{g-1}) \leq cost(n_{g-1},n_g) + h(n_g) = cost(n_{g-1},n_g) + 0$
  • $\therefore h(n_0) \leq \sum_{j=0}^{j=g-1} cost(n_j,n_{j+1}) = h^*(n_0)$

無矛盾性の意味するのは、最適経路の上でf値を計算した場合に、f値が単調増加してゆくということです。なぜなら

  • $h(n) \leq cost(n,m) + h(m)$
  • $g(n)+h(n) \leq g(n)+cost(n,m) + h(m)$
  • $g(n)+h(n) \leq g(m) + h(m)$
  • $f(n) \leq f(m)$

無矛盾性の意味するもうひとつのことは、このヒューリスティック関数が三角不等式を満たすということです。$h(n)$がゴールまでの距離だったことを思い出してください。これを、距離関数$dist(n_1,n_2)$、つまり引数を2つとる関数で表せば、$h(n)=dist(n,v_g), h(m)=dist(m,v_g)$ ですから、

  • $dist(n,v_g) \leq dist(n,m) + dist(m,v_g)$

となります。$cost(n,m)$が$dist(n,m)$である点にも気づけると思います。

近道があるのに教えてくれない

無矛盾でないヒューリスティクスを人間で例えると、言うことがコロコロ変わる信頼の置けない奴という意味です。f値が単調増加しないということは、つまり減る場合があるわけですが、要するに 実は近道があるのに隠して教えてくれない ようなやつです。

inconsistent

無矛盾性は、A*の終了条件に実は大切な意味を持ちます。
仮に無矛盾でないヒューリスティック $h$ を用いるとします(そういうヒューリスティックはいっぱいあります)。すると、次のように意地悪に設計したグラフでは、最大 $O(2^N)$ 回も、同じノードをreopenする必要が出てきます。(reopen = $g$の値を更新してノードをOPENに再挿入する動作。Dijkstraの記事を参照) ここで、$N$の数はノードの総数、下の図のノードに書いてある数字はhの値、辺に書いてある数字は辺のコストです。(Martelli, 1977)これは、いわばA*を騙して騙して騙しまくることに特化したようなシチュエーションだと言えるでしょう。もしも自分の問題のために書いたA*が、許容的にも関わらず異常にに遅い場合は、それがconsistentかどうかを調べてみてください。

martelli.png

(図: Robert C. Holte, Common Misconceptions Concerning Heuristic Search (SoCS 2010) より。)

このお話の続きは、B と PathMaxの時にやります。Bは、このような条件で$O(n^2)$の展開しか行いません。ただし、Bはあまり実用には使われていません。

guicho271828
主にcommon lisp。javascriptもやる。 組み込みマイコンでCやアセンブラを買いたりもする。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away