算法6.分支限界法下的迷宫游戏

以一个m×n的0-1矩形阵表示迷宫，其中0和1分别表示迷宫中的通路和障碍。请用分支限界法设计一个算法，对任意设定的m×n迷宫，求出一条从入口到出口的通路，或得出没有通路的结论；如果有通道，请输出具有最短路径的通道。一个输入实例如下图所示：
/
(1) 算法设计思路
先定义指标如果向右移动，则row=0，col=1，如果先左移动，则row=-1，col=0，先上移动则，row=0，col=-1，先下移动则，row=0，col=1；然后对当前的位置进行上下左右的搜索，如果搜索到对应位置的数值为0时，对应位置的数值=当前位置的数值+1，一直循环下去直到当前位置的row和col=目标位置的row和col。然后利用循环回溯，依次标记可以移动的相邻位置，再判断该位置是否可以移动，不可以移动时判断是否到终点，是否无解，如果都不是就取下一个节点，如果是可以移动的位置，则根据上下左右的标记进行判断，为0则将该位置是数值赋值为上一个位置的值+1

(2) 算法实现的伪代码及其计算时间复杂度分析
求解迷宫老鼠游戏的算法Find(Position start,Position end)
输入：起始位置的坐标，终点位置的坐标
输出：如果有解，则输出最短可行路径，无解则输出-1

s1:  初始化相对位移，posit[] offset=new positon[4]
s2:  右初始化为position（0,1）
s3: 下初始化为position（1,0）
s4: 左初始化为position（0,-1）
s5: 上初始化为position（-1,0）
s6: 初始化起始位置的坐标 position here=new position(start.row,start.col)
s7: 初始化起始位置的距离为2,x[start.row][start.col]=2
s8: 创建一个队列q存放position
s9: position nbr=new position(0,0)
s10: do {标记可达相邻位置
s11: for (inti =0 to 3)
s12: begin nbr.col=here.cor+offset[i].col;
s13: nbr.row=here.row+offset[i].row;
s14: if (当前的行，列不越界并且要到达的位置为0)
s15: begin x[nbr.row][nbr.col] = x[here.row][here.col] + 1
s16: if (当前行，列到终点行，列) break;
s17: else q.add(new position(nbr.row,nbr.col));
s18: end if 
s19: end for
s20: if (当前行，列到终点行，列) break;
s21: if 队列为空，返回-1,无解
s22: else 取下一个扩展结点here=(position)q.remove();
s23: }while (true)
s24: 构造最短迷宫路径
s25: pathlen=x[start.row][start.col]-2;
s26: path=new position[pathlen];
s27: here=new position(end.row,end.col)
s28: for (inti =pathlen-1 to 0){
s29: begin path[i]=new position(here.row,here.col)
s30: for (int j=0 to 3){
s31: begin nbr.row=here.row+offset[i].row;
s32: nbr.col=here.col+offset[i].col;
s33: if当前的行，列不越界并且要到达的位置为2 
s34: break;
s35: end for 
s36: end fo;
s37: here=new position(nbr.row,nbr.col)

算法fucntionA的计算时间复杂度分析：
O（mn）

(3) 实验代码及运行结果

import java.util.LinkedList;
import java.util.Queue;
public class 迷宫游戏 {
private static int[][] x = { { 0, 1, 1, 1, 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 1, 0, 0 }, { 0, 0, 0, 1, 0, 1, 0, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 1, 0 }, { 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 },
{ 0, 1, 1, 1, 0, 1, 0, 1, 0, 1 }, { 0, 1, 0, 0, 0, 1, 0, 1, 0, 1 },
{ 0, 1, 0, 1, 1, 1, 0, 1, 0, 0 }, { 1, 0, 0, 0, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 } };
private static int pathlen = 0; // 最短线路长度
private static position path[] = null;
public static int findPath(position start, position end) {
// 初始化相对位移
position[] offset = new position[4];
offset[0] = new position(0, 1);// right
offset[1] = new position(1, 0);// down
offset[2] = new position(0, -1);// left
offset[3] = new position(-1, 0);// up
position here = new position(start.row, start.col);
x[start.row][start.col] = 2; // 起始位置的距离
int numOfNbrs = 4;
// 标记可达位置
Queue<position> q = new LinkedList<position>();
position nbr = new position(0, 0);
do {// 标记可达相邻方格
for (int i = 0; i < numOfNbrs; i++) {
nbr.col = here.col + offset[i].col;
nbr.row = here.row + offset[i].row;
if (nbr.row >= 0 && nbr.col >= 0
&& (nbr.row <= 9 && nbr.col <= 9)
&& x[nbr.row][nbr.col] == 0) {// 读方格未标记
//
System.out.print(nbr.row + " ");
//
System.out.print(nbr.col + " ");
x[nbr.row][nbr.col] = x[here.row][here.col] + 1;
//
System.out.println(x[nbr.row][nbr.col]);
if ((nbr.row == end.row) && (nbr.col == end.col)) {
break;// 完成
} else {
q.add(new position(nbr.row, nbr.col));
// 这里要将新创建的结点放进去，而不能直接q.add(nbr)，因为这样是将q中的
// 对象引用和nbr指向同一个对象，后续如果改变nbr，将会影响到q中的对象。
}
}
}
if ((nbr.row == end.row) && (nbr.col == end.col))
break; // 完成
if (q.isEmpty())
return -1; // 无解
else {
here = (position) q.remove(); // 取下一个扩展结点
}
} while (true);
//构造最短迷宫路径
pathlen = x[end.row][end.col] - 2;
//System.out.println(pathlen);
path = new position[pathlen];
//从目标位置end开始向前回溯
here = new position(end.row, end.col);
for (int i = pathlen - 1; i >= 0; i--) {
path[i] = new position(here.row, here.col);
//找前驱位置
for (int j = 0; j < 4; j++) {
nbr.row = here.row + offset[j].row;
nbr.col = here.col + offset[j].col;
if (nbr.row >= 0 && nbr.col >= 0
&& (nbr.row <= 9 && nbr.col <= 9)
&& x[nbr.row][nbr.col] == i + 2) {
break;
}
}
here = new position(nbr.row, nbr.col);//先、前移动
}
return x[end.row][end.col] - 2;
}
public static void main(String[] args) {
position start = new position(0, 0);
position finish = new position(9, 9);
findPath(start, finish);
System.out.println("最短路劲为:入口(1,1)->");
for (int i = 0; i < 36; i++){
if (i%6==5)
System.out.println("("+(path[i].row+1) + "," + (path[i].col+1)+")"+"->");
else
System.out.print("("+(path[i].row+1) + "," + (path[i].col+1)+")"+"->");
}
}
}
class position {
public int col, row;
public position(int r, int c) {
this.col = c;
this.row = r;
}
}

最后

以上就是无情红酒为你收集整理的算法6.分支限界法下的迷宫游戏的全部内容，希望文章能够帮你解决算法6.分支限界法下的迷宫游戏所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。