赞
踩
以下算法是我对A星算法的初浅理解而写出来的,主要作为记录用,非常有可能有很多错误,想借来参考的请慎重,如果发现有问题的麻烦各路大神提出。谢谢大神。
A算法框架:
自定义步骤:
1、定义一个状态的描述方式,能将任意状态与需要与之区分的状态区分开来。
2、预测一个状态可能跳转到的所以下一个状态(通常意为状态移动代价不是正无穷,或者非常非常大,会对所有的移动结果产生很大的影响)。
3、定义g(x)的计算规则,即定义从初始状态节点到当前节点的移动总代价。那首先得定义任意两个状态A和B,若A走到B,则这个状态跳转的实际代价计算规则。把已走过的路径的任意相邻状态的权重累加即能得到g(x)。通常把状态间不能跳转的设成正无穷以实现,让不能跳转的两个状态真的不能跳转。(可以把初始节点的g(x)设为0)
4、定义h(x)的计算规则,即定义当前状态A,如果跳到目标状态B(寻路终点),预测需要多少代价的计算规则。如果需要实现A星,一定要让预测的代价小于实际代价。即一定要让h(x)a-b<h*(x)a-b。个人的理解是要让h(x)a-b算出来的代价一定要小于最后g(x)a-b算出来的代价。
【对g(x)和h(x)计算规则的设计,特别是h(x)相对于g(x)相对规则的设计是A星算法质量的好坏,特别是】
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。