【摘要】：取代扩展深度最浅的节点，代价一致搜索扩展的是路径消耗最低的节点 n。注意如果所有单步耗散都相等的话，这种算法就和广度优先搜索算法是一样的。代价一致搜索对一条路径的步数并不关心，而只关心所经步骤总的耗散。因此在扩展到一个具有能返回同一状态的零耗散行动的节点时就会陷入无限循环。这是因为代价一致搜索在探索包括耗散大但可能是有用的步骤的路径之前，可能而且经常会先探索耗散小的步骤所在的很大的树。
3.4.2 代价一致搜索
当所有单步耗散相等的时候，广度优先搜索是最优的，因为它总是先扩展深度最浅的未扩展节点。简单地延伸一下，我们可以找到一个对任何单步耗散函数都是最优的算法。取代扩展深度最浅的节点，代价一致搜索扩展的是路径消耗最低的节点 n。注意如果所有单步耗散都相等的话，这种算法就和广度优先搜索算法是一样的。
代价一致搜索对一条路径的步数并不关心，而只关心所经步骤总的耗散。因此在扩展到一个具有能返回同一状态的零耗散行动的节点时就会陷入无限循环（例如NoOp行动，即无操作行动）。我们可以保证完备性，倘若每一步的耗散都大于等于某个小的正值常数ε。这个条件同样可以有效地保证最优性。这也意味着沿着路径的路径耗散总是增加的。根据这个特性，很容易看出算法是按照路径耗散增加的顺序来扩展节点的。因此，第一个被选中进行扩展的目标节点就是最优解。（记住TREE-SEARCH 只对被选中扩展的节点应用目标测试。）我们建议尝试使用该算法来找到去往Bucharest的最短路径。
代价一致搜索由路径的耗散引导而不是深度，所以它的复杂度不能简单地用b和d来刻画。替代地，用 C*表示最优解的耗散值，并且假设每个行动的耗散至少为ε。那么这个算法最坏情况下的时间和空间复杂度为
，要比bd的值大得多。这是因为代价一致搜索在探索包括耗散大但可能是有用的步骤的路径之前，可能而且经常会先探索耗散小的步骤所在的很大的树。当所有的单步耗散都相等的时候，
就是bd。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
