A 星算法总结_数据结构与算法知识点总结

A 星算法总结_数据结构与算法知识点总结A星算法总结A星算法FPGAEDA工具VPR布线器所采用的布线算法,面试滴滴的时候听说他们的路径规模用的也是A星算法,感觉这个算法还蛮厉害的,对这个算法进行一个总结。文章http://www.tuicool.com/articles/MJrYz26对这个算法用语言描述的很好,搬运下:  A星寻路算法显然是用来寻路的,应用也很普遍,比如梦幻西游。。。算法的思路很简单,就是在bfs的

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

A 星算法总结

A 星算法FPGA EDA工具VPR布线器所采用的布线算法,面试滴滴的时候听说他们的路径规模用的也是A 星算法,感觉这个算法还蛮厉害的,对这个算法进行一个总结。
文章http://www.tuicool.com/articles/MJrYz26 对这个算法用语言描述的很好,搬运下:

  A星寻路算法显然是用来寻路的,应用也很普遍,比如梦幻西游。。。算法的思路很简单,就是在bfs的基础上加了估值函数。它的核心是 F(x) = G(x) + H(x) 和open、close列表。
  G(x)表示从起点到X点的消耗(或者叫移动量什么的),H(X)表示X点到终点的消耗的估值,F(x)就是两者的和值。open列表记录了可能要走的区域,close列表记录了不会再考虑的区域。我们每次都选F值最小的区域搜索,就能搜到一条到终点的最短路径,其中估值H越接近准确值,需要搜索的节点就越少。

A星算法的步骤:
{
将起点区域添加到open列表中,该区域有最小的和值。
重复以下:
  将open列表中最小F值的区域X移除,然后添加到close列表中。
  对于与X相邻的每一块可通行且不在close列表中的区域T:
如果T不在open列表中:添加到open列表,把X设为T的前驱
如果T已经在open列表中:检查 F 是否更小。如果是,更新 T的F值 和前驱
直到:
  终点添加到了close列表。(已找到路径)
  终点未添加到close列表且open列表已空。(未找到路径)
}

估值函数H(X)很有意思,不同的估值函数会带来不同的路径,因此在二维坐标系统下作了个小小的测试:

曼哈顿距离

在二维平面中 点(x1,y1)和点(x2, y2)的曼哈顿距离:H(X)= abs(x1-x2)+ abs(y1 – y2)。其中红色的点表示考察过的点,绿色的点表示最终生成的路径。
曼哈顿距离

殴几里得距离

在二维平面中 点(x1,y1)和点(x2, y2)的曼哈顿距离:H(X)= sqrt((x1-x2)* (x1-x2)+ (y1 – y2)*(y1 – y2))
这里写图片描述

水平距离

这是测着玩的: H(X)= abs(x1 – x2)
这里写图片描述

垂直距离

这也是我测着玩的:H(X) = abs(y1 – y2)
这里写图片描述

迪杰斯特拉算法

令H(x) = 0, A星算法就变成了 迪杰斯特拉算法,想想还真是!!
这里写图片描述

契比雪夫距离

H(X)= max( abs(x1 – x2), abs(y1 – y2) )
这里写图片描述

看来加上H(X)效果大有改善!!
代码为原创:http://download.csdn.net/detail/wjwever1/9669482

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188532.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 电视猫的节目单_湖南卫视2020年电视剧节目单

    电视猫的节目单_湖南卫视2020年电视剧节目单SubMain()DimstrTextAsStringDimobjHTTPAsObjectDimKey_qAsStringDimKey_aAsStringDimK

  • Mint-UI

    Mint-UI一、MUI不同于Mint-UI,MUI只是开发出来的一套很好用的代码片段,里面提供了配置的样式,配置的HTML代码段,类似于Bootstrap;而Mint-UI,是真正的组件库,是使用了Vue技术

  • 【Android开源项目分析】android轻量级开源缓存框架——ASimpleCache(ACache)源代码分析

    【Android开源项目分析】android轻量级开源缓存框架——ASimpleCache(ACache)源代码分析

  • a卡eth挖矿教程_a卡挖eth用什么内核

    a卡eth挖矿教程_a卡挖eth用什么内核  对于ETH挖矿来说,A卡无疑是最合适的选择,性价比高。如果你只想挖ETH,那选择A卡无疑是最明智的。但是,在使用A卡挖矿的过程中,往往会出现很多难以解决的问题,影响挖矿的效率。其中很大一部分原因是由于A卡本身的特性导致的。很多人在使用A卡挖ETH的过程中会出现这样一种情况:开始一段时间还是正常的运行,但是运行一段时间后就开始报错,导致无法正常挖矿。这是由于A卡具有自动更新的特性。所以在使用A卡…

    2022年10月16日
  • .NET中代理服务器WebProxy的各种用法

    .NET中代理服务器WebProxy的各种用法因为涉及到代理的各种情况,WebRequest和WebProxy类的文档写的相当复杂,不但各个文档关注点不同,而且不同版本的同一文档也有小小的区别,网上也没有关于这个类的相关文章。于是乎这篇Blog是我钻研半天MSDN很久后总结并且花了一小时憋出来的,希望下面的内容能帮到大家。(AcDown中也使用了相关的代码,有兴趣的可以找来看看【解析】.NET中代理服务器WebProxy的各种用法)直接进入

  • IntelliJ IDEA 2022.01 x64 激活码【中文破解版】

    (IntelliJ IDEA 2022.01 x64 激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html1M2OME2TZY-eyJsa…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号