部分最適化問題の完全性について
スポンサーリンク
概要
- 論文の詳細を見る
CNF論理式の充足可能性問題(SAT)は基本的な組合せ問題であり, 解法アルゴリズム, 例題生成アルゴリズム等の研究が盛んに行われている。しかし, SATを実用的時間で解くのは不可能であると考えられているため, 近年では, 実用時間でできるだけ多くの項を充足する解を見つける問題であるMAXSATの近似解法の研究も行われている。その中で, 特に局所探索法は最適に近い解を高速に見つけるとの報告もあり, 注目を集めている。これにより, 様々な組合せ最適化問題をMAXSATに変換し, MAXSATに対する高速アルゴリズムを利用して解くという方法を考えることができる。しかしFスケジュール問題等の現実社会に則した最適化問題を模倣するのにはMAXSATは不十分であり, MAXSATの一般化である部分MAXSATという問題が新たに提案された。部分MAXSATの例題は2つのCNF論理式f_Aおよびf_Bからなり, f_Aの項を全て充足させた上でf_Bの項をできるだけ充足する割当を求める問題である。部分MAXSATはMAXSATよりも一般性を有しているにも関わらず, 項に重み付けを施すことによって, 従来のMAXSATアルゴリズムを用いて, 十分に良い解を探索できるということが実験により分かった。このように, 部分MAXSATは様々な問題を模倣でき, 高速に良い解を求めることのできる問題であるが, どのような問題が部分MAXSATを利用して解けるかは明らかになっていない。本論文では, 部分MAXSATの最適化問題のクラスでの完全性を示し, あらゆる最適化問題を模倣可能であることを示す。最適化問題の完全性の議論は盛んに行なわれているが, 部分MAXSATのような, 「部分最適化問題」を取り扱った文献は見受けられない。また, MAXSATに対して部分MAXSATが存在するように, 他の最適化問題にも対応する部分最適化問題を考えることができる。本論文では, そのような部分最適化問題の完全性に関しても議論を行う。
- 1997-09-24
論文 | ランダム
- Part2 問題噴出、日本企業 IT部門弱体化の内情 (特集 崩壊するアウトソーシング--「他人任せ」に未来はない)
- 情報管理 人ごとではない個人情報保護法--対応の差が将来の受注に影響を及ぼす可能性も
- 国連防災世界会議を開催--神戸 地球規模の「減災」協力へ始動--人ごとではないインド洋の惨劇
- *** 黒木香、藤小雪、卑弥呼、田中露央沙、柏木よしみ、乃木真梨子 (総力特集 一挙50人! あの「主人公」はいま)
- 伊都までの水行陸行と耶馬台国