class NgLib::TSPGraph(T)

Overview

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

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

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

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

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

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

Defined in:

nglib/graph/tsp.cr

Constructors

Instance Method Summary

Constructor Detail

def self.new(matrix : Array(Array(T | Nil) | Array(T))) #

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

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

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

[View source]
def self.new(mat : Array(Array(T | Nil))) #

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

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

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

[View source]
def self.new(n : Int) #

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

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

[View source]

Instance Method Detail

def 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

[View source]
def mat : Array(Array(T | Nil)) #

[View source]
def 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

[View source]
def 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]

[View source]
def size : Int32 #

[View source]