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 ]