动态规划—机器人移动问题(Java)

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

😀前言
机器人移动问题是一个经典的动态规划应用场景,它涉及到在给定范围内的位置上进行移动,并计算到达目标位置的方法数。本文将介绍三种解决这一问题的方法:暴力递归、缓存法和动态规划。通过比较不同方法的优缺点,我们将深入理解动态规划在解决问题中的重要性以及如何优化算法以提高性能和空间利用率。

🏠个人主页:尘觉主页

动态规划–机器人移动问题(Java)

机器人移动问题

机器人可在1-N的位置上进行移动,规定三个数据 分别是机器人当前位置 机器人可以移动的步数 机器人的目标位置 计算出机器人用光步数后到达目标位置的方法数

暴力递归

机器人在1-N的范围上进行移动,一共会有3种情况,

在1时,只能右移动

在N时,只能左移动

在中间时,既可以左移,又可以右移;

所以可以根据这几种情况进行暴力递归

递归的终止条件是 当前步数为0 且处于目标位置上

public int moveTimes(int N,int cur,int target,int steps ){
        //三个参数分别是可以移动的范围 当前位置 目标位置
        if(steps==0){
            //如果没有步数了进行返回
            return cur == target?1:0;
        }
        if(cur==1){
            return moveTimes(N,cur+1,target,steps-1);
        }
        if (cur == N){
            return moveTimes(N,cur-1,target,steps-1);
        }
        return moveTimes(N,cur+1,target,steps-1) + moveTimes(N,cur-1,target,steps-1);
    }

缓存法

通过这种方式我们就可以取得最终的全部可能的情况,但是显然,我们的暴力递归,会多做很对运算。比如当机器人处于中间位置的时,当前的状态是 cur = 5,steps = 10 那么在接下来的递归中我们会有这样的2个分支

​ (4,9)-> (5,8)/ (3,8) | (6,9)-> (5,8)/(7,8)

那么我们的(5,8)在计算过一次之后,还会再次进行计算。这样的情况下,我们的运行时间就会变得过长 。

所以我们引出了傻缓存法,缓存的作用在于,我们进行一次递归的过程中,便将这一次递归的结果记录到缓存中,当下一次再次递归时,可以直接调用之前在缓存中数,进行返回,而不是继续向下递归了,这种方法就是再用时间来换空间!

那么回到这道题,我们的cache就可以用一个二维数组来进行存储,row为我们的当前位置 col 为我们的可移动步数

//傻缓存法
    public int moveTimes(int N,int cur,int target,int steps,int[][] cache){
        //cache需要初始化;所有值换成-1;
        if(cache[cur][steps]!=-1){
            return cache[cur][steps];
        }
        int result = -1;
        //分3种情况进行递归移动
        //basecase
        if (steps == 0){
            result = cur == target?1:0;
        } else if (cur == 1){
            result = moveTimes(N,cur+1,target,steps-1,cache);
        } else if(cur == N){
            result = moveTimes(N,cur-1,target,steps-1,cache);
        } else{
            result = moveTimes(N,cur+1,target,steps-1,cache)+moveTimes(N,cur-1,target,steps-1,cache);
        }
        cache[cur][steps] = result;
        return result;
    }
    public void setCache(int[][] cache){
        for (int i = 0; i < cache.length; i++) {
            for (int j = 0; j < cache[1].length; j++) {
                cache[i][j] = -1;
            }
        }
    }

这里相比第一种方式会更快一些,但是也是浪费了较大的空间;

动态规划

我们结合一二一起看,会发现我们能basecase的情况发生时,可以在缓存即二维数组中确定一些数,当 step = 0时,在二维数组中这一列,我们除了是目标位置会返回 1 以外,其他位置都会返回 0 。所以我们就可以把确定的数据填写到二维数组中,在看暴力递归的其他情况,当我们在第 1 行的时候 ,只能向右移动,所以我们的返回值,要从相对于二维数组中的当前位置的左下角中的这个元素获取返回值,同理当我们在最后 1 行的时候,那么就应该从当前位置的左上角进行取返回值了,当我们在中间位置的时候,我们的则是需要从左上和左下相加来获取返回值,依次类推,我们会回到我们最开始的位置,这时就是我们需要的结果了。

    public int moveTimes1(int N,int cur,int target,int steps){
        int[][] cache = new int[N+1][steps+1];
        //给第一列进行赋值
        cache[target][0] = 1;
        for (int i = 1; i <= steps; i++) {
            //第一行手动操作
            cache[1][i] = cache[2][i-1];
            for (int j = 2; j <= N-1 ; j++) {
                cache[j][i] = cache[j+1][i-1]+cache[j-1][i-1];
            }
            cache[N][i] = cache[N-1][i-1];
        }
        return cache[cur][steps];
    }

完整的代码

@SuppressWarnings({"all"})
public class Robot {
    
    //测试
    public static void main(String[] args) {
        Robot robot = new Robot();
        int[][] cache = new int[6][6];
        robot.setCache(cache);
        System.out.println(robot.moveTimes(5, 2, 3, 5, cache));
        System.out.println(robot.moveTimes(5,2,3,5));
        System.out.println(robot.moveTimes1(5,2,3,5));
    }
    
