領域分割を用いたCHORD-LAST法に基づくナンバーリンク解法

• Item type: Symposium(1)
• 公開日: 2014-08-21
• タイトル: 領域分割を用いたCHORD-LAST法に基づくナンバーリンク解法
• タイトル / 言語: en
• タイトル: Numberlink solver based on CHORD-LAST method with area decomposition
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: アルゴリズム・ソルバ
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東京工業大学大学院理工学研究科
• 著者所属: 東京工業大学大学院理工学研究科
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者名: 田中, 雄一郎; 高橋, 篤司
• 著者名(英): Yuichiro, Tanaka; Atsushi, Takahashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，平面基板上の集積回路設計における配線問題と親和性の高いペンシルパズルである，ナンバーリンクの特性について考察し，その解法について述べる．ナンバーリンクは，縦横斜めの周囲 8 マスで隣り合う数字を一塊にして島とすることで，空洞内島配線問題として解くことが可能である．外部配線問題において，CHORD-LAST 法は全ネットが配線可能である時，平面性を失わないネットの配線順序を与える．提案アルゴリズムでは，この順序を利用してナンバーリンクの解を生成する．また，対となる数字が共に外側のマスに位置する時，その数字を結ぶ配線で配線領域を分割することが可能であり，他の数字の組は共に片側の領域に位置する．領域の分割を用いた枝刈りを組み合わせることにより，計算量を削減したアルゴリズムを提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose a method that solves Numberlink which is a pencil puzzle with high affinity to a routing problem in integrated circuit design of planar substrate. Numberlink is solved as an island-in-cavity-routing problem by regarding adjacent numbers as an island. In this island routing problem, CHORD-LAST method gives a feasible routing order of nets when the planer routing is possible. This order is utilized in our proposed algorithm. If both pins of a net exist on the outer boundary, the wire which connects these pins divides routing area and other net belongs to one of them. Our proposed algorithm reduces the computation time by combining pruning obtained by routing area division.
• 書誌情報: DAシンポジウム2014論文集; 巻 2014, p. 221-226, 発行日 2014-08-21
• 出版者 / 言語: ja
• 出版者: 情報処理学会