読者です 読者をやめる 読者になる 読者になる

巡回セールスマン問題

アルゴリズム 競技プログラミング

巡回セールスマン問題を,動的計画法,山登り法,焼きなまし法で解く

厳密解

動的計画法(bitDP)

 dp[p_x][C]を都市 p_0 を出発し,都市集合Cをすべて回った後で都市 p_x に行くときの最短経路長とする.
このとき,以下の式を立てることができる(d[x][y]は都市xと都市yの距離とする)


1. dp [ p_x ] [ \emptyset ] = d [ p_0 ] [ p_x ] \\
2. dp[p_x][C] = \min_{p_y \in C} dp[p_y][C \backslash p_y ] + d [ p_y ] [ p_x ] \\

  1. 都市 p_0 を出発し,都市 p_x に行くときの最短経路長は d[p_0][p_x] となる
    つまり, p_0 ->  p_x の距離は都市 p_0 と都市 p_x の距離
  2. 都市 p_0 を出発し,Cをすべて回ったあとで都市 p_xに行くときの最短経路長は,
    都市 p_0 を出発し,都市 p_y 以外のCをすべて回ったあとで都市 p_y へ行き,
    その後都市 p_y から都市 p_x へ行くときの最短経路長となる
    つまり, p_0 -> C ->  p_x の距離は p_0 ->  C \backslash p_y ->  p_y ->  p_x の距離

都市集合Cはbitで表現する.
求めたい値は,都市 p_0 を出発し,都市 p_0 以外をすべて回った後で,都市 p_0 に行く場合の最短経路長であるため, dp[0][((1 << V) - 1) ^ 1]となる(Vは都市数)
例えばVが15の場合以下のようになる

  • 1 << 15は"1000000000000000"
  • ((1 << 15) - 1)は"111111111111111"
  • (((1 << 15) - 1) ^ 1)は"111111111111110"

計算量はO(2N・N2)
* AOJ - 巡回セールスマン問題

近似解

近傍について

そのうち書く

山登り法

そのうち書く

焼きなまし法

そのうち書く

参考