探索戦略の特徴付け
- 情報利用性 (informedness)
- 各探索戦略において，現在の状態から目標状態に至るステップ数や経路
コストに関する情報(知識)を用いるか用いないかを識別する特性．
- 情報(知識)を用いない探索(uninformed
search): 目標状態と非目標状態を区別するだけで，均一
コスト探索(uniform cost search)とも呼ばれる．
- 情報(知識)を用いる探索(informed search):
探索経路を選定する場合に，現在の状態から目標状態に至るステップ数や
経路コストに関する情報(知識)を用いる．これは発見的探
索(heuristic search)とも呼ばれる．
- 完全性 (completeness)
- 解が一つ存在するときに，それを見つけることが保証されているかどう
かという特性．
- 最適性 (optimality)
- いくつかの異なる解があるとき，戦略は最高品質の解を見つけることが
出来るかどうかという特性．
- 時間計算量 (time complexity)
- 解を見つけるためにどのくらい時間がかかるかという尺度．
- 空間計算量 (space complexity)
- 探索を行うためにどのくらいメモリを必要とするかという尺度．
...Return