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

这篇具有很好参考价值的文章主要介绍了【Python数据结构与算法】--- 递归算法的应用 ---[乌龟走迷宫] |人工智能|探索扫地机器人工作原理。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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


目录

导言 

解决过程 

1.建立数据结构

2.探索迷宫:

算法思路

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

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

运行过程:

拓展:

📝全文总结:



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

导言 

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

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

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

解决过程 

首先,要建立数据结构

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_idx
                self.start_col = row.index(START)
                break
        self.x_translate = -self.columns_in_maze / 2
        self.y_translate = self.rows_in_maze / 2
        self.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] = val
        self.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 = None
        if 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 True
    maze.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 found

my_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)

运行过程:

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


拓展:

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

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


📝全文总结:

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

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

【Python数据结构与算法】--- 递归算法的应用 ---[乌龟走迷宫] |人工智能|探索扫地机器人工作原理,数据结构与算法,游戏,python,机器人,人工智能,前端,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-752756.html

到了这里,关于【Python数据结构与算法】--- 递归算法的应用 ---[乌龟走迷宫] |人工智能|探索扫地机器人工作原理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】二叉树的遍历递归算法详解

    我们来写一个函数 BuyNode(x)函数 用于创建二叉树结点。 用动态开辟函数 malloc 函数进行动态开辟,并强制转换为 BTNode 型,用变量 node 来去管理开辟的空间。 我们初始化结点,其 val 即为传入的参数x,左右指针 left 和 right 都设为NULL。 我们在主函数中创建上面这样一颗二叉树

    2024年01月20日
    浏览(45)
  • 【数据结构与算法】单链表的排序算法(选择,冒泡,递归)

    目录 选择排序 冒泡排序 快速排序 合并两条链表并排序 选择排序 链表的选择排序思想与数组的排序类似,但是链表需要先找到里面最小或者最大的值,然后将这个值用改链语句进行操作 我们先看这个改链语句的操作(min是笔者打错了应该是max,但是图已经画好了就没有改)

    2024年02月04日
    浏览(56)
  • 【数据结构与算法】:非递归实现快速排序、归并排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序,本篇我们来探究非递归实现快速排序和归并排序 快速排序的非递归实现主要依赖于栈(stack)来模拟递归过程中的函数调用栈。递归版本的快速排序通过递归调用自身来处理子

    2024年03月24日
    浏览(54)
  • 【数据结构与算法】归并排序详解:归并排序算法,归并排序非递归实现

    归并排序是一种经典的排序算法,它使用了分治法的思想。下面是归并排序的算法思想: 递归地将数组划分成较小的子数组,直到每个子数组的长度为1或者0。 将相邻的子数组合并,形成更大的已排序的数组,直到最终得到一个完全排序的数组。 归并排序的过程可以分为三

    2024年01月22日
    浏览(69)
  • 【数据结构与算法】快速排序的非递归实现方法

      目录 一.前言 二.非递归实现 如果数据量过大的话,不断递归就会出现 栈溢出 的现象,这个时候你的代码是没问题的,但就是跑不起来,这个时候就要 把递归改成非递归 。 一般有两种改法: 1.直接改,利用循环等; 2.借助栈的辅助。 而快速排序的非递归实现方法就需要

    2023年04月17日
    浏览(54)
  • 数据结构与算法----详解二叉树的遍历(迭代、递归)

    ❤️ 作者简介 :大家好我是小鱼干儿♛是一个热爱编程、热爱算法的大三学生,蓝桥杯国赛二等奖获得者 🐟 个人主页 :https://blog.csdn.net/qq_52007481 ⭐ 个人社区 :【小鱼干爱编程】 🔥 算法专栏 :算法竞赛进阶指南 💯 刷题网站 :虽然市面上有很多的刷题网站,但是里面

    2024年01月24日
    浏览(53)
  • [数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

    目录 1、归并的思想 2、归并排序的思想 2.1 基本思想 2.2 图解分析 3、归并排序递归版本代码实现 3.1 代码解析 3.2 注意事项 3.2.1错误划分:[begin, mid-1],[mid, end] 3.2.2 正确划分:[begin, mid], [mid+1, end] 4、归并排序的测试 5、时间复杂度、空间复杂度分析 5.1 时间复杂度 5.2 空间复杂

    2024年02月16日
    浏览(50)
  • 【数据结构与算法篇】手撕八大排序算法之快排的非递归实现及递归版本优化(三路划分)

    ​👻内容专栏: 《数据结构与算法篇》 🐨本文概括: 利用数据结构栈(Stack)来模拟递归,实现快排的非递归版本;递归版本测试OJ题时,有大量重复元素样例不能通过,导致性能下降,优化快速排序通过将数组划分为三个区域,可以更有效地处理重复元素。 🐼本文作者:

    2024年02月11日
    浏览(83)
  • 【数据结构】树与二叉树(十三):递归复制二叉树(算法CopyTree)

      二叉树是一种常见的树状数据结构,它由结点的有限集合组成。一个二叉树要么是 空集 ,被称为 空二叉树 ,要么由一个根结点和两棵不相交的子树组成,分别称为 左子树 和 右子树 。每个结点最多有两个子结点,分别称为左子结点和右子结点。 引理5.1:二叉树中层数

    2024年02月01日
    浏览(39)
  • 算法分析与设计考前冲刺 (算法基础、数据结构与STL、递归和分治、 动态规划、贪心算法、 回溯算法)

    算法分析与设计考前冲刺 算法基础 算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。 程序是算法用某种程序设计语言的具体的 具体实现 算法特征: 有穷性(有限步) 确定性 输入 输出 可行性(有限时间) 算法的复杂性: 时间复杂性 和空间复

    2024年02月02日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包