Nachdem ich das Problem gelöst hatte, hörte ich, dass ich einen Amazon-Geschenkgutschein oder Fleisch per Lotterie bekommen könnte, also versuchte ich es. https://paiza.jp/poh/phantom_thief
Die Informationen zur Schatzposition werden mit den x, y-Koordinaten von N Schätzen in Metern geschrieben, wobei die Position des Phantomdiebs 0, 0 ist. Es bewegt sich in einer geraden Linie zwischen jeder Koordinate. Beginnen Sie bei 0,0 und drucken Sie die Route, die alle Schätze stiehlt, auf kürzestem Weg.
Wenn Sie die Koordinaten ausgeben, die dem Ursprung am nächsten liegen, geben Sie die Koordinaten wieder aus, die diesen Koordinaten am nächsten liegen, und so weiter. Sie können mit einer kurzen Route fortfahren. Ich dachte, ich habe versucht, es zu lösen.
Es wurde geschrieben, dass die Antwort in einem Blog geschrieben werden könnte, also habe ich sie unten gepostet.
Einreichungscode
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String firstLine = sc.nextLine().replaceAll(" ","");
int itemCount = Integer.parseInt(firstLine);
ArrayList<Point> pointList = new ArrayList<Point>();
//Erstellen Sie eine Koordinatenliste aus der Standardeingabe
for(int i = 0; i < itemCount ; i++){
String[] line = sc.nextLine().split(" ");
int x = Integer.parseInt(line[0]);
int y = Integer.parseInt(line[1]);
pointList.add(new Point(x,y));
}
Point originPoint = new Point(0,0);
while(pointList.size() > 0){
int minDistance = Integer.MAX_VALUE;
Point minDistancePoint = new Point();
//Holen Sie sich die Koordinaten, die dem Referenzpunkt am nächsten liegen, aus der Koordinatenliste
for(Point getPoint : pointList){
int tmpDistance = getDistance(originPoint,getPoint);
if(minDistance > tmpDistance){
minDistance = tmpDistance;
minDistancePoint = getPoint;
}
}
//Koordinatenposition anzeigen
minDistancePoint.output();
//Ändern Sie den Referenzpunkt
originPoint = minDistancePoint;
//Entfernen Sie die Koordinaten aus der Koordinatenliste
int index = pointList.indexOf(minDistancePoint);
pointList.remove(index);
}
}
//Finden Sie den Abstand zwischen den Koordinaten zweier Punkte
public static int getDistance(Point p1, Point p2) {
double x1 = p1.x;
double y1 = p1.y;
double x2 = p2.x;
double y2 = p2.y;
double distance = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
return (int) distance;
}
}
//Klasse koordinieren
class Point{
int x;
int y;
public Point(){
this.x = 0;
this.y = 0;
}
public Point(int x , int y){
this.x = x;
this.y = y;
}
public void output(){
System.out.println(x + " " + y);
}
}
Hier. Es scheint, dass es nicht die optimale Lösung war. https://paiza.jp/poh/phantom_thief/result/a8a222d8
Nach ein wenig Recherche [Circular Salesman Problem](https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E3%82%BB%E3%83%BC%E3 Es scheint ein Problem zu sein, das als% 83% AB% E3% 82% B9% E3% 83% 9E% E3% 83% B3% E5% 95% 8F% E9% A1% 8C bezeichnet wird. (Ist es ein bisschen anders, weil Sie nicht zu den ersten Koordinaten zurückkehren müssen?)
Die Methode, die ich dieses Mal gelöst habe, scheint ein Algorithmus zu sein, der "gierige Methode" genannt wird.
Es gibt "2-Opt-Methode", "Bergsteiger-Methode", "Brennmethode" usw. als Algorithmen zur Lösung des Problems des Handlungsreisenden, und die Verwendung dieser Methoden scheint der optimalen Lösung näher zu sein, aber ich habe aufgegeben, weil es schwierig erscheint.
Recommended Posts