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

人工智能实验 算法具有可采纳性证明A*算法具有可采纳性 一般地说对任意一个图, 当s到目标节点有一条路径存在时, 如果搜索算法总是在找到一条从s到目标节点的最佳路径上结束, 则称该搜索算法是可采纳的(Admissibility)。A*就具有可采纳性, 下面就来证明A*的可采纳性及若干重要性质。 定理1: 对有限图, 如果从初始节点s到目标节点t有路径存在, 则算法A一定成功结束。 证明: 设A搜索失败, 则算法在第2步结束, OPEN表变空, 而CLOSED表中的节点是在结束之前被扩展过的节点。由于图有解, 令(n0 = s, n1, n2, , nk = t)表示某一任一解路, 我们从nk开始逆向逐个检查该序列的节点, 找到出现在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*也能找到最佳解结束。我们先证两个引理: 引理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)> 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)的节点(n是在最佳路径上的节点)。 证明: 设从初始节点s到目标节点t的一条最佳路径序列为 (n0 = s, n1, , nk = t) 算法初始化时, s在OPEN中, 由于A*没有结束, 在OPEN中存在最佳路径上的节点。设OPEN表中的第一个节点n是处在最佳路径序列中(至少有一个这样的节点, 因s一开始是在OPEN上), 显然n的先辈节点np,已在CLOSED中, 因此能找到s到np,的最佳路径, 而n也在最佳路径上, 因而s到n的最佳路径也能找到, 因此有 f(n) = g(n) + h(n) = g*(n) + h(n) g*(n) + h*(n) = f*(n) f*(s)。证 而最佳路径上任一节点均有f* = f*(s) (f*(s)是最佳路径的耗散值), 所以f(n)毕 定理2: 对无限图, 若从初始节点s到目标节点 t有路径存在, 则A*也一定成功结束。 证明: 假定A*不结束, 由引理1有f(n) > f*(s), 或OPEN表中最小的一个f值也变成无界, 这与引理2的结论矛盾, 所以A*只能成功结束。证毕 推论1: OPEN表上任一具有f(n) < f*(s)的节点n, 最终都将被 A*选作为扩展的节点。 定理3: 若存在初始节点s到目标节点t的路 径, 则A*必能找到最佳解结束。 证明: (1) 由定理1、2知A*一定会找到一个目标节点结束。 (2) 设找到的一个目标节点t结束, 而st不是一条最佳路径, 即 f(t) = g(t) > 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)成立。证毕