<![CDATA[我们讲一讲A*算法:
我们描述一个特别的估价函数f(n),它能估算出从起始节点到n最小代价路径的代价和节点n到一目标节点的最小代价路径的代价总和.
我们在介绍A*算法之前先介绍一些有用的记号:
k(n,m)表示从节点n到m的之间的最小代价路径的代价,m和n必须是连通的. h*(n)表示n到整个目标节点集合的所有最小代价路径中最小的一个,也就是说h*(n)是n到目标节点的最小代价.我们定义g*(n)=k(S,n)表示从开始到节点n的最小代价的路径的代价.设f*(n)=g*(n)+h*(n)表示从开始节点通过节点n到目标节点的最小代价路径的代价.
我们的估价函数f(n)=g(n)+h(n)是f*(n)的一个估计.其中h是h*的估计,g是g*的估计.h有赖于启发的信息,我们称h为启发函数.
下面我们就来讲讲A*算法:
1.把S放入OPEN表中,记f=h,令CLOSED为空表.
2.若OPEN表为空,失败退出.
3.在OPEN表中选取有最小f值的节点为best,并将它放入CLOSED表.
4.若best节点是目标节点,则成功退出.
5.best节点不是目标节点,则把best节点扩展,产生后续节点children.
6.对于每个children进行如下的操作:
a..建立值相父节点的指针
b..计算g(children)=g(best)+g(best,children)
c..如果children在OPEN表中,比较新旧路径,如果小于就把原来节点的父节点改为best并用新的代价取代原来的代价.
d..如果节点在CLOSED表中,转向c
e..如果节点即不在OPEN表中也不在CLOSED表中,则加入表OPEN中.
7.计算f值
8.GOTO 2
我们没有详细讨论A*算法的性质,有问题欢迎来信<A href="mailto:sevecol@163.net">sevecol@163.net</A>]]>
|
本类阅读TOP10