基于栈和队列的迷宫问题求解

LastRain

发布日期: 2018-11-06 12:00:00 浏览量: 2708
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

问题描述

以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。

测试数据

迷宫的测试数据如下:左上角(1, 1)为入口,右下角(8, 9)为出口。

一、需求分析

值得注意的是,题目要求中的测试数据给的是右下角(8,9),这个表述可能偏向口语化,是先写列,再写行,这和数学中矩阵元素的表示方法是相反的,从而对我来说有很大的误导作用(原书105页写的是(8,9),而106页写的是(9,8)),为了避免不必要的误解,特别规定右下角那个元素坐标为(9,8),即,采用约定俗成的矩阵元素的那种先行后列的表达方法。

需求

  • 求出至少一条路径

  • 求出从用户输入的起点到终点的最短路径

  • 求出最短路径所走步数

  • 动态演示:在走错路要回退时要用颜色标出

二、算法设计

QRstack.h中栈stack的成员函数介绍

  1. template <typename T> class stack
  2. {
  3. public:
  4. stack();
  5. bool empty(); // 堆栈为空则返回真
  6. void pop(); // 移除栈顶元素
  7. T push(T e); // 在栈顶增加元素
  8. T top(); // 返回栈顶元素
  9. private:
  10. typedef stack* LinkStack;
  11. stack *link;
  12. T data;
  13. LinkStack tianze;
  14. };

QRqueue.h中queue的成员函数介绍

  1. template <typename T>class queue
  2. {
  3. public:
  4. queue();
  5. void push(T e); // 进队列
  6. void pop(); // 元素出队列
  7. T front1(); // 返回队列的第一个元素
  8. T back();
  9. bool empty(); // 返回的布尔值判空
  10. int size(); // 返回值队列长度
  11. typedef struct qnode{
  12. T data;
  13. struct qnode *next;
  14. }qnode;
  15. private:
  16. typedef qnode *queuePtr;
  17. queuePtr front;
  18. queuePtr rear;
  19. };

2.1 迷宫求解核心算法设计

  • DFS栈 depth_first search

  • WFS队列width_first search

栈的算法框架

  1. while 栈不空
  2. 弹出栈顶元素作为当前方向继续探索
  3. 求出下一探查位置
  4. if next postion 是出口,跳出循环,结束
  5. if next postion 尚未探查,将当前位置入栈并退出内层循环

基于栈的(略细化):

  1. do{
  2. 若可通
  3. (显示)
  4. 当前状态入栈、
  5. 若已达终点,直接跳出,结束战斗
  6. 不行还往下走,换个状态(或换个方向或换个位置)
  7. 若此路不通但还有待搜素的状态
  8. 把当前状态弹出来
  9. while栈不空
  10. (栈空意味着已经探索完所有可探索的位置)

队列的算法框架

  1. do{
  2. 取出一个位置 pos
  3. 检查pos的相邻位置
  4. 遇到end成功结束
  5. 尚未探查的都标记入队
  6. }while队列不空
  7. // 队列空,探索失败

详细设计

  1. void MiGong::MazePathQueue()
  2. {
  3. queue<ElemType> q;
  4. ElemType e;
  5. stack <TempType> Tv;
  6. TempType tv;
  7. do{
  8. if(Pass()){
  9. FootPrint();
  10. system("cls");
  11. Display();
  12. //CURRECTWAYTIME means the milliseconds the system will pause in this condition
  13. Sleep(CORRECTWAYTIME);
  14. e.seat.r=curpos.r;
  15. e.seat.c=curpos.c;
  16. e.di=don;
  17. q.push(e);
  18. if(Same())
  19. goto end;
  20. else{
  21. tv.prior=e;
  22. tv.current=NextPos(e);
  23. Tv.push(tv);
  24. }
  25. }
  26. else if(!q.empty())
  27. {
  28. e=q.front1();
  29. q.pop();
  30. //与栈结构算法最大的不同就在此处
  31. //栈若走错需要在地图上标记,并且把结点从栈中弹出
  32. //而队列不需要此过程,队列是探索结束后再回溯
  33. /*
  34. //这里被注释掉的代码正是队列与栈不相同的部分
  35. while(e.di==4&&!q.empty())
  36. {
  37. MakePrint(e);
  38. e=q.front();
  39. q.pop();
  40. }
  41. */
  42. if(e.di<4){
  43. e.di=Xia(e.di);
  44. q.push(e);
  45. //prior和current分别记录前一步和当前状态,以备回溯
  46. tv.prior=e;
  47. tv.current=NextPos(e);
  48. Tv.push(tv);
  49. }
  50. }
  51. }while(!q.empty());
  52. cout<<"fail!"<<endl;
  53. end:
  54. cout<<"Thank you for watching!"<<endl;
  55. cout<<"Start:"<<"("<<start.r<<","<<start.c<<")"<<endl;
  56. cout<<"End :"<<"("<<end.r<<","<<end.c<<")"<<endl;
  57. //////////////////////////////////////////////////
  58. Traceback(Tv);
  59. //回溯,输出最短的路径序列
  60. }

队列的回溯其实也是比较繁琐的,在此说明回溯原理:每一时刻保存当前状态和前一步状态,对每一时刻来说,当前状态必然是另一时刻的前一步状态,找到这个对应的时刻然后如法炮制,直到追踪到起点为止,这样就找到最短路径。

  1. //用于队列结构的回溯的Traceback函数
  2. void Traceback(stack<TempType> &Tv)
  3. {
  4. stack<ElemType> Path;
  5. ElemType now,before;
  6. TempType temp;
  7. now=Tv.top().current;
  8. before=Tv.top().prior;
  9. Path.push(now);
  10. bool a=0;
  11. bool b=0;
  12. while(!Tv.empty())
  13. {
  14. temp=Tv.top();
  15. if(temp.current.seat.r==before.seat.r)
  16. a=1;
  17. else a=0;
  18. if(temp.current.seat.c==before.seat.c)
  19. b=1;
  20. else b=0;
  21. if(a&&b)
  22. {
  23. Path.push(before);
  24. before=temp.prior;
  25. }
  26. Tv.pop();
  27. }
  28. cout<<"The shortest Path:"<<endl;
  29. Voice(Path);
  30. system("pause");
  31. }

2.2 数据类型说明

2.2.1 状态数据类型

某一时刻状态由此时位置和此时将要迈向的方向共同决定

坐标位置类型

  1. //位置类型
  2. typedef struct {
  3. int r;//位置所在行
  4. int c;//位置所在列
  5. }PosType;

方向的东南西北枚举类型

  1. enum direction{don=1,nan=2,xi=3,bei=4};
  2. //某一时刻状态
  3. typedef struct {
  4. PosType seat;//此时所在位置
  5. direction di;//此时将要迈向的方向
  6. }ElemType;

迷宫类型

  1. //迷宫类型
  2. typedef struct {
  3. int m,n; //m迷宫行数(长),n迷宫列数(宽)
  4. char arr[RANGE][RANGE]; //迷宫字符矩阵
  5. }MazeType;

暂时记录类型

  1. //暂时类型TempType是探索出最短路径后由最后一步回溯时用到的缓存结构
  2. typedef struct {
  3. ElemType prior;//前一步状态(位置和方向)
  4. ElemType current;//当前状态(位置和方向)
  5. }TempType;

一些全局变量

  1. 数组shortPath[100]用来保存用队列求出的最短路径
  2. step用来记录最短路径的步数
  3. PosType shortPath[100];
  4. int step=0;
  5. RANGE 20//迷宫矩阵的边长最大值
  6. //the max size of char arr[][]
  7. CORRECTWAYTIME 20//在演示时走正确的路时暂停时间(毫秒)
  8. //Recommended value of CORRECTWAYTIME 200
  9. WRONGWAYTIME 20//在演示时回退时暂停时间(毫秒)
  10. //Recommended value of WRONGWAYTIME:2000

3 调试分析

3.1 调试分析

3.1.1 关于STL

为了使自己写的关于栈和队列的头文件更通用,我查了一下STL中关于stack和queue模板的用法,到VC6看了STL中queue和stack的源代码,不过源代码是长这样的,根本看不懂,所以我决定以STL中stack和queued的用法作为我编程的要求,最后实现和STL一样的功能。实现期间当然遇到很多困难,其中最难写的是栈和队列的构造函数。

3.1.2 链表节点的插入

调试过程中遇到很多问题,首先我先写好QRstack.h和QRqueue.h,不断对它测试,确保它们基本能够达到和STL中stack模板和queue模板一样的效果,然后写栈的核心算法,但是当我主函数调用栈和队列的时候,却总在迷宫的一个角落打转,我以为算法写错了,折腾了很长时间,最后终于发现queue.push()函数有问题,归根结底是链表节点指针指错了,可见基础的重要性。

3.1.3 关于VB.net

写完c程序后,一直想加个界面,但不知道用什么写界面好。开始时尝试MFC,不过MFC过于复杂,就算画个圆都很难,而且只要一个地方写错,能导致很多附带的错误。后来尝试用matlab做界面,这个相对简单一点,不过仍然很难。最后我去请教老师,老师推荐我用VB或者delphi.delphi的开发环境近十个G,我的电脑C盘快满了,再装可能吃不消,另外delphi没有VB这么流行,于是选择了VB。

可能学VB最常用的环境是VB6.0,VB6固然轻量,但是开发出来的东西只能是Windows 98的风格,颜值不高。之前我为了学C语言,电脑里装了VS2010,用它来编译我那种helloworld级别的程序是大材小用,所以平时基本不用,这次终于派上了用场。用Visual studio2010,开发VB.net有几个好处:

  • 一是程序风格是Windows 10风格

  • 二是基于.NET Framework 方便调用系统资源,方便调用其它语言写的函数

  • 三是VB.net和C#.net有很多相似之处,我常有学C#的打算,但C#比较难学,VB.net可作为我熟悉.NET的一个跳板,为日后学C#打基础

下定决心选择了VB.net,不过我从来没有接触过VB,到底能不能做心里也没有底,从图书馆借了几本VB书,翻了一翻,发现它们要么是内容陈旧(VB6.0),要么是面向非计算机专业的,对文件操作这一章要么干脆不谈,要么浅尝辄止,而通过文件操作来传参数恰恰是我最需要的。图书馆的书大多是关于C++和java的,要找一本关于VB.net的比较新的书非常困难。我不断寻找,终于找到一本王栋编写的《VB.net程序设计》,非常高兴。于是周六早上坐进图书馆,拿着书一边学习VB,一边开发我的迷宫求解VB界面程序,这样从早搞到晚,整整两天,终于弄出来了。其过程也遇到不少麻烦,比如设置绝对路径和相对路径问题,数组越界问题,限于篇幅,不再展开。

3.1.4 Windows API

控制台黑底白字,看迷宫十分费力,如何更清楚地显示,以方便调试,查了一下相关的windows API 技术文档,实现了彩色控制台迷宫。

比如在hello world程序里加上这么一句话就能实现红色的helloworld,(注意,这句话的好处在于它可以控制单个字符的颜色,而不是整个屏幕的颜色)

  1. SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_RED);

