組合せとグラフの理論（塩田）第8回 (5)　巡回セールスマン問題
前へ / 戻る / 次へ

巡回セールスマン問題

巡回セールスマン問題　重み付きハミルトングラフ $G$ において、重み最小のハミルトンサイクル $C$ を求めよ。
※　セールスマンが全ての顧客（頂点）を訪問して会社へ戻る最短ルートを求める問題です。
Ex.16　グラフが小さければしらみつぶしで答が出せます：
$G=$
ではハミルトンサイクルは4つあって、その重みは
$C_1=$ $C_2=$
  重み 15  重み 13
$C_3=$ $C_4=$
  重み 14  重み 15

となります。この場合 $C_2$ が最短です。
　有名な問題ですが、これは厄介な代物です：
Rem.17　
  • 残念ながら、巡回セールスマン問題には高速なアルゴリズムは見つかっていません。
  • 巨大なグラフでは、膨大な時間を掛けて最適解を求めるより、
    • 遺伝的アルゴリズム
    • シミュレーテッド・アニーリング法
    などを使って「ましな解」を見つけて実行する方が賢いやり方です。

前へ / 戻る / 次へ