专栏首页ypwA*算法详细讲解以及实现

A*算法详细讲解以及实现

A*简介

A算法是启发式算法重要的一种,主要是用于在两点之间选择一个最优路径,而A的实现也是通过一个估值函数

F=G+H

  • G表示该点到起始点位所需要的代价
  • H表示该点到终点的曼哈顿距离。
  • F就是G和H的总和,而最优路径也就是选择最小的F值,进行下一步移动(后边会做详细介绍)

曼哈顿距离

​ Paste_Image.png

上图中这个熊到树叶的曼哈顿距离就是蓝色线所表示的距离,这其中不考虑障碍物,假如上图每一个方格长度为1,那么此时的熊的曼哈顿距离就为9. 起点(X1,Y1),终点(X2,Y2),H=|X2-X1|+|Y2-Y1| 我们也可以通过几何坐标点来算出曼哈顿距离,还是以上图为例,左下角为(0,0)点,熊的位置为(1,4),树叶的位置为(7,1),那么H=|7-1|+|1-4|=9。

A算法现在被广泛应用与电脑游戏中的路径规划问题。我们就以此为例来介绍A算法的具体实施步骤。如下图所示,其中A表示起点,B表示终点,黑色的实心方块表示障碍物。此外我们假设水平或垂直方向上相邻的两个方块之间距离是10,那么对角线方向上相邻的两个方块距离就约是14。

算法开始,我们首先搜索A相邻的所有可能的移动位置(对应于图中的绿色方块)。每个方块左上角的值G表示该点到A的距离,右上角值为H,注意H不能大于该点到B的距离,所以这里的H就取其到B的距离。最后,还要计算一个F值,F=H+G。

然后像Dijkstra算法一样,我们选一个F值最小的节点来做继续搜索。也就是上图中A的邻域中位于左上角的值(F=42)。然后更新该节点的领域值。

这时你会发现,出现了三个F值都等于48的节点。到底应该选择哪一个来继续接下来的搜索呢?这时需要考察它们中的那个H值最小,结果发现H=24是最小的,所以下面就要从该点出发继续搜索。于是更新该节点的邻域方块中的值。

这个时候再找出全局F值最小的点,结果发现有两个为48(而且它们的H值也相当),于是随机选取一个作为新的出发点并更新其邻域值(例如选择右上方的方块),然后在从全局选取F最小的更新其邻域值,于是有:

此时全局F最小的值为54,而且F=54的节点有两个,所以我们还是选择其中H值最小的来做更新。于是更新该节点邻域方块中的值。这里你需要注意的一个地方是,F=54的红色节点下方邻域(F=68)的方块中,G=38。但是,从A到该节点的最短路径应该是30。这是因为目前程序所选择的路径是下图中紫色线路所规程出来的路径,其G的增长序列是14→24→38。

不过不要紧,只要继续执行算法,更新全局F值为最小节点(F=54)的方块,上面的G值就会给更新为正确的值了。

此时,全局F值最小的方块中F=60,所以更新该节点邻域方块中的值。

现在全局F值最小的有两个,都为68,此时先更新H最小的。这是其实程序已经发现左侧F=68的节点并不能引导一条更短的路径。于是接下来就要转向右侧F=68的节点,并以此为新起点搜索路径。

最终反复执行上述过程,你就会得到如下图中蓝色方块所示的一条最短路径。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Best Cow Line(POJ 3617)

    题意:给定长度为n的字符串s,要构造一个长度为n的字符串t。起初,t是一个空串,随后反复进行下列任意操作。

    用户7727433
  • 购物

    在遥远的东方,有一家糖果专卖店。 这家糖果店将会在每天出售一些糖果,它每天都会生产出m个糖果,第i天的第j个糖果价格为C[i][j]元。 现在的你想要在接下...

    用户7727433
  • POJ 3278 BFS + queue

    农夫知道一头牛的位置,想要抓住它。农夫和牛都于数轴上,农夫起始位于点N(0<=N<=100000) ,牛位于点K(0<=K<=100000) 。农夫有两种移动方...

    用户7727433
  • Excel每隔两行自动求和一次怎么操作?

      今天ytkah得到一份数据,要求进行统计分析,由于是原始数据,还没处理过,数据量有点大,如下图所示(Excel每隔两行自动求和),每天的数字由两项组成,男生...

    ytkah
  • 分布式系统监控:通过JMX看对象模型的优势

    在Java的圈子里面,任何一个技术产品,一般会先公开一系列的接口定义,然后推出对这个接口的一系列实现软件,这种做法,是一个对软件开发非常有益的进步。因为这让使用...

    韩伟
  • 最新Flash漏洞现已加入Nuclear漏洞利用工具包

    微信号:freebuf 趋势科技最新研究发现,Nuclear 漏洞利用(Exp)工具包的最新版本已加入了三月刚刚修复的Flash Player漏洞(CVE-20...

    FB客服
  • K8s远程调试,你的姿势对了吗?

    ? 前言 本文讲述k8s各个系统组件如何进行远程调试, 适用于所有mac、windows以及不方便在本地进行调试的技术宅; 像k8s代码量如此庞大的系统, 调...

    腾讯云TStack
  • 腾讯 Tars-Go 服务 Hello World——从 HTTP 开始

    Tars 框架最新的版本已经把内部的 Taf-Go 开源为 Tars-Go。作为与时俱进的程序员,当然要尝鲜啦。

    amc
  • 伸展树

    没看懂,多看几遍吧 1 简介: 伸展树,或者叫自适应查找树,是一种用于保存有序集合的简单高效的数据结构。伸展树实质上是一个二叉查找树。允许查找,插入,删除,删除...

    用户1154259
  • 一天一大 lee(恢复二叉搜索树)难度:困难-Day20200808

    前端小书童

扫码关注云+社区

领取腾讯云代金券