人工智能实验算法具有可采纳性证明.docx

《人工智能实验算法具有可采纳性证明.docx》由会员分享，可在线阅读，更多相关《人工智能实验算法具有可采纳性证明.docx（4页珍藏版）》请在三一办公上搜索。

1、人工智能实验 算法具有可采纳性证明A*算法具有可采纳性 一般地说对任意一个图, 当s到目标节点有一条路径存在时, 如果搜索算法总是在找到一条从s到目标节点的最佳路径上结束, 则称该搜索算法是可采纳的(Admissibility)。A*就具有可采纳性, 下面就来证明A*的可采纳性及若干重要性质。 定理1: 对有限图, 如果从初始节点s到目标节点t有路径存在, 则算法A一定成功结束。 证明: 设A搜索失败, 则算法在第2步结束, OPEN表变空, 而CLOSED表中的节点是在结束之前被扩展过的节点。由于图有解, 令(n0 = s, n1, n2, , nk = t)表示某一任一解路, 我们从nk开

2、始逆向逐个检查该序列的节点, 找到出现在CLOSED表中的节点nl, 即 nlCLOSED, nl+1 CLOSED (nl一定能找到, 因为n0CLOSED, nkCLOSED)。由于nl在CLOSED中, 必定在第6步被扩展, 且nl+1被加到OPEN中, 因此在OPEN表空之前, ni+1已被处理过。若nl+1是目标节点, 则搜索成功, 否则它被加入到CLOSED中, 这两种情况都与搜索失败的假设矛盾, 因此对有限图不失败则成功。证毕 因为A*是A的特例, 因此它具有A的所有性质。这样对有限图如果有解, 则A*一定能在找到到达目标的路径结束, 下面要证明即使是无限图, A*也能找到最佳解

3、结束。我们先证两个引理: 引理1: 对无限图, 若有从初始节点s到目标节点t的一条路径, 则A*不结束时, 在OPEN中即使最小的一个f值也将增到任意大, 或有f(n)f*(s)。 证明: 设d*(n)是A*生成的搜索树中, 从s到任一节点n最短路径长度的值(设每个弧的长度均为1), 搜索图上每个弧的耗散值为C(ni, ni+1)(C取正)。令e = min C(ni, ni+1), 则 g*(n) d*(n)e。而g(n) f(n) = g(n) + h(n) 任意大。 设 f(n) , M是一个定数, 所以搜索进行到一定程度会有d*(n) M, 或d*(n)e = d*(n) = f*(s

4、) f*(s)。 , 则 g*(n) g(n) d*(n)e, 故有 d*(n)e (设h(n) 0)。若A*不结束, d*(n), f 值将增到 证毕 引理2: A*结束前, OPEN表中必存在f(n) f*(s), 或OPEN表中最小的一个f值也变成无界, 这与引理2的结论矛盾, 所以A*只能成功结束。证毕 推论1: OPEN表上任一具有f(n) f*(s) 而根据引理2知结束前OPEN表上有节点n, 且处在最佳路径上, 并有f(n) 以 f(n) f*(s) f(t) f*(s), 所 这时算法A*应选n作为当前点扩展, 不可能选t, 从而也不会去测试目标节点t, 即这与假定A*选t结束矛盾, 所以A*只能结束在最佳路径上。证毕 推论2: A*选作扩展的任一节点n, 有f(n) f*(s) 证明: 令n是由A*选作扩展的任一节点, 因此n不会是目标节点, 且搜索没有结束, 由引理2而知在OPEN中有满足f(n)必有f(n)f(n), 所以f(n) f*(s)的节点n。若n = n, 则f(n) f*(s), 否则选n扩展, f*(s)成立。证毕