Next: Up: Previous:

ネットワークダイアグラムレイアウト問題

ネットワークダイアグラムレイアウト(NDL)問題はグラフィックスを自動化する上で難 問の一つである. 汎用ネットワークダイアグラムレイアウト(GNDL)の計算量は膨大であ り, 現在知られている発見的な方法は特定の NDL にしか適用できない. Kosak, Marks, Shieber [20] は GNDL 問題に CM-2 上で cellular GA を適用した. CM-2 は 4096プロセッサが二次元グリッド(64×64)状に配置され, トーラス状に接続さ れている. 一つのレイアウトの候補をビット化し, 1個体として各プロセッサに割り当 て, 選択と交配は隣接するプロセッサ間でのみ行なわれた. 30個のネットワークダイア グラムに適用し, 十分に美しく配置することに成功した.



Mitsubishi Research Institute,Inc.
Mon Feb 24 19:32:36 JST 1997