BFS(广度优先搜索)解决迷宫问题(JAVA实现)
程序员文章站
2022-05-22 21:00:03
...
问题:
迷宫问题:现有一个M*N的方阵,其中有若干个路障,先要求求出从出发点S到终点E的最短路径,跨越每个方格的时间固定,均为1。
思路:
本题的解答可以用广度优先搜索(BFS)来做,广度优先搜索本质上是动态规划的一种应用,先求出算法第一步中所有的可行解,然后对解空间中的每一个可行解依次执行算法的下一个步骤,从而得到一个新的解空间。最后得到若干个(或一个)可行解。
对于本题来说,先通过起点求出所有一步(STEP1)内可以直接达到的位置,将其全部存入队列,由于队列存取数据先进先出的特点,遍历得到的新的解空间总是依次存放在上一步解空间(STEP1)最后一个解后面,所以可以达到先遍历出算法上一步(STEP1)解空间所有解,然后再将每一个解对应的新的解空间(STEP2)依次加入队列的效果。然后对新的解空间实行上述操作,直到得到的解空间中存在终点为止。
注意事项:
1,对于每一个点设置一个标记,用来标记是否来过(flag)。如果来过,说明已经对该解已经加入过队列进行运算,再次运算无法得到更优的解,故直接舍弃,转而判断下一个解。
2,此种方法一旦得到的解一定是最优解。为何? 根据动态规划的原理,问题被分为了相同单位时间相同的若干步。每一步都可以得到当前情况下所有的可行解,所以相当于涵盖了问题所有的解空间,其中一定含有最优解的路径。而遍历到整个答案的可行解时,这表示这是用最短步数(时间)达到的可行解,即最优解。由一1也可知即使回溯到上一步也无法找到更优的解法。
代码如下:
首先对每个节点设置属性:
package sort;
public class block {
private boolean flag;//是否来过,默认为false
private int value;//该点是通路还是路障
private int x;//该点横坐标
private int y; //该点纵坐标
private int howfar;//该点距离起点的距离
public int getHowfar() {
return howfar;
}
public void setHowfar(int howfar) {
this.howfar = howfar;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public boolean getFlag() {
return flag;
}
public void setFlag(boolean flag) {
this.flag = flag;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
BFS求迷宫最短路径
public class Harrystair {
private final static int maplength = 5;
private final static int mapweigth = 5;
static block[][] map = new block[maplength][mapweigth];
static int distance;
static ArrayBlockingQueue<block> q = new ArrayBlockingQueue<>(25);
block rightblock = new block();
block leftblock = new block();
block upblock = new block();
block downblock = new block();
private void start(int[][] maptest) {
// 初始化地图
for (int x = 0; x <= maplength - 1; x++)
for (int y = 0; y <= mapweigth - 1; y++) {
map[x][y] = new block();
map[x][y].setFlag(false);
map[x][y].setX(x);
map[x][y].setY(y);
map[x][y].setHowfar(0);
map[x][y].setValue(maptest[x][y]);
q.offer((block) map[0][0]);
}
}
private int findway() {
// 队列非空时
while (!q.isEmpty())
//是否到达终点 到达就脱离循环
{ if( (map[maplength-1][mapweigth-1]).equals(q.element()))
{
block f=(block)q.element();
distance = f.getHowfar();
// System.out.println("到了");
break;
} 将已经到达的点移出队列
block b = (block) q.poll();
//System.out.println(b.getX()+" "+b.getY());
if (b.getFlag() == true)
continue;
获取从该点可以直接到达的节点
{
if (b.getX()>=0&&b.getX()<=maplength-2&&b.getY()>=0&&b.getY()<=maplength-1) {
rightblock = map[b.getX() + 1][b.getY()];
dealway(rightblock,b);
}
if (b.getX()>=1&&b.getX()<=maplength&&b.getY()>=0&&b.getY()<=maplength-1) {
leftblock = map[b.getX() - 1][b.getY()];
dealway(leftblock, b);
}
if (b.getX()>=0&&b.getX()<=maplength-1&&b.getY()>=0&&b.getY()<=maplength-2) {
upblock = map[b.getX()][b.getY() + 1];
dealway(upblock, b);
}
if (b.getX()>=0&&b.getX()<=map.length-1&&b.getY()>=1&&b.getY()<=maplength) {
downblock = map[b.getX()][b.getY() - 1];
dealway(downblock, b);
}
b.setFlag(true);
}
}
return distance;
}
//对节点进行判断并修改
private void dealway(block b, block forntb) {
if (b.getValue() != 1&&b.getFlag()!=true) {//判断该点能否通行
q.offer(b);//将接口加入队列
b.setHowfar(forntb.getHowfar()+1);//向下走一步,距离起点加一
System.out.println(b.getX()+" "+b.getY());
}
}
public static void main(String[] args) {
Harrystair h = new Harrystair();
int[][] map = { { 0, 0, 0, 0,1 }, { 1, 1, 1, 0,1 }, { 1, 0, 0, 0,1 }, { 1, 0, 1, 0,1 },{1,0,0,0,0} };
h.start(map);
System.out.println(h.findway());
}
}
推荐阅读
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
算法学习之BFS广度优先搜索(java版)
-
PHP实现广度优先搜索算法(BFS,Broad First Search)详解
-
python实现图的深度优先搜索(DFS)和广度优先搜索(BFS)算法及Dijkstra最短路径应用
-
详解Java利用深度优先遍历解决迷宫问题
-
算法图解-广度优先搜索-芒果销售商(Java实现)
-
图的深度优先搜索(DFS)和广度优先搜索(BFS)及其Java实现
-
深度优先搜索(DFS)与广度优先搜索(BFS)简单实现
-
C++实现BFS(广度优先搜索算法)
-
利用Python实现广度优先搜索BFS