使用广度优先搜索算法存储迷宫求解的路径
Store the path for maze solving using Breadth First Search Algorithm
我正在使用广度优先搜索算法来解迷宫。我的算法成功地找到了最短路径，但它没有存储最短路径。它只是告诉我完成这条路径所用的步数，但会保存所有已检查的方块，无论它们是否属于最短路径。我真的尝试了很多方法来存储最短路径，但我在路径中遇到错误，其中还包括不在最短路径中的方块。如果您能帮我找到一种将最短路径存储在 ArrayList 或 ArrayQueue 或数组或任何东西中的方法。 correctPath() 是我所做的，所以我可以决定哪些方块在最短路径中，但这是错误的。我认为这并不复杂，只是我不知道该怎么做。谢谢你的时间。
正方形具有 x 和 y 位置属性以及与目的地的距离。
public class BreathAlgorithm {
// Java program to find the shortest path between a given source cell to a destination cell.
static int ROW;
static int COL;
// These arrays are used to get row and column numbers of 4 neighbours of a given cell
static int[] rowNum = {-1, 0, 0, 1};
static int[] colNum = {0, -1, 1, 0};
// check whether given cell (row, col) is a valid cell or not.
static boolean isValid(int row, int col)
{
// return true if row number and column number is in range
return (row > 0) && (row <= ROW) && (col > 0) && (col <= COL);
}
// Checks if a square is an adjacent to another square
static boolean isNearSquare(Square a,Square b){
int x = 1;
int y = 0;
if((Math.abs((a.getX()+x) - (b.getX()+x))) + (Math.abs((a.getY()+y) - (b.getY()+y))) != 1){
return false;
}
x = -1;
y = 0;
if((Math.abs((a.getX()+x) - (b.getX()+x))) + (Math.abs((a.getY()+y) - (b.getY()+y))) != 1){
return false;
}
x = 0;
y = 1;
if((Math.abs((a.getX()+x) - (b.getX()+x))) + (Math.abs((a.getY()+y) - (b.getY()+y))) != 1){
return false;
}
x = 0;
y = -1;
return (Math.abs((a.getX() + x) - (b.getX() + x))) + (Math.abs((a.getY() + y) - (b.getY() + y))) == 1;
}
// returns the Square of the ending position
public static Square findEnd(int[][] mat){
for (int i=0;i<mat.length;i++){
for(int j=0;j<mat[0].length;j++){
if(mat[i][j] == 9)
return new Square(i,j,0);
}
}
return new Square(1,1,0);
}
/*
In this method i tried to define which squares are to be deleted from the fullPath
and return a new path with only the squares who are actually used in the shortest path.
This method doesn't work for all examples it just works for some so i guess it is lacking.
*/
public static ArrayQueue<Square> correctPath(ArrayList<Square> path) throws QueueFullException {
int i=0;
while(i<path.size()-1){
if (path.get(i).getDistance() == path.get(i+1).getDistance()){
if (path.get(i+2)!=null && path.get(i-1)!=null && (!isNearSquare(path.get(i),path.get(i+2)) || !isNearSquare(path.get(i),path.get(i+2)))){
path.remove(i);
}
else if (path.get(i+2)!=null && path.get(i-1)!=null && (!isNearSquare(path.get(i+1),path.get(i-1)) || !isNearSquare(path.get(i+1),path.get(i+2)))){
path.remove(i+1);
}
else if (!isNearSquare(path.get(i),path.get(i+1))){
path.remove(i);
}
}
i++;
}
ArrayQueue<Square> correctPath = new ArrayQueue<>(path.size());
while(i>=0){
correctPath.enqueue(path.get(i));
i--;
}
return correctPath;
}
static void printCorrectPath(ArrayQueue<Square> correctPath) throws QueueEmptyException {
Square[] originalPath = new Square[correctPath.size()];
for(int i=originalPath.length-1;i>=0;i--){
originalPath[i] = correctPath.dequeue();
}
int i=0;
while(i<originalPath.length-1){
if(i == 0) System.out.println(originalPath[i]+" is the starting point.");
System.out.println("From "+originalPath[i]+"to "+originalPath[i+1]);
i++;
if(i == originalPath.length-1) System.out.println(originalPath[i]+" is the ending point.");
}
}
public static void searchPath(int[][] mat,Square start) throws QueueEmptyException, QueueFullException {
//mat is the maze where 1 represents a wall,0 represent a valid square and 9 is the destination
// When a square is visited from 0 it becomes a 2
ROW=mat.length;
COL=mat[0].length;
Square dest = findEnd(mat); // search for the number 9 and make a new Square and put it in dest
int dist = BFS(mat, start, dest); // find the least distance
if (dist != Integer.MAX_VALUE)
System.out.println("\nShortest Path is " + dist+" steps.");
else
System.out.println("Shortest Path doesn't exist");
}
// function to find the shortest path between a given source cell to a destination cell.
static int BFS(int[][] mat, Square src, Square dest) throws QueueFullException, QueueEmptyException {
ArrayList<Square> fullPath = new ArrayList<>(); // path of all the squares checked
boolean [][]visited = new boolean[ROW][COL]; // if a square is visited then visited[x][y] = true
ArrayQueue<Square> q = new ArrayQueue<>(mat.length*mat[0].length); // Create a queue for BFS
// check source and destination cell of the matrix have value 1
if (mat[src.getY()][src.getX()] != 0 || mat[dest.getX()][dest.getY()] != 9) {
return -1;
}
mat[src.getY()][src.getX()] = 2; // Mark the source cell as visited
visited[src.getX()][src.getY()] = true;
q.enqueue(src); // Enqueue source cell
fullPath.add(src); // Add source to the full path
while (!q.isEmpty()) // Do a BFS starting from source cell
{
Square curr = q.front();
if (curr.getX() == dest.getX() && curr.getY() == dest.getY()) { // If we have reached the destination cell we are done
printCorrectPath(correctPath(fullPath));
return curr.getDistance();
}
q.dequeue(); // Otherwise dequeue the front cell in the queue and enqueue its adjacent cells
for (int i = 0; i < 4; i++){
int row = curr.getX() + rowNum[i];
int col = curr.getY() + colNum[i];
// if adjacent cell is valid, has path and not visited yet, enqueue it.
if (isValid(row, col) && mat[row][col] == 0 || mat[row][col] == 9 && !visited[row][col]){
mat[row][col] = 2;
visited[row][col] = true; // mark cell as visited and enqueue it
Square Adjcell = new Square(row,col, curr.getDistance() + 1 );
q.enqueue(Adjcell);
fullPath.add(Adjcell);
}
}
}
return -1; // Return -1 if destination cannot be reached
}
}
这是我进行测试的 class。
public class MazeRunner {
// Maze is a 2d array and it has to be filled with walls peripherally
// with walls so this algorithm can work. Our starting position in this
// will be (1,1) and our destination will be flagged with a 9 which in
// this occasion is (11,8).
private int[][] maze ;
private final List<Integer> path = new ArrayList<>();
public long startTime,stopTime;
public MazeRunner(int [][] maze){
this.maze = maze;
}
public void runBFSAlgorithm(int startingX,int startingY) throws QueueEmptyException, QueueFullException {
startTime = System.nanoTime();
BreathAlgorithm.searchPath(maze,new Square(startingX,startingY,0));
stopTime = System.nanoTime();
System.out.printf("Time for Breath First Algorithm: %.5f milliseconds.\n",(stopTime-startTime)*10e-6);
}
public void printMaze(){
for (int[] ints : maze) {
for (int anInt : ints) {
System.out.print(anInt + " ");
}
System.out.println();
}
}
public static void main(String[] args) throws FileNotFoundException, QueueEmptyException, QueueFullException {
int [][] maze = {{1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,1,0,1,0,1,0,0,0,0,0,1},
{1,0,1,0,0,0,1,0,1,1,1,0,1},
{1,0,0,0,1,1,1,0,0,0,0,0,1},
{1,0,1,0,0,0,0,0,1,1,1,0,1},
{1,0,1,0,1,1,1,0,1,0,0,0,1},
{1,0,1,0,1,0,0,0,1,1,1,0,1},
{1,0,1,0,1,1,1,0,1,0,1,0,1},
{1,0,0,0,0,0,0,0,0,0,1,9,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1}};
int[] startingPoint = {1,1};
MazeRunner p = new MazeRunner(maze);
p.printMaze();
p.runBFSAlgorithm(startingPoint[0],startingPoint[1]);
}
}
我的执行是这样的：
The execution output
给 Square 的实例一个额外的 属性: Square cameFrom;.
然后在你的 BFS 中更改：
q.enqueue(Adjcell);
至：
Adjcell.cameFrom = curr;
q.enqueue(Adjcell);
然后，更改 correctPath，使其以 dest 作为参数，并根据 cameFrom [=28] 形成的链表将路径构建为 ArrayList<Square> =].
然后只需颠倒此列表即可使其按正确的顺序排列。
我正在使用广度优先搜索算法来解迷宫。我的算法成功地找到了最短路径，但它没有存储最短路径。它只是告诉我完成这条路径所用的步数，但会保存所有已检查的方块，无论它们是否属于最短路径。我真的尝试了很多方法来存储最短路径，但我在路径中遇到错误，其中还包括不在最短路径中的方块。如果您能帮我找到一种将最短路径存储在 ArrayList 或 ArrayQueue 或数组或任何东西中的方法。 correctPath() 是我所做的，所以我可以决定哪些方块在最短路径中，但这是错误的。我认为这并不复杂，只是我不知道该怎么做。谢谢你的时间。
正方形具有 x 和 y 位置属性以及与目的地的距离。
public class BreathAlgorithm {
// Java program to find the shortest path between a given source cell to a destination cell.
static int ROW;
static int COL;
// These arrays are used to get row and column numbers of 4 neighbours of a given cell
static int[] rowNum = {-1, 0, 0, 1};
static int[] colNum = {0, -1, 1, 0};
// check whether given cell (row, col) is a valid cell or not.
static boolean isValid(int row, int col)
{
// return true if row number and column number is in range
return (row > 0) && (row <= ROW) && (col > 0) && (col <= COL);
}
// Checks if a square is an adjacent to another square
static boolean isNearSquare(Square a,Square b){
int x = 1;
int y = 0;
if((Math.abs((a.getX()+x) - (b.getX()+x))) + (Math.abs((a.getY()+y) - (b.getY()+y))) != 1){
return false;
}
x = -1;
y = 0;
if((Math.abs((a.getX()+x) - (b.getX()+x))) + (Math.abs((a.getY()+y) - (b.getY()+y))) != 1){
return false;
}
x = 0;
y = 1;
if((Math.abs((a.getX()+x) - (b.getX()+x))) + (Math.abs((a.getY()+y) - (b.getY()+y))) != 1){
return false;
}
x = 0;
y = -1;
return (Math.abs((a.getX() + x) - (b.getX() + x))) + (Math.abs((a.getY() + y) - (b.getY() + y))) == 1;
}
// returns the Square of the ending position
public static Square findEnd(int[][] mat){
for (int i=0;i<mat.length;i++){
for(int j=0;j<mat[0].length;j++){
if(mat[i][j] == 9)
return new Square(i,j,0);
}
}
return new Square(1,1,0);
}
/*
In this method i tried to define which squares are to be deleted from the fullPath
and return a new path with only the squares who are actually used in the shortest path.
This method doesn't work for all examples it just works for some so i guess it is lacking.
*/
public static ArrayQueue<Square> correctPath(ArrayList<Square> path) throws QueueFullException {
int i=0;
while(i<path.size()-1){
if (path.get(i).getDistance() == path.get(i+1).getDistance()){
if (path.get(i+2)!=null && path.get(i-1)!=null && (!isNearSquare(path.get(i),path.get(i+2)) || !isNearSquare(path.get(i),path.get(i+2)))){
path.remove(i);
}
else if (path.get(i+2)!=null && path.get(i-1)!=null && (!isNearSquare(path.get(i+1),path.get(i-1)) || !isNearSquare(path.get(i+1),path.get(i+2)))){
path.remove(i+1);
}
else if (!isNearSquare(path.get(i),path.get(i+1))){
path.remove(i);
}
}
i++;
}
ArrayQueue<Square> correctPath = new ArrayQueue<>(path.size());
while(i>=0){
correctPath.enqueue(path.get(i));
i--;
}
return correctPath;
}
static void printCorrectPath(ArrayQueue<Square> correctPath) throws QueueEmptyException {
Square[] originalPath = new Square[correctPath.size()];
for(int i=originalPath.length-1;i>=0;i--){
originalPath[i] = correctPath.dequeue();
}
int i=0;
while(i<originalPath.length-1){
if(i == 0) System.out.println(originalPath[i]+" is the starting point.");
System.out.println("From "+originalPath[i]+"to "+originalPath[i+1]);
i++;
if(i == originalPath.length-1) System.out.println(originalPath[i]+" is the ending point.");
}
}
public static void searchPath(int[][] mat,Square start) throws QueueEmptyException, QueueFullException {
//mat is the maze where 1 represents a wall,0 represent a valid square and 9 is the destination
// When a square is visited from 0 it becomes a 2
ROW=mat.length;
COL=mat[0].length;
Square dest = findEnd(mat); // search for the number 9 and make a new Square and put it in dest
int dist = BFS(mat, start, dest); // find the least distance
if (dist != Integer.MAX_VALUE)
System.out.println("\nShortest Path is " + dist+" steps.");
else
System.out.println("Shortest Path doesn't exist");
}
// function to find the shortest path between a given source cell to a destination cell.
static int BFS(int[][] mat, Square src, Square dest) throws QueueFullException, QueueEmptyException {
ArrayList<Square> fullPath = new ArrayList<>(); // path of all the squares checked
boolean [][]visited = new boolean[ROW][COL]; // if a square is visited then visited[x][y] = true
ArrayQueue<Square> q = new ArrayQueue<>(mat.length*mat[0].length); // Create a queue for BFS
// check source and destination cell of the matrix have value 1
if (mat[src.getY()][src.getX()] != 0 || mat[dest.getX()][dest.getY()] != 9) {
return -1;
}
mat[src.getY()][src.getX()] = 2; // Mark the source cell as visited
visited[src.getX()][src.getY()] = true;
q.enqueue(src); // Enqueue source cell
fullPath.add(src); // Add source to the full path
while (!q.isEmpty()) // Do a BFS starting from source cell
{
Square curr = q.front();
if (curr.getX() == dest.getX() && curr.getY() == dest.getY()) { // If we have reached the destination cell we are done
printCorrectPath(correctPath(fullPath));
return curr.getDistance();
}
q.dequeue(); // Otherwise dequeue the front cell in the queue and enqueue its adjacent cells
for (int i = 0; i < 4; i++){
int row = curr.getX() + rowNum[i];
int col = curr.getY() + colNum[i];
// if adjacent cell is valid, has path and not visited yet, enqueue it.
if (isValid(row, col) && mat[row][col] == 0 || mat[row][col] == 9 && !visited[row][col]){
mat[row][col] = 2;
visited[row][col] = true; // mark cell as visited and enqueue it
Square Adjcell = new Square(row,col, curr.getDistance() + 1 );
q.enqueue(Adjcell);
fullPath.add(Adjcell);
}
}
}
return -1; // Return -1 if destination cannot be reached
}
}
这是我进行测试的 class。
public class MazeRunner {
// Maze is a 2d array and it has to be filled with walls peripherally
// with walls so this algorithm can work. Our starting position in this
// will be (1,1) and our destination will be flagged with a 9 which in
// this occasion is (11,8).
private int[][] maze ;
private final List<Integer> path = new ArrayList<>();
public long startTime,stopTime;
public MazeRunner(int [][] maze){
this.maze = maze;
}
public void runBFSAlgorithm(int startingX,int startingY) throws QueueEmptyException, QueueFullException {
startTime = System.nanoTime();
BreathAlgorithm.searchPath(maze,new Square(startingX,startingY,0));
stopTime = System.nanoTime();
System.out.printf("Time for Breath First Algorithm: %.5f milliseconds.\n",(stopTime-startTime)*10e-6);
}
public void printMaze(){
for (int[] ints : maze) {
for (int anInt : ints) {
System.out.print(anInt + " ");
}
System.out.println();
}
}
public static void main(String[] args) throws FileNotFoundException, QueueEmptyException, QueueFullException {
int [][] maze = {{1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,1,0,1,0,1,0,0,0,0,0,1},
{1,0,1,0,0,0,1,0,1,1,1,0,1},
{1,0,0,0,1,1,1,0,0,0,0,0,1},
{1,0,1,0,0,0,0,0,1,1,1,0,1},
{1,0,1,0,1,1,1,0,1,0,0,0,1},
{1,0,1,0,1,0,0,0,1,1,1,0,1},
{1,0,1,0,1,1,1,0,1,0,1,0,1},
{1,0,0,0,0,0,0,0,0,0,1,9,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1}};
int[] startingPoint = {1,1};
MazeRunner p = new MazeRunner(maze);
p.printMaze();
p.runBFSAlgorithm(startingPoint[0],startingPoint[1]);
}
}
我的执行是这样的：
The execution output
给 Square 的实例一个额外的 属性: Square cameFrom;.
然后在你的 BFS 中更改：
q.enqueue(Adjcell);
至：
Adjcell.cameFrom = curr;
q.enqueue(Adjcell);
然后，更改 correctPath，使其以 dest 作为参数，并根据 cameFrom [=28] 形成的链表将路径构建为 ArrayList<Square> =].
然后只需颠倒此列表即可使其按正确的顺序排列。