队列的应用提问

august

     关于队列里有这么一道例题 : 解迷宫问题:迷宫是如图示的m行n列的0-1矩阵,其中0表示无障碍,1表示有障碍.设入口为(1,1),出口为(m,n) , 每次移动只能从一个无障碍的单元移到其周围8个方向上任一无障碍的单元.
列号---->  1  2  3  4  5
行号-->1|  0  0  0  1  0
             2|  0  1  0  0  0
             3|  0  0  1  0  1
             4|  1  1  0  1  0
             5|
使用这样的数据结构:用数组mg[1..m, 1..n]表示迷宫,为了算法方便, 在四周加上一圈"哨兵",即变为数组
mg[0...m+1, 0...n+1]表示迷宫, 用数组zx, zy 分别表示 X, Y 方向的移动增量,如图示, 使用一个队列queue记录走过的点, 并用变量front, rear分别表示队列的首与尾.
队列的结构如下:
struct stype
{
            int   x, y,pre   /*x,y为点的坐标, pre为到达本点的上一步步号*/
} queue[MaxSize];


图2:
方向    北    东北   东   东南   南   西南   西     西北
下标    1            2          3          4         5         6          7             8
zx            -1           -1         0          1         1         1          0            -1
zy             0            1         1           1         0         -1        -1          -1

算法搜索过程: 首先从(1,1)处开始搜索,将其周围8个方向可走(为0值)的点均插入到队列queue中,pre为到达本点的上一步步号,也就是当前的front之值,并将该点赋值为-1,避免回来重复搜索.如果其中某点是出口,算法结束,根据 rear 指示的前驱步号可回溯得到走迷宫的最短路径;否则从队列 删除一个点,进入下一步,同样将其周围8个方向可走的点插入到队列中,  pre为到达本点的上一步步号,也就是当前的front之值,并将该点赋值为-1,避免回来重复搜索.如果其中某点是出口,算法结束,根据 rear 指示的前驱步号可回溯得到走迷宫的最短路径;否则从队列 删除一个点,进入下一步 ,直到循环算法结束,如果queue队列中没有元素且末找到出口,则表示不存在路径.

图3:迷宫路径搜索过程
步号          x                    y                       pre
1                        1                   1                         0
2                        1                   2                          1
3                        2                   1                          1
4                        1                   3                          2
5                         2                  3                          2
6                         3                   2                         3
7                         3                   1                         3
8                          2                  4                         4
9                         3                   4                         5
10                      4                    3                        6
11                      1                    5                         8
12                      2                   5                          8
13                     4                     5                         9
14                     5                    3                          10
15                    5                      2                         10
16                      5                    5                           13

程序如下:

2. #include<stdio.h>
3. #define m 5
4. #define n 5
5. #define MaxSize 100
6. struct stype
7. {
8.     int x,y,pre;
9. }queue[MaxSize];
10. int mg[m+1][n+1];
11. int zx[8],zy[8];
12. void printlj(int rear)
13. {
14.     int i=rear,j;
15.     do                      /*反向找到最短路径,将路径上点的pre成员设置成-1*/
16.     {
17.         j=i;
18.         i=queue[i].pre;
19.         queue[j].pre=-1;
20.     }
21.     while (i!=0);
22.     printf("search the maze road:\n\t entry->");
23.     i=0;
24.     while(i<MaxSize)            /*正向搜索pre为-1的点,构成正向路径*/
25.     {
26.         if(queue[i].pre==-1)
27.             printf("(%d,%d)->",queue[i].x,queue[i].y);
28.         i++;
29.     }
30.     printf("exit\n");
31. }
32. void mglj()
33. {
34.     int i,j,x,y,v,front,rear,find=0;
35.     queue[1].x=1;queue[1].y=1;queue[1].pre=0;  /*从(1,1)开始搜索,将该点插入队列*/
36.     front=1;rear=1;                         /*队列指针置初值1*/
37.     mg[1][1]=-1;                             /*将其赋值-1,避免回来重复搜索*/
38.     while(front<=rear && !find)     /*队列不为空且末找到路径时循环*/
39.     {
40.         x=queue[front].x;
41.         y=queue[front].y;
42.         for(v=1;v<=8;v++)           /*循环扫描每个方向,把每个可走方向插入队列*/
43.         {
44.             i=x+zx[v];j=y+zy[v];     /*选择一个前进方向(i,j) */
45.             if(mg[i][j]==0)            /*如果该方向可走*/
46.             {
47.                 rear++;       /*将该方向插入队列*/
48.                 queue[rear].x=i;  /*将其赋值-1,避免重复搜索*/
49.                 queue[rear].y=j;
50.                 queue[rear].pre=front;
51.                 mg[i][j]=-1;
52.             }
53.             if(i==m && j==n)     /* 找到出口*/
54.             {
55.                 printlj(rear);  /*打印找到的路径*/
56.                 find=1;           /*设置为1退出循环*/
57.             }
58.         }
59.         front++;               /*从队列中删除一个元素*/
60.     }
61.     if(!find) printf("no presence!\n");
62. }
63. void main()
64. {
65.     int i,j;
66.     for(i=1;i<=m;i++)
67.         for(j=1;j<=n;j++)       /*获取迷宫数据, 自己输入*/
68.         scanf("%d",&mg[i][j]);
69.     for(i=0;i<=m+1;i++)
70.     {
71.         mg[i][0]=1;mg[i][n+1]=1;   /*加上为1的外框*/
72.     }
73.     for(j=0;j<=n+1;j++)
74.     {
75.         mg[0][j]=1;mg[m+1][j]=1;
76.     }
77.     zx[1]=-1;zx[2]=-1;zx[3]=0;zx[4]=1;                /*建立方向数据*/
78.     zx[5]=1;zx[6]=1;zx[7]=0;zx[8]=-1;
79.     zy[1]=0;zy[2]=1;zy[3]=1;zy[4]=1;
80.     zy[5]=0;zy[6]=-1;zy[7]=-1;zy[8]=-1;
81.     mglj();                                                         /*产生迷宫路径
82. }

复制代码

问题:
1.首先对这程序的实现很难理解,不知从何入手,
2.开始时他所说的加上一圈"哨兵"是什么意思呢?
3.为什么要设图2 这样的移动增量?
4.图3的搜索过程怎么理解呢?
5.在mglj() 函数中为什么要用 front++ 来删除数据呢?
6.main函数里为什么要加上什么 1的外框?
7.他的结果(1,1)->(1,2)->(2,3)->(3,4)->(4,5)->(5,5)  到底是怎么判断得到的??

rednaxela

总体来说,这是一个广度优先的搜索算法.
1. 画个图就清楚了,跟随算法步骤在图上用纸笔和大脑来算
2. 这是硬翻的英语了...原文是sentinel,就是一种表示"无效""不存在"的值,作为错误或边界的检查条件之类.在这里,设置成任意非0的值意味着是障碍,所以任意非0的值都可以作为"哨兵". (这词用中文说真不习惯 =_=
3. 为了代码整洁.完全可以用if...else或者switch代替,但现在的这种做法属于table-driven的一种表现,代码更容易维护
4. 参考1.
5. 在mglj()的while循环里有

1. x=queue[front].x;
2. y=queue[front].y;

复制代码

这就是说每次都用队列的头的数据来获取当前步的数据.在while循环中的最后一句之后,进到下次循环前,要更新循环量.所以要把头从当前节点向后移到下次的头.结果就是删除了队列原本的头(注意到队列的FIFO性质)
6. 参考2.
7. 参考1

august

还有这里,这个 zx[8] , zy[8]  关于这两个数组的赋值, 为什么它们去到 zx[8]=-1,  zy[8]=-1
这样为啥不会出错呢?这不是下标越界了吗 [s:6]

rednaxela

引用第2楼august于2007-11-03 16:32发表的  :
还有这里,这个 zx[8] , zy[8]  关于这两个数组的赋值, 为什么它们去到 zx[8]=-1,  zy[8]=-1
这样为啥不会出错呢?这不是下标越界了吗 [s:6]

呵呵，这确实值得吐槽。要是声明为zx[9], zy[9]会比较安全（更好还是遵循0起始的下标）。
至于为什么不会出错，其实这种小范围的越界很难引发立即的、明显的错误。很有可能很长时间都不会出错。即便如此也不应该容许自己的代码有不安全的地方，除非你清楚知道自己这么做的理由（例如有时候会申请长度为1的数组然后故意越界之类）

august

我还想问问,上面的 queue[1].x=1, queue[1].y=1,  在以后是 queue[front].x,  那么当 queue[2].x
queue[2].y,  的时候,它怎么确定,它们的值是多少呢?

august

哦,偶知道了,不好意思 [s:7]