列挙アルゴリズムの遅延時間減少とその手法の一般化

点击翻译按钮获取中文摘要

本年度は、主に現在までに開発したアルゴリズムの応用を中心に研究を行った。一つ目はグラフのサイクル、およびコードレスサイクルを列挙するアルゴリズムである。これは去年度の研究成果であるが、本年はこれを化学シフト推定問題に適用した。化学シフトとは化合物中の原子が持つある種の測定値であり、化合物中の他の原子との距離により値が決まる。このため、化合物の実際の形状を正確に求めるために使われるのだが、環構造などが含まれる化合物では、局所的な結合の状態のみからではよい予測ができず、実験から効率良く推定値を求めることは難しかった。今回の研究では、環構造、つまりグラフのコードレスサイクルを列挙することで環構造のおおまかな形状を推定し、予測を行うシステムに応用した。現在までに行ってきた高速な列挙を行う手法がそのまま適用され、精度、時間ともに効率を上げることに成功した。2つ目は極大重みつきクリークの列挙アルゴリズムである。重みつきクリークとは、頂点重みの和が与えられた閾値を越えないもののことをいい、このようなクリークの中で極大なものを極大重みつきクリークと呼ぶ。この問題に対する効率の良いアルゴリズムは知られていなかったが、今回の研究では、極大クリーク列挙アルゴリズムを改良し、この問題に対して初めての多項式時間アルゴリズムを与えた。また、このアルゴリズムの実装も行い、現実問題でも高速であり、通常の極大クリークに比べても遜色ない時間で列挙できることがわかった。重みつき極大クリークを列挙することで、点集合を最小な正方形で被覆する問題に対する効率良い列挙型解法を与えることができる。今回の研究では、この解法に対する計算実験も行い、解法の有効性を検証した。