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

àì夳堔傛蜴生んèń 2022-07-13 08:23 148阅读 0赞

以一个m×n的0-1矩形阵表示迷宫，其中0和1分别表示迷宫中的通路和障碍。请用分支限界法设计一个算法，对任意设定的m×n迷宫，求出一条从入口到出口的通路，或得出没有通路的结论；如果有通道，请输出具有最短路径的通道。一个输入实例如下图所示：  
/![这里写图片描述][SouthEast]  
(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;
            }
    
        }

![这里写图片描述][SouthEast 1]

[SouthEast]: /images/20220713/7ff8665764ae40078e1b7a2df11a51c8.png
[SouthEast 1]: /images/20220713/c1878a8b69834cdb9046900e16076c4f.png