java - Java (Swing) 中的旅行商可视化

Question

出于练习目的，我挑战自己编写了一个程序来求解 TSP 并一步步可视化结果。

至于现在，我的程序使用简单的最近邻算法。我希望我的程序具有灵 active ，因此当我添加新算法时，它也能够将结果可视化，而不会扰乱显示逻辑。

我遇到的一个问题是——如何逐步显示解决方案？我通过创建多个部分解决方案、存储它们并一个接一个地显示来解决它。我觉得它可以做得更好，但我的图形不是很好，我希望能在这里得到一些线索。

这是一些代码:Point 类 - 代表一个城市。

class Point {
    private double x;
    private double y;

    public double getX() {
        return x;
    }
    public double getY() {
        return y;
    }

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public Point(){
        Random r = new Random();
        x=r.nextInt(1000);
        y=r.nextInt(650);
    }

    public double calculateDistanceToPoint(Point p) {
        double dist = Math.sqrt(Math.pow(this.x-p.x, 2) + Math.pow(this.y-p.y, 2));
        return round(dist,2);
    }

    private static double round(double value, int places) {
        if (places < 0) throw new IllegalArgumentException();

        BigDecimal bd = new BigDecimal(value);
        bd = bd.setScale(places, RoundingMode.HALF_UP);
        return bd.doubleValue();
    }
}

然后，执行计算的 Solver 类:

class Solver {
    //list of all points to visit
    private static ArrayList<Point> points = new ArrayList<>();

    //adjacency matrix
    private ArrayList<ArrayList<Double>> adjMatrix = new ArrayList<>();

    //found solution
    private static ArrayList<Point> solution = new ArrayList<>();

    //visited points
    private ArrayList<Integer> visitedPoints = new ArrayList<>();

    //used for visualisation
    private static Solution finalSolution = new Solution();

    public void clear() {
        points.clear();
        solution.clear();
        visitedPoints.clear();
        adjMatrix.clear();
        finalSolution.clear();
    }

    public void addPoint(Point p) {
        points.add(p);
    }

    public static ArrayList<Point> getPoints() {
        return Solver.points;
    }

    public void fillAdjacencyMatrix() {
        int iter_x;
        int iter_y;
        for (iter_x = 0; iter_x < points.size(); iter_x++) {
            ArrayList<Double> temp = new ArrayList<>();
            for (iter_y = 0; iter_y < points.size(); iter_y++) {
                if (iter_x == iter_y) {
                    temp.add(-1.0);
                } else {
                    temp.add(points.get(iter_x).calculateDistanceToPoint(points.get(iter_y)));
                }
            }
            adjMatrix.add(temp);
        }
    }

    private int getIndexOfMin(ArrayList<Double> arr) {
        Double min = Double.MAX_VALUE;
        int index = -2;
        for (int i = 0; i < arr.size(); i++) {
            Double val = arr.get(i);
            if (!(val == -1.0) && !visitedPoints.contains(i) && val < min) {
                min = val;
                index = i;
            }
        }
        return index;
    }

    public void solveUsingNN(int startingPoint) {
        int noOfVisited = 0;

        //find nearest point from the starting one
        int nearest = getIndexOfMin(adjMatrix.get(startingPoint));
        Solution sol = new Solution();

        //until we've visited all points
        while (noOfVisited!=points.size()) {
            //get next nearest point and add it to visited
            nearest = getIndexOfMin(adjMatrix.get(nearest));
            visitedPoints.add(nearest);

            //add this point to solution
            Point newPoint = points.get(nearest);
            solution.add(newPoint);

            //create a new frame for animation, containing all previous steps and recently added one
            SolutionStep ss = new SolutionStep();
            Point p;
            for (Point newPoint : solution) {
                p = new Point(newPoint.getX(), newPoint.getY());
                ss.addPoint(p);
            }
            sol.addStep(ss);
            noOfVisited++;
        }
        finalSolution=sol;
    }
}

然后，SolutionStep 类:

class SolutionStep{
    public final ArrayList<Point> step = new ArrayList<>();
    public SolutionStep(){}

    public void addPoint(Point p){
        step.add(p);
    }
    public void draw(Graphics g) {
        Graphics2D g2 = (Graphics2D) g;
            for (int i = 0; i < step.size()-1; i++) {
                g2.draw(new Line2D.Double(step.get(i).getX(), step.get(i).getY(), step.get(i + 1).getX(), step.get(i + 1).getY()));
        }
    }
}

和解决方案，其中包含许多步骤。

public class Solution {
    private ArrayList<Point> points = new ArrayList<>();
    private static ArrayList<SolutionStep> playbackSolution = new ArrayList<>();
    private int noOfFrames;

