多次元直方体被覆問題および充足可能性問題を解くアルゴリズム

鈴木 晋  茨木 俊秀  

誌名
電子情報通信学会論文誌 D   Vol.J80-D1   No.7   pp.591-604
発行日: 1997/07/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 
アルゴリズム,  計算複雑性,  NP完全,  多次元直方体被覆問題,  充足可能性問題,  

本文: PDF(1016.9KB)>>
論文を購入




あらまし: 
一つのd次元直方体(全領域と呼ぶ)が複数のd次元直方体の和により被覆されているか否かを判定する問題(多次元直方体被覆問題と呼ぶ)を考える.この問題は充足可能性問題の変形であり,充足可能性問題の代表的解法であるDavis-Putnum法と局所探索法を素直に拡張して,この問題を解くことができる.本論文では,直方体群の幾何学的性質を利用してDavis-Putnum法を拡張することにより新しい解法を提案し,提案した解法と従来の解法の効率を計算機実験により比較する.実験の結果,多次元直方体被覆問題および充足可能性問題のどちらにおいても,全領域の全体または全領域のほとんどの部分が被覆されていて,かつ,直方体の重複の度合が低い問題例では,提案した解法がDavis-Putnum法および局所探索法より効率的であることがわかった.