接着上回的说,首先提出一个贪婪算法,此算法每次不考虑实际的情况,简单的从代价函数出发,选择下次要要扩展的节点.因此引入一个问题,贪婪算法是不完备的,可能会找不到目标.
      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）,也就是说，搜索的范围在那些不超过给定值的节点中进行深度优先搜索。如果搜索不成功，那么返回头节点，并且使限定的耗散值变大（具体为所有超过上次限定值节点中的最小耗散），也就是说，在迭代过程中我们需要纪录一下那些我们已经探知的，超过限定的节点的耗散函数值，然后挑选其中的最小值，再次进行搜索。（个人感觉，太浪费前面已经所作的工作了）。
      说了这些，上面的算法总没有脱离一个话题，即代价函数。如果你能找到一个好的代价函数，不但可以使你的算法变成完备的，而且将使花费代价大大减小。通常一般流行的代价函数有海明距离，直线距离，反正越是将问题抽象化，代价函数越好找。当然找的时候，可以人为的忽略掉很多的限制。比如，AB之间没有路，在抽象时，我们可以假设他们之间有路。
      因为还没有学会贴图，所以描述可能不清楚，见谅。在8数码游戏之下，程序见文集。

posted on 2006-11-10 18:18  空空色色  阅读(4245)  评论()    收藏  举报