GAによる遅延評価での直線スタイナー問題

スポンサーリンク

概要

論文の詳細を見る
近年, VLSI回路での配線のレイアウトを行う時に効率的になるように求める問題が多く考えられている。そこで注目を集めている直線スタイナー木を用いることによって効率的なレイアウトを求める。しかし, この問題はNP-完全であるということから最適解を得るのが非常に困難であるとされている。そこで本研究では遺伝的アルゴリズム(GA)を適用してこの解の近似値を求める。また, 今まで多くの研究はその評価基準にその生成された木の総合計の長さを用いているが, 本研究では木において最大となる通信遅延で評価している。しかし最近の研究により長さが最小であるからといって必ずしも遅延が最小であるとは限らないとされている。よってここでは物理的な遅延としてエルモアー遅延と呼ばれるものを用いている。
一般社団法人情報処理学会の論文
1997-09-24

著者

関連論文

もっと見る

スポンサーリンク