イントロダクション

離散的構造（組合せ的構造）を持つ問題は，オペレーションズ・リサーチ，コンピュータサイエンス，システム工学，経営学，社会科学， 金融工学，経済学などの広範な領域において，さまざまな形で出現します．いまや， 大量なデータの処理や複雑な問題を解決する必要のある現場では，計算機の利用は欠かすことができません． 作業の処理速度の向上の為には計算機のハードウエアの高速化だけではなく， それ以上に使用するソフトウエアの高性能化が大切になります． どのような問題を解くソフトウエアも計算機上では基本操作の系列による離散的な構造の処理に帰着されますが， 実は離散構造を有する問題には解決をするために多大な時間を要するものが身近に潜んでいます． これらの問題の中には，計算の複雑さの理論においてNP-困難と呼ばれる解決の困難な問題がある一方， 数学的に洗練されたアルゴリズムによれば華麗に解決を見ることのできる問題も含まれています． 従ってアルゴリズムの理論的研究があらゆるソフトウエア技術の基盤になっていると言って過言ではありません．

一般に，離散的な構造を有する対象から与えられた基準に対し最適な答えを求める問題は離散最適化問題と呼ばれます． この問題の範疇にはデータの整列などの基本的な手続きの設計問題から生産計画，配送経路，乗員スケジューリング，VLSI配線， 通信ネットワークの信頼性，施設配置，資源配分，投資問題などの数多くの応用問題まで含まれます． 離散最適化問題では最適解の候補となる解の数がしばしは有限個に限定されますが，単純な列挙による方法では， 高性能の計算機を用いても問題の規模が少し大きくなると現実的な時間で最適なものを求めることは不可能になります． そこで，これらの問題を効率よく解くためには，離散数学の立場から，これら問題の数学的性質を理解し， 問題を解く計算の複雑さ(NP-困難性等)を調べ，問題にあったアルゴリズムを設計することが重要です．

例えば，地図上での２地点間の経路のうち長さが最短のものを選ぶ問題は離散最適化問題の１つの例ですが， もし，２地点間の経路をすべて列挙して最短の経路を求めたとすると，経路の総数は地図の複雑さが増すにつれ爆発的に多くなり， 単純な列挙では計算機を使っても最適な答えを求めることができなくなります．しかし，一方で，この最短路問題のもつ数学的性質を利用すれば， （地図の複雑さに比例する程度の計算ステップ数しか要しない）極めて効率のよいアルゴリズムを設計することができます． では問題の設定を少し変えて，地図上でn地点が与えられたとき，これらn地点を最短で一周する経路を求める問題にしてみます． するとこれはNP-困難な問題と呼ばれ，２地点間の最短経路とは一線を画す解決困難な問題になります．この場合， 実用的な時間で厳密解を得るアルゴリズム，あるいは，近似解を高速に求めるアルゴリズムを設計する必要があります．

我々の研究室では，特にグラフ・ネットワーク問題を中心にしてさまざまな離散最適化問題に対して 効率のよいアルゴリズムを開発することに従事しています．以下にこれまでに研究室のスタッフが行ってきた研究テーマ・成果を挙げておきます． 離散的な構造を持っている問題であれば新しいテーマにも取り組んでいくつもりです．