巡回セールスマン問題におけるLin-Kernighan法の実装2008/02/04 瀧川啓介 目次 巡回セールスマン問題とは何か 研究の背景 目標 アルゴリズムの概要 構造体に関して 実験結果 考察、まとめ リンク 参考文献 巡回セールスマン問題とは何か 英語ではTraveling Salesman Problemと言い、頭文字を取ってTSPとも呼ぶ。 多くの市と各市間の移動コストが与えられたとき、全ての市を一度だけ回って戻ってくるルートのうちコスト最小のものを求める（セールスマンが所定の数の都市を1回だけ巡回する場合の最短経路を求める）問題のことを指す。 [ index ] 研究の背景 よく知られるNP困難問題で、30年以上前から研究されてきた内容 単純に最適解を求めるには要素数n個のTSPグラフの場合、n!通りの場合について考えれば良いが、当然ながら膨大な計算量となる。 しかし、馴染みのないコマンドを利用するよりも、 近年においてはTSP自
