旅游销售人员问题的可视化

Question

我正在做一个小项目来可视化旅行推销员问题的算法。我有城市，它们是用AWT和Swing绘制的可移动的物体。另外，我还可以以无向边的形式在两个城市之间建立联系。每个城市之间至少应该有一个联系。

在我目前的解决方案中，每个城市都有一个连接城市的ArrayList。但恐怕这不是最佳的解决办法。我希望听到一些关于我的代码的评论，以及对我解释的解决方案的改进。

PS:我知道有很多外部库，但是我想不使用任何外部库来解决这个问题。

The City Panel

public class CityPanel extends JPanel implements MouseListener, MouseMotionListener {

    public final static int UNIT = 16;
    public final static int GRIDWIDTH = 3 * UNIT;
    public final static int PANELWIDTH = 12 * GRIDWIDTH;
    public final static int PANELHEIGHT = 12 * GRIDWIDTH;

    private boolean connect;
    private boolean connectClick;
    private Mediator mediator;
    private CityList cityList = new CityList();
    private CityList bestTrail = new CityList();
    private City marked;
    private boolean move;
    private int pressX;
    private int pressY;

    private Graphics2D g2;

    public CityPanel(Mediator mediator)  {
        this.setPreferredSize(new Dimension(PANELWIDTH, PANELHEIGHT));
        this.setBorder(BorderFactory.createLineBorder(Color.BLACK));
        this.mediator = mediator;
        this.mediator.registerCityPanel(this);
        this.addMouseListener(this);
        this.addMouseMotionListener(this);
    }

    //Painting methods

    private void paintGrid() {
        g2.setColor(Color.LIGHT_GRAY);
        for(int i = 0; i < PANELWIDTH; i += GRIDWIDTH) {
            this.g2.drawLine(i,0,i,PANELHEIGHT);
            this.g2.drawLine(0,i,PANELHEIGHT,i);
        }
    }

    private void paintCities() {
        g2.setColor(Color.BLUE);
        for (int i = 0; i < cityList.size(); i++) {
            paintEdge(cityList.get(i));
            paintCity(cityList.get(i));
        }
        if (marked != null) {
            paintEdge(marked);
        }
    }

    private void paintCity(City city) {
        int rimX = city.getRimX();
        int rimY = city.getRimY();
        int x = city.getPos().x();
        int y = city.getPos().y();
        g2.setColor(city.getColor());
        box(rimX, rimY, City.WIDTH, true);
        write(String.valueOf(city.getId()), x, y);
        if (marked == city) {
            g2.setColor(Color.GREEN);
        } else {
            g2.setColor(Color.WHITE);
        }
        box(rimX, rimY, City.WIDTH, false);
    }

    private void paintConnections() {
        for (int i = 0; i < this.cityList.size(); i++) {
            for (int k = i+1; k < this.cityList.size(); k++) {
                paintConnection(this.cityList.get(i), this.cityList.get(k));
            }
        }
    }

    private void paintConnection(City city1, City city2) {
        if (city1.contains(city2)) {
            g2.setColor(Color.GRAY);
            g2.drawLine(city1.getPos().x(), city1.getPos().y(),
                city2.getPos().x(), city2.getPos().y());
        }
    }

    private void paintEdge(City city) {
        g2.setColor(Color.CYAN);
        if (city == marked) {
            g2.setColor(Color.YELLOW);
        }
    }

    private void box(int x, int y, int width, boolean b) {
        if(b) {
            g2.fillOval(x, y, width, width);
        }
        else
            g2.drawOval(x, y, width, width);
    }

    private void write(String name, int x, int y) {
        g2.setFont(new Font("Calibri", Font.PLAIN, City.WIDTH/2));
        g2.setColor(Color.WHITE);
        final FontMetrics fm = g2.getFontMetrics();
        final int strWidth = SwingUtilities.computeStringWidth(fm, name);
        g2.drawString(name, (int) (x - strWidth/2), (int) (y + fm.getMaxAscent()/2));
    }

    private void paintDescriptions() {
        for (int i = 0; i < this.cityList.size(); i++) {
            City city1 = this.cityList.get(i);
            for (int k = 0; k < city1.getConnections().size(); k++) {
                City city2 = city1.getConnections().get(k);
                Pos pos = getCenterOfLine(city1, city2);
                String dist = String.valueOf(this.cityList.getDistance(city1, city2));
                g2.setColor(Color.GRAY);
                g2.setFont(new Font("Calibri", Font.PLAIN, City.WIDTH/3));
                final FontMetrics fm = g2.getFontMetrics();
                final int strWidth = SwingUtilities.computeStringWidth(fm, dist);
                g2.drawString(dist, pos.x() - strWidth/2, pos.y());
            }
        }
    }

