优化2D数组寻路算法

Question

我正在尝试查找通过以0和1的矩阵表示的地图的最短路径，其中0是可通过的空间，而1是可通过的墙壁。入口在左上角（0，0），出口在右下角（宽度-1，高度-1）。

我的函数solution(int[][] map)查找从入口到出口的最短路径的长度，您可以在其中移除一堵墙作为路径的一部分。路径长度是您经过的节点总数，同时计算入口和出口节点。 map上的条件包括：开始和结束位置始终是可通过的（0），地图将始终是可求解的，尽管您可能需要也可能不需要移除墙，并且地图的高度和宽度可以是2至20。只能沿基本方向进行移动；不能移动。不允许对角线移动。

几个测试用例：

输入：

int[][] a = {{0, 1, 1, 0}, 
             {0, 0, 0, 1}, 
             {1, 1, 0, 0}, 
             {1, 1, 1, 0}, 
             {1, 1, 1, 0}};

输出：

8

输入：

int[][] b = {{0, 1, 0, 0, 0}, 
             {0, 0, 0, 1, 0}, 
             {0, 0, 1, 1, 0}, 
             {0, 1, 1, 0, 0},
             {0, 1, 1, 0, 0}};

输出：

9

输入：

int[][] c = {{0, 1, 0, 0, 0}, 
             {0, 0, 0, 1, 0}, 
             {0, 0, 1, 1, 1}, 
             {0, 1, 1, 0, 0},
             {0, 1, 1, 0, 0}};

输出：

11

我的解决方案代码如下：

public static int solution(int[][] map) {
    int rows = map.length; 
    int cols = map[0].length; 

    Graph graph = new Graph(map);

    Queue<Node> queue = new LinkedList<>();
    ArrayList<Node> marked = new ArrayList<>();
    Node start = graph.getNode(0, 0);

    queue.add(start);
    marked.add(start);
    start.setDistanceFromStart(1);

    while(!queue.isEmpty()) {
        Node current = queue.remove();

        if(current.getX() == rows - 1 && current.getY() == cols - 1) {  //if we have reached goal node
            return current.getDistanceFromStart();
        }

        for(Node n : current.getNeighbors()) {
            queue.add(n);
            n.setDistanceFromStart(current.getDistanceFromStart() + 1);

        }
    }
    return -1; //no path found
}

我与一起创建了两个类以及解决方法Graph和Node：

class Graph{
    private Node[][] _nodeMap;

    private int _rows;
    private int _cols;

    public Graph(int[][] map) {
        _nodeMap = new Node[map.length][map[0].length];
        _rows = _nodeMap.length;
        _cols = _nodeMap[0].length;

        for (int i = 0; i < _rows; i++) {
            for(int j = 0; j < _cols; j++) {
                _nodeMap[i][j] = new Node(i, j, map[i][j], false, this);
            }
        }
    }

    /**
     * Gets the Node at location (x,y)
     * @param x - the x val of the Node being retrieved
     * @param y - the y val of the Node being retrieved 
     * @return
     */
    public Node getNode(int x, int y) {
        return _nodeMap[x][y];
    }

    /**
     * Replace the node at x,y with the new node n.
     * @param x
     * @param y
     * @param n
     */
    public void setNode(int x, int y, Node n) {
        _nodeMap[x][y] = n;
    }

    /**
     * Checks to see if a node has a neighbor (either a wall or a path) to the north 
     * @param n - the node being checked
     * @return boolean - true if there is a neighbor, false if there is not
     */
    public boolean hasNorth(Node n) {
        if(n.getX() > 0) {
            return true;
        } else {
            return false;
        }
    }
    /**
     * Return's the neighbor to the north
     * @param n - the current node
     * @return Returns the Node to the north of n
     */
    public Node getNorth(Node n) {
        return _nodeMap[n.getX() - 1][n.getY()];
    }

