2分決定グラフ新構成法に基づく離散システム論と大規模最適化法の新展開
【研究分野】計算機科学
【研究キーワード】
グラフ / ネットワーク / マトロイド / Tutte多項式 / 離散システム / ネットワーク信頼度 / 2分決定グラフ / Jones多項式 / Tutte 多項式 / Jones 多項式 / Trtte多項式
【研究成果の概要】
本研究では,2分決定グラフ(BDD)に基づいた離散システム論に対する統一的アプローチを確立することと,プロトタイプシステムを統合システムへと発展させることを目指した.これによって,従来は不可能であった離散システムの構造全体の暗黙的・効率的表現をコンピュータ上に行なうことが可能になり,新たな展開が種々可能となった.本アプローチをネットワーク信頼性解析・結び目のJones多項式計算への展開し,実際に計算システムを開発した.計算量的には#P完全で難しいとされている問題でも,構造を活用して中規模な問題を解けることを実証した.たとえば,14×14の格子状のグラフのネットワーク信頼性関数を計算することが可能となった.また,Jones多項式計算の結果により,BDDアプローチの計算位相幾何学への発展も開けた.BDDの基礎理論においても,単調論理関数とその主項のBDDのサイズに関して理論的解析を行い,指数ギャップを証明した.
代数的なアプローチとの関係では,Grobner基底に代表される計算代数の離散システムへの適用についても新展開を図った.本研究では,整数計画の効率よく解けるネットワークフローの場合にこのアプローチを適用し,理論的解析がかなりのところまで進められることを示した.さらに,2分決定グラフが分岐プログラムの特殊な場合であることに着目し,計算モデルとしてのパワーを新コンピューティングモデルである量子計算に発展させる研究でも成果をあげた.具体的には,量子計算においてJones多項式との関係について検討し,さらにBDDのレベルにおいて,量子と現在の計算モデルとの間の計算能力差を示すことにも成功し,これについては発表を予定している.
【研究代表者】