数据结构课程设计_迷宫求解.doc资源-CSDN文库

版权申诉

97 浏览量 2021-10-04 22:14:53 上传评论收藏 313KB DOC 举报

资源推荐

资源详情

资源评论

迷宫求解

一．问题描述

对迷宫问题的求解过程实际就是从入口开始，一步一步地走到出口

的过程。

基本要求：

输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条

走出迷宫的路径，并将路径输出。

二．设计思路

在本程序中用两种方法求解迷宫问题-非递归算法和递归算法。

对于非递归算法采用回溯的思想，即从入口出发，按某一方向向

前探索，若能走通，并且未走过，则说明某处可以到达，即能到达

新点，否则试探下一方向；若所有的方向均没有通路，或无路可走

又返回到入口点。在求解过程中，为了保证在到达某一点后不能向

前继续行走（无路）时，能正确返回前一点以便继续从下一个方向

向前试探，则需要用一个栈保存所能到达的没一点的下标与该点前

进的方向，然后通过对各个点的进出栈操作来求得迷宫通路。

对于递归算法，在当前位置按照一定的策略寻找下个位置，在下

个位置又按照相同的策略寻找下下个位置…；直到当前位置就是出

口点，每一步的走法都是这样的。随着一步一步的移动，求解的规

模不断减小；如果起始位置是出口，说明路径找到，算法结束，如

果起始位置的四个方向都走不通，说明迷宫没有路径，算法也结束。

另外，为了保证迷宫的每个点都有四个方向可以试探，简化求解

1 / 23

剩余22页未读，继续阅读

内容反馈

版权申诉

huayuya123

粉丝: 26
资源: 31万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip