《人工智能：计算Agent基础》——3.4　一个通用搜索算法

3.4　一个通用搜索算法

这一节描述在图中寻找解路径的一个通用算法。这个算法独立于任何特定的搜索策略和特定的图。

通用搜索算法背后的直观理念就是给定一个图、一个起始节点集和一个目标节点集，循序渐进地从起始节点探索路径。这要通过维持已经探索过的从起始节点开始的路径的边界（或外围）来实现。边界包含能构成从起始节点到目标节点的初始部分的所有路径。（见图3-3，边界就是指通向灰色节点的那组路径。）77最初，边界包括从起始节点开始的无出弧的那些平凡的（不重要的）路径。随着搜索的深入，边界扩展到未扩展节点，最终到达目标节点。为了扩大边界，搜索者继续挑选，从边界去除路径，从最新节点出弧扩展新的路径并将这些新路径加入边界。搜索策略就界定了在每一步中需要选择哪些边界要素。
图3-4中给出了通用搜索算法。最初，边界是一组从起始节点开始的空路径。每一步中，算法通过从边界去除路径〈s0,…,sk〉而继续推进边界。如果goal(sk)是真（即sk是目标节点），它就找到了解并返回已找到的路径，即〈s0,…,sk〉。否则就通过增加一条出弧来寻找sk的邻居，从而扩展路径。因为对于sk的每一个邻居s，路径〈s0,…,sk,s〉都会加入到边界中。这一步叫做扩展（expanding）节点sk。

1：procedure Search(G,S,goal)
2：　Inputs
3：　　G：具有N个节点和A条边的图
4：　　S：开始节点集
5：　　goal：布尔状态函数
6：　Output
7：　　从S的一个成员到goal值为真的节点的一条路径，
8：　　或者如果无解路径则⊥
9：　Local
10：　　边界：路径集合
11：　Frontier←{〈s〉∶s∈S}
12：　While Frontier≠{}do
13：　　select and remove 〈s0,…,sk〉from Frontier
14：　　if goal(sk) then
15：　　　return〈s0,…，sk〉
16：　　Frontier←Frontier∪{〈s0,…，sk,s〉∶〈sk,s〉∈A}
17：　return ⊥

https://yqfile.alicdn.com/c8fed22ca726cd395ddfb87650cd80f5b721bf7c.png" >

这个算法有一些要注意的特征：

• 13行中路径的选择是不确定性的。路径的选择会影响效率，5.2.2节中“不确定性选择”处有更多关于路径筛选使用的详细描述。特定的搜索策略决定选择哪一条路径。
• 15行中的return应视为临时返回，通过继续进行的16行指令可得出另一条到达目标的搜索路径。78
• 如果该过程返回⊥，则不存在解（或者即使再次试验进行验证也无其余解）。
• 这个算法只能用来测试从边界挑选的路径是否能终止在目标节点，而不是测试任意加入到边界的路径。对此有两点主要原因。有时边界上的节点到目标节点的弧花费很大，搜索就不应当通过这条弧返回路径，因为可能存在更低花费的路径。当要求最低花费路径的时候，这就显得尤为重要了。第二点原因是确定一个节点是目标节点的代价很大。

如果选择的路径不在目标节点处终止，并且终止节点没有邻居，那么扩展路径意味着去除路径。这种结果是合理的，因为这条路径不能看做是从起始节点到目标节点的路径的一部分。