3次元格子スタイナー木を求める並列遺伝的アルゴリズムの改良

摘要

格子スタイナー木は，LSI概略配線設計等にも応用される重要な問題のひとつである．また，ナノCMOS時代のこれらの配線に関しては，折れ曲がりが増えると，タイミングの見積もりなどに悪影響を及ぼすと考えられる．著者らは，空間上に3次元座標を持っ点の集合，それらを結ぶユークリッド最小全域木，障害物が与えられたとき，木の枝をX軸，Y軸，及びZ軸に平行な線分に置き換え，最小＋1の折れ曲がりを使うことにより，より柔軟に障害物をよける3次元最小格子スタイナー木を求める並列遺伝的アルゴリズムを提案しているが，本稿ではこれを改良し，障害物がない場合でも，共有部分が長くなりそうな分岐点を求めてそこで折れ曲がることにより配線長を短くしようと試みる．評価のために行った実験結果についても述べる．