計算と言語の科学

研究展示 9

敷き詰めかたをすべて見つけます

~厳密被覆問題の高速な全解列挙法~

概要

厳密被覆問題とよばれる問題のすべての答えを高速に見つける方法を紹介します。例えば、電子回路基板のモジュール配置を決める問題や、マンションの部屋の配置を決める問題などが厳密被覆問題に相当します。私達の方法は、既存法よりも最大1万倍高速に動作し、かつ、見つけたすべての解を圧縮して保存しておいて、条件に合わせて高速に解を選び出すことが可能であるという特徴を備えています。この方法を用いて、例えば、基板上の無駄のないモジュール配置を見つけることで消費電力を削減したり、利用者の好みに合わせたマンションの部屋の配置を見つけることができます。

ポスター


ポスターの画像をクリックすると、PDFファイルが開きます。

展示担当者

西野 正彬
西野 正彬
協創情報研究部
安田 宜仁
安田 宜仁
協創情報研究部
坂上 晋作
坂上 晋作
協創情報研究部
上垣外 英剛
上垣外 英剛
協創情報研究部