0

我有一个应用程序读取一组点并将它们绘制在 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);
            }
        }

    }

}

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

4

1 回答 1

0

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

一个非常简单的算法是从一个随机点开始，计算到每个点的距离并选择最短的路径，然后重复直到你访问了每个点。为了使这更智能，您可以沿着路径走并尝试每两行交换一次（例如，如果您执行 aB Bc cD 尝试 ac cB BD），如果它使路径更短，请保留它。

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

于 2013-01-31T01:32:15.250 回答