人工智能--代价树的盲目搜索

在一般树的搜索策略中，我们都进行了一种假设，认为状态孔家那种各边的代价都相同，且为一个单位量。。

但是对许多实际问题，这样的假设是不实际的。例如，城市交通问题，各城市之间的距离不可能是相同的。

代价树及其代价运算

概念

在代价树中，可以用g(n)表示从初始节点S0​到节点n的代价，用c(n1​,n2​)表示从父节点n1​到其子节点n2​的代价。这样，对节点n2​的代价有：
g(n2​) = g(n1​) + c(n1​,n2​)

通常，在代价树中和有可能是不同的。

代价树搜索的目的是为了找到最佳解，即找到一条的解路径。

代价树的广度优先搜索

算法描述

1. 把初始节点S0​放入Open表中
2. 如果Open表为空，则问题无解，失败退出
3. 把Open表的第一个节点取出，放入Closed表，并记该节点为n
4. 考察节点n是否为目标节点，若是，则得到问题的解，成功退出
5. 若节点n不可扩展，则转第二步
6. 扩展节点n，将其子节点放入Open表的尾部，并未每一个子节点设置指向父节点的指针。按如下公式：
   g(n2​) = g(n1​) + c(n1​,n2​)
   计算各子节点的代价，并根据各节点的代价对Open表中的按照从小到大的顺序重新进行排序。。然后转到第二步。

总结

代价树的广度优先策略是完备的，如果问题有解则算法一定能找到它，并且找到的一定是最优解。

代价树的深度优先搜索

算法步骤与广度优先基本相同，区别在于代价树的深度优先搜索每次都是。