【Python数据结构与算法】--- 递归算法的应用 ---[乌龟走迷宫] |人工智能|探索扫地机器人工作原理

🌈个人主页: Aileen_0v0
🔥系列专栏:PYTHON数据结构与算法学习系列专栏
💫"没有罗马,那就自己创造罗马~" 


目录

导言 

解决过程 

1.建立数据结构

2.探索迷宫:

算法思路

递归调用的“基本结束条件”

3.乌龟走迷宫的实现代码:

运行过程:

拓展:

📝全文总结:



导言 

 乌龟探索迷宫这个问题与机器人领域也有关系,

如果我们有一个Roomba扫地机器人,我们或许可以利用乌龟探索迷宫这个问题的解决方法对扫地机器人进行重新编程.

解决过程 

首先,要建立数据结构

1.建立数据结构

我们将整个迷宫的空间(矩形)分为行列整齐的方格,区分出墙壁和通道给每个方格具有行列位置,并赋予“墙壁”,"通道”的属性

考虑用矩阵方式来实现迷宫数据结构采用“数据项为字符列表列表”这种两级列表的方式保存方格内容

采用不同字符来分别代表“通道为空格  " ,“墙壁我为+”,“海龟投放点S"从一个文本文件逐行读入迷宫数据

2.探索迷宫:

算法思路


龟龟探索迷宫的递归算法思路如下

将海龟从原位置向北移动一步,以新位置递归调用探索迷宫寻找出口;

如果上面的步骤找不到出口,那么将海龟从原位置向南移动一步,以新位置递归调用探索迷宫:

如果向南还找不到出口,那么将海龟从原位置向西移动一步,以新位置递归调用探索迷宫;

如果向西还找不到出口,那么将海龟从原位置向东移动一步,以新位置递归调用探索迷宫;

如果上面四个方向都找不到出口,那么这个迷宫没有出口!


递归调用的“基本结束条件

归纳如下 :

海龟碰到“墙壁”方格,递归调用结束,返回失败.
海龟碰到“面包屑”方格,表示此方格已访问过递归调用结束,返回失败.

海龟碰到“出口”方格,即“位于边缘的通道”方格,递归调用结束,返回成功!

海龟在四个方向上探索都失败,递归调用结束返回失败


3.乌龟走迷宫的实现代码:

import turtle
#迷宫搜索程序全局常量
START = "S" #--->起始位置
OBSTACLE = "+"  #--->墙
TRIED = "." # 走过的路
DEAD_END = "-" # 死路
PART_OF_PATH = "0" # 走出迷宫的出口#Maze类构造方法
class Maze:def __init__(self,maze_filename):with open(maze_filename,"r") as maze_file:self.maze_list = [[ch for ch in line.strip("\n")]for line in maze_file.readlines()]self.rows_in_maze = len(self.maze_list)self.columns_in_maze = len(self.maze_list[0])for row_idx, row in enumerate(self.maze_list):if START in row:self.start_row = row_idxself.start_col = row.index(START)breakself.x_translate = -self.columns_in_maze / 2self.y_translate = self.rows_in_maze / 2self.t = turtle.Turtle()self.t.shape("turtle")self.wn = turtle.Screen()self.wn.setworldcoordinates(-(self.columns_in_maze - 1) / 2 - 0.5,-(self.rows_in_maze - 1) / 2 - 0.5,(self.columns_in_maze - 1) / 2 + 0.5,(self.rows_in_maze - 1) / 2 + 0.5,)#Maze 类绘制方法def draw_maze(self):self.t.speed(10)self.wn.tracer(0)for y in range (self.rows_in_maze):for x in range (self.columns_in_maze):if self.maze_list[y][x] == OBSTACLE:self.draw_centered_box(x + self.x_translate,-y + self.y_translate,"orange",)self.t.color("black")self.t.fillcolor("blue")self.wn.update()self.wn.tracer(1)def draw_centered_box(self, x, y, color):self.t.up()self.t.goto(x - 0.5, y - 0.5)self.t.color(color)self.t.fillcolor(color)self.t.setheading(90)self.t.down()self.t.begin_fill()for i in range(4):self.t.forward(1)self.t.right(90)self.t.end_fill()#Maze 类移动方法def update_position(self,row,col,val=None):"""标记路径并更新迷宫图景"""if val:self.maze_list[row][col] = valself.move_turtle(col, row)if val == PART_OF_PATH:color = "green"elif val == OBSTACLE:color = "red"elif val == TRIED:#已走color = "black"elif val == DEAD_END:color = "red"else:color = Noneif color:self.drop_bread_crumb(color)#留下标记物def move_turtle(self, x, y):self.t.up()self.t.setheading(self.t.towards(x + self.x_translate,-y + self.y_translate,))self.t.goto(x + self.x_translate, -y + self.y_translate)def drop_bread_crumb(self,color):self.t.dot(10,color)def is_exit(self, row, col):"""如果乌龟处于迷宫边缘,表示到达出口"""return (row in [0,self.rows_in_maze - 1]or col in [0,self.columns_in_maze - 1])def __getitem__(self, idx):return self.maze_list[idx]def search_from(maze, row, column):"""对当前位置的四个方向逐一尝试直至找到出口"""maze.update_position(row, column)#检查基本情况:#1. 遇到了障碍if maze[row][column] == OBSTACLE:return False#2. 遇到已经访问过的位置if maze[row][column] in [TRIED, DEAD_END]:return False#3. 找到了出口if maze.is_exit(row,column):maze.update_position(row, column, PART_OF_PATH)return Truemaze.update_position(row, column, TRIED)#使用逻辑 or 对各个方向进行#逐一尝试found = (#利用段路经,逐语句读取  北,南,西,东search_from(maze, row - 1, column)or search_from(maze, row + 1, column)or search_from(maze, row, column-1)or search_from(maze, row, column+1))if found:maze.update_position(row, column , PART_OF_PATH)else:maze.update_position(row, column , DEAD_END)return foundmy_maze = Maze('maze2.txt')
my_maze.draw_maze()
my_maze.update_position(my_maze.start_row, my_maze.start_col)
search_from(my_maze, my_maze.start_row, my_maze.start_col)

运行过程:


拓展:

在死胡同里乌龟的是如何走的呢?


📝全文总结:

这篇文章主要讲解的是,如何用递归算法解决乌龟🐢走迷宫问题,这个问题类似于我们的扫地机器人,但是这个算法存在这一写缺点,比如说 时间方面和距离方面.如果我们要利用这个算法来写机器人我们可以从记录的路径信息,对机器人进行重新编程,以便它可以在较少的时间内清理地面,并优化其行进路线。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/206254.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

phpstudy和IDEA 配置php debug

1.安装xdebug 扩展,phpinfo() 查看 2.配置php.ini zend_extensionD:/phpstudy_pro/Extensions/php/php7.4.3nts/ext/php_xdebug.dll xdebug.collect_params1 xdebug.collect_return1 xdebug.auto_traceOn xdebug.trace_output_dirD:/phpstudy_pro/Extensions/php_l…

3.OpenResty系列之Nginx反向代理

1. Nginx简介 Nginx (engine x) 是一款轻量级的 Web 服务器 、反向代理服务器及电子邮件(IMAP/POP3)代理服务器 什么是反向代理? 反向代理(Reverse Proxy)方式是指以代理服务器来接受 internet 上的连接请求&#x…

Web安全漏洞分析-XSS(上)

随着互联网的迅猛发展,Web应用的普及程度也愈发广泛。然而,随之而来的是各种安全威胁的不断涌现,其中最为常见而危险的之一就是跨站脚本攻击(Cross-Site Scripting,简称XSS)。XSS攻击一直以来都是Web安全领…

springboot+vue项目如何集成onlyoffice开源文档组件

一、onlyoffice是什么 ONLYOFFICE 是一个开源的办公套件,适合多人在线协作。由总部位于总部在拉脱维亚的 IT 公司Acensio System SIA 开发。它提供在线协作文档编辑器(包括文档、电子表格、演示文稿和表单),适用于 Windows、Linu…

Python with提前退出:坑与解决方案

Python with提前退出:坑与解决方案 问题的起源 早些时候使用with实现了一版全局进程锁,希望实现以下效果: Python with提前退出:坑与解决方案 全局进程锁本身不用多说,大部分都依靠外部的缓存来实现的,r…

进阶C语言-字符函数和字符串函数

字符函数和字符串函数 🎈1.函数介绍🔎1.1strlen函数🔭1.1.1strlen函数的模拟实现📖1.计数器法📖2.递归法📖3.指针-指针 🔎1.2strcpy函数🔭1.2.1strcpy函数的模拟实现 🔎1…

【机器学习】算法性能评估常用指标总结

考虑一个二分问题,即将实例分成正类(positive)或负类(negative)。对一个二分问题来说,会出现四种情况。如果一个实例是正类并且也被 预测成正类,即为真正类(True positive&#xff0…

1.前端--基本概念【2023.11.25】

1.网站与网页 网站是网页集合。 网页是网站中的一“页”,通常是 HTML 格式的文件,它要通过浏览器来阅读。 2.Web的构成 主要包括结构(Structure) 、表现(Presentation)和行为(Behavior&#xff…

【深度学习】DAMO-YOLO,阿里,701类通用检测模型,目标检测

https://github.com/tinyvision/DAMO-YOLO/blob/master/README_cn.md DAMO-YOLO是由阿里巴巴达摩院智能计算实验室TinyML团队开发的一个兼顾速度与精度的目标检测框架,其效果超越了目前的一众YOLO系列方法,在实现SOTA的同时,保持了很高的推理速度。DAMO…

虚幻学习笔记4—文本内容处理

一、前言 本文使用的虚幻引擎5.3.2,在虚幻中已经集成了很多可以直接处理多样化文本的蓝图,比如格式化动态显示、浮点数多样化等。 二、实现 2.1、格式化文本显示动态内容:在设置某个文本时可以使用“Format Text”蓝图设置自定义可以的显示…

继承中的析构函数的权限的深入了解

如果一个父类中的析构函数如果设置为 private 权限 ,一个子类public继承了这个父类,那么 这个父类可以创建对象吗? 答案是 不可以 看看下面的代码 class A { public:private:~A() {} };class B :public A {A a; // 这个地方编译不报错&…

数据结构——带头循环双向链表(List)

1、带头双向循环链表介绍 在上一篇博客中我们提到了链表有三个特性,可以组合成为8种不同类型的链表。单链表是其中比较重要的一种,那么这次我们选择和带头双向循环链表会会面,这样我们就见识过了所有三种特性的呈现。 带头双向循环链表&#…

基于C#实现优先队列

一、堆结构 1.1性质 堆是一种很松散的序结构树,只保存了父节点和孩子节点的大小关系,并不规定左右孩子的大小,不像排序树那样严格,又因为堆是一种完全二叉树,设节点为 i,则 i/2 是 i 的父节点,2i 是 i 的…

Pytorch 基于 deeplabv3_resnet50 迁移训练自己的图像语义分割模型

一、图像语义分割 图像语义分割是计算机视觉领域的一项重要任务,旨在将图像中的每个像素分配到其所属的语义类别,从而实现对图像内容的细粒度理解。与目标检测不同,图像语义分割要求对图像中的每个像素进行分类,而不仅仅是确定物…

图形数据库的实战应用:如何在 Neo4j 中有效管理复杂关系

关系数据库管理系统( RDBMS ) 代表了最先进的技术,这在一定程度上要归功于其由周边技术、工具和广泛的专业技能组成的完善的生态系统。 在这个涵盖信息技术(IT) 和运营技术(OT) 的技术革命时代,人们普遍认识到性能方面出现了重大挑战,特别是…

【广州华锐互动】Web3D云展编辑器能为展览行业带来哪些便利?

在数字时代中,传统的展览方式正在被全新的技术和工具所颠覆。其中,最具有革新意义的就是Web3D云展编辑器。这种编辑器以其强大的功能和灵活的应用,正在为展览设计带来革命性的变化。 广州华锐互动开发的Web3D云展编辑器是一种专门用于创建、编…

关于网站的favicon.ico图标的设置需要注意的几点

01-必须在网页的head标签中放上对icon图标的说明语句&#xff1a; 比如下面这样的语句&#xff1a; <link rel"shortcut icon" href"/favicon.ico">否则&#xff0c;浏览器虽然能读到图标&#xff0c;但是不会把图标显示在标签上。 02-为了和本地开…

DHCP、ARP、FTP、DNS、VRRP、STP、报文交互流程

目录 一、DHCP 1、DHCP终结 1、DHCP discover 2、DHCP offer 3、DHCP request 4、DHCP ack 5、DHCP request 6、DHCP 续租 2、DHCP终结 二、ARP 1、ARP类型 动态ARP 静态ARP ARP代理 ARP代理的分类&#xff1a;路由式代理、VLAN内的ARP代理、VLAN间的ARP代理。 6…

【Hadoop】分布式文件系统 HDFS

目录 一、介绍二、HDFS设计原理2.1 HDFS 架构2.2 数据复制复制的实现原理 三、HDFS的特点四、图解HDFS存储原理1. 写过程2. 读过程3. HDFS故障类型和其检测方法故障类型和其检测方法读写故障的处理DataNode 故障处理副本布局策略 一、介绍 HDFS &#xff08;Hadoop Distribute…

electron调用dll问题总汇

通过一天的调试安装&#xff0c;electron调用dll成功&#xff0c;先列出当前的环境&#xff1a;node版本: 18.12.0&#xff0c;32位的&#xff08;因为dll为32位的&#xff09; VS2019 python node-gyp 1、首先要查看报错原因&#xff0c;通常在某一行会有提示&#xff0c;常…