北大公开课-人工智能基础13 通过搜索求解问题之搜索求解（树搜索和图搜索比较）

用树状搜索拓扑图，简化图搜索问题，简化成逻辑节点及其相互关系

(资料图)

使用树搜索，解决图搜索问题

功能：通过树搜索（问题）方案， 返回一个解决方案或报错（无路可走状态）

初始化定义出发状态（问题的初始状态）

循环

如果出发状态为空，则返回 报错

选择一个初始状态相邻的节点

如果 该相邻节点状态为解决问题状态，则返回 对应的解决方案

“初始状态”是一种数据结构，用户存储所有的当前（阴影部分）的节点信息

循环扩展持续进行，直到找到一个解，或者没有其他状态可扩展（无路可走）。

初始状态又成为open list， 将后继节点添加到初始状态frontier中

红字部分为图搜索算法比树搜索算法多出的部分

定义了拓展状态explored，也称为closed list，拓展状态初始值为空

如果frontier为空，也即没有可扩展的节点，则返回失败

从frontier中，取出一个叶节点

如果该叶节点包含目标状态，则返回对应的解

然后将该节点扩展到explored这个数据结构中

继续扩展该节点，并将后继节点添加到frontier数据结构中，

仅当frontier或explored两个数据集中都不存在该节点时，我们继续上述循环（直到该节点包含目标状态为止）。

标签：