MAX 2SATに対するシンプルな正解付テスト例題生成について
スポンサーリンク
概要
- 論文の詳細を見る
本稿ではMAX 2SATに対するテスト例題生成問題を考える.アルゴリズムの性能評価をシミュレーションなどの実験的手法を用いて行うとき,テスト例題が必要になる.しかし,組み合わせ最適化問題に対する近似アルゴリズムの(近似面での)性能を評価するときは,テスト例題だけではなくその最適解がないと,どのくらいよい近似解が得られたのか評価することが出来ない.したがって,テスト例題とその最適解を(ランダムに)出力する例題生成アルゴリズムが必要となる.ところが,NP = co-NPでない限り,多項式時間アルゴリズムで全ての可能な例題とその最適解を出力することは不可能である.そこで本稿ではMAX 2SAT問題のテスト例題として2CNFの部分集合とその最適解を生成する手法を考える.このとき,もし着目した2CNFの部分集合が例題として簡単なものばかりであるなら,これらはテスト例題として適当ではない.すなわち,この部分集合の困難性を示す必要がある.今回は,この部分集合がNP完全であることを示す.
- 社団法人電子情報通信学会の論文
- 2003-12-15
著者
関連論文
- ある投票ゲームのシミュレーション
- 単純多角形の生成に関する発見的手法(セッション2)
- 3充足可能性判定問題3SATの単一解を持つ正例題生成手法
- 3充足可能性判定問題 3SAT の単一解を持つ正例題生成手法の解析
- MAX 3SATのランダムな例題生成
- MAX-3SATの解の平均の解析
- Dirichlet分布に従う多項式時間近似サンプリング法(マルコフ連鎖)
- Dirichlet分布のrapidly mixing approximate sampler
- Dirichlet 分布の rapidly mixing approximate sampler
- パス幅を用いた#2SATの厳密アルゴリズム
- MAX 2SATに対するシンプルな正解付テスト例題生成について
- MAX 2SATに対するシンプルな正解付テスト例題生成について
- Test Instance Generation for MAX 2SAT with Fixed Optimal Value (New Aspects of Theoretical Computer Science)
- ある投票ゲームのシミュレーション