部分最適化問題の完全性について
スポンサーリンク
概要
- 論文の詳細を見る
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
論文 | ランダム
- ナースの出番! PCPSの合併症と看護のポイント (特集 循環器・集中治療に携わるナース必修! IABP・PCPS誌上勉強会)
- 病院職員の経営・管理研修の受講時期と意識
- Plasma Level of Homocysteine is Inversely-Associated With the Development of Collateral Circulation in Patients With Single-Vessel Coronary Artery Disease
- -P218- CYCLIC AMP DEPENDENT PROTEIN KINASE ACTIVITY IN STREPTOZOTOCIN-INDUCED DIABETIC RAT HEART
- SEVEN YEAR PROGNOSIS OF RESIDENTS WHO RECEIVED HOLTER ECG AFTER ARRHYTHMIA WAS DETECTED DURING ROUTINE ECG : AFLLOW-UP STUDY OF CARDIOLOGICAL MEDICAL EXAMINATIONS IN CENTRAL SHIZUOKA PREFECTURE