运动规划(Motion planning)- Grassfire 算法

好的,第一篇技术博客。我们开始吧。

image.png

刷过leetcode的朋友看见这张应该会会心一笑,BFS,DFS这类词争先恐后往外跳。但是呢,太高级了,我的朋友们。让我们先用一种最文艺(傻气)的办法,来解决这个问题。

我们的目标是:找到start-end之间的最短路径,如图所示


image.png

来吧,Grassfire 算法。小时候,大家都背过一首诗:离离原上草,一岁一枯荣。 野火烧不尽,春风吹又生。说的就是这种算法。这首诗告诉我们,草,都是从旁边的草开始燃烧蔓延的!grassfire-烧草,就这么简单又有力。

首先把终点的距离设定为0,然后设定距离终点最近的格子距离为1。如图所示

image.png

然后,距离1最近的格子是2,距离2最近的格子是3,以此类推

image.png

好了,这时候每一个数字都代表这该单元格到终点的距离。我们把数字连起来,就形成了最短路径,注意了,这个路径很可能不是唯一解。


image.png

整个过程用伪代码表示就是


image.png

但是有些时候,我们会遇见走不通的情况,我们写代码的时候就要考虑好这个问题


image.png

实现过程:
1.如果start-end之间有路,找到最短路径
2.如果start-dend之间没有路,跳出循环,报错

下面谈谈这个算法计算复杂度的问题,这个算法是一种遍历搜索,火会席卷每一个角落。

计算复杂度为:
image.png

其中,V是图中格子的数量。我们假设我们有100个格子,要访问的格子数
2维棋盘:100 X100 = 1000
3维棋盘: 100X100X100 = 1000000
6维棋盘: 100X100X100X100X100X100 =1000000000000

1000000000000啊朋友们,什么概念,就差不多和天上的星星一样多了哇!grassfire的计算量随着格子的变多或者维度的上升而变得很大。

好啦,总的来说这是一个很简单的算法,一定能找到全局最优解。宛若春风吹过每一个角落,吹到我们每一个人的心中

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 回溯算法 回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并...
    fredal阅读 14,015评论 0 89
  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 5,384评论 0 12
  • 本篇将尝使用canvas + wasm画一个迷宫,生成算法主要用到连通集算法,使用wasm主要是为了提升运行效率。...
    极乐君阅读 3,859评论 0 9
  • 写在前面的话 无意中在cocoaChina的首页看到了一篇介绍A*算法用swift实现的文章,对A*寻路算法产生了...
    数码资讯站阅读 15,434评论 2 57
  • 现实生活中有很大一类问题可以用简洁明了的图论语言来描述,可以转化为图论问题。 相关定义 图可以表示为G=(V, E...
    芥丶未央阅读 1,835评论 0 7

友情链接更多精彩内容