    //动态规划法
    public int moveTimes1(int N,int cur,int target,int steps){
        int[][] cache = new int[N+1][steps+1];
        //给第一列进行赋值
        cache[target][0] = 1;
        for (int i = 1; i <= steps; i++) {
            //第一行手动操作
            cache[1][i] = cache[2][i-1];
            for (int j = 2; j <= N-1 ; j++) {
                cache[j][i] = cache[j+1][i-1]+cache[j-1][i-1];
            }
            cache[N][i] = cache[N-1][i-1];
        }
        return cache[cur][steps];
    }
    
    //暴力递归法
    public int moveTimes(int N,int cur,int target,int steps ){
        //三个参数分别是可以移动的范围 当前位置 目标位置
        if(steps==0){
            //如果没有步数了进行返回
            return cur == target?1:0;
        }
        if(cur==1){
            return moveTimes(N,cur+1,target,steps-1);
        }
        if (cur == N){
            return moveTimes(N,cur-1,target,steps-1);
        }
        return moveTimes(N,cur+1,target,steps-1) + moveTimes(N,cur-1,target,steps-1);
    }

    //傻缓存法
    public int moveTimes(int N,int cur,int target,int steps,int[][] cache){
        //cache需要初始化;所有值换成-1;
        if(cache[cur][steps]!=-1){
            return cache[cur][steps];
        }
        int result = -1;
        //分3种情况进行递归移动
        //basecase
        if (steps == 0){
            result = cur == target?1:0;
        } else if (cur == 1){
            result = moveTimes(N,cur+1,target,steps-1,cache);
        } else if(cur == N){
            result = moveTimes(N,cur-1,target,steps-1,cache);
        } else{
            result = moveTimes(N,cur+1,target,steps-1,cache)+moveTimes(N,cur-1,target,steps-1,cache);
        }
        cache[cur][steps] = result;
        return result;
    }

    public void setCache(int[][] cache){
        for (int i = 0; i < cache.length; i++) {
            for (int j = 0; j < cache[1].length; j++) {
                cache[i][j] = -1;
            }
        }
    }
}

😄总结

通过本文的学习,我们了解了三种解决机器人移动问题的方法:暴力递归、缓存法和动态规划。暴力递归虽然简单易懂,但效率低下;缓存法通过牺牲空间来换取时间,提高了效率;而动态规划则利用填充二维数组的方式,避免了重复计算,进一步优化了性能和空间利用率。动态规划在解决各种问题中都有广泛的应用,是一种重要的算法思想。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞文章来源地址https://www.toymoban.com/news/detail-861343.html

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

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

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

相关文章

  • 基于Dijkstra算法的机器人编队路径规划问题

    基于Dijkstra算法的机器人编队路径规划问题 路径规划是机器人领域中的一个重要问题,它涉及确定从起点到目标点的最佳路径。Dijkstra算法是一种经典的图算法,用于解决最短路径问题。在本文中,我们将介绍如何使用Dijkstra算法来实现机器人编队的路径规划,并提供相应的

    2024年02月08日
    浏览(15)
  • 【路径规划matlab代码】基于遗传算法求解机器人栅格地图路径规划问题

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

    2024年03月08日
    浏览(13)
  • 【路径规划】基于遗传算法求解机器人栅格地图路径规划问题matlab代码

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

    2024年01月24日
    浏览(22)
  • 移动机器人农田机器人全覆盖路径规划

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

    2024年01月25日
    浏览(14)
  • 基于遗传算法求解机器人栅格地图路径规划问题matlab仿真

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

    2024年01月22日
    浏览(20)
  • 移动机器人运动规划及运动仿真

    博客地址:https://www.cnblogs.com/zylyehuo/ 基于[基于SLAM系统建图仿真,完成定位仿真],详见之前的博客 基于SLAM系统建图仿真,完成定位仿真 - zylyehuo - 博客园 参考链接 Autolabor-ROS机器人入门课程《ROS理论与实践》 ubuntu 18.04 结构树请参考下图

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

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

    2024年02月05日
    浏览(21)
  • 【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记

    Configuration Space等概念 机器人配置: 指机器人位置和所有点的表示。 DOF: 指用于表示机器人配置所需的最小的实数坐标的数量n。 C-space: 包含机器人n维所有配置的空间。 在C-space中机器人的pose是一个点。 机器人在C-space中被表示为一个点,pose包含为R,t 空间中的障碍物也需要映

    2024年01月22日
    浏览(14)
  • 动态规划学习——机器人运动

    问题: 一共有N个位置,机器人从start开始,走K步到end 机器人到1后只能向2运动,到N后只能向N-1运动,即不能越界,只能在1-N的位置运动 求总的路线的个数 例: N=4,startp=1,endp=3,K=4 则路线如下: 1-2-3-4-3 1-2-3-2-3 1-2-1-2-3 总共有3条路线 参考资料: bilibili 马士兵教育——左程云

    2024年01月22日
    浏览(15)
  • 【深蓝学院】移动机器人运动规划--第5章 最优轨迹生成--笔记

    Ch2讲了基于搜索的路径规划方法,Ch3讲了基于采样的路径规划方法,这些都是global methods,框架都是Exploration and Exploitation,且在算力足够大的情况下,一定能够找到全局最优解。 除了global methods,还有local methods,主要是Deterministic Optimization确定性优化。基于优化的方法,主要

    2024年02月19日
    浏览(14)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包