罗密欧与朱丽叶的迷宫问题

ID：969754

大小：2.17 MB

页数：9页

时间：2022-03-17

加入VIP免费下载

 申诉

加入VIP免费下载

温馨提示：
1. 部分包含数学公式或PPT动画的文件，查看预览时可能会显示错乱或异常，文件下载后无此问题，请放心下载。
2. 本文档由用户上传，版权归属用户，天天资源网负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容，确认文档内容符合您的需求后进行下载，若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误，付费完成后未能成功下载的用户请联系客服处理。
网站客服：403074932

资料简介

罗密欧与朱丽叶的迷宫问题学号：201312172067姓名：李亚光问题描述问题分析动画演示思路分析代码及运行结果总结罗密欧与朱丽叶的迷宫问题罗密欧与朱丽叶身处一个m×n的迷宫中，下图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8个方向进入未封闭的房间。罗密欧位于迷宫的(p,q)方格中，他必须找到一条通向朱丽叶所在(r,s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯的次数为最少。每改变一次前进方向算作转弯一次。设计一个算法帮助罗密欧找到这样一条路。问题描述：问题分析限制条件演示条件限制：迷宫中的任何位置均可沿八个方向进入未封闭的房间。找到朱丽叶之间，必须遍历所有未封闭的房间各一次。并且使到达朱丽叶的转弯次数最少。Nosolution!!! 动画演示：关键函数设置：设置dir[9][2]罗密欧的行走路线设置comp(intx,inty)判断罗密欧的位置是否可行设置search(intdep,intx,inty,intdi)进行深度优先搜索和回溯回溯的原因：边界值限制遍历完所有的房间，但是没有找到J找到J，没有遍历所有的房间遍历完所有的房间并且找到J，但不是最优解思路分析： code代码及运行结果：迷宫问题，就是图的深度优先遍历，也就是采用回溯的方法进行求解。优化想法：假设在方向没有改变的情况下，得知自己的前一个节点的某个方向不能遍历，那么该节点能否直接排除该方向的遍历呢？算法有待改进总结： Anyquestions?

罗密欧与朱丽叶的迷宫问题

罗密欧与朱丽叶的迷宫问题

资料简介

你可能关注的文档

推荐资源

天天课堂