    public Solution(ArrayList<SolutionStep> listOfSteps, int noOfFrames){
        this.noOfFrames=noOfFrames;
        playbackSolution=listOfSteps;
    }
    public Solution(){}

    public static ArrayList<SolutionStep> getPlayback(){
        return playbackSolution;
    }
    public void clear(){
        playbackSolution.clear();
    }

    public void addStep(SolutionStep solutionStep){
        playbackSolution.add(solutionStep);
    }

    public void draw(Graphics g) {
        int numberOfPoints;
        points = Solver.getPoints();
        Graphics2D g2 = (Graphics2D) g;
        //draw all points
        for (Point point : points) {
            g2.fill(new Rectangle2D.Double(point.getX(), point.getY(), 6, 6));
        }

        //draw next line
        for(int i = 0;i<noOfFrames;i++) {
            playbackSolution.get(i).draw(g);
        }

        //if we are at the final solution, draw a line from last point to the first
        if (noOfFrames == points.size()){
            numberOfPoints = points.size();
            Point first = playbackSolution.get(0).step.get(0);
            Point last = playbackSolution.get(numberOfPoints-1).step.get(numberOfPoints-1);
            g2.draw(new Line2D.Double(first.getX(), first.getY(), last.getX(), last.getY()));
        }
    }
}

最后，可视化

class Visualisation extends JFrame {
    private DrawingPanel contentPane;
    private int noOfPoints = 10;
    private int delay_time = 300;

    public Visualisation() {
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setBounds(100, 100, 1100, 700);
        contentPane = new DrawingPanel();
        setContentPane(contentPane);
        JButton start = new JButton("Start");
        start.addActionListener(new ActionListener() {
            @Override
            public void actionPerformed(ActionEvent actionEvent) {
                Solver s = new Solver();
                s.clear();
                contentPane.displayNoOfSteps = 0;
                for (int i=0;i<noOfPoints;i++) {
                    s.addPoint(new Point());
                }
                s.fillAdjacencyMatrix();
                s.solveUsingNN(0);
                new javax.swing.Timer(delay_time, new ActionListener(){
                    @Override
                    public void actionPerformed(ActionEvent e){
                            contentPane.repaint();
                    }
                }).start();
                contentPane.repaint();
            }
        });
        contentPane.add(start);
    }
}

和DrawingPanel:

class DrawingPanel extends JPanel{
    public int displayNoOfSteps = 1;

    DrawingPanel(){}
    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        Solution sol = new Solution(Solution.getPlayback(),displayNoOfSteps);
        sol.draw(g);

        if (displayNoOfSteps< Solution.getPlayback().size())
        displayNoOfSteps++;
        }
    }

主类:

class Main {
    public static void main(String[] args){
        Visualisation frame = new Visualisation();
        frame.setVisible(true);
    }
} 

1. 现在，在 Visualisation 类中我有一个 Timer。此计时器每隔 delay_time 毫秒调用 DrawingPanel 上的 repaint()，并且在每次迭代中它会增加要显示的步骤数。问题是，如果我运行一个模拟，然后再次点击 Start，模拟运行得更快，并且在运行几次之后，它几乎立即显示最后一步。我不知道出了什么问题。我该如何处理？

2. 程序启动时出现错误-

   在 Solution.draw(Solution.java:57)

   在 DrawingPanel.paintComponent(Visualisation.java:53)

指的是行:

playbackSolution.get(i).draw(g);

和

sol.draw(g);

但是我还没有画任何东西! repaint() 位于 JButton 的 ActionListener 中。或者绘制一个 JButton 无论如何都会调用 draw()？我怎样才能摆脱这个问题？

1. 此外，我觉得我使用了太多的静态字段和方法 - 但另一方面，创建 Solver 的实例会更好，然后有非静态方法来获得解决方案吗？或者也许使 Solver 成为单例？反正有一个例子。

2. 正如我之前提到的，我想在编写更复杂的算法(例如模拟退火)之前获得有关此代码的一些反馈，以便保持良好的代码质量。我可以更改此代码中的哪些内容以便更轻松地添加新功能？

Answer 1

有维护相当大的 Java Swing 应用程序的经验，我绝不会自愿 promise 在 Swing 中做一些新的事情。

我认为通过使用第三方工具可视化图表可以很好地解决这个特殊问题。 Graphviz是一个选项，但还存在其他几种工具。看here更多示例。

您所做的只是用您的可视化工具的符号生成图表。您可以使用节点名称来显示销售员采取的路径:1、2、3 等。