Algorithm Engineering

アルゴリズム工学

　アルゴリズムとは問題を解決するための解き方です．離散最適化問題には解くことが簡単なものから非常に難しいものまで様々な問題が存在します．本研究室では対象となる問題に制約や制限を加えたり，多種多様なアイデアを適用させて多くの離散最適化問題を効率よく解くためのアルゴリズム開発に関する研究をしています．
　本研究室で取り組んでいるアルゴリズム工学研究の一部を紹介します．

１．全域木構築問題

　全域木とは与えられたグラフから，その全ての節点を含む連結木の一つを導出する問題です．全域木問題は，ネットワーク回線網や電力供給網などのインフラ整備や，回路解析などで利用されています．一般的に全域木問題はO(n^2)時間（nは節点数）で解くことが可能ですが，交差グラフと呼ばれる特殊なクラスのグラフに対しては，非常に速い時間で解くことができます．本研究室では様々な交差グラフに対して全域木問題のための効率的なアルゴリズム開発を行っています．

２．要節点導出問題

　要節点とは，その節点がグラフから削除されたとき，そのことによって通信距離がそれまでよりも長くなってしまう節点対が存在するような節点のことをいいます．例えばグラフをコンピュータネットワークとみなしたとき，要節点に対応する端末機器が故障してしまうと，他の端末間の通信に遅延が生じることになります．したがって，要節点に対応する端末の耐久性や性能を向上させることで，ネットワーク全体の安定性を保つことができます．本研究室では様々な交差グラフに対して要節点導出問題のための効率的なアルゴリズム開発を行っています．

３．フィードバック節点集合問題

　グラフからある節点集合を全て削除したとき，元のグラフに１つも閉路が無くなるとします．このとき，削除された節点集合をフィードバック節点集合と呼びます．フィードバック節点集合問題とは，節点数が最小なフィードバック節点集合を導出する問題です．この問題は，大規模電子回路の解析や，プロセスのデッドロック解除システムなどに応用されています．一見簡単そうに見えるフィードバック節点集合問題ですが，実はこの問題はNP完全問題といわれる効率的な解法が存在しない，解くことが非常に困難な問題となっています．本研究室ではクラスを限定した特殊なグラフに対してフィードバック節点集合のための効率的なアルゴリズム開発を行っています．

４．最適スケジューリング問題

　スケジューリングとは処理しなければならないいくつかの作業の処理順序を決定する問題です．スケジューリングはたとえば学校の時間割，工場の人員ローテーション，プロスポーツの試合の組み合わせ，観光旅行計画など非常に身近に存在しています．一般的にスケジューリングは時間や費用を最小化させたり，仕事の条件を満たすように順序を決定する訳ですが，実はこれは最適な解を得るのが非常に困難であることが知られています．本研究室では様々な事例に対して可能な限り現実的な条件を満たした精度のよいスケジューリングアルゴリズムの開発を行っています．