グラフの格子描画に対するコンパクション手法のプリント基板設計への応用

摘要

プリント基板設計のコンパクション問題とは，部品とそれらの端子を結ぶ配線からなる初期レイアウトが与えられたとき，初期レイアウトの制約を満たし，かつ基板面積が最小なレイアウトを求める問題である．この問題はNP困難であり，様々な発見的解法が提案されている．本稿では，グラフの格子描画におけるコンパクション手法をプリント基板設計のコンパクション問題解法に応用した発見的手法を提案し，計算機上での実験結果に基づく比較によりその性能を評価する．