第3篇 计算机是如何找到最优路径的 艾博士导读 最优路径问题是人工智能研究中的一个重要问题,很多问题都可以转化为最优路径求 解问题,如语音识别、汉字识别后处理、拼音输入法等。 A* 算法是求解最优路径的一个重要算法,在人工智能中具有重要地位,曾经被列为计 算机领域最重要的32 个算法之一。 那么都有哪些最优路径搜索算法呢 ? 这些算法各自的特点是什么 ? 每种算法是否可以 找到最优路径 ? 或者在什么条件下可以找到最优路径 ? 本篇将逐一介绍,解开这些谜团。 本篇内容按照难易程度划分为3个等级,读者可以根据自身需要有选择地选读其中几 节或者全部内容。 第一级:3.1节、2节、5节。介绍什么是最优路径问题, 3节和3.然后通过一个实际 例子,引出了宽度优先搜索算法,介绍宽度优先搜索算法的具体过程,有哪些性质,以及存在 的不足。在此基础上,引出迪杰斯特拉算法,介绍该算法的求解过程以及所具有的性质,并 分析该算法存在的不足。介绍什么是深度优先搜索算法及其性质。 第二级:3.4节。针对迪杰斯特拉算法的不足,引入启发函数的概念,给出了 A 算法 , 介绍 A 算法的求解过程。然后通过对启发函数加以必要的限制,引出A* 算法,介绍A* 算 法的性质,介绍如何设计启发函数的基本思路,并给出几个具体例子。介绍如何评价两个不 同的启发函数的方法。针对A* 算法存在的问题,引出单调启发函数的概念,分析单调启发 函数的性质。最后介绍如何克服A* 算法存在的不足,提出改进的A* 算法。 第三级:3.8节。针对宽度优先搜索算法、A* 算法存在的占用空间过大的问题 , 3.3. 6~3. 提出迭代加深式搜索的概念,利用深度优先搜索占用空间比较小的优势,与宽度优先搜索算 法、A* 算法相结合,提出迭代加深式宽度优先搜索算法、迭代加深式A* 算法,实现在占用 较小空间的情况下求解最优路径问题。介绍一种常用的动态规划算法Viterbi算法,介绍算 法适用的问题和实现的基本原理。最后通过一个拼音输入法问题实例,介绍如何将该问题 转换为一个最优路径问题,并给出用Viterbi算法求解拼音输入法问题的方法。 秋天到了,正是看红叶的季节。北京香山的红叶最为著名,小明计划周末和同学们一起 骑车去香山看红叶,线路图如图3.但是每次都 1所示。小明虽然以前多次和父母去过香山 , 是爸爸开车去的,小明并不熟悉如何到达香山。不过这也难不倒小明,手机上有导航软件 , 输入目的地香山后,很容易就可以找到到达香山的路线。现在的导航软件做的是真好,可以 提供好几条路线供选择:有距离最短,有花费时间最短,还有经过的红绿灯最少等,给出的 150艾博士:深入浅出人工智能 图3.从清华大学到香山公园路线 1 是不同条件下的最优路径。这引起了小明强烈的好奇心:计算机是如何找到最优路径 的呢? 游玩香山回来之后,带着这个问题,小明又来找艾博士请教。 3.路径搜索问题 1 明白了小明的来意之后,艾博士从书柜里找出了一张很久未用的纸质地图。 艾博士指着地图对小明说:现在真是太方便了,无论想去哪里,导航软件都能很快给出 路径。以前我们都是依靠这种地图,在地图上查找半天,才能找到一条合适的路线。 艾博士让小明尝试着找到一条去香山的路。小明由于是第一次使用这种纸质地图,在 地图上探索半天,才好不容易找到了一条到达香山的路线。 艾博士问小明:小明,你刚才是怎么找到去香山的路线的呢? 小明回答说:刚开始我有些不得要领,完全是无规律地乱找。后来我发现主要是找路 口,重要的是在哪个路口应该向哪个方向走,因为相邻的两个路口之间只有一条路,是不需 要考虑如何走的。 艾博士夸奖道:小明你真聪明! 其实所谓的路线,就是将经过的路口———包括道路的 入口和出口———连接在一起。所以找路线,重要的就是找到这些必须经过的路口。 为此,我们可以将路口看作是一个状态,相邻的路口用称作“边”的连线连接在一起,这 样地图就可以用这种状态连接图表示了。如图3.2所示,就表示了一个简单的地图,图中 A、B、C等表示的是路口,两个相邻路口用边连接在一起。边旁边的数字表示两个路口之间 的距离。比如S到A的距离为6。这里的状态,在图中又称作是节点。 艾博士总结说:在地图上找出从起始地点S到目标地点T的路线,就是在这样的状态 连接图上寻找出几个状态,这些状态连接在一起,可以从起始点S到达目标地点T。这就是 路径搜索问题。如果找到的路径满足一定的最优条件,则是最优路径搜索问题。由于这种 搜索是在状态连接图上进行的,所以又可以称为状态搜索问题。 第3篇计算机是如何找到最优路径的151 图3.状态连接图示意 2 小明着急地问道:艾博士,那么如何通过状态连接图搜索到路径呢? 艾博士:小明,我们先不着急介绍具体的搜索算法,先来看看这里的关键问题是什么。 以图3.假设S是所在的起点,C、E,我们用 2为例,T是要去的终点。从S出发可以到达A、 图3.3所示的搜索图表示。图中由于A、C、E3 个节点是从S生成出来的,所以这3个节点 称作S的子节点,S称作这几个节点的父节点。父节点产生子节点的过程称作扩展。 由于连接S的只有A、C、E这3个路口,所以要到达目标T的话,必须经过这3个路口 中的一个,那么下一步应该选择哪个节点扩展呢? 假设选择了节点E扩展,则生成子节点B 和F,得到的搜索树如图3. 4所示。 图3.从S扩展出3个子节点A、C、图3.扩展节点E生成出子节点B、 3 E4F 到这一步之后,又面临选择哪个节点扩展的问题,从可能经过的A、B、C、F4 个路口中 选择一个节点扩展。 讲到这里,艾博士问小明:小明你说说看,这里的关键问题是什么? 小明想了想回答道:这里的关键问题应该是如何选择哪个节点优先扩展。 听了小明的回答,艾博士非常高兴:小明,你说得很对。如何选择节点优先扩展是状态 搜索问题的关键所在。事实上,不同的选择方法,就构成了不同的搜索算法。不同的算法具 有不同的性质,下面我们分别介绍几个常用的方法。 另外我们需要强调的是,通过状态搜索不只可以求解路径问题,其他很多问题也都可以 转化为状态搜索问题进行求解。比如八数码问题。 小明不解地问道:八数码问题是个什么问题呢? 艾博士解释说:八数码问题是一个智力游戏问题。在3×3 组成的九宫格棋盘上,摆有 8个将牌,每一个将牌都刻有1~8数码中的某一个数码。棋盘中留有一个空格,允许其周围 的某一个将牌向空格移动,这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的 问题是:给定一种初始的将牌布局(初始状态)和一个目标布局(目标状态), 问如何通过移动 152艾博士:深入浅出人工智能 将牌,实现从初始状态到达目标状态的转变。图3. 5给出了一个八数码问题的示意图。 小明:我明白什么是八数码问题了,但是这与路径搜 索问题有什么关系呢? 艾博士解释说:这个问题实际上跟路径搜索问题是 一样的。初始状态可以认为是出发点,在这个状态下走 图3.5 八数码问题示例一个将牌形成的新状态可以看作是与初始状态相邻的 “路口”。八数码问题的解就是找到若干个相邻的“路口” (状态), 可以从初始状态一步步达到目标状态。 小明恍然大悟道:经您这么一解释,八数码问题还真是和路径搜索问题是一样的。 艾博士:还有定理证明问题,从搜索的角度来说,也可以认为是寻找路径的过程。 小明:定理证明也跟路径搜索问题有关? 艾博士:你学过几何吧? 几何证明题一般是怎么描述的? 又是怎么证明的? 小明想了想回答说:一般都是先给几个已知条件,然后要求证明某个结论,比如证明两 条直线平行、两个角相等等。证明过程一般是用某个定理,从已知条件推理出某个结论,然 后再反复运用已知的定理得出更多的结论,直到最终得出要求证明的结论。 艾博士:这里的已知条件就相当于路径搜索问题中的起始状态,而要证明的结论就相 当于目标状态。运用定理推导出的一些中间结果可以认为是搜索过程中出现的中间状态, 从一个状态推导出另一个状态所用的定理,就相当于连接两个状态的边。所以从搜索的角 度描述定理证明的话,就是找到一条从初始条件出发,通过一系列定理连接的、到达要证明 的结论的路径。 小明认真思考后说:仔细想想还真是这么一回事。 艾博士:很多问题都可以转化为路径搜索问题,在下面的讲解中,除非特殊说明,我们 均以状态连接图上的路径搜索为例做介绍。 小明读书笔记 路径搜索问题就是在一个状态图上,如何选择被扩展的节点,不同的选择方法就构成 了不同的搜索算法。 路径搜索方法不仅适用于求解地图上查找路线问题,这里的“路径”是广义的路径概 念,很多问题可以转化为路径搜索问题来求解。 3.宽度优先搜索算法 2 艾博士:小明,我们首先从宽度优先算法开始介绍。所谓宽度优先算法,就是选择节点 深度最浅的节点优先扩展。 小明:什么是节点深度呢? 艾博士解释说:在搜索图中,第一个节点称作根节点,根节点的深度为0,其他节点的深 度为其父节点的深度加1。简单地说,根节点深度为0,根节点的子节点深度为1,再下一层 子节点深度为2,…… 第3篇计算机是如何找到最优路径的153 艾博士:小明,你说说看,4中几个节点的深度分别多少? 图3. 小明回答说:S是根节点,深度为0;A、C、E3 个节点均为S的子节点,所以它们的深度 均为1;B、F均为E的子节点,节点深度均为2。 艾博士接着说:宽度优先搜索就是从根节点开始,每次选择一个节点深度最浅的节点 扩展,直到生成出目标节点为止。 小明问道:艾博士,如果深度最浅的节点存在多个时如何选择呢? 艾博士:这种情况下可以随机选择一个深度最浅的节点进行扩展。 下面我们以图3. 2为例介绍如何采用宽度优先搜索求解从起点S到终点T的路径。 图3.6给出了该问题的搜索图,其中红圈数字表示节点被扩展的次序,这里假定当深度一样 时,排在左边的节点优先扩展。 该搜索过程首先选择深度最浅的根节点S进行扩展,产生了3个子节点A、C、E;由于 这时这3个节点的深度都是1,我们根据假定优先扩展左边的节点E,产生节点B、F;这时 A、C的节点深度最浅,我们选择C扩展,产生节点D;这时A的深度最浅,扩展后产生节点 T。而这时T就是终点节点,搜索结束,得到路径S-A-T。 这个问题比较简单,很快就找到了达到终点也就是目标状态的路径。对于复杂一些的 情况,需要继续寻找节点深度最浅的节点扩展,直到找到目标为止。 小明问艾博士:宽度优先搜索如何求解其他问题呢? 比如前面提到过的八数码问题。 艾博士:当然可以求解八数码问题,方法是一样的。对于图3. 7所示的八数码问题, 图3.其中红圈中的数字表示的是该 8给出了用宽度优先搜索求解该八数码问题的搜索图, 节点被扩展的次序。 图3.6 宽度优先搜索求解示意图7 图3.八数码问题 艾博士对照着图3. 8给出的八数码问题搜索图说:我们来看看用宽度优先搜索求解八 数码问题的搜索过程。开始只有初始节点S,对S进行扩展,生成A、B、C3 个子节点。由 于A、B、C3 个节点的深度是一样的,深度均为1,按照约定选择最左边的节点A扩展,生成 D、E、F3 个子节点。这时节点B、C的深度最浅,同样选择排在左边的节点B扩展,生成出 子节点G。再选择深度最浅的节点C扩展,生成出子节点H。此时深度最浅的节点有D、 E、F、G、H5 个节点,深度均为2。同样依次扩展节点D、E、F、G,当扩展到节点G时,其子 节点中出现了目标节点,搜索到此结束。通过搜索图,可以得到该八数码问题的解,也就是 为达到目标状态将牌的移动方法:将牌2右移,将牌1上移,将牌8左移。 小明听着艾博士的讲解,有些不太明白地问道:艾博士,这种方法为什么叫宽度优先搜 索呢? 154艾博士:深入浅出人工智能 图3.宽度优先搜索求解八数码问题搜索图 8 艾博士解释说:小明你看图3.8中所示的节点扩展次序,是沿着“横向”进行的,先优先 扩展第一层节点,再扩展第二层、第三层…… 这就是宽度优先名称的由来。 小明:明白了。那么宽度优先搜索有什么特点呢? 艾博士:宽度优先搜索有一个重要的结论,就是在单位代价下,当问题有解时,可以找 到问题的最优解,也就是路径总代价最小的解。 小明:单位代价是什么意思呢? 艾博士:我们先解释一下什么是代价。所谓代价就是父节点到子节点的广义“距离”。 比如从路口A到路口B距离多少千米可以是代价,需要用多长时间也是代价,花费多少钱 也是代价。而单位代价指的是任何两个父子节点间的代价总是为1。比如在上面的八数码问 题中,如果移动一个将牌的代价为1的话,则该问题就是单位代价的。在单位代价下,我们用 宽度优先搜索得到的八数码问题的解,就是总代价最小的,也就是将牌的移动次数最少的解。 对于地图上求两个地点间的一条路径,如果认为两个相邻路口的代价为1,则找到的是 经过的路口最少的路径。当每个路口都有红绿灯时,实际上就是经过的红绿灯最少的路径。 在城市中,寻找一条红绿灯最少的路径也是很有意义的。 小明问:为什么在单位代价下宽度优先搜索得到的就是代价最小的路径呢? 艾博士解释说:如同前面说过的,宽度优先搜索在搜索图上体现的是“横着”走,先扩展 深度为1的节点,再扩展深度为2的节点…… 逐步加深扩展节点的深度。假设从初始节点 到目标节点存在不同的路径,通过这些路径到达目标节点的深度也不相同。宽度优先搜索 优先选择深度最浅的节点扩展,所以当第一次出现目标节点时,一定是经过这条路径计算的 目标节点深度最浅。在单位代价下,节点深度就是初始节点到目标节点的总代价,所以宽度 第3篇计算机是如何找到最优路径的155 优先搜索可以找到总代价最小的路径。 小明:经您这么一解释就明白了。在单位代价条件下,从初始节点到达一个节点的总 代价等于该节点所处的深度,宽度优先搜索算法的思想是选择深度最浅的节点扩展,也就是 选择总代价最小的节点优先扩展,所以当第一次遇到目标节点时,一定就找到了到达目标节 点的最短路径。 小明读书笔记 宽度优先搜索算法是一种常用的路径搜索算法,其特点是每次选择节点深度最浅的 节点优先扩展。当问题是单位代价时,也就是任何相邻节点之间的代价均为1时,可以找 到从初始节点到目标节点代价最小的最优路径。 3.迪杰斯特拉算法 3 小明:在单位代价下,宽度优先搜索算法可以找到代价最小的路径,但是很多问题并不 是单位代价的。比如说对于八数码问题,如果移动将牌的代价为将牌的数码,如数码为5的 将牌移动一次的代价为5,每个将牌的数码不一样,移动的代价也不相同。再比如,如果步 行或者骑车去某个地方,相对于红绿灯最少来说,可能距离最短更重要。即便是开车,距离 也是一个重要的影响因素。那么是否有办法求解一般情况下总代价最小路径的方法呢? 艾博士反问小明:小明,宽度优先搜索是如何选择被扩展节点的? 小明马上回答说:优先选择深度最浅的节点扩展。 艾博士:小明回答得很好。如果我们用g(表示从初始节点到节点 n 的一条路径的 n) 代价,节点 n 的深度就相当于单位代价下的g()。所以, n 宽度优先搜索优先选择深度浅的 节点,就相当于单位代价条件下优先选择g(小的节点扩展。我们修改一下宽度优先搜索 算法,优先选择g(小的节点扩展, n) n) 宽度优先搜索算法就变成了迪杰斯特拉算法。但是需 要修改一下结束条件:当目标节点的g(n)值最小时,算法才结束,而不是只要目标一出现 就马上结束。 小明问:为什么要加上这样的条件呢? 艾博士:这个条件很关键,我们后面再讲为什么要有这样的条件。 我们还是通过图3.为了看起来方便,2的状 2的例子介绍迪杰斯特拉算法, 我们将图3. 态连接图重画在图3.图3.红圈里的数字表示节点被 9中, 10 给出了该问题的搜索图。同样, 扩展的顺序,连接线旁边的数字表示的是两个节点间的距离。 图3.状态连接图示意 9 156艾博士:深入浅出人工智能 图3.迪杰斯特拉算法搜索示意图 10 在图3.首先扩展初始节点S, E、C,按照S到这3个节点的距离, 分别得到: 10 中, 生成出节点A、 g(A)=6 g(C)=2 g(E)=3 由于g(C)最小,所以第二次选择C扩展,生成出节点D,并得到g(D)=g(C)+7=9。 接下来从A、D、g(=产生节点 E中选择一个 g 值最小的节点,E)3被选中第三个扩展, B、F,分别计算出: g(B)=5 g(F)=7 在A、D、B、F几个节点中,g(B)=5最小,成为第四个被选择扩展的节点,生成出节点 T,经计算有: g(T)=8 这时虽然已经找到一条从初始节点S到目标节点T的路径S-E-B-T,但是由于g(T) 并不是最小的(g(A)=6、g(F)=7,均小于g(T)=8), 所以算法并不停止,继续选择 g 值最 小的节点扩展。 接下来第五个被选择扩展的节点是A,再一次生成出节点T。这时找到了两条到达T 的路径,一条是之前找到的S-E-B-T,另一条是刚找到的S-A-T。这种情况下,需要做一次 选择,保留代价最小的路径,由于通过路径S-E-B-T计算g(T)为8,而通过路径S-A-T计算 g(T)为9,所以保留前者,而忽略后者,图中用虚线表示。 这时g(F)又成为了最小的,所以第六次选择节点F扩展,生成出节点G,并计算 g 值为: g(G)=12 这时,已经生成但还未被扩展的节点有F、G、T,3个节点中T的 g 值最小,而T又是目 标节点,算法结束。 这样就找到了从初始节点S到达目标节点T的路径S-E-B-T。 小明:艾博士,迪杰斯特拉算法每次选择 g 值最小的节点扩展,当问题是单位代价时, 第3篇计算机是如何找到最优路径的157 与宽度优选搜索算法是等价的。那么在一般情况下,迪杰斯特拉算法一定能够找到最小代 价的路径吗? 艾博士:可以证明,迪杰斯特拉算法可以找到代价最小的路径。即便不满足单位代价 条件,找到的也一定是代价最小的路径。 但是一定要记住前面我们提到过的迪杰斯特拉算法的结束条件,当目标节点的 g 值最 小时,算法才结束。这是迪杰斯特拉算法能找到最小代价路径的一个重要条件。因为迪杰 斯特拉算法总是从搜索图的叶节点(即搜索图中已经产生但是还没有被扩展的节点)中选择 一个节点扩展,当目标节点的 g 值最小时,其他节点还没有到达目标节点,其 g 值就已经比 目标节点的 g 值大了,所以通过其他节点到达目标节点的路径代价肯定不会比目前得到的 这条路径小,从而找到的一定是代价最小的路径。不过这里也需要做一个补充说明,即代价 都是大于0的,不存在负的代价。 小明还是有些不太明白地问道:在上面的例子中,最初就找到了路径S-E-B-T为什么 不能马上结束呢? 最终找到的最短路径也是这一条路径啊。 艾博士解释说:小明你看图3.图中虚线部分的代价如果不是3而是 10 所示的搜索图, 1,会出现什么情况? 这时从S到T的最短路径应该是S-A-T,而非S-E-B-T,如果开始找到 了S-E-B-T就马上停止,还能找到最短路径吗? 小明想了想明白了:确实是这样的,所以迪杰斯特拉算法的这个结束条件是必须有的, 否则就不能保证找到最优路径。 艾博士进一步补充说:我们还需要强调一下,一般介绍迪杰斯特拉算法时,叙述方法可 能与我们这里介绍的不太一样,但是其核心思想是一样的。我们之所以这样讲解,主要是为 了从宽度优先搜索算法扩展到迪杰斯特拉算法,后面还将再次扩展到启发式搜索方法,将这 几个方法采用同一个框架连贯、统一起来。事实上,宽度优先搜索算法没有利用两个节点间 的代价信息,所以只能在单位代价下找到最优路径。而迪杰斯特拉算法利用了两个节点间 的代价信息,适应面更加广泛,在非单位代价情况下,也同样能找到最优路径。 小明读书笔记 迪杰斯特拉算法充分利用了到达每个节点的代价信息,优先选择代价最小的节点扩 展,即便问题是非单位代价时,也可以找到最优路径。需要强调的是,当被选择扩展的节 点是目标节点时算法才结束,而不是一发现目标节点马上就结束,只有这样才能保证算法 找到最优解。 3.启发式搜索 4 3.4.1 A 算法 艾博士:迪杰斯特拉算法具有很好的性质,可以找到最小代价的路径。但是该算法也 存在明显的不足。小明你想想看,有什么不足? 小明仔细看着图3.我一时还说不出来有什么 10 所示的搜索图思考了一下说:艾博士 , 不足 。 158艾博士:深入浅出人工智能 艾博士启发小明说:你把图3.9所示的 10 所示的搜索图中节点的扩展次序标注到图3. 状态连接图上,是否会发现点什么问题? 小明思考了一下,按照艾博士的要求在状态连接图上标识出节点的扩展次序,如图3. 11 所示。 图3.标注了扩展次序的状态连接图 11 然后,小明看着图思考起来。不一会儿小明就发现了问题,对艾博士说:我知道了迪杰 斯特拉算法存在的不足了,我试着说一下,请艾博士看看是否正确。 在图3.状态C是远离目标状态的, 比距离目标更近且方向也 11 中, 却第二个就被扩展, 正确的E、B先扩展。而状态F不仅远离目标状态,方向也是完全相反的,却也要尝试进行 扩展。这是不是就是该算法存在的问题? 艾博士高兴地说:小明你分析得非常正确,这正是该算法存在的不足。算法只利用了 节点的 g 值,优先扩展 g 值小的节点,而完全没有考虑这个节点是否距离目标更近。这样 会造成很多不必要的节点扩展,严重降低算法的求解效率。 小明忍不住问艾博士:那么怎么克服这一不足呢? 艾博士:一种解决办法就是在选择待扩展节点时,不只是考虑该节点的 g 值,同时还 要考虑该节点到目标节点的距离。假设我们用h(n)表示节点 n 到目标节点的距离,那么: f(=g(n) n)n)+h( 就反映了从初始节点S经过节点 n 到达目标节点T的路径距离,也就是这条路径的代价。 比如在前面的例子中,由于C和F都是远离目标状态的,它们的 h 值就会比较大,从而导致 f 值比较大,就有可能避免对这两个节点的扩展,从而提高了算法的效率。 听到这里,小明很高兴地说:对啊,这样的话就可以提高搜索效率了。 刚说到这里,小明刚刚还在微笑的面孔突然又凝固起来:可是,一个节点的 h 值怎么计 算呢? 我们如何知道一个节点到达目标的距离呢? 艾博士说:你的疑虑是对的,一个节点的 h 值确实无法事先知道,但是我们可以大概估 计,如果可以估计出一个节点到达目标的大概距离,哪怕是不太准确,那么对于搜索路径也 是很有帮助的。 nn) 小明:想一想是这样的道理。艾博士,公式中的f()、g(和h(n)这3个函数具有 什么物理含义吗? 艾博士:这3个函数都具有明确的物理含义,我们具体总结一下。g(n)表示的是从初 始节点S到达节点 n 最短路径代价的估计值,通常为搜索图中已经找到的从S到 n 的路径 第3篇计算机是如何找到最优路径的159 代价。h(称作启发函数, n) 表示的是从S出发、 该 n) 表示的是从节点 n 到达目标节点T最短路径代价的估计值, 值的计算与具体问题有关。f(称作评价函数, 经过节点 n 到达目标 节点T最短路径代价的估计值,该值通过累加g(和h(获得。f(是对节点 n 的总体 n) n) n) 评价,既考虑了从初始节点S到节点 n 的代价,又考虑从节点 n 到目标节点T的代价,是对 通过节点 n 到达目标节点最佳路径代价的估计,体现了节点 n 是否在到达目标节点最佳路 径上的可能性。f(n)越小说明节点 n 在最佳路径上的可能性越大, n) 的节点,是一个可行的搜索策略。 因此优先扩展f(小 采用这样的搜索策略,每次优先选取 f 值最小的节点扩展,直到目标节点的 f 值最小 为止,这样的搜索算法称作A算法。A算法与迪杰斯特拉算法的区别就是用节点的 f 值代 替 g 值,每次选取 f 值最小的节点优先扩展。 小明有些着急地问道:我觉得A算法中最重要的就是启发函数h(n)的计算,那么如何 估计节点的 h 值呢? 看着小明的样子,艾博士安慰说:先不用着急,这个问题我们后面再详细讲解。先假定 已经给出了节点的 h 值,看看A算法是如何工作的。 如图3. 还是以上面说的问题为例,但是这次我们给出了每个节点的 h 值, 12 所示。 图3.给出了节点 h 值的示意图 12 艾博士对小明说:这次你尝试着用A算法求解一下试试。 小明马上找来一张纸画了起来,得到了图3. 13 所示的搜索图。 图3. 13 A 算法搜索示意图 160艾博士:深入浅出人工智能 艾博士对小明说:请你解释一下做的过程。 小明对照着图3. f(S)=g(S)+h(S) 计算S的 f 值: 13 解释说:首先以初始节点S建立根节点, 由于S是初始节点,所以g(S)=0,而h(S)图3.所以f(S)= 12 中给出的结果是6, 6。 这时待扩展节点只有一个节点S,选择S扩展,生成子节点A、C、E。分别计算这3个节点的 f 值: f(A)=g(A)+h(A)=6+3=9 f(C)=g(C)+h(C)=2+8=10 f(E)=g(E)+h(E)=3+4=7 从A、C、E3 个待扩展节点中,选择 f 值最小的节点E优先扩展,生成子节点B、F。同 样计算这两个节点的 f 值: f(B)=g(B)+h(B)=5+1=6 f(F)=g(F)+h(F)=7+7=14 这样待扩展节点为A、C、B、F这4个节点。从中选择 f 值最小的B节点进行扩展,生 成出节点T,计算T的 f 值: f(T)=g(T)+h(T)=8+0=8 此时待扩展节点为A、C、F、T4 个节点,其中 f 值最小的是节点T,同时T也是目标节 点,所以算法结束,得到路径S-E-B-T。 看到小明的求解结果,艾博士夸奖道:小明讲解得非常清楚,尤其最后特意指明f(T) 最小才结束,这一点是非常重要的。 在A算法中,还有一些细节需要处理,为此我们先给出A算法的详细描述,以便说清楚 这些细节。 在介绍算法之前,先介绍几个算法中用到的符号。S为给定的初始节点。OPEN 是一 个表,当前的待扩展节点放在该表中,并按照 f 值从小到大排列。CLOSED 也是一个表,所 有扩展过的节点放在该表中。 .................................................................................... A算法。 1 初始化:OPEN=(S),CLOSED=(), 计算f(S); 2 循环做以下步骤直到OPEN 为空结束: 3 循环开始 4 从OPEN 中取出第一个节点,用 n 表示该节点; 5 如果 n 就是目标节点,算法结束,输出节点n,算法成功结束; 6 否则将 n 从OPEN 中删除,放到CLOSED 中; 7 扩展节点n,生成出 n 的所有子节点,用mi 表示这些子节点; 8 计算节点mi 的 f 值,由于可能存在多个路径到达mi,用f(n,mi)表示经过节点 n 到达mi 计算出的 f 值,不同的到达路径其g(mi)值可能不同,但是h(mi)是 一样的,因为h(mi)是从mi 到目标节点路径代价的估计值,与如何从初始节点 到达mi 无关; 9 如果mi 既不在OPEN 中,也不在CLOSED 中,说明这是一个新出现的节点,则 第3篇计算机是如何找到最优路径的161 将mi 加入OPEN 中,并标记mi 的父节点为n; 10 如果mi 在OPEN 中, n,mi), mi)f(mi) , 并且f(mi)h1( h1 扩展的节点数≥用h2 扩展的节点数。 这里“用hi 扩展的节点”的含义是,当 h 函数采用hi 时,A*算法所扩展的节点。 由于两个 h 函数均满足A*条件,所以取值越大的 h 函数,说明对最小路径代价的估值 越准确。该定理表明,估计越准确的 h 函数,其性能越好。 小明又问道:艾博士,定理中要求对于所有非目标节点有h2(n)>h1(n), 也就是要求 h2(恒大于h1(这里可以加上等号吗? n)≥h1()。 n) n), 即h2( n 艾博士摇了摇头说:是不可以的,因为我们可以很容易举出反例来。小明你还记得我 们反复强调过的A*算法的结束条件吗? 小明:您强调过多次这个问题,只有当目标节点排在OPEN 的第一个位置时算法才成 功结束。 艾博士:是的,这一点很重要,是A*算法可以找到最优解的一个重要条件。但是当多 个节点的 f 值相等时,这些节点在OPEN 中如何排序,算法并没有说明。问题也就出现在 这里。比如有非目标节点m,刚好有f(m)=f(T), 其中T是目标节点。在这种情况下,如 果 m 在OPEN 中排在了T的前面,则A*算法将会扩展 m 节点;如果 m 排在了T的后面, 则T被从OPEN 中取出后算法就结束了,节点 m 并不会被扩展。如果是h2(n), n)≥h1( 并且刚好有f1(m)=f2(m)=f1(T)=f2(T), 其中f1、f2 分别指用h1、h2 计算的 f 值。 由于 m 排序位置的不确定性,可能会导致h2 扩展了 m 节点,但是h1 不扩展 m 的情况发 生,这样定理就不成立了。所以这个等号是不能加的。但是,如果在计算扩展的节点时排除 这样的节点,均排在目标节点的后边,则即便加上等号定理也同样成立。 小明:这么一解释就明白了为什么定理中不能加上等号了。 艾博士举例说:比如对于前面八数码的例子,我们定义: