文件名称：A*以及迭代加深的A*算法（IDA*）
文件大小：21KB
文件格式：DOC
更新时间：2011-10-26 05:56:31
A* IDA*
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）,也就是说，搜索的范围在那些不超过给定值的节点中进行深度优先搜索。如果搜索不成功，那么返回头节点，并且使限定的耗散值变大（具体为所有超过上次限定值节点中的最小耗散），也就是说，在迭代过程中我们需要纪录一下那些我们已经探知的，超过限定的节点的耗散函数值，然后挑选其中的最小值，再次进行搜索。（个人感觉，太浪费前面已经所作的工作了）。