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

文章目录

• 代价树及其代价运算
• 概念
• 代价树的广度优先搜索
• 算法描述
• 总结
• 代价树的深度优先搜索

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

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

代价树及其代价运算

概念

通常，我们把每条边上都标有其代价的树称为代价树。

在代价树中，可以用$g\left(n\right)$表示从初始节点$S_0$到节点n的代价，用$c(n_1,n_2)$表示从父节点$n_1$到其子节点$n_2$的代价。这样，对节点$n_2$的代价有：
$g\left(n_2\right)=g\left(n_1\right)+c(n_1,n_2)$

通常，在代价树中最小代价的路径和最短路径有可能是不同的。

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

代价树的广度优先搜索

也称分支限界法。每次从Open表中选择节点或往Closed表中存放节点时总是选择代价最小的节点。

算法描述

总结

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

代价树的深度优先搜索

算法步骤与广度优先基本相同，区别在于代价树的深度优先搜索每次都是从刚扩展的子节点中选择一个代价最小的节点。