What was the [Traveling Salesman Problem](https://ja.wikipedia.org/wiki/Traveling Salesman Problem)? It's fluffy, so to understand it, first simply brute force the solution. I tried it. only.
Solving the traveling salesman problem with various approximate solutions (1)
from itertools import permutations as IT_perm
total_cost = lambda costs : lambda seq : sum(
costs[ seq[i - 1] ][ e ]
for i, e in enumerate( seq )
)
head_fixed_permutations = lambda nodes : (
nodes[ 0:1 ] + list( tail )
for tail in IT_perm( nodes[ 1: ] )
)
costs = [
[0, 6, 5, 5]
, [6, 0, 7, 4]
, [5, 7, 0, 3]
, [5, 4, 3, 0]
]
nodes = [0, 1, 2, 3]
print(
min(
head_fixed_permutations( nodes )
, key = total_cost( costs )
)
)
#result:[0, 1, 3, 2]
In the list costs, it is assumed that the cost of moving from node a to node b is given by cost [a] [b]. nodes is a list of the nodes, the starting point is fixed to nodes [0]: (value is 0).
The way I thought about it was In the permutation of nodes with fixed heads, The value applied to the function that calculates the total cost, The smallest one Output about it.
I see, this is what it is. It was surprisingly simple.
Recommended Posts