当前位置: 王朝网络 >> other >> <<AI入门(4)>>(C)

<<AI入门(4)>>(C)

王朝other·作者佚名 2006-01-08

我们讲一讲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*算法的性质,有问题欢迎来信sevecol@163.net

点击展开全文

上一篇：<<AI入门(5)>>(C)

下一篇：<<AI入门(3)>>(C)

免责声明：本文为网络用户发布，其观点仅代表作者个人观点，与本站无关，本站仅提供信息存储服务。文中陈述内容未经本站证实，其真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。

没有找到您想要的？点此查看更多相关文章
相关文章▶

2023年上半年GDP全球前十五强
百态 2023-10-24

美众议院议长启动对拜登的弹劾调查
百态 2023-09-13

上海、济南、武汉等多地出现不明坠落物
探索 2023-09-06

印度或要将国名改为“巴拉特”
百态 2023-09-06

男子为女友送行，买票不登机被捕
百态 2023-08-20

手机地震预警功能怎么开？
干货 2023-08-06

女子4年卖2套房花700多万做美容：不但没变美脸，面部还出现变形
百态 2023-08-04