バックトラック無しアルゴリズムの実験評価

概要

論文の詳細を見る
制約充足問題(CSP)は問題の対象の構成要素の局所的な構造に基づいて可能な局所解の侯補を求め、それらの中から対象全体について矛盾のない局所解の組合せを求める問題である。CSPを解くとは、制約を充足するような局所解すなわち変数への値の割り付けの組合せを探索していく処理である。この処理はバックトラックを基本とした縦型探索が主流である。これは、矛盾が起こらない限り中間解を拡張していく方法であり、矛盾が生じると探索木を遡り、別の局所解の候補を調べる。したがって、もし探索の過程が常に最終解に至る探索路に乗っていることが保証されるならば、バックトラックは発生しないはずである。このような探索を、'バックトラック無し'としいう。我々は先に、バックトラックによって探索木を遡る範囲がある一定サイズk(「幅」という、後述)以内に限られるようなCSPの部分クラスに注目して、バックトラック無しアルゴリズムを提案した。本稿はバックトラック無しアルゴリズムの計算時問量について実験で評価ま平価したものである。
一般社団法人情報処理学会の論文
1993-03-01