#12. Traveling Salesman Problem

  • Dynamic Programming problem
1
2
Time O(N^2 * 2^N)
Space O(N * 2^N)

Python Traveling Salesman Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
# Problem: Travelling salesman problem
# Given a complete weighted graph, find a hamiltonian cycle of the minimum cost
#
# Algorithm:
# Dynamic programming, O(N^2 * 2^N) time, O(N * 2^N) space
import math
def tsp(matrix, start):
"""
:type matrix: List[List[int]], adjacency matrix
:type start: int, staring node
:rtype: int
"""
if not matrix:
return 0
n = len(matrix)
# dp[n][2^n], represents the minimum cost from s to i with x ndoes visited, where x is the bit set in the state.
dp = [[math.inf for j in range(1 << n)] for i in range(n)]
for i in range(n):
if i != start:
dp[i][(1 << start | 1 << i)] = matrix[start][i]
for r in range(3, n + 1):
# r means how many nodes have been visited
for state in combinations(r, n):
if is_set(start, state):
for adj in range(n):
if adj != start and is_set(adj, state):
prev_state = state ^ (1 << adj)
min_dist = math.inf
for prev in range(n):
if prev != start and prev != adj and is_set(prev, state):
dist = dp[prev][prev_state] + matrix[prev][adj]
min_dist = min(min_dist, dist)
dp[adj][state] = min_dist
# Find min cost from the last state to back to start
res = math.inf
end_state = (1 << n) - 1
for i in range(n):
if i != start:
dist = dp[i][end_state] + matrix[i][start]
res = min(res, dist)
get_path(matrix, dp, start)
return res
def get_path(matrix, dp, start):
"""
:type matrix: List[List[int]], adjacency matrix
:type dp: List[List[int]]
:type start: int
:rtype: tuple(int)
"""
n = len(matrix)
last_index = start
state = (1 << n) - 1
path = [0 for i in range(n + 1)]
for i in range(n - 1, 0, -1):
candidate = -1
min_dist = math.inf
for j in range(n):
if j != start and is_set(j, state):
dist = dp[j][state] + matrix[j][last_index]
if dist < min_dist:
min_dist = dist
candidate = j
path.append(j)
state = state ^ (1 << candidate)
last_index = candidate
path[0] = path[n] = start
return path[::-1]
# Find all combinations of n bits with r set to 1s
# example: combinations(3, 4) => [0111, 1011, 1101, 1110]
def combinations(r, n):
"""
:type r: int
:type n: int
:rtype: List[int]
"""
res = set()
backtrack(0, 0, r, n, res)
return res
def backtrack(curr, pos, r, n, res):
"""
:type curr: int, curr value
:type pos: int, current index
:type r: int
:type n: int
:type res: List[int]
"""
if r == 0:
res.add(curr)
return
for i in range(pos, n):
curr |= (1 << i)
backtrack(curr, i + 1, r - 1, n, res)
curr &= ~(1 << i)
def is_set(i, bits):
return bits & (1 << i) == 1

Comments

01/03/2020