北大公开课-人工只能基础 15 通过搜索求解问题之无信息搜索策略 （二）

一致代价搜索，实质上是选择路径代价最低的节点来优先扩展

一致代价搜索算法解释：

首先和宽度优先搜索相同，先定义四个变量，四个变量的定义与宽度优先搜索也相同。

变量 node 定义是当前状态的节点，初始化，该变量为问题的初始状态 problem INITIAL-STATE

PATH-TEST 定义为路径的代价，也即步骤代价。初始化为零 （初始状态的当前节点，即为初始状态节点）

frontier 参数是按照路径的代价进行排序，（含义就是代价最低的路径优先探索）

explored （已探索过的节点之集合），初始化为一个空集 

loop do 主循环

第一个步骤，首先口判断frontier表是否为空，如果为空，则返回失败

如果frontier不为空，则从frontier中弹出一个路径成本最低的值，计入node节点表中，

    如果该节点能够通过目标测试，则将该节点作为解solution返回。

    否则将该节点放入explored表中，代表该节点已探索过。

    对于该节点的每一个动作（该节点本身已经处于路径代价最低的路径上），执行下列子循环语句：

        将该节点的下一级节点，计入child 子节点表中

               判断：如果该子节点不在explored表或者不在frontier表中，

               则将该子节点，插入frontier表中。

        否则，如果child在frontier中，且该chilld具有最高的路径代价

则将该子节点child作为当前的frontier节点中。

优先扩展路径代价最低的子节点，

与宽度优先搜索相比，

一致代价搜索的时间复杂性和空间复杂性是一样的。