A*是对上面算法的一个改进,具体来说就是改变了代价函数,例如,目标是 D,起始为 A,首先
的初始化将每个节点到 D 的直线距离赋给节点做代价函数,然后在访问了 A 之后,马上预测
A 的子节点 BC,求得 B 的实际代价为 A 到 B 的花费加上 B 的原始代价.同理取得 C 的实际代
价,之后在 A 的所有子节点中选择代价最小的节点进行扩展。上面的过程重复进行直到找到
目标。
迭代加深(ID),有些许不同于上面的算法, ID 算法将深度设置为 dep,对于一个
树做深度优先的遍历(节制条件:所有节点的深度不大于 dep),如果没有找到目标,那
么将 dep++,重复上面的过程直到找到目标。
IDA*算法(也就是迭代深度优先算法),将上面的 A*和 ID 算法结合起来,也就是,
在进行搜索时,使用耗散值替代 ID 中的深度值(f=g +h),也就是说,搜索的范围在那些
不超过给定值的节点中进行深度优先搜索。如果搜索不成功,那么返回头节点,并且使限
定的耗散值变大(具体为所有超过上次限定值节点中的最小耗散),也就是说,在迭代过
程中我们需要纪录一下那些我们已经探知的,超过限定的节点的耗散函数值,然后挑选其
中的最小值,再次进行搜索。(个人感觉,太浪费前面已经所作的工作了)。
评论3
最新资源