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