连接文件中的点 - 最短路径

Question

我有一个应用程序，它可以读取一组点并将它们绘制在JPanel上。我现在想要修改该代码，以便它在每个点之间画一条线。这是我只绘制点的代码。

法典：

import javax.swing.*;
import java.awt.*;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
public class Test {
    private static final String FILE = "Desktop/Test1.txt";
    private static Point[] points;
    public static void main(final String[] args){
        try{
            final BufferedReader br = new BufferedReader(new FileReader(new File(FILE)));
            points = new Point[Integer.parseInt(br.readLine())];
            int i = 0;
            int xMax = 0;
            int yMax = 0;
            while(br.ready()){
                final String[] split = br.readLine().split("t");
                final int x = Integer.parseInt(split[0]);
                final int y = Integer.parseInt(split[1]);
                xMax = Math.max(x, xMax);
                yMax = Math.max(y, yMax);
                points[i++] = new Point(x, y);


            }
            final JFrame frame = new JFrame("Point Data Rendering");
            final Panel panel = new Panel();
            panel.setPreferredSize(new Dimension(xMax + 10, yMax + 10));
            frame.setContentPane(panel);
            frame.pack();
            frame.setVisible(true);
            frame.repaint();
        } catch (final Exception e){
            e.printStackTrace();
        }
    }
    public static class Panel extends JPanel {
        @Override
        public void paintComponent(final Graphics g){
            g.setColor(Color.RED);
            for(final Point p : points){
                g.fillRect((int) p.getX(), (int) p.getY(), 2, 2);
            }
        }
    }
}

如果有人有任何很酷的算法可以找到连接所有点的最短路径，我会非常有兴趣学习它们！

Answer 1

找到连接所有点的最短路径被称为旅行推销员问题，被称为NP-hard。基本上，这意味着没有快速算法可以找到最短路径。但是，有一些快速算法可以找到一条非常短的路径，最重要的是，如果点的数量非常小（10 或更少），那么您可以想象出所有可能的解决方案。

一个非常简单的算法是从随机点开始，计算到每个点的距离并选择最短的路径，然后重复直到你访问了每个点。为了使它稍微聪明一点，然后你可以沿着路径尝试每两条线交换一次（例如，如果你做a-B B-c c-D，尝试a-c c-B B-D），如果它使路径更短，则保持它。

在这里阅读有关旅行推销员问题的信息：http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms