[JAVA] J'ai essayé de résoudre le problème de la campagne paiza "Challenge from Phantom Thief 813"

Après avoir résolu le problème, j'ai entendu dire que je pouvais obtenir un chèque-cadeau Amazon ou de la viande par loterie, alors j'ai essayé. https://paiza.jp/poh/phantom_thief

problème

Les informations de localisation du trésor sont écrites avec les coordonnées x, y de N trésors en mètres, avec l'emplacement du voleur fantôme comme 0, 0. Il se déplace en ligne droite entre chaque coordonnée. Commencez à 0,0 et imprimez l'itinéraire qui vole tous les trésors dans l'itinéraire le plus court possible.

Façon de penser

Si vous sortez les coordonnées les plus proches de l'origine, sortez à nouveau les coordonnées les plus proches de ces coordonnées, et ainsi de suite, vous pouvez suivre un itinéraire court. J'ai pensé, j'ai essayé de le résoudre.

Il était écrit que la réponse pouvait être écrite sur un blog, je l'ai donc postée ci-dessous.

Code de soumission

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>();
        
        //Créer une liste de coordonnées à partir d'une entrée standard
        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();

            //Obtenez les coordonnées les plus proches du point de référence à partir de la liste des coordonnées
            for(Point getPoint : pointList){
                int tmpDistance = getDistance(originPoint,getPoint);
                if(minDistance > tmpDistance){
                    minDistance = tmpDistance;
                    minDistancePoint = getPoint;
                }
            }
            //Afficher la position des coordonnées
            minDistancePoint.output();
            //Changer le point de référence
            originPoint = minDistancePoint;
            //Supprimer les coordonnées de la liste des coordonnées
            int index = pointList.indexOf(minDistancePoint);
            pointList.remove(index);
        }
    }

    //Trouvez la distance entre les coordonnées de deux points
    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;
    }

}

//Classe de coordonnées
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);
    }
}

résultat

Ici. Il semble que ce n'était pas la solution optimale. https://paiza.jp/poh/phantom_thief/result/a8a222d8

Comment trouver la solution optimale?

Après quelques recherches, [Problème de vendeur circulaire](https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E3%82%BB%E3%83%BC%E3 Cela semble être un problème appelé% 83% AB% E3% 82% B9% E3% 83% 9E% E3% 83% B3% E5% 95% 8F% E9% A1% 8C). (Est-ce un peu différent parce que vous n'avez pas besoin de revenir aux premières coordonnées?)

La méthode que j'ai résolue cette fois semble être un algorithme appelé "méthode gourmande".

Il existe des algorithmes pour résoudre le problème du voyageur de commerce, «méthode à 2 opt», «méthode d'alpinisme», «méthode de gravure», etc.