优化二维数组寻路算法
Optimizing a 2D array pathfinding algorithm
我试图找到通过表示为 0 和 1 矩阵的地图的最短路径,其中 0 是可通过的 space,1 是不可逾越的墙。入口在左上角 (0, 0),出口在右下角 (width - 1, height - 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
}
我创建了两个 类 以及解决方法,图形和节点:
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 地图)需要很长时间才能解决。我如何优化我的代码以使其 运行 更快?谢谢!
您有一个名为 "marked" 的 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 是网格的维度。
另请阅读 2d 中的 BFS 算法 space。祝你好运:)
编辑#1
如果您想进一步改进代码,请尝试检查 A* algorithm。
此外,您可以将所有 "in progress" 个节点保留在 PriorityQueue 上,而不是队列
带有特殊参数,它将尝试选择最佳节点。该参数可以是笛卡尔平面中节点与 (width - 1, height - 1) 之间的距离(简单勾股定理)。
再次祝你好运:)
我认为这会有所帮助
Union Find 来自普林斯顿
https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
我试图找到通过表示为 0 和 1 矩阵的地图的最短路径,其中 0 是可通过的 space,1 是不可逾越的墙。入口在左上角 (0, 0),出口在右下角 (width - 1, height - 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
}
我创建了两个 类 以及解决方法,图形和节点:
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 地图)需要很长时间才能解决。我如何优化我的代码以使其 运行 更快?谢谢!
您有一个名为 "marked" 的 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 是网格的维度。
另请阅读 2d 中的 BFS 算法 space。祝你好运:)
编辑#1
如果您想进一步改进代码,请尝试检查 A* algorithm。
此外,您可以将所有 "in progress" 个节点保留在 PriorityQueue 上,而不是队列 带有特殊参数,它将尝试选择最佳节点。该参数可以是笛卡尔平面中节点与 (width - 1, height - 1) 之间的距离(简单勾股定理)。 再次祝你好运:)
我认为这会有所帮助 Union Find 来自普林斯顿 https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf