電子情報通信学会ソサイエティ大会講演要旨
A-6-1
矩形パッキングのための効率的な探索木の構成法
◎北出哲大・藤吉邦洋(東京農工大)
組合せ最適化問題の一つである矩形パッキング問題は、「与えられた矩形の集合を互いに重なることなく、出来るだけ小さな矩形の範囲内に収める」というNP困難な問題であり、LSIの配置問題の基本である。この問題に対しては解表現に基づいた解探索がよく行われる。
全探索などの各種探索は探索木に基づいて行われる。探索木の構成は解表現に基づいて複数考えられ、その違いは探索効率に影響する。そのため、探索木を用いて解探索をおこなう場合は適切な探索木を選択する必要がある。本研究では、パッキングの表現方法であるSequence-pairに基づいた探索木の構成法3種についてモンテカルロ木探索を用いた実験を行い、探索効率の比較を行う。探索効率を比較したところ、探索木の節点数が少ないものほど効率が良かった。