知的情報処理 其の二 20171013

探索について

　電車に乗るとき「一番安い経路」を検索することがある。この時、プログラムは大量の経路情報から条件に合う経路を探索している。このように、探索なくして検索システムなし。非常に重要な技術なのである。

種類

　いろいろあるが、大きい分類では二つ。その分類それぞれに二つの小分類がある。大きい分類は

• 状態空間探索
• 問題分解法

の二つ。状態空間探索では、初期状態から目標の状態へ向けてオペレータ（規則、ルール）を用いて探索していく方法。問題分解法は、大きな問題を小さな問題の集合と考えていく。小さな問題を解いていくことにより、全体の問題を解決していくという方法だ。
　小分類のほうは

• 盲目的探索
• 発見的探索

の二種類。盲目的探索は、手当たり次第に試していく方法。発見的探索はいい経路が見つかる可能性を計算して経路を決めていく方法になっている。発見的探索のほうが、人間的なプロセスを踏む探索方法だといえるだろう。
　次から、これら合わせて4パターンの探索方法について、代表的な方法例を交えての説明を書いていく。

迷路問題

　ここでは、それぞれの方法を使って迷路問題を解いていく。そのプロセスを見て、方法ごとの特徴を観察していく。そのために、迷路問題とはいったい何なのかを書いていく。

問題

　次のような迷路があったとする。この迷路を最短で解くにはどのような経路をたどっていけばいいだろうか。

　もちろん、人間の目で見て考えれば「A→E→I→J→F→G→K→O→P」の順だと一発で分かるが、ここではコンピュータにこの問題を解かせる。

問題の簡略化

　この問題をコンピュータに解かせるためには、いくつかの前処理が必要になってくる。結論から言うと、木構造に落とし込んでいく。つまり、上の問題を

このような木構造として扱っていく。これから出てくる探索方法が解決する問題は「この木構造のAからPまでの経路を探索する」と仮定しておく（横でごめんなさい）。

状態空間探索

　初期状態から目標状態までの経路をオペレータを用いて探索していく方法。すべての状態を合わせたものの組み合わせが状態空間と呼ばれるため、状態空間探索と呼ばれる。

盲目的探索

　手当たり次第に試していく方法になる。この探索法には「深さ優先探索」と「幅優先探索」の二つの方法例がある。

深さ優先探索

　木構造の最終端までいって目的のものがなかったら一番近い分岐点まで戻って、別の経路を探索するというもの。一番近い分岐点に戻る機構のことをバックトラックと呼ぶ。この方法は「次の状態」と「一番近い分岐点」の二つの情報だけを覚えておく必要がある。そのため、必要となるメモリを抑えることができる。ただシステムを作るだけでなく、各手法がどのような特徴を持っているのかを把握し、利用者にとって最適なものを作る。これもモノづくりで重要なことだ。

幅優先探索

　木構造の同じ階層にあるものを調べていく方法。この方法では、最短で目的の状態を見つけることができる。しかし、同じ階層にある状態すべてを覚えておく必要があるので、メモリ消費は多くなってしまう。そのため、さくさく動くシステムを作るには向かない手法といえる。

　これらの方法は最適な解が木構造のどこにあるかで、その性能に幅が出て来ることにも注意しておきたい。

発見的探索

　こちらの方法は人間的に、「こっちの道に行ったらどうなるかな…？」なんてことを見積りながら経路を探索していく方法になる。この見積もりを立てる関数を発見関数と呼ぶ。発見関数を最適化することでよりいい見積もりを立てることができる。
　以下では、この迷路問題を解くために「目標につくにはJ地点を通る必要がある」といった特徴量が分かっている前提とする。この特徴を見つけ出す技術については「推論・学習」の範囲になるのでここでは割愛。

最良優先探索

　発見関数値の最も大きな（小さな）経路を選んでいく（階層は関係ない）。
　ここでは、迷路問題を解くにあたって現地点から目標地点までの最小距離を発見関数として設定する（もちろん、もっといい発見関数の設定があるかもしれない）。ここでいう「最小距離」とは迷路の壁を取り去ったときの最小距離のこと。例えば、今J地点にいて、目標がP地点だったとする。このときJ地点からP地点までは横に2回、縦に1回移動するので、最小距離は3ということになる。より早くこの問題を解きたいので、ここでは発見関数値の小さな経路を優先的にたどっていく。

（発見関数）

　この方法で解いていくと、盲目的探索よりも早く解ける可能性がある。しかし、見探索ノードの発見関数値をすべて記憶しておかなければならないので、メモリの消費は激しい。また、発見関数の性能によっては全く逆効果になる場合がある。

A*（エースター）探索

　最良優先探索の改良版。発見関数をだけではなく、開始地点から現地点までの実際の最小距離を足したものに変更する。

（発見関数）

　発見関数の値が同じであれば、階層の深いほうから順に探索を行っていく。
　この方法には、すべてのにおいてが実際の距離よりも小さい場合、必ず最適なものが見つかるという特徴がある。また、今回の問題では最良優先探索との違いが分からないが、経路の組み合わせが複数個ある場合はその中で最適な経路を見つけることができる。現在出回っている乗換案内などの探索システムは、ほとんどがこのA*探索を用いている。

山登り探索

　基本的な構造は最良優先探索、A*探索と変わらない。ただ、未探索経路を無視していく点で特徴的なものになっている。未探索経路を無視するので、バックトラック機構が不必要になり、メモリ消費を抑えることができる。しかし、最適解が発見できない可能性がある。この方法は、株取引などの時間制限が設けられている場合に「とりあえず答えが欲しい」というスタンスで使われる（解が出たら買う、出なかったら買わないなど）。

　こんなかんじで、状態空間探索法にはいろいろな手法がある。メモリの消費、探索完了までの時間などいろいろな要素があるため、一概に決めることができない。どれが一番有能かというよりも、用途によって使い分けることが大切になってくる。
　次回は、問題分解法についてやっていくそうです。