C04班実践的な列挙アルゴリズムの理論構築研究代表者研究分担者宇野毅明（国立情報学研究所＆総合研究大学院大学）中野眞一（群馬大学）松井泰子（東海大学）岡本吉央（豊橋技術科学大学）清見礼（北陸先端科学技術大学院大学） 2007年5月14日新世代の計算限界全体会議列挙アルゴリズムの歴史・初期は、計算機パワーの不足で、数理面、理論面が中心－ある種の構造からなる集合の、大きさ、隣接性  直径や連結性の議論へ・最適化の一部として（最適化に使われるような）比較的シンプルな部分構造を列挙する問題－パス、全張木、マッチング、サイクル、多面体の頂点など  出力の大きさに対する多項式性、計算量の減少近年の変化・近年、計算機パワーの増大＆計算の目的があいまい化、により、列挙が応用に使われるようになってきた（データマイニング、データ解析、多目的最適化、厳密アルゴリズムなど）・培われてきた技術は、いまひとつピントがぼけている（応用先、問題、データの構造・・・）どんな問題を、どのようなアルゴリズムで解くと、どのような性質が見えるのか？新たな問題・大きな入力、それほど大きくない解の数、という状況で、効率良いアルゴリズムをどのように構築するか？（既存のデータ構造は少し視点が違う）・複雑な構造を列挙するにはどうしたらいいのだろうか（単純なバックトラックなどは通用しない）・部分構造ではなく、ある種の構造全てを列挙するにはどうするか？（同型性が問題となる）・厳密アルゴリズムや、数学の問題への列挙・数え上げの応用には何が必要か？（多大な時間  長い時間、にする）解数のコントロール・列挙を応用で使うための大きなボトルネックは、解の多さ・この問題を解決するため、極大（極小）解のみの列挙、評価値によるフィルタリング、といった方法がとられ始めてきた・これによって解数は抑えられるが、解と解との距離が開きがちになり、探索のコストは増大する・しかし、実際に解きたい問題は巨大な入力を持つことがしばしばある。特にデータマイニング・解１つあたりの計算時間が、入力に対して非常に小さくなる必要がある頻出パターン発見・例として、データマイニングの基本問題である、頻出パターン発見（マイニング）を見てみる・データベースの、閾値以上の項目に含まれるパターン（頻出パターン）を全て見つける問題・パターンは、集合、文字列、シークエンス、グラフ、木など・閾値を調節することで、解の数をコントロールできる・最適化のほうで研究されてきた k-best 問題よりも、実装が楽で実践的・現場では、データベース系の技術を中心にした議論・多項式性が自明であることが多く（バックトラック）、アルゴリズム的には研究が少ない末広がり性・バックトラックは、各反復で複数の再帰呼び出しをする  計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル計算時間長・・・計算時間短・頻出パターン列挙では、解の候補がどの項目に含まれるか調べる必要があり、ここが計算上のボトルネック・各反復ごとにデータを縮約して、見るべき領域を減らすと、末広がり性から高速化される実装コンテストで優勝 [宇野・清見・有村] より複雑な構造へ・ある程度単純なパターンが発見できるようになると、次により複雑なものができるか、より複雑な構造で解数を減らせるか、といった点が疑問になる・解数に関しては、飽和集合という、意味的に同値なパターンの代表のみを列挙する問題に対して効率的なアルゴリズムをいくつか提案した（逆探索法による、初めての多項式時間アルゴリズム）（部分集合[宇野・有村]、ワイルドカード付き文字列[有村・宇野]．．．）・極大元に関しても同様に効率的なアルゴリズムを得た（極大クリーク[牧野・宇野]、頻出集合＆双対化[佐藤・宇野]．．．）実用的には十分速いより複雑な構造に、極大・飽和の概念をどう持ち込むかパターン列挙・より複雑なパターンにグラフ構造がある・頻出するグラフを列挙する問題は興味深いが、同型性の判定が大変  同型性が判定できるクラスを考える・大きさがある程度以下のグラフ構造を、小さいものからすべて列挙するフレームワークがほしい標準型＋家系図法・同型性を排除するため、各構造に標準型、という唯一的に定まる構造を定義（木なら子どもの順番を決める）・各構造に（１つ大きさの小さい）親を定めることで、構造全体を連結な木でつなぐ（これを家系図という）・木[中野、中野・宇野、浅井・中野・宇野・有村]、色付き木[中野・宇野]、フロアプラン[中野]、極大2連結3角形グラフ[中野、中野・宇野]、直並列グラフ[中野]、 Linear Extension[中野], distance hereditary graph [上原・宇野・中野] ．．１つあたり定数時間のものが多く、非常に効率が良い標準型＋家系図法・標準型は単純で決まりのある構造を持つので、これを使うとグラフの圧縮ができる（フロアプラン[中野]、極大平面グラフ[中野、中野]、 distance hereditary graph [上原・宇野・中野] ）・平面的な構造に対して、「根」という概念を入れることで、比較的シンプルに標準形が導入できるようになった（しかし、根のつけかたによる重複の回避が少々ボトルネックになっている）根を使わない、単純な標準形は作れるのか？木構造と関連しない構造をいかに列挙するか？複雑なグラフ構造の列挙・より複雑なグラフ構造の列挙にも興味がある。ただし、こんどはパターン列挙ではなく、部分グラフ列挙・探索・生成自体がそれほど自明でない  木などの構造は、それの生成法が（非決定性であれば）簡単にわかる、問題は重複の回避だった・例えば、コーダルグラフ、インターバルグラフ、擬似クリークなど・これらの構造では、どのように生成するか、も難しい隣接性の解明・探索ができるようになるためには、解と解の間にある種の隣接性が成り立たないといけない－全体をスパンすること－隣接する解を多項式時間で見つけられること－近傍サイズが多項式であること、あるいは指数であっても、効率良く隣接解の候補から隣接解を見つけられること・コーダルグラフ・インターバルグラフ、擬似クリーク頂点を取り除くことで他の解が必ず得られる・線形計画の多目的最適解集合枝による隣接性が上記の条件を満たすことがわかる  上の条件を満たす逆探索の利用・隣接性がわかったので、後は逆探索を使って列挙すればよい・面白いことに、いわゆる分枝限定法的な列挙法を使うと、子問題がNP完全になる  逆探索の優位性の、ある種の証明になる・さらに、＋αのアルゴリズムの工夫で計算量を下げる－コーダル部分グラフ： O(1) [清見・宇野] －コーダルスーパーグラフ： O(n3) [清見・宇野・来嶋] －インターバル部分・スーパーグラフ： O(n3) [清見・宇野・来嶋] －擬似クリーク： O(Δ(Δ+log n)) [宇野] －多目的最小全域木：多項式 [岡本・宇野] 厳密アルゴリズムへの適用・計算機パワーの増大は、難しい問題を素朴でない方法で厳密に解こうという研究の流れを生んだ－厳密アルゴリズム（固定パラメータアルゴリズムも）－数理計画へのグレブナー基底の応用・基本的に指数個の構造を探索しなければ最適解を得ることはできないが、探索しなければいけない構造を少なくすることで、計算時間を短縮できる厳密アルゴリズムへの適用・ 2次元幾何問題に対する固定パラメータアルゴリズム [岡本ら] －凸包上にない点が少ない場合、それらの点のつながり方の可能性を絞り込み、列挙して最適解を得る－ TSPの計算量 O(2k k2 n) (n=点数，k=凸包上にない点数) －最小重み三角形分割の計算量 O(6k n5 log n) ・グラフクラスにおけるTutte多項式厳密計算アルゴリズム [岡本ら] －グラフの特徴を活かして候補を絞り込み、列挙により計算－単位区間グラフ O(1.9706m poly) (m=辺数) －３正則グラフ O(1.8494m poly) (m=辺数) ・グレブナー基底計算に用いる「変数順序」の列挙 O(N2 m) [松井] －コーダルグラフに付随する perfect sequence の列挙により実現列挙合宿・この特定領域野期間中、列挙に興味のある人間が集まって、合宿形式、ディスカッション中心の研究会を行ってきた・この３月に７回目を行った４回目あたりから、広く参加者をつのるようにしてきた・非常にアクティビティが高く、毎回、ある研究に対して改良があったり、提議された問題が解決されたりしてきた・このようなコミュニティーが得られたことは、大いなる成果だと考えている・できれば、「列挙学校」という、チュートリアル、あるいはスクールを開きたいと思っている。いかがでしょうか？