組合せ最適化

組合せ的な離散構造に由来する制約条件によって規定された実行可能解の中から, 目的関数を最小(または最大)にするものを見出す問題を組合せ最適化問題という. 代表的な組合せ最適化問題としては, 各辺に長さが与えられたグラフにおいて, ２点間の最短経路を求める最短路問題や各頂点を１度ずつ通る最短巡回路を求める巡回セールスマン問題がある．最短路問題が動的計画法によって効率的に解けるのに対し, 巡回セールスマン問題はNP困難であり, 効率的に解くことは不可能であろうと考えられている．このような難しい組合せ最適化問題に対しても, 各種の近似解法や分枝限定法を含めて, 現実的な時間内に, 実際的な問題を解決するための研究がなされている．