左神算法题系列:动态规划机器人走路

这篇具有很好参考价值的文章主要介绍了左神算法题系列:动态规划机器人走路。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

机器人走路

假设有排成一行的N个位置记为1~N,N一定大于或等于2
开始时机器人在其中的start位置上(start一定是1~N中的一个)
如果机器人来到1位置,那么下一步只能往右来到2位置;
如果机器人来到N位置,那么下一步只能往左来到N-1位置;
如果机器人来到中间位置,那么下一步可以往左走或者往右走;
规定机器人必须走K步,最终能来到aim位置(P也是1~N中的一个)的方法有多少种
给定四个参数 N,start,aim,K 返回能走到的方法数

递归思路

1、当cur在1位置时,只能向2位置移动
2、当cur在N位置时,只能向N-1位置移动
3、当cur在中间位置,可以向cur+1位置移动、也可以向cur-1位置移动
4、如果剩余步数刚好走完时,来到目标位置,返回1,否则返回0

class RobotWalk(object):
    def ways_a(self, pos, steps, start, target):
        """

        :param pos: 总共有pos个位置
        :param steps: 可以走的步数
        :param start: 开始位置
        :param target: 目标位置
        :return:
        """
        if pos < 2 or steps < 1 or start < 1 or start > pos or target < 1 or target > pos:
            return 0
        return self.process_a(pos, start, steps, target)

    def process_a(self, pos, cur, rest, target):
        """
        :param pos: 总共有pos个位置
        :param cur: 当前来到的位置
        :param rest: 还剩下的步数
        :param target: 目标位置
        :return: 机器人从cur出发,走过rest步之后,最终停留在target的方法数
        """
        # 步数走完时,如果机器人刚好到达目标位置,则返回1
        if rest == 0:
            return 1 if cur == target else 0
        # 如果在1位置,只能向右走 -> cur+1
        if cur == 1:
            return self.process_a(pos, cur + 1, rest - 1, target)
        # 如果在最后一个位置,只能向左 -> cur-1
        if cur == pos:
            return self.process_a(pos, cur - 1, rest - 1, target)
        # 中间位置 既能向左又能向右
        return self.process_a(pos, cur + 1, rest - 1, target) + self.process_a(pos, cur - 1, rest - 1, target)

动态规划

加缓存

class RobotWalk(object):
    def ways_b(self, pos, steps, start, target):
        """

        :param pos: 总共有pos个位置
        :param steps: 可以走的步数
        :param start: 开始位置
        :param target: 目标位置
        :return:
        """
        if pos < 2 or steps < 1 or start < 1 or start > pos or target < 1 or target > pos:
            return 0
        # 转移条件 剩下的步数 和 当前位置
        # 当前位置cur 范围 1~pos
        # 剩余步数rest 范围 0~steps
        # steps(总步数) 列 pos(总共位置数) 行的数组
        cache = [[-1] * (steps + 1) for _ in range(pos + 1)]
        return self.process_b(pos, start, steps, target, cache)

    def process_b(self, pos, cur, rest, target, cache):
        """
        加缓存减少重复计算
        :param pos:
        :param cur:
        :param rest:
        :param target:
        :param cache:
        :return:
        """
        # 当前位置没有计算过,则计算后存入缓存,否则直接返回缓存数据
        if cache[cur][rest] == -1:
            # 步数走完时,如果机器人刚好到达目标位置,则返回1
            if rest == 0:
                index = 1 if cur == target else 0
            elif cur == 1:
                index = self.process_b(pos, 2, rest - 1, target, cache)
            elif cur == pos:
                index = self.process_b(pos, pos - 1, rest - 1, target, cache)
            else:
                index = self.process_b(pos, cur + 1, rest - 1, target, cache) + \
                        self.process_b(pos, cur - 1, rest - 1, target, cache)
            cache[cur][rest] = index
        return cache[cur][rest]

假如:
位置数 pos=6
剩余步数steps=5
开始位置start=1
目标位置target=4
cur为当前位置
创建动态表dp 行代表位置数 pos(1,pos), 列代表剩余步数rest(0,steps)
根据递归条件填表:
1、当剩余步数为0时,刚好来到target位置,dp值为1,如果在其他位置,说明未到目标位置,dp值为0
即:dp[cur][rest] = dp[4][0] = 1
2、当cur=1时,只能向2位置移动,都依赖dp[2][rest-1]位置的值
3、当cur=pos时,只能向pos-1位置移动,都依赖dp[pos-1][rest-1]位置的值
4、当1<cur<pos时,既能向cur-1位置移动,也能向cur+1位置移动,都依赖dp[cur-1][rest-1]+dp[cur+1][rest-1]
最终求dp[start][rest] --> dp[1][5] = 4

| cur/rest

位置/剩余步数 0 1 2 3 4 5
0 x x x x x x
1 0 0 0 1 0 4
2 0 0 1 0 4 0
3 0 1 0 3 0 10
4 1 0 2 0 6 0
5 0 1 0 3 0 9
6 0 0 1 0 3 0

代码实现文章来源地址https://www.toymoban.com/news/detail-735133.html

