第17回 KIDS
日時
２００４年４月１９日（月） 13:00--16:20（開始時間が早まりました）
場所
京都大学ベンチャービジネスラボラトリ ２階セミナー室
プログラム
13:00--14:00
平井 広志（数理解析研究所）
有限距離空間の離散凸性
14:10--15:10
古賀 祐一（旧茨木研）
MAX-2-SATに対する分枝限定法
15:20--16:20
玉置 卓（岩間研）
3SATの計算時間について
リンクの張ってある題名は、クリックすると概要が見られます。
概要
平井 広志（数理解析研究所）
題目
有限距離空間の離散凸性
概要
本研究では，バイオインフォマティックス等の分野で現れる
有限個の要素からなる距離空間を離散的な凹関数と見なすという
新しいアプローチを提案した．これによって
凸解析の観点から有限距離空間の組合せ構造を抽出できるようになった．
特に進化系統樹の構成法として知られるH.-J. BandeltとA. Dressの
距離関数のスプリット分解理論を，
多面体的凸関数および離散凸関数のスプリット分解に一般化し，
その多面体的な幾何構造をより明確にした．
またDressらによる有限距離空間の組合せ論を論じる
統合的枠組「T理論」の中心的概念である
tight spanの双対的概念である距離複体の概念を導入した．
本研究で用いた手法の多くは室田による多面体的組合せ論から
離散凸解析に至るアプローチを精神的に受け継いでいる
古賀 祐一（旧茨木研）
題目
MAX-2-SATに対する分枝限定法
概要
MAX-2-SATとは、最大充足可能性問題(maximum satisfiability problem, MAX-SAT)の一種
で、n変数m節(各節に含まれるリテラルの数は高々2)の集合が与えられたとき，
充足節の重みの和を最大にする変数の割当を求める問題である。この問題はNP困難であることが知られており，
これまでに様々な近似解法が提案されてきたが、厳密解法の研究については比較的歴史が浅い．
MAX-2-SATでは，分枝限定法において分枝を行うと，単一リテラル節(unit clause)を生じることが多く，
それを利用したルールが効果的であるという性質がある．
従来の研究では，分枝限定法における上界値の優れた計算方法がなく，単一リテラル節に基づくルールが有効
に作用するまで多くの分枝操作を行って探索木を展開せざるをえなかった．そのため，探索木の節点数が増え
る傾向があった．
本研究では，この問題を解決するため，新たな上界値計算のアルゴリズムを提案し，それを組み込んだ分枝限定法の性能を評価する．
代表的なベンチマーク問題に対する計算実験の結果，提案した上界値計算法は，探索の初期の段階から有効に作用することが観測できた．その結果，
多くの問題例に対して探索木の節点を減らすことに成功し，他の解法よりも短い計算時間で最適解を出力することを確認した．
玉置 卓（岩間研）
題目
3SATの計算時間について
概要
CNF論理式の充足可能性問題（SAT）は和積形のブール式が与えられた時，全ての
節を真にする，つまり式全体を真にする様な変数への真理値割り当てが存在する
かどうかを問う問題である．各節に含まれるリテラルの数が高々k個であるCNF論
理式(k-CNF論理式) の充足可能性問題はk-SATと呼ばれる. 特にNP完全性が成立
する最小のk=3の場合が重要であり, 3SATの計算時間の改善を目指して活発な研
究が行なわれている.
本発表では3SATに対するいくつかの代表的なアルゴリズムとその計算時間を紹介
する. また我々の得た3SATに対する現時点で最良の計算時間 1.324^n を与える
アルゴリズムとその解析についても解説を行う.