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)
blank

相关推荐

  • 二进制 补码 反码 原码「建议收藏」

    二进制 补码 反码 原码「建议收藏」原码补码反码

  • 霍尼韦尔与浙江石化扩大合作,助力中国最大石化项目进一步建设[通俗易懂]

    霍尼韦尔与浙江石化扩大合作,助力中国最大石化项目进一步建设[通俗易懂]霍尼韦尔在第二届中国国际进口博览会上宣布,浙江石油化工有限公司(以下称“浙江石化”)将在其位于浙江省舟山的炼化一体化二期项目采用霍尼韦尔一系列先进技术,包括工艺技术、催化剂、关键设备和控制自动化技术。舟山炼化一体化项目是中国国家经济最新发展规划中的数个大型石化产业基地之一。合作内容包括:霍尼韦尔UOPMD/ECMD塔盘,用于两套240万吨芳烃装置中的精馏和汽提环节,为客户提供出色的性能和经济效…

    2022年10月16日
  • /etc/ssh/sshd_config 关建字:PermitRootLogin no  禁示以root身份登录服务器

    /etc/ssh/sshd_config 关建字:PermitRootLogin no  禁示以root身份登录服务器这种情况,不会影响,普通用户su到root

  • Navicat 15 激活补丁破解方法

    Navicat 15 激活补丁破解方法,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 安卓ddos攻击器_android设备是什么意思

    安卓ddos攻击器_android设备是什么意思原标题:Android移动设备上的DDOS攻击双11马上要到了,你家网站做好准备了吗什么是DDOS攻击?举个形象的例子你就明白了:某饭店可以容纳100人同时就餐,某日有个商家恶意竞争,雇佣了200人来这个饭店坐着不吃不喝,导致饭店满满当当无法正常营业。(DDOS攻击成功)老板当即大怒,派人把不吃不喝影响正常营业的人全都轰了出去,且不再让他们进来捣乱,饭店恢复了正常营业。(添加规则和黑名单进行D…

    2022年10月21日
  • 变量以及数据类型_数据类型定义

    变量以及数据类型_数据类型定义变量以及数据类型变量的相关概念为什么需要变量变量的介绍概念变量使用的基本步骤变量使用注意事项变量的数据类型注意:数据类型相关整型:基本介绍整数的类型整型的使用细节浮点类型基本介绍浮点类型说明一下:浮点型使用细节字符类型基本介绍字符类型使用细节字符类型本质探讨布尔类型基本介绍变量的相关概念为什么需要变量不论是使用哪种高级程序语言编写程序,变量都是其程序的基本组成单位。如下代码:voidmain(){ inta=1;//定义了一个整型变量,取名为a,并赋值为1(强数据类型语言) int

    2022年10月21日

发表回复

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

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