class RobotWalk(object):
    def ways_c(self, pos, steps, start, target):
        """
        :param pos: 总共有pos个位置
        :param steps: 可以走的步数
        :param start: 开始位置
        :param target: 目标位置
        :return:
        """
        if pos < 2 or steps < 1 or start < 1 or start > pos or target < 1 or target > pos:
            return 0
        # 当前位置cur 范围 1~pos
        # 剩余步数rest 范围 0~steps
        # steps(总步数) 列 pos(总共位置数) 行的数组
        dp = [[0] * (steps + 1) for _ in range(pos + 1)]
        # 当剩余0步时,刚好来到target位置 则dp值为1, 其他位置值为0
        dp[target][0] = 1
        # 列
        for col in range(1, steps + 1):
            # 第一行依赖左下元素
            dp[1][col] = dp[2][col - 1]
            # 中间行依赖左下和左上
            for row in range(1, pos):
                dp[row][col] = dp[row + 1][col - 1] + dp[row - 1][col - 1]
            # 最末行依赖左上元素
            dp[pos][col] = dp[pos - 1][col - 1]

        return dp[start][steps]

到了这里,关于左神算法题系列:动态规划机器人走路的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 迷路的机器人(递归回溯+动态规划两个方法实现)

    题目: 设想有个机器人坐在一个网格的左上角,网格 r 行 c 列。机器人只能向下或向右移动,但不能走到一些被禁止的网格(有障碍物)。设计一种算法,寻找机器人从左上角移动到右下角的路径。 示例: 输入: [   [0,0,0],   [0,1,0],   [0,0,0] ] 输出: [[0,0],[0,1],[0,2],[1,2],[2,2]] 解

    2024年02月12日
    浏览(34)
  • 【路径规划】基于动态窗口法DWA算法的机器人动态避障路径规划研究附Matlab实现

     ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进, 代码获取、论文复现及科研仿真合作可私信。 🍎个人主页:Matlab科研工作室 🍊个人信条:格物致知。 更多Matlab完整代码及仿真定制内容点击👇 智能优化算法       神经网络预测       雷达通信    

    2024年02月03日
    浏览(59)
  • Python 动态规划 实现机器人躲避障碍物获取最短路径

    要设计一种算法来寻找机器人从左上角移动到右下角的路径,可以使用动态规划来解决这个问题。下面是一种可能的算法: 创建一个处理机器人运动的函数 find_path ,函数接受一个矩阵 grid 作为参数,用于表示机器人移动的网格环境,该矩阵一个由 0 和 1 组成的二位列表,其

    2024年04月09日
    浏览(42)
  • 六自由度机器人(机械臂)运动学建模及运动规划系列(四)——轨迹规划

    对机器人进行轨迹规划的主要任务是,根据机器人的工作环境和工作任务要求,求得一系列机器人末端位姿变换的时间序列,使得机器人末端可以正确地从初始姿态沿着期望的轨迹运动到终止位姿,完成工作任务,。对于六自由度的机器人来说,轨迹规划要解决的关键问题是

    2024年02月03日
    浏览(67)
  • 六自由度机器人(机械臂)运动学建模及运动规划系列(一)——简介

    毕业设计做了六轴机器人相关的课题,做完之后学到很多,在这里分享一下。本篇首先对六轴机器人及其研究内容进行简单的介绍。 六轴机器人中的六轴指个六自由度,由关节和连杆组成。常见的六轴机器人为 串联型旋转关节机器人 。这里以一款川崎机器人为例,展示一下

    2024年02月02日
    浏览(45)
  • 【MATLAB源码-第64期】matlab基于DWA算法的机器人局部路径规划包含动态障碍物和静态障碍物。

    动态窗口法(Dynamic Window Approach,DWA)是一种局部路径规划算法,常用于移动机器人的导航和避障。这种方法能够考虑机器人的动态约束,帮助机器人在复杂环境中安全、高效地移动。下面是DWA算法的详细描述: 1. 动态窗口的概念 动态窗口法的核心概念是“动态窗口”,这是

    2024年02月05日
    浏览(52)
  • 移动机器人农田机器人全覆盖路径规划

    鉴于目前网上对于全覆盖路径规划方面的资料比较少,本次博客内容主要分享下拖拉机在农田里面作业的路径规划,以及轨迹优化。 目录 1. 什么是全覆盖路径规划 2. 实用案例 3. 农田作业机器人 如何获取地图 如何规划出全覆盖的路径 如何确保规划出来的路径是符合车辆动力

    2024年01月25日
    浏览(52)
  • 机器人-轨迹规划

    旋转矩阵--R--一个3*3的矩阵,其每列的值时B坐标系在A坐标系上的投影值。 代表B坐标系相对于A坐标系的姿态。 其实A相对于B的旋转矩阵就相当于把B的列放到行上就行。 视频  (将矩阵的行列互换得到的新矩阵称为转置矩阵。) 所以说B相对于A的旋转矩阵就是A相对于B的旋转

    2024年04月28日
    浏览(41)
  • 机器人轨迹生成:轨迹规划与路径规划

    机器人轨迹生成涉及到轨迹规划和路径规划两个关键概念,它们是机器人运动控制中的重要组成部分。下面对轨迹规划和路径规划进行深入比较。 轨迹规划(Trajectory Planning): 定义:轨迹规划是指在机器人运动中确定机器人末端或关节的期望轨迹。它是在特定的工作空间中

    2024年02月12日
    浏览(48)
  • 清洁机器人规划控制方案

    作者 联系方式 Forrest 709335543@qq.com 室内商用 扫地/洗地 机器人规划控制(PNC)方案。有以下功能包组成: clean_msg:功能消息定义 clean_pnc:规划控制算法 clean_rviz:rviz仿真测试插件 目前PNC方案支持以下功能: 定点自主导航 固定路线清洁 区域覆盖清洁 贴边沿墙清洁 自主返航

    2024年02月16日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包