巡回セールスマン問題をpythonで解きます。
01整数計画法を使っても解けますが、今回は動的計画法を使用します。
解説
解説用のpdfを文書を作成したので是非ご覧ください。
pythonコード
DPは配列ではなく、辞書を使用しています。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from collections import defaultdict, namedtuple | |
def tsp(d): | |
"""solve the traveling salesman problem by bitDP | |
Parameters | |
----------- | |
d : list of list or numpy.array | |
distance matrix; d[i][j] is the distance between i and j | |
Returns | |
------- | |
the minimum cost of TSP | |
""" | |
n = len(d) # number of cities | |
# DP[A] = {v: value} | |
# A is the set of visited cities other than v | |
# v is the last visited city | |
# value is the cost | |
DP = defaultdict(dict) | |
for A in range(1, 1 << n): | |
if A & 1 << 0 == 0: # 0 is not included in set A | |
continue | |
# main | |
for v in range(n): | |
if A & (1 << v) == 0: # v is not included in set A | |
if A == (1 << 0): # v is the first visited city | |
DP[A][v] = d[0][v] if d[0][v] > 0 else float('inf') | |
else: | |
# A ^ (1 << u) <=> A - {u} | |
DP[A][v] = float('inf') | |
for u in range(1, n): | |
if d[u][v] > 0 and A & (1 << u) != 0: | |
DP[A][v] = min(DP[A][v], DP[A ^ (1 << u)][u] + d[u][v]) | |
V = 1 << n | |
DP[V][0] = float('inf') | |
for u in range(1, n): | |
if d[u][0] > 0 and A & (1 << u) != 0: | |
DP[V][0] = min(DP[V][0], DP[A ^ (1 <<u)][u] + d[u][0]) | |
return DP[V][0] | |
def tsp_route(d): | |
"""solve the traveling salesman problem by bitDP | |
Parameters | |
----------- | |
d : list of list or numpy.array | |
distance matrix; d[i][j] is the distance between i and j | |
Returns | |
------- | |
the minimum cost of TSP | |
""" | |
n = len(d) # number of cities | |
# DP[A] = {v: (cost, pre)} | |
# A is the set of visited cities other than v | |
# v is the last visited city | |
# cost is the total distance of A | |
# pre is previous visited city | |
DP = defaultdict(dict) | |
Data = namedtuple('Data', 'cost route') | |
for A in range(1, 1 << n): | |
if A & 1 << 0 == 0: # 0 is not included in set A | |
continue | |
# main | |
for v in range(n): | |
if A & (1 << v) == 0: # v is not included in set A | |
if A == (1 << 0): # v is the first visited city | |
cost = d[0][v] if d[0][v] > 0 else float('inf') | |
DP[A][v] = Data(cost=cost, route=[]) | |
else: | |
# A ^ (1 << u) <=> A - {u} | |
DP[A][v] = Data(cost=float('inf'), route=[]) | |
for u in range(1, n): | |
if d[u][v] > 0 and A & (1 << u) != 0: | |
new_cost = DP[A ^ (1 << u)][u].cost + d[u][v] | |
if new_cost < DP[A][v].cost: | |
new_route = DP[A ^ (1 << u)][u].route + [v] | |
DP[A][v] = Data(cost=new_cost, route=new_route) | |
V = 1 << n | |
DP[V][0] = Data(cost=float('inf'), route=None) | |
for u in range(1, n): | |
if d[u][0] > 0 and A & (1 << u) != 0: | |
new_cost = DP[A ^ (1 << u)][u].cost + d[u][0] | |
if new_cost < DP[V][0].cost: | |
new_route = DP[A ^ (1 << u)][u].route + [0] | |
DP[V][0] = Data(cost=new_cost, route=new_route) | |
return DP[V][0] | |
if __name__ == '__main__': | |
data = [ | |
[-1, 3, -1, 4, -1], | |
[-1, -1, 5, -1, -1], | |
[4, -1, -1, 5, -1], | |
[-1, -1, -1, -1, 3], | |
[7, 6, -1, -1, -1] | |
] | |
res = tsp(data) | |
print(res) | |
res = tsp_route(data) | |
print(res) |
次回からはcpythonを使ってこのコードを高速化していこうと思います。