代价树搜索

代价树搜索（cost-tree search），工学-控制科学与工程-智能系统-智能系统-问题求解-搜索论，一种考虑节点间代价的盲目搜索策略。基本内容在实际问题求解中，将一个状态变换成另一个状态时所付出的操作代价(或费用)是不一样的，即状态空间图中各有向边的代价是不一样的。把有向边上标有代价的搜索树称为代价搜索树，又称代价树。盲目搜索方法假设状态空间中各有向边代价相同，然而在实际中这样的假设并不合理。例如城市中的交通问题，各城市间的距离并不相同。为此，在搜索树的过程中需要对每条边标出代价。在代价树中，最小代价路径和最短路径很可能是不同的。代价树搜索的目的是找到代价最小的路径。根据搜索方法角度的不同，代价树搜索可分为代价树宽度优先搜索和代价树深度优先搜索。代价树宽度优先搜索的基本思想是：每次从OPEN表中选择一个代价最小的节点，移入COLSED表。因此，每当对一节点扩展之后，就要计算它的所有后继节点的代价，并将它们与OPEN表中已有的待扩展的节点按代价的大小从小到大依次排序。而从OPEN表选择被扩展节点时即选择排在最前面的节点（代价最小）。代价树宽度优先搜索算法是完备算法。