障害物を有する格子グラフにおけるスタイナ一木構成法 : スタイナー候補点の改良選択法による性能強化

摘要

格子スタイナー木問題とは,格子グラフH=(V,E),障害物集合D_iからなる族D,およびV-Dに含まれる指定点集合Pが与えられたとき,HからD_iの各点とその接続辺を取り除いたグラフにおいて,指定点をすべて含み,辺数が最小となる木(格子スタイナー木)を求める問題である.これはVLSI基板設計などに幅広い応用を持つが,|P|≧4でNP-完全であり,本問題に対する様々な近似解法や発見的解法が既に提案され,それらの性能が計算機実験により評価されている.本稿では,スタイナー候補点に基づく既存解法に着目して,これらに改良候補点抽出法を組込んだ発見的解法を提案し,それらの性能を計算機実験により評価する.