列挙アルゴリズムの高速化手法の一般化とその適用

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

今年度の研究は、平面三角分割と極大マッチングとクリークの列挙アルゴリズムである。どのアルゴリズムも、既存のアルゴリズムに、これまでにはない技法を開発したことにより、計算時間の大幅な短縮に成功している。最初の成果は平面3角分割の仕方を列挙するアルゴリズムの改良である。この問題に対するアルゴリズムはすでに提案されているが、出力の重複を避ける部分が難しいために計算が複雑になり、多くの計算時間を要する結果になっている。今回の研究では、このような平面のグラフ構造の列挙時に出力の重複を避けるための、一般的な手法を開発し、平面3角分割列挙のアルゴリズムに適用した。この結果、計算量を従来のものよりも下げることに成功した。次の成果は、極大2部マッチングを列挙するアルゴリズムの開発である。この問題は既存の、極大クリークを列挙するアルゴリズムを用いると解けるが、計算時間が大きくなる。今回の研究では、極大マッチングに特化したアルゴリズムを開発し、また、このようなタイプの列挙アルゴリズムの反復数を減少する方法を開発した。その結果、既存のアルゴリズムよりも大幅に計算量を減少させることができた。最後の成果は、極大クリークを列挙するアルゴリズムである。この問題に対しては、すでにアルゴリズムが提案されているが、問題が大きくなると非常に時間がかかるようになる。今回の研究では、このような極大なクリークや2部クリークなどの列挙アルゴリズムに対する、大規模かつ疎な問題での高速化手法を考案した。この結果、既存のアルゴリズムでは、何ヶ月もかかるような計算が10分ほどでできるようになった。また、この研究の副産物として、極大クリーク、および準クリークを1つ求める高速アルゴリズムが開発された。これも、実際に使われているアルゴリズムよりも大幅に高速であり、現実問題への適用を進めている。