    /**
     * Checks to see if a node has a neighbor (either a wall or a path) to the south 
     * @param n - the node being checked
     * @return boolean - true if there is a neighbor, false if there is not
     */
    public boolean hasSouth(Node n) {
        if(n.getX() < _rows - 1) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * Return's the neighbor to the south
     * @param n - the current node
     * @return Returns the Node to the south of n
     */
    public Node getSouth(Node n) {
        return _nodeMap[n.getX() + 1][n.getY()];
    }

    /**
     * Checks to see if a node has a neighbor (either a wall or a path) to the east 
     * @param n - the node being checked
     * @return boolean - true if there is a neighbor, false if there is not
     */
    public boolean hasEast(Node n) {
        if(n.getY() < _cols - 1) {
            return true;
        } else {
        return false;
        }
    }

    /**
     * Return's the neighbor to the east
     * @param n - the current node
     * @return Returns the Node to the east of n
     */
    public Node getEast(Node n) {
        return _nodeMap[n.getX()][n.getY() + 1];
    }

    /**
     * Checks to see if a node has a neighbor (either a wall or a path) to the west 
     * @param n - the node being checked
     * @return boolean - true if there is a neighbor, false if there is not
     */
    public boolean hasWest(Node n) {
        if(n.getY() > 0) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * Return's the neighbor to the west
     * @param n - the current node
     * @return Returns the Node to the west of n
     */
    public Node getWest(Node n) {
        return _nodeMap[n.getX()][n.getY() - 1];
    }
}



class Node {
    private int _x; //x location
    private int _y; //y location
    private int _type; //1 if a wall, 0 if a path
    private Graph _map;
    private int _distFromStart;
    private boolean _wallRemoved;

    public Node(int x, int y, int type, boolean wallRemoved, Graph map){
        _x = x;
        _y = y;
        _type = type;
        _wallRemoved = wallRemoved;
        _map = map;
        _distFromStart = -1;
    }

    public int getX() {
        return _x;
    }

    public int getY() {
        return _y;
    }

    public int getType() {
        return _type;
    }

    public boolean getWallRemoved() {
        return _wallRemoved;
    }

    public int getDistanceFromStart() {
        return _distFromStart;
    }

    public void setDistanceFromStart(int distance) {
        _distFromStart = distance;
    }

    /**
     * Returns an ArrayList<Node> containing the neighbors of a node.
     * @return
     */
    public ArrayList<Node> getNeighbors(){
        ArrayList<Node> neighbors = new ArrayList<>();

        if(this._wallRemoved) { //if a wall has already been removed
            if(_map.hasWest(this) && _map.getWest(this)._type == 0) { //check west neighbor
                Node node = _map.getWest(this);
                Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map/*, node._timesEvaluated + 1*/);
                neighbors.add(n);
            }

            if(_map.hasEast(this) && _map.getEast(this)._type == 0) { //check east neighbor
                Node node = _map.getEast(this);
                Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map);
                neighbors.add(n);
            }

            if(_map.hasNorth(this) && _map.getNorth(this)._type == 0) { //check north neighbor
                Node node = _map.getNorth(this);
                Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map);
                neighbors.add(n);
            }

            if(_map.hasSouth(this) && _map.getSouth(this)._type == 0) { //check south neighbor
                Node node = _map.getSouth(this);
                Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map/);
                neighbors.add(n);
            }

        } else { //if a wall hasn't been removed yet

            if(_map.hasWest(this)) { //check west neighbor
                if(_map.getWest(this)._type == 1) { //if west neighbor is a wall
                    if(!this._wallRemoved) {
                        Node node = _map.getWest(this);
                        Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map);
                        neighbors.add(n);
                    }
                } else { //if west neighbor is a path
                    Node node = _map.getWest(this);
                    Node n = new Node(node.getX(), node.getY(), node.getType(), false, _map);
                    neighbors.add(n);
                }
            }

            if(_map.hasEast(this)) { //check east neighbor
                if(_map.getEast(this)._type == 1) {
                    if(!this._wallRemoved) {
                        Node node = _map.getEast(this);
                        Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map);
                        neighbors.add(n);
                    }
                } else {
                    Node node = _map.getEast(this);
                    Node n = new Node(node.getX(), node.getY(), node.getType(), false, _map);
                    neighbors.add(n);
                }
            }


            if(_map.hasNorth(this)) { //check north neighbor
                if(_map.getNorth(this)._type == 1) {
                    if(!this._wallRemoved) {
                        Node node = _map.getNorth(this);
                        Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map);
                        neighbors.add(n);
                    }
                } else {
                    Node node = _map.getNorth(this);
                    Node n = new Node(node.getX(), node.getY(), node.getType(), false, _map);
                    neighbors.add(n);
                }
            }

            if(_map.hasSouth(this)) { //check south neighbor
                if(_map.getSouth(this)._type == 1) {
                    if(!this._wallRemoved) {
                        Node node = _map.getSouth(this);
                        Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map);
                        neighbors.add(n);
                    }
                } else {
                    Node node = _map.getSouth(this);
                    Node n = new Node(node.getX(), node.getY(), node.getType(), false, _map);
                    neighbors.add(n);
                }
            }
        }
        return neighbors;
    }
}

我的代码有效，每个测试用例均返回正确答案。我的问题是代码太慢了。我非常确定迷宫正在通过蛮力解决（如果不是，则时间限制至少类似于蛮力）会导致大型地图（例如20x20地图）花费很长时间才能解决。我该如何优化代码以使其运行更快？谢谢！

Answer 1

您将这个ArrayList称为“已标记”。我建议使用它;）

for(Node n : current.getNeighbors()) {
    if(!marked.contains(n)){
        queue.add(n);
        n.setDistanceFromStart(current.getDistanceFromStart() + 1);
        marked.add(n);
    }
}

这将复杂度降低到O（n * m），其中n，m是网格的尺寸。

还阅读了二维空间中的BFS算法。祝你好运：）

编辑＃1

如果您想进一步改进代码，则尝试检查A* algorithm。

也可以将所有“进行中”的节点保留在PriorityQueue上，而不是使用Queue带有特殊参数的参数，它将尝试选择最佳节点。此参数可以是节点与（宽度-1，高度-1）（简单的毕达哥拉斯定理）之间在笛卡尔平面中的距离。再次祝你好运：）

Answer 2

我认为这可能会有所帮助普林斯顿联合发现https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf