出迷宫图Р输入x,yР否Р(x,y)是否合法Р是Р广度优先搜索Р标记最短路径Р输出最短路径Р结束Р2.程序运行结果截图:Р测试条件:Р以实验题目中给出的迷宫图进行测试。Р测试时固定终点位置,选择不同的起点位置进行测试,测试各个位置下的输出是否正常。Р测试结论:Р本程序对于测试地图在不同起始和终止位置输出都完全正确。Р四.总结Р1、在最初尝试编写代码时,采用的是递归算法。虽然用栈实现代码很简单,只需要向四个方向不断递归即可,但是使用栈并不能保证输出的路径是最佳路径。所以在完成了递归算法之后,我开始思索如何能输出最短路径。查找大量资料,结论是用栈很难实现,即使要实现也需要不断比较各种路径的长短,然后不断更新最短路径。偶然发现迪杰斯特拉算法,后又学习广度优先搜索算法,才用队列才最终使得问题得以解决。Р2、在将新算法应用到迷宫问题过程中,遇到不少困难,反复琢磨和看书才将其解决。由于顺序队列的出队入队操作加上了赋值和标记位置、建立链表关系,实际将一个顺序队列以指针的作用,变成了一棵树的结构,而树的深度恰好能反映最短路径。Р3、从一个小小的迷宫问题,引出了许多知识,这种探索式的学习是很有意义的。从迷宫基本的递归和回溯到栈的运用和理解,再到队列的运用,后又到树与图以及队列的综合运用,将很多知识点串联起来了,加深了理解。同时探索式地学习迪杰斯特拉算法也收获颇多。Р4、改进:本题为了实现代码的简便,没有采用链队结构,因而浪费了一定的空间,特别是当迷宫的边长很长的时候,空间复杂度以O(n*n)增长,程序效率将大大降低,因而如果是计算复杂的迷宫,可以考虑将本程序的顺序队列稍加修改变为链队,实现动态分配内存,以节省空间消耗。Р5、进一步的思考:此方法只能输出一条最短路径,如何能输出所有最短路径?初步算法是将同一深度的节点全部遍历,如果后续还有同样长度的路径则输出该路径,如果没有则只有一条最短路径。
全文预览