    private void paintBestTrail() {
        for (int i = 1; i < this.bestTrail.size(); i++) {
            City a = this.bestTrail.get(i-1);
            City b = this.bestTrail.get(i);
            g2.setColor(Color.RED);
            g2.drawLine(a.getPos().x(), a.getPos().y(), b.getPos().x(), b.getPos().y());
        }
    }

    //other methods

    public void addCities(int number) {
        this.cityList.clear();
        for (int i = 1; i <= number; i++) {
            this.cityList.add(new City(i));
        }
        this.repaint();
    }

    public void connectAllCities() {
        for (int i = 0; i < this.cityList.size(); i++) {
            for (int k = i+1; k < this.cityList.size(); k++) {
                this.cityList.get(i).addConnection(this.cityList.get(k));
                this.cityList.get(k).addConnection(this.cityList.get(i));
            }
        }
        repaint();
    }

    public void showConnections() {
        for (int i = 0; i < this.cityList.size(); i++) {
            System.out.print("City " + this.cityList.get(i).getId() + ":\t");
            for (int k = 0; k < this.cityList.get(i).getConnections().size(); k++) {
                System.out.print(this.cityList.get(i).getConnections().get(k).getId() + "\t");
            }
            System.out.println();
        }
        System.out.println();
    }

    public void setConnect(boolean connect) {
        this.connect = connect;
    }

    public Pos getCenterOfLine(City city1, City city2) {
        Pos pos1 = city1.getPos();
        Pos pos2 = city2.getPos();
        int newX = (pos2.x() - pos1.x()) / 2 + pos1.x();
        int newY = (pos2.y() - pos1.y()) / 2 + pos1.y();
        return new Pos(newX, newY, true);
    }

    private boolean isStartable() {
        boolean b = true;
        for (City city : this.cityList) {
            if (city.getConnections().size() == 0)
                b = false;
        }
        return this.cityList.size() != 0 && b;
    }

    public void setBestTrail() {
        this.bestTrail.clear();
        CityList temp = (CityList) this.cityList.clone();
        Random rand = new Random();
        for (int i = 0; i < temp.size(); i++) {
            int r = rand.nextInt(this.cityList.size()-i);
            this.bestTrail.add(temp.get(r));
            temp.remove(r);
        }
    }

    //MouseListener methods

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        this.g2 = (Graphics2D) g;
        this.g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
                RenderingHints.VALUE_ANTIALIAS_ON);
        this.g2.setRenderingHint(RenderingHints.KEY_INTERPOLATION,
                RenderingHints.VALUE_INTERPOLATION_BICUBIC);

        this.paintGrid();
        this.paintConnections();
        this.paintCities();
        if (connectClick) {
            g2.setColor(Color.GRAY);
            g2.drawLine(this.marked.getPos().x(), this.marked.getPos().y(),
                    this.pressX, this.pressY);
        }
        paintDescriptions();
        paintBestTrail();
        this.mediator.enableStartButton(isStartable());
    }

    @Override
    public void mouseClicked(MouseEvent e) {
        if(SwingUtilities.isRightMouseButton(e)) {
            if(this.cityList.isOccupied(new Pos(e.getX(), e.getY()), null)) {
                cityList.remove(cityList.getMarked(e.getX(), e.getY()));
                repaint();
            } else  {
                cityList.add(new City(cityList.size() + 1, e.getX(), e.getY()));
                repaint();
            }
        } else
            showConnections();
    }

    @Override
    public void mousePressed(MouseEvent e) {
        if (marked != null) {
            if (this.connect) {
                this.connectClick = true;
            }
            this.move = true;
        }
    }

    @Override
    public void mouseReleased(MouseEvent e) {
        if (this.connectClick)  {
            City city = this.cityList.getMarked(e.getX(), e.getY());
            if (city != null)   {
                city.addConnection(this.marked);
                this.marked.addConnection(city);
            }
        }
        this.move = false;
        this.connectClick = false;
        this.connect = false;
        this.repaint();
    }

    @Override
    public void mouseEntered(MouseEvent e) {
    }

    @Override
    public void mouseExited(MouseEvent e) {
    }

    @Override
    public void mouseDragged(MouseEvent e) {
        if (this.connectClick)  {
            this.pressX = e.getX();
            this.pressY = e.getY();
        } else {
            int maxHeight = CityPanel.PANELHEIGHT - City.WIDTH / 2;
            int minHeight = City.WIDTH / 2;
            int maxWidth = CityPanel.PANELWIDTH - City.WIDTH / 2;
            int minWidth = CityPanel.WIDTH / 2;
            if (e.getX() > maxWidth || e.getX() < minWidth ||       //Checks if Mouse is out of Panelrange, the field is Occupied, or if move=false
                e.getY() > maxHeight || e.getY() < minHeight ||
                this.cityList.isOccupied(new Pos(e.getX(), e.getY()), marked) ||
                !move)
                return;
            this.marked.setPos(new Pos(e.getX(), e.getY()));
        }
        repaint();
    }

    @Override
    public void mouseMoved(MouseEvent e) {
        if (this.move || this.connectClick)
            return;
        City neu = this.cityList.getMarked(e.getX(), e.getY());
        if (this.marked != neu) {
            this.marked = neu;
            this.repaint();
        }
    }
}

