软件工程

本类阅读TOP10

·PHP4 + MYSQL + APACHE 在 WIN 系统下的安装、配置
·Linux 入门常用命令(1)
·Linux 入门常用命令(2)
·使用 DCPROMO/FORCEREMOVAL 命令强制将 Active Directory 域控制器降级
·DirectShow学习(八): CBaseRender类及相应Pin类的源代码分析
·基于ICE方式SIP信令穿透Symmetric NAT技术研究
·Windows 2003网络负载均衡的实现
·一网打尽Win十四种系统故障解决方法
·数百种 Windows 软件的免费替代品列表
·收藏---行百里半九十

分类导航
VC语言Delphi
VB语言ASP
PerlJava
Script数据库
其他语言游戏开发
文件格式网站制作
软件工程.NET开发
<<AI入门(4)>>(C)

作者:未知 来源:月光软件站 加入时间:2005-2-28 月光软件站

我们讲一讲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>


相关文章

相关软件