Python: I tried the traveling salesman problem

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

Python: I tried the traveling salesman problem
I tried to implement the traveling salesman problem
I tried to solve the problem with Python Vol.1
About the Ordered Traveling Salesman Problem
I tried "Implementing a genetic algorithm (GA) in python to solve the traveling salesman problem (TSP)"
Solve the traveling salesman problem with OR-Tools
I tried the Python Tornado Testing Framework
I tried Python> autopep8
I tried Python> decorator
I tried "smoothing" the image with Python + OpenCV
[Python] I tried substituting the function name for the function name
vprof --I tried using the profiler for Python
I tried "differentiating" the image with Python + OpenCV
I tried simulating the "birthday paradox" in Python
I tried the least squares method in Python
I tried python programming for the first time.
I tried using the Datetime module by Python
I tried fp-growth with python
I tried scraping with Python
I tried to graph the packages installed in Python
I tried Python on Mac for the first time.
I tried to touch the CSV file with Python
I tried to solve the soma cube with python
I tried python on heroku for the first time
I tried the changefinder library!
I tried Python C extension
[Python] I tried using OpenPose
I tried gRPC with Python
I tried scraping with python
I downloaded the python source
I tried hitting the API with echonest's python client
I tried to summarize the string operations of Python
The 15th offline real-time I tried to solve the problem of how to write with python
I tried "gamma correction" of the image with Python + OpenCV
I tried using the Python library from Ruby with PyCall
I tried face recognition of the laughter problem using Keras.
I tried face recognition from the video (OpenCV: python version)
I tried programming the chi-square test in Python and Java.
[Python] I tried to visualize the follow relationship of Twitter
I tried to implement the mail sending function in Python
Miscellaneous notes that I tried using python for the matter
[Python] I tried collecting data using the API of wikipedia
I tried to enumerate the differences between java and python
I tried changing the python script from 2.7.11 to 3.6.0 on windows10
I tried to divide the file into folders with Python
I tried the TensorFlow tutorial 1st
I tried to touch Python (installation)
Simulated Annealing and Traveling Salesman Problem
I tried using Thonny (Python / IDE)
I tried Grumpy (Go running Python).
I liked the tweet with python. ..
I wrote the queue in Python
I tried the Naruro novel API
I tried running prolog with python 3.8.2.
I tried Line notification in Python
I tried SMTP communication with Python
I tried to move the ball
I tried using the checkio API
[Python] I tried using YOLO v3
I wrote the stack in Python
I tried to estimate the interval.