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 困難として知られています。基本的にこれは、SHORTEST パスを見つける高速なアルゴリズムがないことを意味します。ただし、かなり短いパスを見つける高速なアルゴリズムがあり、さらに、ドットの数が非常に少ない (10 個以下) 場合は、考えられるすべての解を列挙できます。

非常に単純なアルゴリズムは、ランダムなポイントから開始し、各ポイントまでの距離を計算して最短のパスを選択し、すべてのポイントを訪れるまで繰り返すことです。これを少し賢くするために、パスに沿って 2 行ごとに交換を試み (たとえば、aB Bc cD を実行する場合は ac cB BD を試行)、パスが短くなる場合はそのままにしておくことができます。

巡回セールスマン問題については、こちらをご覧ください: http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms

于 2013-01-31T01:32:15.250 に答える