The City Class

public class City {

    private int id;
    private Pos pos;
    public static int WIDTH = (int) (0.75 * CityPanel.GRIDWIDTH);
    private Color color = Color.BLACK;
    private ArrayList<City> connections = new ArrayList<City>();
    private Random r = new Random();

    public City(int id) {
        this.id = id;
        System.out.println("City " + id);
        this.pos = new Pos();
    }

    public City(int id, int x, int y) {
        this.id = id;
        this.pos = new Pos(x,y);
    }

    public boolean isMarked(int x, int y) {
        return (distFromCenter(x, y) < this.WIDTH/2);
    }

    public double distFromCenter(int x, int y) {
        int dx = Math.abs(pos.x() - x);
        int dy = Math.abs(pos.y() - y);
        return Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
    }

    public int getRimX() {
        return this.pos.x() - this.WIDTH / 2;
    }

    public int getRimY() {
        return this.pos.y() - this.WIDTH / 2;
    }

    public void addConnection(City city) {
        if (!this.connections.contains(city))
            this.connections.add(city);
    }

    public void removeConnection(City city) {
        this.connections.remove(city);
    }

    public boolean contains(City city) {
        return this.connections.contains(city);
    }

    public Pos getPos() {
        return this.pos;
    }

    public void setPos(Pos pos) {
        this.pos = pos;
    }

    public int getId() {
        return this.id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public Color getColor() {
        return this.color;
    }

    public ArrayList<City> getConnections() {
        return this.connections;
    }
}

CityList类

public class CityList extends ArrayList<City> {

    private double[][] distances;
    private Random r = new Random();

    public CityList() {
    }

    public boolean isOccupied(Pos pos, City marked) {
        for (int i = 0; i < this.size(); i++)   {
            if(get(i).getPos().equals(pos) && !get(i).equals(marked))
                return true;
        }
        return false;
    }

    public City getMarked(int x, int y) {
        for (int i = size() - 1; i >= 0; i--) {
            if (get(i).isMarked(x, y)) {
                return get(i);
            }
        }
        return null;
    }

    public int getDistance(City a, City b) {
        int x = Math.abs(a.getPos().x() - b.getPos().x());
        int y = Math.abs(a.getPos().y() - b.getPos().y());
        double dist = Math.sqrt(Math.pow(x,2) + Math.pow(y,2));
        return (int) Math.round(dist / CityPanel.UNIT);
    }

    public boolean add(City city) {
        while (this.isOccupied(city.getPos(), city)) {
            city.setPos(new Pos());
        }
        return super.add(city);
    }

    public boolean remove(City city) {
        for (City c : city.getConnections()) {
            c.removeConnection(city);
        }
        boolean b = super.remove(city);
        for (int i = 0; i < this.size(); i++) {
            this.get(i).setId(i+1);
        }
        return b;
    }
}

Answer 1

您可以从ArrayList更改为HashMap。这将为大量城市提供更好的性能(对于少数城市而言，使用HashMap的开销可能比使用ArrayList获得的开销还要多)。

我还建议在CityList中添加一个新变量--一个由Pos索引的新HashMap。然后，您的isOccupied函数变成：

public boolean isOccupied(Pos pos, City marked) {
    //returns true only if there is a Pos p in the map so p.equals(marked.getPos()) is true.
    return posMap.containsKey(marked.getPos());
}

为什么？

在CityPanel中，paintCities需要在所有城市中迭代，paintConnections需要迭代所有连接，即在城市中进行双次迭代(最好的情况是O(n^2) )。paintDescriptions也是一样的。addCities为生成的每个城市调用add()一次。所以它是O(n *add()的复杂性)

在City中，addConnection调用contains()和add() --这将是O(n)，因为连接列表上有contains() removeConnection calls remove()。contains是具有ArrayList的O(n)。

CityList实际上只存在isOccupied的一个问题；为了给出答案，它必须遍历整个列表(所以是O(n))。add依赖于isOccupied remove calls removeConnection()在列表中的每个城市，即O(n *remove的成本)