I tried paiza's campaign problem. (Traveling salesman problem)

It seems that you can get meat or amazon gift vouchers by lottery, so this time I tried it with python3. https://paiza.jp/poh/phantom_thief

Problem summary

N treasure x,Given the y coordinate.
Move in a straight line between each coordinate.
0,Start from position 0.
Output the route to get each treasure with the shortest route possible.
It does not have to be the shortest distance.

Value to be entered
N (N is the total number of treasures)
x_1 y_1 (x_1 is the x-coordinate of the first treasure location, y_1 is the y coordinate of the first treasure location)
x_1 y_1 (x_2 is the x-coordinate of the second treasure location, y_2 is the y coordinate of the second treasure location)
・ ・ ・
x_N y_N (x_N is the x-coordinate of the Nth treasure location, y_N is the y coordinate of the Nth treasure location)

・ All values are integers
・ 1 ≤ N ≤ 100
・ 1 ≤ x_i, y_i ≦ 1000000 (1 ≦ i ≦ N) 

Expected output
Please output the route where you can get all the treasure.
At the end, start a new line and do not include extra characters or blank lines.

Example
Input example 1
3
90 100
40 15
30 30

Output example 1
90 100
40 15
30 30

Input example 2
5
1 1
40 120
199 256
10 30
50 5

Output example 2
1 1
40 120
199 256
10 30
50 5

The code I wrote.

import math

def cal_distance(current_point, point):
    """Find the distance between two points"""
    x1 = current_point[0]
    y1 = current_point[1]
    x2 = point[0]
    y2 = point[1]
    distance = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    return distance

def make_distance_list(current_point, position_list):
    """Create a list of distances between two points"""
    distance_list = [(i, cal_distance(current_point, x)) for (i, x) in enumerate(position_list)]
    return distance_list

#Get input value
list_len = int(input())
position_list = []
for i in range(list_len):
    position_list.append(list(map(int,input().split())))

#Move closer to the current position
current_point = [0, 0]
while len(position_list) > 0:
    distance_list = make_distance_list(current_point, position_list)
    sorted_distance_list = [x[0] for x in sorted(distance_list, key=lambda d: d[1])]
    print('{0} {1}'.format(position_list[sorted_distance_list[0]][0],
                             position_list[sorted_distance_list[0]][1]))
    current_point = position_list.pop(sorted_distance_list[0])

Execution result (It is a little difficult to understand the boundary between input and output)

$ python PaizaRouteSearch.py
5
1 2
4 2
10 40
3 2
1 1
1 1
1 2
3 2
4 2
10 40

I wrote it with a simple idea that I should follow the treasure closest to me from my current position. According to what I heard, the shortest route is to solve it with an algorithm called the "traveling salesman problem."

I would like to investigate and review it when I have time.

Postscript: There was an article explaining the problem on paiza's blog. [http://paiza.hatenablog.com/entry/2017/09/26/ [Problem explanation] How to solve the mystery from the phantom thief 813 and get the treasure](http://paiza.hatenablog.com/entry/ 2017/09/26 /% E3% 80% 90% E5% 95% 8F% E9% A1% 8C% E8% A7% A3% E8% AA% AC% E3% 80% 91% E6% 80% AA% E7 % 9B% 97913% E3% 81% 8B% E3% 82% 89% E3% 81% AE% E8% AC% 8E% E3% 82% 92% E8% A7% A3% E3% 81% 84% E3% 81 % A6% E3% 80% 81% E3% 81% 8A% E5% AE% 9D% E3% 82% B2% E3% 83% 83% E3% 83% 88)

It seems that my solution is a greedy algorithm, and I introduced the same solution on paiza's blog. In addition, "simulated annealing", "beam search", "2-opt", "genetic algorithm", It seems that there are various algorithms such as "Christofeed algorithm", "spanning tree", and "slime mold algorithm". Looking at Wikipedia, the formula is ... I have a headache because I have been away from math since I was a student.

About gifts It seems that shipping to the winners has already started, and I have not contacted myself so it seems that I missed it. Sorry.

By the way, the following was wrong. There seems to be a problem and there are several algorithms as a solution.

According to what I heard, the shortest route is to solve with an algorithm called the "traveling salesman problem".

Addendum 2: About gifts About a month and a half later, when I forgot, I received an Amazon gift certificate (1000 yen worth)! I'm glad I didn't expect it! It seems to be a hit unexpectedly, so I would like to participate again next time!

Recommended Posts

I tried paiza's campaign problem. (Traveling salesman problem)
Python: I tried the traveling salesman problem
I tried to implement the traveling salesman problem
About the traveling salesman problem
Simulated Annealing and Traveling Salesman Problem
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 scraping
I tried PyQ
I tried AutoKeras
I tried papermill
Traveling salesman problem practice collection ③ ~ Non-random map edition ~
I tried django-slack
I tried Django
I tried spleeter
I tried cgo
I tried to solve the problem with Python Vol.1
I tried using parameterized
I tried using mimesis
I tried using anytree
I tried competitive programming
I tried running pymc
I tried ARP spoofing
I tried using aiomysql
I tried using Summpy
I tried Python> autopep8
I tried using coturn
I tried using Pipenv
I tried using matplotlib
I tried using "Anvil".
I tried using Hubot
I tried using ESPCN
I tried PyCaret2.0 (pycaret-nightly)
I tried using openpyxl
I tried deep learning
I tried AWS CDK!
I tried using Ipython
I tried to debug.
I tried using PyCaret
I tried using cron
I tried Kivy's mapview
I tried using ngrok
I tried using face_recognition
I tried to paste
I tried using Jupyter
I tried using PyCaret
I tried moving EfficientDet
I tried shell programming
I tried using Heapq
I tried using doctest
I tried Python> decorator
I tried running TensorFlow
I tried Auto Gluon
I tried using folium
I tried using jinja2
I tried AWS Iot
I tried Bayesian optimization!
I tried using folium
I tried using time-window
I tried face recognition of the laughter problem using Keras.