この回からしばらくは、非最適探索に特化した探索アルゴリズムを紹介します。
非最適探索とは、基本的に 正しい経路であればなんでもよい という種類のアルゴリズムです。しかし、そんな経路に使い道はあるのでしょうか?
非最適探索を使う事の意義はいくつかあります。
非最適探索は最適探索よりも簡単である。
これは、通常、探索空間において、経路がながければ長いほど、多くの数の経路がゴールたどり着くからです。例えば地図で考えてみましょう。多くの場合、 最短経路というのは一本しかありません。しかし、最短よりもちょびっとだけ長い経路というのは、数えきれないくらいあるのがわかるでしょうか。
例えば、下の地図の経路通りに歩いている時、途中で一回コンビニに入ってみたとしましょう。すると、それだけで経路は少し長くなります。経路上のどこでほんの少し寄り道をしても、その経路は非最適です。仮に寄り道をする方法が $n$ 個あったとしたら、 2 回寄り道する方法は $n^2$ こあります。3回寄り道なら $n^3$ 個です。寄り道の数が増えれば増えるほど、許される解の個数も指数的に増え、問題は簡単になるのです。
解を素早く見つけられるので、実用化しやすい。
非最適探索は最適探索よりも簡単なので、非最適向けのアルゴリズムを用いると、答えを素早く得られます。解の質/良さ、つまりコストが最適であることを犠牲にして、 とりあえずの解を素早く得る ことは重要です。だって、カーナビがナビを開始するまでに一時間もかかったりしたら使い物にならないでしょう?
これは人工知能の問題でもあります。実世界を動き回るロボットにとって、危険に素早く反応して生き延びること は重要なタスクの1つです。例えば、道を歩いているロボットに、暴走する珍走団が突っ込んできたとしましょう。この時に、どうやって珍走団を最適に避けるべきなのかをじっくり考えていたら、行動を行う前に轢かれてしまうかもしれません。このように、反応時間が重要になるような問題では、高速な非最適探索は必須の手段になります。
非最適解をとりあえず実行しつつより良い解を探すこともできる。
おそらく、より賢い戦略はこちらなのではないでしょうか。非最適解はおそらく最適解とある程度似通っていて、最適解にいくつかの無駄が入り込んだものだと考えられるでしょう。ある程度実行しながらより良い最適解を探すというのは、アジャイルプログラミングにも通じるものがあります。それとくらべると最適探索は、ウォーターフォール開発のようなものです。
それにそもそも、完璧にゴールまでたどり着く経路が必要とも限りません。人間でも、車で遠出をする時、最寄りの高速ICに乗って目的地付近のパーキングエリアに行くまではカーナビを起動しない人もいるのではないでしょうか。(いや、休日で渋滞が予測されれば別ですが。)
最適化に関する鉄則を思い出しましょう:
- プログラム最適化の第一法則: 最適化するな。
- プログラム最適化の第二法則（上級者限定）: まだするな。 - Michael A. Jackson
このように、最適性が相対的に重要でない問題のため、あるいは最適性をある程度あとで取り戻せる問題のために、非最適探索は有用です。今日は、そのような手法のうち最もシンプルなものの1つである 山登り法 という局所探索の一種を紹介します。
Hill Climbing (山登り法)
簡単!
- Algorithm $HillClimbingSearch(n)$ :
- If $goal(n)$
- Exit Algorithm
- Else
- $HillClimbingSearch(\arg \min_{m\in children(n)} f(m))$
- If $goal(n)$
つまり、よい$f$の方向にひたすら進み、戻ってきもしないという、シンプル明快な方法ですね!
でも、 $h$ の極小値にハマってしまう場合があるので、そのままでは実用になりません。重複検知などでループを防ぐ必要や、タブーサーチとの組み合わせなど、さまざまな拡張が考えられます。
このように、あまり広い空間全体のことを考えず、付近の状況だけをみて探索を行う種類の探索を局所探索と言います。
Enforced HillClimbing (Hoffman 2001)
[Hoffmann, Jörg, and Bernhard Nebel. "The FF planning system: Fast plan generation through heuristic search." Journal of Artificial Intelligence Research (2001): 253-302.]
山登りの変種。ノードごとに幅優先探索を行い、 $h(s) < h(s')$ を満たすような $s'$ がみつかれば続行、失敗すればアルゴリズム全体で失敗。失敗した場合には普通のA*などに移行することで、アルゴリズム全体の完全性が保てます。
- Algotithm $EHC(s)$:
- If $goal(s)$
- return $s$
- Else
- let $s' \leftarrow \mbox{BreadthFirstSearch}(s)$ (under $h(s) < h(s')$)
- If $s' = \mbox{NotFound}$
- return $\mbox{Fail}$
- Else
- EHC($s'$)
まとめ
山登り法を解説しました。初回なのでこんなもので。