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

摘要

本稿では，NTTと北海道大学で開発した，厳密被覆問題と呼ばれる問題のすべての解を高速に見つけることができるアルゴリズムを紹介します．マンションの間取り決め，電子回路の部品の配置決め，ポリオミノパズルは厳密被覆問題として定式化して解くことができます．本方法は，既存法よりも最大１ 万倍高速にすべての答えを発見するだけでなく，見つけたすべての解を圧縮して記憶しておき，条件に応じて取り出すことができるので，良い解を効率的に探すことが可能になります.