ネットワークフロー問題に対する高速かつ実用的アルゴリズムに関する研究

本研究では,古典的な組合せ最適化問題であるネットワークフロー問題に関連する様々な離散構造をもつ問題を考察した。当初の計画では、ネットワークフロー問題自体のアルゴリズム開発を目的としたが、結果としては、本研究では.、フロー問題に関連する施設配置問題、モノポリー問題、マッチング問題、ならびに、そのとき得られた離散的な知見を利用した、人工知能分野の推論問題等に大きな成果を得た。本研究の最終年度どして最も大きな成果は、仮説列挙問題に対する多項式時間アルゴリズムの開発である。この仮説列挙問題は、知識ベースとしてのホーン理論と観測事象が与えられたとき、知識ベースを用いてその事象を説明する仮説を列挙するという問題である。この問題は、人工知能分野の古典的な推論問題であり、古くから盛んに研究されてきたが、現在に至るまで効率的に(多項式時間で)解けるかどうか未解決のまま残されていた。1990年にSelmanとLevesqueによって否定的に(すなわち、対応する決定問題がNP困難であると)予想されるほど、多項式時間アルゴリズムを開発することは困難とされていた。本年度に、ウイーン工科大学のEiter教授との共同研究でこの否定的な予想を覆し、初めての多項式時間アルゴリズムを開発した。この成果は、他の推論問題にも広く適用可能であり、人工知能における知識表現・推論分野の進歩に大きく貢献したとして高く評価されている。このことは、アメリカ人工知能学会(American Association for Artificial Intelligence)が主催する会議AAAI National Conference on Artificial Intelligence 2002(AAAI-02)からOutstanding Paper Awardを授与されたことからも分かる。

本研究では,古典的な組合せ最適化問題であるネットワークフロー問題に関連する様々な離散構造をもつ問題を考察した。当初の計画では、ネットワークフロー問題自体のアルゴリズム開発を目的としたが、結果としては、本研究では.、フロー問題に関連する施設配置問題、モノポリー問題、マッチング問題、ならびに、そのとき得られた離散的な知見を利用した、人工知能分野の推論問題等に大きな成果を得た。本研究の最終年度どして最も大きな成果は、仮説列挙問題に対する多項式時間アルゴリズムの開発である。この仮説列挙問題は、知識ベースとしてのホーン理論と観測事象が与えられたとき、知識ベースを用いてその事象を説明する仮説を列挙するという問題である。この問題は、人工知能分野の古典的な推論問題であり、古くから盛んに研究されてきたが、現在に至るまで効率的に(多項式時間で)解けるかどうか未解決のまま残されていた。1990年にSelmanとLevesqueによって否定的に(すなわち、対応する決定問題がNP困難であると)予想されるほど、多項式時間アルゴリズムを開発することは困難とされていた。本年度に、ウイーン工科大学のEiter教授との共同研究でこの否定的な予想を覆し、初めての多項式時間アルゴリズムを開発した。この成果は、他の推論問題にも広く適用可能であり、人工知能における知識表現・推論分野の進歩に大きく貢献したとして高く評価されている。このことは、アメリカ人工知能学会(American Association for Artificial Intelligence)が主催する会議AAAI National Conference on Artificial Intelligence 2002(AAAI-02)からOutstanding Paper Awardを授与されたことからも分かる。