3.1.5 关于树结构

写了栈和队列以后,我想,学的那几种结构都用到了,就差二叉树了,我能不能使用树结构呢.迷宫问题从起点开始,下一个位置分别是东南西北四个状态,对下一个位置又分别对应东南西北四个状态,这岂不是四叉树?这个树显然太大,太占存储空间,但是我们可以在探索时先判断,如果不通,是墙,就不生成结点。这样树的存储空间就大为减少。四叉树没有学过,但我们学过树转化为二叉树,那么,用长子兄弟表达法建这样一棵树是完全有可能的。我尝试建树,也写了其中的很多函数。但是如何将迷宫类和树结构结合起来呢? 其中最大的困难是如何写树的构造函数。探索时的判断必然要交给迷宫类的成员函数来实现,但是判断完后结点如何插到树中?我始终没有想明白,树结构的计划只好夭折。最终我的代码中没有出现这样的树。

但是静下来想一想,我是否真的没有用树结构?

我觉得栈其实对应着树的深度优先搜索,队列对应树的广度优先搜索。记得当时学数据结构二叉树的层次遍历时要用到一个辅助的队列结构,我看这队列的算法其实就是树的层次遍历,不过这树是动态的,我们也一直没有建出这样一棵树。

由此看来我们是用了树而浑然不知。从而,我之前所说的树不建也罢,建了反倒是要浪费存储空间。

