🐸

[鉄則B23] Traveling Salesman Problem

2024/04/12に公開

Ruby

配送業で活用できそうな巡回セールスマン問題。

問題を要約する

いくつかの家を効率よく訪問したときの一周の距離は？

元の問題では時間を求められているが同じことなので、イメージしやすい距離にする。

問題を理解する

例1

1 から 4 の家を効率よく訪問したときの一周の距離は？

	1	2
1	1	2
2	4	3

答えは 4 で 1 2 3 4 1 と回ればよい。斜めに移動しなければよさそう。

例2

1 から 7 の家を効率よく訪問したときの一周の距離は？

	1	2	4	5	6	7
1	4		3
2						5
3		2		6
4
5		1			7

答えは 18.87 で 1 2 4 3 5 6 7 1 と辿ればよい。たしかに目視でも合ってそう。

どこから開始すべきか？

どこから開始するかは重要ではない。どちらの答えも 1 から 1 に戻ってきているので営業所に相当する 1 から出発しないといけないのかと当初勘違いしていた。一周するのでどこから開始しても最短距離は変わらない。

全探索 (TLE)

すべてのルートを列挙する
ルート毎に一周の距離を求める
最短距離が答え

N = gets.to_i                                        # => 7
XY = N.times.collect { gets.split.collect(&:to_i) }  # => [[2, 5], [2, 3], [4, 1], [1, 1], [7, 2], [5, 3], [6, 5]]
d = -> (x1, y1, x2, y2) { Math.sqrt((x2 - x1)**2 + (y2 - y1)**2) }
min = N.times.to_a.permutation.collect { |routes|
  routes = [*routes, routes.first]
  routes.each_cons(2).sum { |a, b| d[*XY[a], *XY[b]] }
}.min
p min                                                # => 18.870481592667748

とするのは、いくつか TLE になる。

解説の模範解答 (AC)

入力例1を受けとるとする。

760 ms

N = gets.to_i                                        # => 4
XY = N.times.collect { gets.split.collect(&:to_i) }  # => [[0, 0], [0, 1], [1, 0], [1, 1]]
d = -> (x1, y1, x2, y2) { Math.sqrt((x2 - x1)**2 + (y2 - y1)**2) }
W = N                           # 横幅は訪問先の数だけだが、
H = 1 << N                      # 縦幅は集合なので 2^N になる(4なら16)
dp = Array.new(H) { Array.new(W, Float::INFINITY) }  # => [[Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity], [Infinity, Infinity, Infinity, Infinity]]
dp[0][0] = 0
H.times do |y|                         # y = 訪問済みの集合(番号ではない)
  W.times do |x|                       # x = 現在位置番号
    if dp[y][x].infinite?              # まだ訪問していないので
      next                             # スキップする (スキップしなくても結果は同じになる)
    end
    W.times do |to|                    # 現在位置番号(x)から次の場所(to)に移動する
      if y.anybits?(1 << to)           # 訪問済みの集合(y)に次の場所(to)が含まれているなら
        next                           # 訪問済みなのでスキップする
      end
      v = y | (1 << to)               # 次の場所(to)を訪問済みのもの
      dp[v][to] = [
        dp[v][to],                    # 次の場所(to)への最小移動距離と、
        dp[y][x] + d[*XY[x], *XY[to]], # 現在地 + 次の場所への距離の、
      ].min                            # 近い方を取る
    end
  end
end
p dp[H.pred].first                                   # => 4.0

	0	1	2	3
0000	0
0001	0.0
0010		1.0
0011	2.0	1.0
0100			1.0
0101	2.0		1.0
0110		2.41	2.41
0111	3.41	2.41	2.41
1000				1.41
1001	2.83			1.41
1010		2.41		2.0
1011	3.41	2.41		2.0
1100			2.41	2.0
1101	3.41		2.41	2.0
1110		3.0	3.0	3.41
1111	4.0	3.0	3.0	3.41

dp[訪問済みの集合][現在位置] == 現時点の最小移動距離
縦は集合を表すために 16 行ある
最適値は最後の左端

これはむずい。