組合せ最適化とアルゴリズム

組合せ最適化は，いま最も活発に研究がなされている応用数学の分野の1つである。アルゴリズム論，組合せ論，計算量の理論，データ構造，線形計画など種々の分野のテクニックを駆使して問題解決を行う。本書では，組合せ最適化問題に対するアルゴリズムの本質，特に実際問題を解くための基礎となる理論を学ぶことを目的とする。 本書の特徴は以下のようである。 ・ 具体的な例題の積み重ねから一般論を導くこと。 ・ アルゴリズムの動機づけを与えること。 ・ 問題の構造に対する洞察に主眼を置くこと。 ・ アルゴリズムの実務的な評価について考えること。 ・ インターネットを通じて，スライド，練習問題，プログラム，または関連するホームページへのリンクなどを供給すること。 Part1　グラフ・アルゴリズム・計算量 1.1　グラフの定義と最大安定集合問題 1.2　Euler閉路・Eulerの定理・アルゴリズム 1.3　ハノイの塔ー無向グラフと有向グラフー 1.4　最小木問題 1.5　巡回セールスマン問題ーPとNP- Part2　線形計画 2.1　線形問題と図式解法 2.2　辞書と単体法 2.3　双対問題 2.4　主問題と双対問題（一般論） Part3　ネットワーク理論 3.1　最短路問題 3.2　最大流問題 3.3　最少費用問題 Part4　組合せ最適化 4.1　分枝限定法 4.2　多面体的アプローチ 4.3　Lagrange緩和 4.4　動的計画 4.5　主・双対法 4.6　実験的解析 参考文献 索引