class

NgLib::TSPGraph(T)

Inherits Reference < Object

巡回セールスマン問題を解きます。

内部では BitDP を用いているため、頂点数が大きいグラフには対応できません。

通常の巡回セールスマン問題を解きたい場合は、 #shortest_route(should_back : Bool = true) を利用してください。

始点を指定したいという特殊な場合は、 #shortest_route(start : Int, should_back : Bool = true) を利用してください。

オリジナルの巡回セールスマン問題は各頂点に一度しか訪れることができません。同じ頂点に複数回訪れられる場合は、NgLib::FloydWarshall などで、全点対最短経路長を求め、それを隣接行列として渡してください。

計算量は $O(N^2 2^N)$ です。

Constructors

new(matrix : Array(Array(T | Nil) | Array(T)))

隣接行列に従ってグラフを作ります。

nil は辺が存在しないことを表します。無限大の重みを持つ辺と捉えても良いです。

mat = [[0, 3, 1], [-2, 0, 4], [nil, nil, 0]]
NgLib::TSPGraph(Int32).new(mat)

Source

new(mat : Array(Array(T | Nil)))

隣接行列に従ってグラフを作ります。

nil は辺が存在しないことを表します。無限大の重みを持つ辺と捉えても良いです。

mat = [[0, 3, 1], [-2, 0, 4], [nil, nil, 0]]
NgLib::TSPGraph(Int32).new(mat)

Source

new(n : Int)

$n$ 頂点 $0$ 辺のグラフを作ります。

n = 10
NgLib::TSPGraph(Int64).new(n)

Source

Instance methods

add_edge(u : Int, v : Int, w : T, directed : Bool = true)

重みが $w$ の辺 $(u, v)$ を追加します。

directed が true である場合、有向辺として追加します。

n, m = read_line.split.map &.to_i
graph = NgLib::TSPGraph.new(n)
m.times do
  u, v, w = read_line.split.map &.to_i64
  u -= 1; v -= 1 # 0-index
  graph.add_edge(u, v, w, directed: true)
end

Source

mat

Source

shortest_route(should_back : Bool = true)

dp[S][i] := 今まで訪問した頂点の集合が S で、最後に訪れた頂点が i であるときの最小経路長 を返します。

should_back が true なら、始点の頂点に戻ってこない場合の最小経路長を計算します。また、任意の始点に対しての答えを求める点に注意してください。

should_back が false なら通常の巡回セールスマン問題の答えです。始点が頂点 $0$ であることに注意してください。つまり、dp[(1 << n) - 1][0] が答えです。

どのような順でも到達できない場合は nil が格納されます。

graph = TSPGraph(Int64).new(n)
dist = graph.shortest_route
dist[(1 << n) - 1][0] # => ans
dist.last.first       # => ans

Source

shortest_route(start : Int, should_back : Bool = true)

dp[S][i] := 今まで訪問した頂点の集合が S で、最後に訪れた頂点が i であるときの最小経路長 を返します。

should_back が true なら、始点の頂点に戻ってこない場合の最小経路長を計算します。また、始点が start であることに注意してください。

should_back が false なら通常の巡回セールスマン問題の答えです。始点が頂点 start であることに注意してください。つまり、dp[(1 << n) - 1][start] が答えです。

どのような順でも到達できない場合は nil が格納されます。

graph = TSPGraph(Int64).new(n)
dist = graph.shortest_route(start: 2)
dist[(1 << n) - 1][2]

Source

size

Source