如何使用python动画演示深度优先算法搜寻逃出迷宫的路径开发技术

Python主要应用于:1、Web开发;2、数据科学研究;3、网络爬虫;4、嵌入式应用开发;5、游戏开发;6、桌面应用开发。

深度优先算法(DFS算法)是什么?

寻找起始节点与目标节点之间路径的算法,常用于搜索逃出迷宫的路径。主要思想是,从入口开始,依次搜寻周围可能的节点坐标,但不会重复经过同一个节点,且不能通过障碍节点。如果走到某个节点发现无路可走,那么就会回退到上一个节点,重新选择其他路径。直到找到出口,或者退到起点再也无路可走,游戏结束。当然,深度优先算法,只要查找到一条行得通的路径,就会停止搜索;也就是说只要有路可走,深度优先算法就不会回退到上一步。

下图是使用DFS算法搜寻出来的一条路径:

总结一下:

从起点开始,查询下一步走得通的节点,将这些可能的节点压入堆栈中,已经走过的节点不再尝试。查询完毕之后,从堆栈中取出一个节点,查询该节点周围是否存在走得通的节点。如果不存在可能的节点,就继续从堆栈中取一个节点。重复以上操作,直到当前节点为终点,或者堆栈中再无节点。

定义数据:

定义辅助函数

首先,我们来定义栈这种数据结构,栈是一种后进先出的数据结构。

#find_path.pyfromutilsimportStackdefdfs(initial,_next=successor,_test=test_goal):s:Stack=Stack()marked={initial}s.push(initial)whiles:parent:state=s.pop()if_test(parent):returnparentchildren=_next(parent)forchildinchildren:ifchildnotinmarked:marked.add(child)s.push(child)接下来,我们使用DFS算法寻找迷宫路径,并对搜寻到的迷宫路径进行可视化演示。

首先使用枚举,来表示路径的颜色,EMPTY为正常节点,BLOCKED为障碍节点,START为迷宫入口,END为迷宫出口,PATH为搜寻的路径。

fromenumimportIntEnumclassCell(IntEnum):EMPTY=255BLOCKED=0START=100END=200PATH=150接下来,我们来定义迷宫。首先,我们采用Namedtuple来定义迷宫每个节点的坐标:

classMazeLocation(NamedTuple):row:intcol:int首先为了方便确定节点之间的关系,我们在Maze类中定义了一个内部类_Node,用来记录节点的状态,及节点的父节点。

class_Node:def__init__(self,state,parent):self.state=stateself.parent=parent接着初始化,确定入口与出口的坐标,使用np.random.choice函数随机生成迷宫,并标记入口和出口。

def__init__(self,rows:int=10,cols:int=10,sparse:float=0.2,seed:int=365,start:MazeLocation=MazeLocation(0,0),end:MazeLocation=MazeLocation(9,9),*,grid:Optional[np.array]=None)->None:np.random.seed(seed)self._start:MazeLocation=startself._end:MazeLocation=endself._grid:np.array=np.random.choice([Cell.BLOCKED,Cell.EMPTY],(rows,cols),p=[sparse,1-sparse])self._grid[start]=Cell.STARTself._grid[end]=Cell.END其次是test_goal方法,只要该节点坐标与目标节点相即可。

def_test_goal(self,m1:MazeLocation)->bool:returnm1==self._end再就是successor方法,只要上下左右方向的节点不是障碍节点且在边界之内,就纳入考虑范围,加入列表之中。

List[MazeLocation]:location:List[MazeLocation]=[]row,col=self._grid.shapeifm1.row+1=0andself._grid[m1.row-1,m1.col]!=Cell.BLOCKED:location.append(MazeLocation(m1.row-1,m1.col))ifm1.col+1=0andself._grid[m1.row,m1.col-1]!=Cell.BLOCKED:location.append(MazeLocation(m1.row,m1.col-1))returnlocation显示路径,pause为显示图像的间隔,plot为是否绘图标志。通过目标节点出发,遍历每一个节点的父节点,直到到达初始节点,并绘制路径图。

THE END
1.十大经典排序算法动画演示AlgorithmMan,一套免费的算法演示神器,附带GitHub开源下载地址。 1、Sorting Algorithms Animations 2、算法的分类 3、时间复杂度 算法 1、冒泡排序 它重复地访问要排序的元素列,一次比较两个相邻的元素,如果他们的顺序不符合预期就把他们交换过来。访问元素的工作是重复地进行直到没有相邻元素需要交换时为止。 https://www.jianshu.com/p/e9cfc2cc869c
2.排序算法动画演示冒泡法教育视频小狐狸151613关注https://tv.sohu.com/v/dXMvMTUxNjEzLzE4NzIzNzI4OS5zaHRtbA==.html
3.希尔排序算法的原理实现过程开始希尔排序算法动画演示突破了文本表述方式的局限性,将希尔排序算法的实现过程形象化、可视化的展现出来,使得那些可能不太熟悉编程语言或基础数学概念的人也能够轻松理解该算法的原理和实现过程。如果你对希尔排序算法还感到迷茫,不妨欣赏一下这个希尔排序算法动画演示,相信它一定能够帮助你更好地理解该算法及其运作机制。http://www.yanshidonghua.com/article/b18b4bb5076f976e.html
4.难得的AES加密解密算法的动画演示AES算法的实现代码,使用的是c语言开发,用DEMO 上传者:weixin_42653672时间:2022-09-23 rijndael_ingles2004.rar AES加密算法动画演示,非常不错。原网站在:https://coolshell.cn/wp-content/uploads/2010/10/rijndael_ingles2004.swf 上传者:xiansong1005时间:2018-07-09 https://www.iteye.com/resource/aven507-3906466
5.10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径这篇文章主要介绍了10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下 深度优先算法(DFS 算法)是什么? 寻找起始节点与目标节点之间路径的算法,常用于搜索逃出迷宫的路径。主要思想是,从入口开始,依次搜寻周围可能的节点坐标,但不会重复经过同一个节点,且https://www.jb51.net/article/167505.htm
6.数据结构和算法Flash动画演示数据结构队列动画资源“数据结构”课程算法动画演示(FLASH) 浏览:193 本资源共包括19个FLASH制作的数据结构中算法演示,从顺序结构到最后章节的排序,希望对您的课程学习有所帮助。 数据结构和算法FLASH动画演示( 无密码) 浏览:76 数据结构里45个经典算法的FLASH演示,有利于理解学习 https://download.csdn.net/download/tianxingjian136/10237915
7.可视化的数据结构各种算法动画演示5.哈夫曼 (Huffman) 树的动画演示: http://people.cs.pitt.edu/~kirk/cs1501/animations/Huffman.html 6.可视化算法:算法也可以很美。 这篇文章虽有点长,不过值得一看。 http://bost.ocks.org/mike/algorithms/ 想从直观角度学习算法,数据结构,所以在百度搜索相关资源时,在CSDN上发现了这个,特意转发到个人博客https://blog.51cto.com/yuan606/1759543
8.机器人是如何规划路径的?动画演示一下吧澎湃号·湃客动画演示一下吧 机器之心报道 机器之心编辑部 走机器的路,让你看一下。 在机器人研究领域,给定某一特定任务之后,如何规划机器人的运动方式至关重要。 最近,GitHub 上开源了一个存储库,该库实现了机器人技术中常用的一些路径规划算法,大部分代码是用 Python 实现的。值得一提的是,开发者用 plotting 为每种算法https://www.thepaper.cn/newsDetail_forward_9959477
9.蚁群算法基本原理(附带动画演示)教案资料(11页)蚁群算法基本原理(附带动画演示)教案资料.pptx 11页内容提供方:135***6041 大小:5.77 MB 字数:约3.92千字 发布时间:2021-11-24发布于浙江 浏览人气:19 下载次数:仅上传者可见 收藏次数:0 需要金币:*** 金币 (10金币=人民币1元)蚁群算法基本原理(附带动画演示)教案资料.pptx 关闭预览 想预览更多https://max.book118.com/html/2021/1122/8064140117004042.shtm
10.沃罗诺伊图(VoronoiDiagram)的动画演示,一种高效的空间分割算法。首页 频道 搜索热搜榜 开通会员 客户端 看过 收藏 消息 您的Flash插件已过期或被禁止 升级或启用Flash 沃罗诺伊图(Voronoi Diagram)的动画演示,一种高效的空间分割算法。 沃罗诺伊图(Voronoi Diagram)的动画演示,一种高效的空间分割算法。 295 内容简介https://v.pptv.com/show/X0BY1DyiaElCzMZk.html
11.机器学习算法系列(一)感知器学习算法(PLA)前面一节我们了解了机器学习算法系列(〇)- 基础知识,接下来正式开始机器学习算法的学习,首先我们从最简单的一个算法——感知器学习算法(Perceptron Learning Algorithm)开始。 我们在使用电子邮件时,应该注意到现代邮箱都有反垃圾邮件的功能,系统根据邮件的内容自动判断是否是垃圾邮件,节省了我们的时间,试https://www.imooc.com/article/322776
12.好玩的Raft动画演示,原理秒懂每个节点上都有一个倒计时器 (Election Timeout),时间随机在150ms;tom”,通过这么一个过程,就完成了在Network Partition 情况下的复制日志,保证了数据的一致性。 小总结Raft是能够实现分布式系统强一致性的算法,每个系统节点有三种 raft算法动画演示https://www.pianshen.com/article/25201628898/
13.算法笔记(1)——搜索算法:线性搜索(LS)二分搜索(BS)记忆化【动画演示】 二分搜索(BinarySearch)[动画由Python tkinter模块制作] 【Python实现】 【循环型二分搜索】 def BinarySearch(lis: list[int], obj: int): #lis:搜索序列 obj:目标值 max_index, min_index = len(lis)-1, 0 #初始化搜索的上下边界(索引) while True: #无限循环 middle = (max_index+mihttps://developer.aliyun.com/article/1248265
14.五分钟弄懂有点难度的排序:堆排序腾讯云开发者社区算法演示 排序动画过程解释 首先,将所有的数字存储在堆中 按大顶堆构建堆,其中大顶堆的一个特性是数据将被从大到小取出,将取出的数字按照相反的顺序进行排列,数字就完成了排序 在这里数字 5 先入堆 数字2 入堆 数字7 入堆, 7 此时是最后一个节点,与最后一个非叶子节点(也就是数字 5 )进行比较,由于 7 https://cloud.tencent.com/developer/article/1366827
15.热二年级上册数学教案1.教学例7【演示动画"应用题"】. (1)指导学生操作学具. 第一行摆4个圆片 ○○○ 第二行摆三角形,比圆片多2个. 应先摆和圆片一一对应的同样多的部分 △△△ 再摆比圆片多的2个三角形 △△ 第二行摆___个三角形 △△△ 让学生说一说是https://www.unjs.com/jiaoan/shuxue/20230113090152_6259012.html
16.数据结构B树的生成动画演示数据结构B树的生成动画演示_b树动画Lo**gs 上传41.66 KB 文件格式 swf 动画 简单形象的描述出B树的生成,使人较容易理解其思想。点赞(0) 踩踩(0) 反馈 所需:1 积分 电信网络下载 lynnpierre 2020-04-28 11:51:54 评论 生动形象,一看就懂u010040425 2017-07-31 16:44:45 评论 一看就懂,厉害哦,https://www.coder100.com/index/index/content/id/1119644
17.五年级数学教案热是小数乘整数知识的扩展和延伸,教学中充分利用已有的知识和技。复习中通过动画演示,从观察整数乘法算式得出积的变化规律 为理解小数乘法中积的小数位数就是两个因数的小数位数的和奠定了基础。 教学中重视引导学生运用转化的思想和知识的迁移规律,在充分理解算理的基础上,逐步总结出小数乘法的计算法则。 https://www.fwsir.com/jiaoan/html/jiaoan_20221126083108_2100232.html
18.theformofanimation.(用动画的形式呈现解LeetCode题目的思路)我会尽力将 LeetCode 上所有的题目都用动画的形式演示出来,计划用 3 到 4 年时间去完成它,期待与你见证这一天! 文章最新首发于微信公众号 吴师兄学算法,您可以关注获取最新的文章。 为了帮助大家更好的入门学习算法,经过半年的积累,我给大家整理了《剑指 Offer》系列的四十道题目,都是算法面试的高频题目,每一道https://github.com/MisterBooo/LeetCodeAnimation
19.《Photoshop平面设计》课程设计任务书(精选8篇)17、基数排序过程动画演示 要求:使用图形用户界面 基数排序算法的实现过程参照《数据结构》教材,动画效果强。可以采用最高位优先算法实现,也可以 采用最低位优先算法实现,人机交互、便于教学。 课程设计时间安排 序号 时间 实习主要内容 实习地点 指导教师 1星期一 上午 概要设计:确定项目的实施方案、设 计程序模块连接https://www.360wenmi.com/f/fileq3f1zkxm.html