線形な領域計算量の最良優先探索の探索順序の緩和

概要

論文の詳細を見る
人工知能における問題空間の探索法の分野で、限られたメモリーの上で実行できる探索法について、これまでに様々な方法が考え出されている。中でもR.E.Korfが示した再帰的最良優先探索法(Recursive Best-first Search以下RBFS)は、領域計算量が線形のオーダーですみ、かつ節点の探索順序は最良優先探索と同じく、最小のコストを持つ節点を優先して展開する探索法である。この探索法の特徴は時間計算量は発生した節点の数に比例することですが、問題を解く途中で同じ節点を再び展開しなければならないことがあり、それによって節点の重複が起こり、そのため発生する節点の総量は従来の最良優先探索よりも相対的に多くなり、問題を解く速さに影響する。そこで本研究では、速さを高めるために、開節点の中での最小のコストにある程度近い値を持つ節点であれば探索を打ち切らずに展開を行うようにして、発生する節点の総量を押さえる探索法を考え、RBFSとの計算の速さ、解の質などについて比較実験を行っている。本稿ではその概要を示す。
一般社団法人情報処理学会の論文
1994-09-20