組合せとグラフの理論(塩田)第8回 (5) 巡回セールスマン問題
巡回セールスマン問題
巡回セールスマン問題 重み付きハミルトングラフ $G$ において、重み最小のハミルトンサイクル $C$ を求めよ。
※ セールスマンが全ての顧客(頂点)を訪問して会社へ戻る最短ルートを求める問題です。
有名な問題ですが、これは厄介な代物です:
Rem.17
- 残念ながら、巡回セールスマン問題には高速なアルゴリズムは見つかっていません。
- 巨大なグラフでは、膨大な時間を掛けて最適解を求めるより、
- 遺伝的アルゴリズム
- シミュレーテッド・アニーリング法
などを使って「ましな解」を見つけて実行する方が賢いやり方です。