列挙や数え上げなどを統一的に扱うための基盤技術

点击翻译按钮获取中文摘要

列挙、数え上げ、サンプリングなどのアルゴリズムは、互いに深く関連しつつも、それぞれ独自の技法が必要とされることが多い。ここで、同じ制約条件のもとで、つまり同じ解空間において、解の列挙、数え上げなどタイプの異なるアルゴリズムそれぞれを個別に設計する状況を見つめ直し、アルゴリズム設計者が頭の中に持つ解空間に関する理解をもとにアルゴリズムを導出する過程を明らかにすることで、列挙、数え上げ、サンプリングなどのアルゴリズム設計を統一的に扱うための指針を与えることを本研究課題の目的としている。本研究課題の研究者のみならず、課題外の連携研究者との議論も通して、列挙や数え上げなどのアルゴリズム設計の過程の再検討を行った。具体的には、たとえば、グラフの同型性の観点から代表元のみを列挙する同型性の除去について、ZDD (Zero-Suppressed Binary Decision Disgrams; 零抑制型二分決定グラフ) を用いるアプローチの検討を行った。制約条件を満たす解集合をうまく区分し、それらの区分された解集合相互の関係を表す方法を検討する際に、非同型なものを漏れなく重複なく求められる保証を与える必要があり、具体的なアルゴリズム設計を通して、アルゴリズム設計とアイデア記述に関する知見を得た。また、列挙と深い関連を持つ組合せ遷移問題も含めて、関連分野への応用に関する検討を行った。具体的には、たとえば、45度系格子パターン上での折り紙の展開図の列挙と数え上げの技法についてである。この問題では、縦横および斜め45度方向の格子上のみに折り線の位置を限定し、各頂点で平坦に折ることのできる局所平坦性を制約として、展開図の列挙または数え上げを行っている。また、格子の規則性から、回転および鏡映反転による同型性を考慮する必要があり、応用上の要請だけでなく、本研究課題の方向性にも沿った研究成果である。