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