Grant amount：\5200000 （ Direct Cost: \4000000 、 Indirect Cost：\1200000 ）

本研究では，集合の集合の集合である組合せ集合族を効率的に扱うための効率良いデータ構造の開発を目指している．組合せ集合として表現されるデータは学術分野でも産業分野でも数多くの状況で出現する離散構造であり，それらを集めたものである組合せ集合族も重要な概念である．また，機械学習や論理回路など多くの分野で用いられる論理関数は組合せ集合と一対一対応させられる離散構造であり，組合せ集合族をうまく表すことができるなら論理関数の集合もまたコンパクトに格納できる．そのため組合せ集合族用のデータ構造を実現できれば多くの実問題に対し有用性が期待できる．しかしながら，組合せ集合族に特化したデータ構造はこれまでに存在せず，省領域かつ高速に組合せ集合族を扱うことは困難であった．そこで本研究ではいままでうまく扱えなかった組合せ集合族に関する問題や組合せ集合族の表現に取り組み，以下の成果を得た：
1) k-集合選択問題を高速に解くアルゴリズム
与えられた組合せ集合の中から目的関数を最大化するようにk個の集合を選択する方法を全て求める問題であり，これを入力を圧縮表現した決定グラフ上で解くことにより既存手法よりも遥かに高速に解を全列挙することができる．さらに，決定グラフならではの構造を活かした工夫によりさらに計算速度を向上させた．
2) 組合せ集合族を表現するデータ構造
通常の組合せ集合を表すデータ構造であるゼロサプレス型二分決定グラフを部分構造として用いる新たなデータ構造を提案した．これにより複数の決定グラフを並べて表す従来の手法より大幅にコンパクトに組合せ集合族を表現することが可能となった．また，このデータ構造内の組合せ集合を検索するアルゴリズムも提案することで組合せ集合族用のデータベースとして使用できるようになった．さらに，完全一致検索だけでなく部分一致など組合せ集合ならではの検索を行うアルゴリズムも開発した．

researchmap

Grant amount：\17160000 （ Direct Cost: \13200000 、 Indirect Cost：\3960000 ）

列挙、数え上げ、サンプリングなどのアルゴリズムは、互いに深く関連しつつも、それぞれ独自の技法が必要とされることが多い。ここで、同じ制約条件のもとで、つまり同じ解空間において、解の列挙、数え上げなどタイプの異なるアルゴリズムそれぞれを個別に設計する状況を見つめ直し、アルゴリズム設計者が頭の中に持つ解空間に関する理解をもとにアルゴリズムを導出する過程を明らかにすることで、列挙、数え上げ、サンプリングなどのアルゴリズム設計を統一的に扱うための指針を与えることを本研究課題の目的としている。
連携研究者も交えた議論を通して、列挙や数え上げなどのアルゴリズム設計の過程の再検討を行った。具体的には、たとえば、グラフの同型性の観点から代表元のみを列挙する同型性の除去について、ZDD (Zero-Suppressed Binary Decision Disgrams; 零抑制型二分決定グラフ) を用いるアプローチの検討を行った。これまでの同型性の除去手法では ZDD 構築時に同型性の認識のために保持する情報が膨大であり、新たな手法の模索・開発を行った。展開図の重なり判定に回転展開法により得られた展開図の重なりを元にそれと同型な部分展開図を ZDD で管理することで、多面体の展開図の重なりを網羅的に調査できるようになった。切頂二十面体では375,291,866,372,898,816,000個の展開図の97.6％が重ならないなど、莫大な個数の展開図を効率的に扱うことができる。また、アルキメデスの角柱や反角柱に対して、上下の正n角形のnと重なりを持たない展開図の割合との関係を調査し、角柱はn=28, 29で88.7％, 48.7％、反角柱はn=17, 18で91.6％, 18.7％と大きなギャップを持つことが分かった。他にも組合せ遷移や文字列等の関連分野への応用に関する検討を行った。

researchmap

Grant amount：\2600000 （ Direct Cost: \2000000 、 Indirect Cost：\600000 ）

論理関数や組合せ集合を超える複雑さの離散構造は従来技術では扱うことが困難であった．本研究では組合せ集合のさらに集合である組合せ集合族や，一般化された多段の集合である遺伝的有限集合と関わりの深い木構造を対象としてアルゴリズムの開発を行った．特に，予め圧縮により小さくしてから処理することで計算時間や計算資源の劇的な削減を実現する圧縮表現上での計算技術の開発に注力した．本年度の研究実績の概要は以下のとおりである．
(1) 与えられた組合せ集合とk個の組合せを引数に取る目的関数に対し，目的関数を最大化するようなk個の組合せの選び方を求める問題を解くアルゴリズムを開発した[学会2，特許1]．これによりk個の組合せからなる最適な組合せ集合を全て求めることが可能となった．既存手法では圧縮前の組合せ数に対して指数的な時間がかかるところ，提案手法では決定グラフによって圧縮表現された組合せ集合を処理するため入力データが圧縮されているほど高速な最適化が実現できる．また，決定グラフと親和性が高くこのアルゴリズムを適用することのできる関数クラスを明らかにすることで多くの実用的な設定や数理的に重要な問題に対して本手法が活用できることを示した．加えて，最適解を導く組合せ集合全てを表す索引を構築し，解の検索や数え上げ，列挙を圧縮索引の大きさに依存した計算で実行する方法も提案した[特許2]．これは本研究の目的でもある組合せ集合族を扱う索引になっている．
(2) 各頂点の次数が指定された際に考えうる全ての木構造を列挙するアルゴリズムを開発し，それが多項式時間遅延で実行されることを証明した[学会1]．この設定での木構造は各集合に含まれる要素の数が決められた遺伝的有限集合にほぼ等しい．これにより制約つきの遺伝的有限集合の個数を正確に計算することができ，それら表現に必要な情報量の情報論的下限を計算することに利用できる．

researchmap

Grant amount：\4160000 （ Direct Cost: \3200000 、 Indirect Cost：\960000 ）

In this study, I developed a computational technique for compressed representations that dramatically reduces computation time and space by compressing large-scale data in advance. We proposed compression methods that apply not only to sequence binary decision diagrams but also to various types of decision diagrams and evaluated their performance. These results provide a data structure and algorithm that can further compress a sequence binary decision diagrams representing large-scale sets of strings into a compact size and process them at high speed.

researchmap

Grant amount：\2990000 （ Direct Cost: \2300000 、 Indirect Cost：\690000 ）

I have developed methods to process and analyze huge databases that are efficiently represented as directed acyclic graphs, by using Binary Decision Diagrams (BDDs). I have researched data structures to represent huge databases as directed acyclic graphs in compressed form, efficient algorithms to process and analyze databases based on BDDs, and applying these fundamental techniques for real data with performance evaluations and feedbacks.

researchmap