著者

田中 雄一郎 高橋 篤司

雑誌

DAシンポジウム2014論文集

巻号頁・発行日

vol.2014, pp.221-226, 2014-08-21

---

本稿では,平面基板上の集積回路設計における配線問題と親和性の高いペンシルパズルである,ナンバーリンクの特性について考察し,その解法について述べる.ナンバーリンクは,縦横斜めの周囲 8 マスで隣り合う数字を一塊にして島とすることで,空洞内島配線問題として解くことが可能である.外部配線問題において,CHORD-LAST 法は全ネットが配線可能である時,平面性を失わないネットの配線順序を与える.提案アルゴリズムでは,この順序を利用してナンバーリンクの解を生成する.また,対となる数字が共に外側のマスに位置する時,その数字を結ぶ配線で配線領域を分割することが可能であり,他の数字の組は共に片側の領域に位置する.領域の分割を用いた枝刈りを組み合わせることにより,計算量を削減したアルゴリズムを提案する.

著者

伊藤 直也 石浦 菜岐佐 冨山 宏之 神原 弘之

雑誌

DAシンポジウム2014論文集

巻号頁・発行日

vol.2014, pp.121-126, 2014-08-21

著者

人見 光夫

雑誌

DAシンポジウム2014論文集

巻号頁・発行日

vol.2014, pp.1-2, 2014-08-21