3.2 算法比较

用队列结构时,相当于多人同时走迷宫,(主要体现在岔路口时)在某一时刻若“某人”找到了,就停止探索,此时其实已经穷尽了从开始时刻到这一步的所有可能,所以用队列求出的路径必然是最短路径,

而用栈只能求出可行路径(并不保证最短)由于栈到最后一步时,栈中恰好保存着一条从起点到终点的路径序列,输出路径比较方便。

但是队列到最后一步时,虽然已经知道已经“有人”找到了,但是“谁”找到的?求出的路径在哪还是不太明晰,所以需要从最后一步往前回溯,每一时刻保存当前状态和前一步状态,对每一时刻来说,当前状态必然是另一时刻的前一步状态,找到这个对应的时刻然后如法炮制,直到追踪到起点为止,这样就找到最短路径。

3.3 算法的时空分析

栈和队列这两种解法优劣如何,不能一概而论,要看其适用的环境,如果不含解的子区域很多,栈会浪费很多时间,而队列则不会,因为队列是由近及远,可以看到,队列探索过的空间都连成了一片。不过如果迷宫不是这种狭长型的迷宫,队列的回溯过程可能会占用较多存储空间。

比较:栈“不撞南墙不回头”,急躁冒进,是机会主义者,队列稳打稳扎,步步为营。当然,队列也不是没有问题,存储空间有时要多一些。实际上,对于深度优先搜索,栈所需要的空间由找到一个解之前遇到过的最长那一条搜索路径决定。对于广度优先搜索,所需队列的空间由搜索过程中可能路径分支最多的那一层决定。

3.4 经验和体会

我在10月17日已经初步完成课设程序的编写,不过优化和调试的过程十分艰辛,我花在debug上的时间远远超过了我当初写出代码的时间,这才深刻意识到“行百里者半九十”
的深刻含义。

4 用户使用说明

用户进入Battle Curie\Battle Curie\bin\Debug路径下找到Battle Curie.exe,点击运行,按Start按钮,打开新的Form,之后如何操作,程序会有详细提示,不再说明。(程序最终是动态的)

本程序分两个版本:

  • 一是只用C++写成的控制台应用

  • 二是给前者加了VB.net界面的windows应用

前者可以单独使用,存放在Battle Curie\Battle Curie\bin\Debug\QRmaze目录下,生成的可执行文件为QRmazeQueueStack.exe文件;后者存放Battle Curie\Battle Curie\bin\Debug路径下,生成的可执行文件为Battle Curie.exe 它需要和运行QRmazeQueueStack.exe后动态创建的Command.txt配套使用(已经存在)。

本程序的开发环境

  • C++用的是Dev-C++,采用GCC编译器编译

  • VB.net用的是Microsoft Visual Studio2010 Ultimate,要查看VB代码建议用它打开

  • 程序的运行环境为Windows 10

5 测试结果

测试数据

默认:(1, 1)(9, 8)对应存放迷宫布尔矩阵tu1.txt文件

队列结构(最短路径):

栈结构(不一定最短):

可以很方便地用栈结构,为什么要用队列来实现?我的答案是用队列可以求出最短路径。

为了更好地说明问题,我专门设计了一个用来“坑”栈解法的迷宫,通过此例子,二者区别一看便知:

起点(1, 1)终点(3, 2)对应地图tu5.txt

由图可知,“队列”一眼识破我的诡计,知道终点就在家附近;而“栈”则真是被我耍得“团团转”,出门绕了那么一大圈才知道原来终点就在起点附近。

上传的附件 cloud_download 基于栈和队列的迷宫问题求解.7z ( 3.87mb, 37次下载 )
error_outline 下载需要11点积分

发送私信

人生就像坐飞机,飞多高不重要,重要的是安全到达目的地

10
文章数
19
评论数
最近文章
eject