組合せ爆発を乗り越える最先端アルゴリズム技術とその実装

本記事では、NTTコミュニケーション科学基礎研究所の西野正彬氏による数理システム ユーザーコンファレンス2021講演
「組合せ爆発を乗り越える最先端アルゴリズム技術とその実装」
の内容をもとに、組合せ爆発を扱う最先端アルゴリズム技術と、その理論を実社会で活用可能なソフトウェアへと昇華させる実装の重要性について紹介します。

社会の至る所に潜む組合せ爆発

現代のAIや最適化技術において、避けて通れない巨大な壁となっているのが「組合せ爆発」です。対象となる要素がわずかに増えるだけで、考えられる選択肢が指数関数的に増大し、現実的な時間で計算することが困難になります。

例えば、50人を2グループに分ける方法は126,410,606,437,752通り、100人では100,891,344,545,564,193,334,812,497,256通りにも達します。このように問題規模がわずかに増えるだけで、解の数が爆発的に増加することが分かります。

組合せ問題では、条件を満たす組合せの列挙や数え上げを行いたい場面が多くあります。しかし、すべての組合せを単純に列挙する方法では組合せ爆発のため現実的な時間で処理することができません。 そこで注目されているのが、膨大な組合せを「圧縮」して扱うアプローチです。

例えば格子状のグラフにおいてスタートからゴールまで進む経路問題でも、考えられる経路は789,360,053,252通りに達します。 図1に示すように、この問題では各交点で進行方向を選択することで経路が決まり、その組合せが膨大になります。

このような単純な構造の問題であっても、解の総数は非常に大きくなることが分かります。

膨大な組合せを圧縮して扱う技術

この技術の基盤となるのが、組合せの集合をグラフ構造で表現する「二分決定グラフ（BDD）」と、そのバリエーションの一つである「ゼロサプレス型二分決定グラフ（ZDD）」です。 BDDやZDDでは、複数の組合せに共通する部分構造を共有することで、組合せ集合をコンパクトに表現することができます。 例えば先ほどの経路問題では、789,360,053,252通り存在する経路集合を、ZDDでは33,580個の頂点を持つグラフとして表現できます。

図2はその圧縮の様子を示しています。

このように、組合せの数そのものではなく、組合せの構造を表現することで、大規模な問題でも現実的なサイズで扱うことが可能になります。

図3は二分決定グラフの基本構造を示したものです。

このような表現を用いることで、圧縮した状態のまま様々な計算が可能になります。 例えば、条件を満たす組合せだけを抽出したり、複数の組合せ集合を合成したり、組合せの総数を数え上げたりといった処理を、膨大な組合せを一つずつ確認することなく決定グラフ上で直接実行できます。

図4は、ZDD上で集合演算や条件付けを直接行うことで、膨大な組合せを列挙せずに高速計算できることを示しています。

この結果、計算時間は組合せ数ではなく決定グラフのサイズに依存するようになり、巨大な組合せ問題でも現実的な時間で扱えるようになります。

応用例：敷き詰め問題

この技術は様々な問題に応用されています。 例えばマンションの間取り設計などにも関係する敷き詰め問題では、盤面を特定の形状で隙間なく埋める配置方法を求めます。

図5はその問題例を示しています。

このような問題では考えられる組合せ数が非常に大きくなりますが、BDD/ZDDを用いることで解集合を圧縮したまま扱うことが可能になります。

実装の重要性

こうした最先端アルゴリズムを実際に活用するためには、高度な実装技術が不可欠です。 例えばZSDD（Zero-suppressed Sentential Decision Diagram）はBDD/ZDDの拡張的な構造であり、特定の問題においてより高い圧縮率を実現できます。

図6はZDDとZSDDの構造の違いを示しています。

しかし、その効率的な実装には高度な専門知識と実装技術が必要になります。 このような研究成果を実際のソフトウェアとして活用するためには、アルゴリズムの理論理解だけでなく、それを安定して動作する形で実装する技術が重要になります。

本事例では、NTTデータ数理システムがアルゴリズム理解から実装までを担い、研究成果の実用化に貢献しました。

理論と実装の両方が揃うことで、最先端アルゴリズムは初めて社会で活用可能な技術になります。

終わりに

より詳しい内容を知りたい方は、以下の資料もご参照ください。

• 西野正彬氏による数理システム ユーザーコンファレンス2021講演資料
  「組合せ爆発を乗り越える最先端アルゴリズム技術とその実装」
  https://www.msi.co.jp/event/conference/uc2021/lp/pdf/msi2021_1_4.pdf

• NTTコミュニケーション科学基礎研究所 Open House 2021 展示資料
  「組合せ爆発を乗り越える最先端アルゴリズム技術」
  https://www.kecl.ntt.co.jp/openhouse/2021/download/exhibition_03.pdf