J'ai essayé le problème de campagne de Paiza. (Problème de vendeur circulaire)

Il semble que vous puissiez obtenir un chèque-cadeau de viande ou d'Amazon par loterie, alors cette fois je l'ai essayé avec python3. https://paiza.jp/poh/phantom_thief

Résumé du problème

N trésor x,Étant donné la coordonnée y.
Déplacez-vous en ligne droite entre chaque coordonnée.
0,Commencez à partir de la position 0.
Sortez l'itinéraire pour obtenir chaque trésor avec l'itinéraire le plus court possible.
Il n'est pas nécessaire que ce soit la distance la plus courte.

Valeur à saisir
N (N est le nombre total de trésors)
x_1 y_1 (x_1 est la coordonnée x de l'emplacement du premier trésor, y_1 est la coordonnée y de l'emplacement du premier trésor)
x_1 y_1 (x_2 est la coordonnée x de l'emplacement du deuxième trésor, y_2 est la coordonnée y de l'emplacement du deuxième trésor)
・ ・ ・
x_N y_N (x_N est la coordonnée x du Nième emplacement du trésor, y_N est la coordonnée y du Nième emplacement du trésor)

・ Toutes les valeurs sont des entiers
・ 1 ≤ N ≤ 100
・ 1 ≤ x_i, y_i ≦ 1000000 (1 ≦ i ≦ N) 

Production attendue
Veuillez indiquer l'itinéraire où vous pouvez obtenir tous les trésors.
À la fin, commencez une nouvelle ligne et n'incluez pas de caractères supplémentaires ou de lignes vides.

Exemple
Exemple d'entrée 1
3
90 100
40 15
30 30

Exemple de sortie 1
90 100
40 15
30 30

Exemple d'entrée 2
5
1 1
40 120
199 256
10 30
50 5

Exemple de sortie 2
1 1
40 120
199 256
10 30
50 5

Le code que j'ai écrit.

import math

def cal_distance(current_point, point):
    """Trouvez la distance entre deux 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):
    """Créer une liste de distances entre deux points"""
    distance_list = [(i, cal_distance(current_point, x)) for (i, x) in enumerate(position_list)]
    return distance_list

#Obtenir la valeur d'entrée
list_len = int(input())
position_list = []
for i in range(list_len):
    position_list.append(list(map(int,input().split())))

#Rapprochez-vous de la position actuelle
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])

Résultat d'exécution (Il est un peu difficile de comprendre la frontière entre l'entrée et la sortie)

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

Je l'ai écrit avec une idée simple que je devrais suivre le trésor le plus proche de moi depuis ma position actuelle. D'après ce que j'ai entendu, le chemin le plus court est de résoudre avec un algorithme appelé "Circular Salesman Problem".

J'aimerais enquêter et l'examiner quand j'en ai le temps.

Post-scriptum: Il y avait un article expliquant le problème sur le blog de paiza. [http://paiza.hatenablog.com/entry/2017/09/26/ [Explication du problème] Comment résoudre le mystère du voleur fantôme 813 et obtenir le trésor](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)

Il semble que ma solution soit une méthode gourmande, et j'ai présenté la même solution sur le blog de paiza. En outre, "méthode de gravure", "recherche de faisceau", "2-opt", "algorithme génétique", Il semble qu'il y ait différentes choses telles que "l'algorithme de Christofeed", "Whole area tree", "Muscle algorithm". En regardant Wikipedia, la formule est ... J'ai mal à la tête parce que je suis loin des mathématiques depuis que je suis étudiant.

À propos des cadeaux Il semble que l'expédition aux gagnants a déjà commencé, et je ne me suis pas contacté donc il semble que je l'ai manqué. Pardon.

Au fait, ce qui suit était faux. Il semble y avoir un problème et il existe plusieurs algorithmes comme solution.

D'après l'histoire que j'ai entendue, le chemin le plus court semble être de résoudre avec un algorithme appelé "Circular Salesman Problem".

Addendum 2: À propos des cadeaux Environ un mois et demi plus tard, quand j'ai oublié, j'ai reçu un chèque-cadeau Amazon (d'une valeur de 1000 yens)! Je suis content de ne pas m'y attendre! Cela semble être un succès inattendu, alors j'aimerais participer à nouveau la prochaine fois!

Recommended Posts

J'ai essayé le problème de campagne de Paiza. (Problème de vendeur circulaire)
Python: j'ai essayé le problème du voyageur de commerce
J'ai essayé de mettre en œuvre le problème du voyageur de commerce
À propos du problème du voyageur de commerce
Problème de méthode de gravure et de voyageur de commerce
À propos du problème du vendeur de patrouille commandé
J'ai essayé "Implémentation d'un algorithme génétique (GA) en python pour résoudre le problème du voyageur de commerce (TSP)"
Résolvez le problème du voyageur de commerce avec OR-Tools
J'ai essayé de gratter
J'ai essayé PyQ
J'ai essayé AutoKeras
J'ai essayé le moulin à papier
J'ai essayé django-slack
J'ai essayé Django
J'ai essayé spleeter
J'ai essayé cgo
J'ai essayé de résoudre le problème avec Python Vol.1
J'ai essayé d'utiliser paramétré
J'ai essayé d'utiliser la mimesis
J'ai essayé d'utiliser anytree
J'ai essayé d'exécuter pymc
J'ai essayé le spoofing ARP
J'ai essayé d'utiliser aiomysql
J'ai essayé d'utiliser Summpy
J'ai essayé Python> autopep8
J'ai essayé d'utiliser coturn
J'ai essayé d'utiliser Pipenv
J'ai essayé d'utiliser matplotlib
J'ai essayé d'utiliser "Anvil".
J'ai essayé d'utiliser Hubot
J'ai essayé d'utiliser ESPCN
J'ai essayé PyCaret2.0 (pycaret-nightly)
J'ai essayé d'utiliser openpyxl
J'ai essayé le deep learning
J'ai essayé AWS CDK!
J'ai essayé d'utiliser Ipython
J'ai essayé de déboguer.
J'ai essayé d'utiliser PyCaret
J'ai essayé d'utiliser cron
J'ai essayé la mapview de Kivy
J'ai essayé d'utiliser ngrok
J'ai essayé d'utiliser face_recognition
J'ai essayé d'utiliser Jupyter
J'ai essayé de déplacer EfficientDet
J'ai essayé la programmation shell
J'ai essayé d'utiliser doctest
J'ai essayé Python> décorateur
J'ai essayé d'exécuter TensorFlow
J'ai essayé Auto Gluon
J'ai essayé d'utiliser du folium
J'ai essayé d'utiliser jinja2
J'ai essayé AWS Iot
J'ai essayé l'optimisation bayésienne!
J'ai essayé d'utiliser du folium
J'ai essayé d'utiliser la fenêtre de temps
J'ai essayé la reconnaissance faciale du problème du rire en utilisant Keras.