サブロウ丸

Sabrou-mal サブロウ丸

主にプログラミングと数学

bitDPで巡回セールスマン問題を解く; Python

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

01整数計画法を使っても解けますが、今回は動的計画法を使用します。

解説

解説用のpdfを文書を作成したので是非ご覧ください。

drive.google.com

pythonコード

DPは配列ではなく、辞書を使用しています。

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)
view raw tsp.py hosted with ❤ by GitHub

次回からはcpythonを使ってこのコードを高速化していこうと思います。