Es scheint, dass Sie Fleisch oder Amazon Geschenkgutschein per Lotterie bekommen können, also habe ich es dieses Mal mit Python3 versucht. https://paiza.jp/poh/phantom_thief
Problemzusammenfassung
N Schatz x,Die y-Koordinate ist angegeben.
Bewegen Sie sich in einer geraden Linie zwischen den einzelnen Koordinaten.
0,Starten Sie von Position 0.
Geben Sie die Route aus, um jeden Schatz mit der kürzest möglichen Route zu erhalten.
Es muss nicht die kürzeste Entfernung sein.
Wert eingegeben werden
N (N ist die Gesamtzahl der Schätze)
x_1 y_1 （x_1 ist die x-Koordinate des Ortes des ersten Schatzes, y_1 ist die y-Koordinate des Ortes des ersten Schatzes)
x_1 y_1 （x_2 ist die x-Koordinate des Ortes des zweiten Schatzes, y_2 ist die y-Koordinate des Ortes des zweiten Schatzes)
・ ・ ・
x_N y_N （x_N ist die x-Koordinate des N-ten Schatzortes y_N ist die y-Koordinate des N-ten Schatzortes)
・ Alle Werte sind Ganzzahlen
・ 1 ≤ N ≤ 100
・ 1 ≤ x_i, y_i ≦ 1000000 (1 ≦ i ≦ N)
Erwartete Ausgabe
Bitte geben Sie die Route aus, auf der Sie alle Schätze erhalten können.
Beginnen Sie am Ende eine neue Zeile und fügen Sie keine zusätzlichen Zeichen oder Leerzeilen hinzu.
Beispiel
Eingabebeispiel 1
3
90 100
40 15
30 30
Ausgabebeispiel 1
90 100
40 15
30 30
Eingabebeispiel 2
5
1 1
40 120
199 256
10 30
50 5
Ausgabebeispiel 2
1 1
40 120
199 256
10 30
50 5
Der Code, den ich geschrieben habe.
import math
def cal_distance(current_point, point):
"""Finden Sie den Abstand zwischen zwei Punkten"""
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):
"""Erstellen Sie eine Liste mit Abständen zwischen zwei Punkten"""
distance_list = [(i, cal_distance(current_point, x)) for (i, x) in enumerate(position_list)]
return distance_list
#Eingabewert abrufen
list_len = int(input())
position_list = []
for i in range(list_len):
position_list.append(list(map(int,input().split())))
#Gehen Sie näher an die aktuelle 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])
Ausführungsergebnis (Es ist etwas schwierig, die Grenze zwischen Eingabe und Ausgabe zu verstehen)
$ python PaizaRouteSearch.py
5
1 2
4 2
10 40
3 2
1 1
1 1
1 2
3 2
4 2
10 40
Ich schrieb es mit einer einfachen Idee, dass ich dem Schatz, der mir am nächsten ist, von meiner aktuellen Position aus folgen sollte. Nach dem, was ich gehört habe, ist der kürzeste Weg die Lösung mit einem Algorithmus namens "Circular Salesman Problem".
Ich würde es gerne untersuchen und überprüfen, wenn ich Zeit habe.
Nachtrag: In Paizas Blog gab es einen Artikel, in dem das Problem erklärt wurde. [http://paiza.hatenablog.com/entry/2017/09/26/ [Erklärung des Problems] Wie man das Rätsel des Phantomdiebs 813 löst und den Schatz erhält](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)
Es scheint, dass meine Lösung eine gierige Methode ist, und ich habe dieselbe Lösung in Paizas Blog vorgestellt. Zusätzlich "Brennmethode", "Strahlensuche", "2-opt", "genetischer Algorithmus", Es scheint, dass es verschiedene Dinge gibt, wie "Christofeeds Algorithmus", "Gesamtflächenbaum", "Sukkulentenpilz-Algorithmus". Bei Wikipedia lautet die Formel ... Ich habe Kopfschmerzen, weil ich seit meiner Studienzeit keine Mathematik mehr habe.
Über Geschenke Es scheint, dass der Versand an die Gewinner bereits begonnen hat, und ich habe mich nicht kontaktiert, so dass ich es anscheinend verpasst habe. Es tut uns leid.
Das Folgende war übrigens falsch. Es scheint ein Problem zu geben und es gibt verschiedene Algorithmen, um es zu lösen.
Nach der Geschichte, die ich gehört habe, scheint der kürzeste Weg darin zu bestehen, mit einem Algorithmus namens "Circular Salesman Problem" zu lösen.
Nachtrag 2: Über Geschenke Etwa anderthalb Monate später, als ich es vergaß, erhielt ich einen Amazon-Geschenkgutschein (im Wert von 1000 Yen)! Ich bin froh, dass ich es nicht erwartet habe! Es scheint unerwartet ein Hit zu sein, also würde ich gerne das nächste Mal wieder teilnehmen!
Recommended Posts