A*算法可采纳性、一致性、最优性证明 |
您所在的位置：网站首页 › pla算法有界证明 › A*算法可采纳性、一致性、最优性证明 |
A*算法可采纳性、一致性、最优性证明
|
A*算法可采纳性、一致性、最优性证明
前言： 【网络上A*算法相关的文章都集中算法的步骤及代码上，对算法原理介绍不多，因此特意花了几天时间阅读原论文，对其中的定理、引理、推论进行说明，希望能够知其然并知其所以然。由于本人水平有限，关于A*算法最优性的证明部分一知半解，也希望本文能抛砖引玉，望多多交流、答疑解惑。】 以下内容均基于A*算法的原论文：A Formal Basis for the Heuristic Determination of Minimum Cost Paths 论文链接：https://ieeexplore.ieee.org/abstract/document/4082128/references#references 一、相关概念 1.1、评估函数 f ^ \hat{f} f^Evaluation Function作用：用于从多个可选节点中选出路径拓展（expand）的下一个节点 例如开始节点 S S S，当前节点为 n n n，需要从 n n n的相邻可选节点（successor）中选择一个节点进行路径拓展，好的评估函数能在节点拓展后尽可能靠近目标节点；论文中以可选节点评估函数值最小的节点作为要拓展的节点 1.2、算法步骤步骤1：将开始节点 S S S的状态记为open（文中为mark as open），计算 f ^ ( S ) \hat{f}(S) f^(S)； 步骤2：从所有状态为open的节点中选择评估函数值最小的节点作为要拓展的节点（节点 n n n）； 步骤3：若 n n n为目标节点，则算法结束，否则，执行步骤4； 步骤4：将 n n n记为closed，对 n n n的所有相邻节点计算评估函数值，对于某个相邻节点 n i n_i ni，评估函数值原值与现值分别计为 f ^ n i B e f o r e \hat{f}^{Before}_{n_i} f^niBefore、 f ^ n i A f t e r \hat{f}^{After}_{n_i} f^niAfter 若不是closed，则将该节点记为open；若是closed，则需要比较 f ^ n i B e f o r e \hat{f}^{Before}_{n_i} f^niBefore、 f ^ n i A f t e r \hat{f}^{After}_{n_i} f^niAfter 若 f ^ n i B e f o r e ≤ f ^ n i A f t e r \hat{f}^{Before}_{n_i}\le\hat{f}^{After}_{n_i} f^niBefore≤f^niAfter，则保持不变，仍为closed；若 f ^ n i A f t e r < f ^ n i B e f o r e \hat{f}^{After}_{n_i}f(S) f(n)>f(S)该结论说明 f ( n ) f(n) f(n)可以用于选择下一步要拓展的节点，因为 f ( n ) f(n) f(n)不是先验已知的，可以使用评估函数 f ^ ( n ) \hat{f}(n) f^(n)估计 f ( n ) f(n) f(n) 详见原文：
f ( n ) f(n) f(n)可以拆分为两部分： f ( n ) = g ( n ) + h ( n ) 其中， g ( n ) 为最优路径上开始节点 S 到节点 n 的实际成本； h ( n ) 为最优路径上节点 n 到目标节点 E 的实际成本 f(n)=g(n)+h(n)\\ 其中，g(n)为最优路径上开始节点S到节点n的实际成本；\\ h(n)为最优路径上节点n到目标节点E的实际成本 f(n)=g(n)+h(n)其中，g(n)为最优路径上开始节点S到节点n的实际成本；h(n)为最优路径上节点n到目标节点E的实际成本 同样的， f ^ ( n ) = g ^ ( n ) + h ^ ( n ) \hat{f}(n)=\hat{g}(n)+\hat{h}(n) f^(n)=g^(n)+h^(n) g ^ ( n ) \hat{g}(n) g^(n)是对 g ( n ) g(n) g(n)的估计，表示截至目前开始节点 S S S到节点 n n n的成本（the smallest cost so far），该值动态更新，但始终满足 g ^ ( n ) ≥ g ( n ) \hat{g}(n)\ge g(n) g^(n)≥g(n)，即“局部最小值”不小于“全局最小值”； h ^ ( n ) \hat{h}(n) h^(n)是对 h ( n ) h(n) h(n)的估计，表示节点 n n n目标节点 E E E的成本估计值（下一章节会证明 h ^ ( n ) \hat{h}(n) h^(n)满足一定条件时，算法一定能找到最优解）； 二、可采纳性 2.1、可采纳性说明定理1：若对于所有节点 n n n，均满足 h ^ ( n ) ≤ h ( n ) \hat{h}(n)\le h(n) h^(n)≤h(n)，则A*算法满足可采纳性（A* is admissible），即算法能找到起点与目标节点之间的最短路 We call an algorithm admissible if it is guaranteed to find an optimal path from S to a preferred goal node of S for any graph. 证明该定理需要使用一些前置结论： 引理1：对于任意非关闭状态（nonclosed）的节点 n n n以及从 S S S到 n n n的任意最短路 P P P，在 P P P上都存在一个状态为开（open）的节点 n ′ n' n′满足 g ^ ( n ′ ) = g ( n ′ ) \hat{g}(n')=g(n') g^(n′)=g(n′)
推论：假定对于所有节点 n n n，均满足 h ^ ( n ) ≤ h ( n ) \hat{h}(n)\le h(n) h^(n)≤h(n)并且A*算法未结束，则对于从 S S S到目标节点的任意最短路 P P P，在 P P P上都存在状态为开（open）的节点 n ′ n' n′满足 f ^ ( n ′ ) ≤ f ( S ) \hat{f}(n')\le f(S) f^(n′)≤f(S)
引理1：对于任意非关闭状态（nonclosed）的节点 n n n以及从 S S S到 n n n的任意最短路 P P P，在 P P P上都存在一个状态为开（open）的节点 n ′ n' n′满足 g ^ ( n ′ ) = g ( n ′ ) \hat{g}(n')=g(n') g^(n′)=g(n′) 证明思路：通过证明 g ^ ( n ′ ) ≥ g ( n ′ ) \hat{g}(n')\ge g(n') g^(n′)≥g(n′) 且 g ^ ( n ′ ) ≤ g ( n ′ ) \hat{g}(n')\le g(n') g^(n′)≤g(n′)，可得 g ^ ( n ′ ) = g ( n ′ ) \hat{g}(n')=g(n') g^(n′)=g(n′) （1）对于 g ^ ( n ′ ) ≥ g ( n ′ ) \hat{g}(n')\ge g(n') g^(n′)≥g(n′) 其中，易知 g ^ ( n ′ ) ≥ g ( n ′ ) \hat{g}(n')\ge g(n') g^(n′)≥g(n′)（可见章节1.3中关于 g ^ ( n ) \hat{g}(n) g^(n)的说明），因此仅需证明 g ^ ( n ′ ) ≤ g ( n ′ ) \hat{g}(n')\le g(n') g^(n′)≤g(n′) （2）对于 g ^ ( n ′ ) ≤ g ( n ′ ) \hat{g}(n')\le g(n') g^(n′)≤g(n′) 证明： 设 P = ( S = n 0 , n 1 , n 2 , . . . , n k = n ) P=(S=n_0,n_1,n_2,...,n_k=n) P=(S=n0,n1,n2,...,nk=n) A*算法开始执行时： 节点 S S S为open（可认为 n ′ = S n'=S n′=S），此时 g ^ ( S ) = g ( S ) = 0 \hat{g}(S)=g(S)=0 g^(S)=g(S)=0，引理成立；A*算法执行时的某一状态： 设 Δ \Delta Δ为 P P P 上所有状态为closed的节点 n i n_i ni的集合，集合内节点均满足 g ^ ( n i ) = g ( n i ) \hat{g}(n_i)=g(n_i) g^(ni)=g(ni)， Δ \Delta Δ非空（因为 S S S一定在其中），设最后一个进入集合 Δ \Delta Δ的节点为 n ∗ n^* n∗（with the highest index），易知 n ∗ ≠ n n^* \neq n n∗=n（因为 n n n为nonclosed），设 n ′ n' n′为路径 P P P上 n ∗ n^* n∗的“子节点”（successor）， n ′ n' n′可能为节点 n n n，节点 n ∗ 、 n ′ n^*、n' n∗、n′之间的成本为 c n ∗ , n ′ c_{n^*,n'} cn∗,n′则 g ^ ( n ′ ) ≤ g ^ ( n ∗ ) + c n ∗ , n ′ \hat{g}(n')\le \hat{g}(n^*)+c_{n^*,n'} g^(n′)≤g^(n∗)+cn∗,n′ 因为 g ^ ( n ) \hat{g}(n) g^(n)的更新方式为： g ^ ( n ′ ) = m i n ( g ^ ( n ′ ) , g ^ ( n ∗ ) + c n ∗ , n ′ ) \hat{g}(n')=min(\hat{g}(n'),\hat{g}(n^*)+c_{n^*,n'}) g^(n′)=min(g^(n′),g^(n∗)+cn∗,n′)，可证明该不等式成立 则 g ^ ( n ∗ ) = g ( n ∗ ) \hat{g}(n^*)=g(n^*) g^(n∗)=g(n∗)，因为 n ∗ ∈ Δ n^* \in \Delta n∗∈Δ则 g ( n ′ ) = g ( n ∗ ) + c n ∗ , n ′ g(n')=g(n^*)+c_{n^*,n'} g(n′)=g(n∗)+cn∗,n′，因为 n ′ n' n′在 P P P上考虑以上三个结论可以推导出 g ^ ( n ′ ) ≤ g ^ ( n ∗ ) + c n ∗ , n ′ = g ( n ∗ ) + c n ∗ , n ′ = g ( n ′ ) \hat{g}(n')\le \hat{g}(n^*)+c_{n^*,n'}=g(n^*)+c_{n^*,n'}=g(n') g^(n′)≤g^(n∗)+cn∗,n′=g(n∗)+cn∗,n′=g(n′)根据上述分析，证明得到 g ^ ( n ′ ) = g ( n ′ ) \hat{g}(n')=g(n') g^(n′)=g(n′)，论文中描述如下：
推论：假定对于所有节点 n n n，均满足 h ^ ( n ) ≤ h ( n ) \hat{h}(n)\le h(n) h^(n)≤h(n)并且A*算法未结束，则对于从 S S S到目标节点的任意最短路 P P P，在 P P P上都存在状态为开（open）的节点 n ′ n' n′满足 f ^ ( n ′ ) ≤ f ( S ) \hat{f}(n')\le f(S) f^(n′)≤f(S) 基于引理1，可知存在一个节点 n ′ n' n′，其 g ^ ( n ′ ) = g ( n ′ ) \hat{g}(n')=g(n') g^(n′)=g(n′) 对于该节点（该节点在最短路上，因此 f ( n ′ ) = f ( S ) f(n')=f(S) f(n′)=f(S)）： f ^ ( n ′ ) = g ^ ( n ′ ) + h ^ ( n ′ ) = g ( n ′ ) + h ^ ( n ′ ) ≤ g ( n ′ ) + h ( n ′ ) = f ( n ′ ) = f ( S ) \hat{f}(n')=\hat{g}(n')+\hat{h}(n')=g(n')+\hat{h}(n') \le g(n')+h(n')=f(n')=f(S) f^(n′)=g^(n′)+h^(n′)=g(n′)+h^(n′)≤g(n′)+h(n′)=f(n′)=f(S) 结论成立
定理1：若对于所有节点 n n n，均满足 h ^ ( n ) ≤ h ( n ) \hat{h}(n)\le h(n) h^(n)≤h(n)，则A*算法满足可采纳性（A* is admissible） 所有节点均满足 h ^ ( n ) ≤ h ( n ) \hat{h}(n)\le h(n) h^(n)≤h(n)，若能证明A*算法不能找到从 S S S到目标节点的最短路而结束，则说明定理1不成立，否则定理1成立 可分为3种情况分别讨论： case1：算法在非目标节点结束；case2：算法不能正常结束（可理解为“死循环”）；case3：算法在目标节点结束，但是所得路径不是最短路。 2.3.1、case1分析根据章节1.2中所述A*算法步骤，算法仅在目标节点处终止，因此case1所述情况不存在。
设节点 S S S到目标节点 t t t的最短路成本为 f ( S ) f(S) f(S)，路段长度至少为 δ \delta δ，记 M = f ( S ) / δ M=f(S)/\delta M=f(S)/δ 根据 M M M值，分两种情况讨论是否算法不能正常结束的可能性 （1）对于 M M M步之后 则对于 M M M步之后的节点 n n n，一定有 f ^ ( n ) ≥ g ^ ( n ) ≥ g ( n ) > M δ = f ( S ) \hat{f}(n) \ge \hat{g}(n) \ge g(n)>M\delta=f(S) f^(n)≥g^(n)≥g(n)>Mδ=f(S) 根据推论1，A*算法结束之前，存在一个节点 n ′ n' n′，使得 f ^ ( n ′ ) ≤ f ( S ) \hat{f}(n')\le f(S) f^(n′)≤f(S) 因此， f ^ ( n ′ ) < f ^ ( n ) \hat{f}(n')f(S) f^(t)>f(S) 根据推论1，A*算法结束之前，存在一个节点 n ′ n' n′，使得 f ^ ( n ′ ) ≤ f ( S ) \hat{f}(n')\le f(S) f^(n′)≤f(S) 可得 f ^ ( n ′ ) ≤ f ^ ( t ) \hat{f}(n')\le \hat{f}(t) f^(n′)≤f^(t)，因此，在步骤2时会选择节点 n ′ n' n′而不是节点 t t t 根据上述分析，可知算法会选择最短路上的节点而不是其他节点，在目标节点处结束所得路径一定是最短路。
实际问题对 h ^ ( n ) \hat{h}(n) h^(n)存在一定的限制，使用不等式进行描述 假设对于任意节点 m m m、 n n n，均满足 h ( m , n ) + h ^ ( n ) ≥ h ^ ( m ) h(m,n)+\hat{h}(n)\ge \hat{h}(m) h(m,n)+h^(n)≥h^(m) 且 h ( n , m ) + h ^ ( m ) ≥ h ^ ( n ) h(n,m)+\hat{h}(m)\ge \hat{h}(n) h(n,m)+h^(m)≥h^(n)，即 h ^ ( n ) \hat{h}(n) h^(n)满足一致性要求（consistency assumption） 式中， h ( m , n ) h(m,n) h(m,n)表示最优路径上节点 m m m、 n n n之间的成本 说明：论文中讨论了实际问题对于 h ^ ( n ) \hat{h}(n) h^(n)的约束，得到结论 h ^ ( n ) = inf θ ∈ Θ n h θ ( n ) \hat{h}(n)=\inf\limits_{\theta\in \Theta_n}h_\theta(n) h^(n)=θ∈Θninfhθ(n) （该部分内容详见论文III.ON THE OPTIMALITY OF A*——A. Limitation of Subgraphs by Information from the Problem）
一致性意味着节点经过其他节点到目标节点的成本不低于直接到目标节点的成本（一种简单但不严谨的理解：“三角形两边之和大于第三边”），可参考该链接加深对一致性的理解： 人工智能中A*算法的启发式的一致性有什么意义？ - Hepta的回答 - 知乎https://www.zhihu.com/question/23052955/answer/1648645823 考虑一致性之后，设计 h ^ ( n ) \hat{h}(n) h^(n)的注意事项 所有节点采用一致的计算方法，不同节点的计算复杂性不一致（某些节点采用更复杂的计算方式），都可能违反一致性假设；考虑节点状态，要求节点状态与所研究的问题相关，例如实际问题是确定路网中节点间的最短路，那么使用节点的坐标计算 h ^ ( n ) \hat{h}(n) h^(n)就比较合适
因此，引理2成立
引理3：若 h ^ ( n ) \hat{h}(n) h^(n)满足一致性，则评估函数 f ^ ( n ) \hat{f}(n) f^(n)单调不减，即若节点 p p p先于节点 q q q被拓展，则 f ^ ( p ) ≤ f ^ ( q ) \hat{f}(p)\le\hat{f}(q) f^(p)≤f^(q) 证明思路：只需证明相邻两个被拓展的节点（例如节点 m m m拓展之后就拓展节点 n n n）满足该不等式，就可以证明引理成立 case1：开始节点 S S S到节点 n n n的最短路不经过节点 m m m，则拓展节点 m m m的时候，节点 n n n可选，显然 f ^ ( m ) ≤ f ^ ( n ) \hat{f}(m)\le\hat{f}(n) f^(m)≤f^(n) case2：开始节点 S S S到节点 n n n的最短路经过节点 m m m，则 g ( n ) = g ( m ) + h ( m , n ) g(n)=g(m)+h(m,n) g(n)=g(m)+h(m,n) 由引理2可知， g ( n ) = g ^ ( n ) g(n)=\hat{g}(n) g(n)=g^(n)， g ( m ) = g ^ ( m ) g(m)=\hat{g}(m) g(m)=g^(m) f ^ ( m ) = g ^ ( m ) + h ^ ( m ) = g ( m ) + h ^ ( m ) ≤ g ( m ) + h ( m , n ) + h ^ ( n ) = g ( n ) + h ^ ( n ) = g ^ ( n ) + h ^ ( n ) = f ^ ( n ) \hat{f}(m)=\hat{g}(m)+\hat{h}(m)=g(m)+\hat{h}(m)\le g(m)+h(m,n)+\hat{h}(n)=g(n)+\hat{h}(n)=\hat{g}(n)+\hat{h}(n)=\hat{f}(n) f^(m)=g^(m)+h^(m)=g(m)+h^(m)≤g(m)+h(m,n)+h^(n)=g(n)+h^(n)=g^(n)+h^(n)=f^(n)两两相邻的节点都满足不等式，则 f ^ ( p ) ≤ f ^ ( q ) \hat{f}(p)\le\hat{f}(q) f^(p)≤f^(q)因此，引理3成立
推论：若节点 n n n被拓展，则 f ^ ( n ) ≤ f ( S ) \hat{f}(n)\le f(S) f^(n)≤f(S) 证明： 设目标节点为 t t t，则基于引理3可知 f ^ ( n ) ≤ f ^ ( t ) \hat{f}(n)\le \hat{f}(t) f^(n)≤f^(t) 因为 f ^ ( t ) = g ^ ( t ) + 0 = g ( t ) = f ( t ) = f ( S ) \hat{f}(t)=\hat{g}(t)+0=g(t)=f(t)=f(S) f^(t)=g^(t)+0=g(t)=f(t)=f(S) 所以 f ^ ( n ) ≤ f ( S ) \hat{f}(n)\le f(S) f^(n)≤f(S) 因此，推论成立
说明：该部分内容详见论文III.ON THE OPTIMALITY OF A*——C. Proof of the Optimality of A* 【读了几天都没完全想明白(-_-)，仅贴出来原文证明，及存在疑问的地方，希望大家能在评论区多交流，期待有研究者能答疑解惑】 4.1、最优性说明对于一个满足可采纳性的算法A，如果它不能比A*算法获取更多关于图的信息，可称其为no more informed，则任意被A*拓展的节点都会被A拓展 （对于一个图/问题，可以设计不同的算法 h ^ ( n ) \hat{h}(n) h^(n)使其满足可采纳性，即A算法可以看作是一个包含多个算法的集合，其中的最优算法为A*算法，其拓展的节点数最少）
定理2的成立有三个前提条件： 算法A是任何满足可采纳性的算法，且no more informed than A*；若节点 n ≠ m n \neq m n=m，则 f ^ ( n ) ≠ f ^ ( m ) \hat{f}(n) \neq \hat{f}(m) f^(n)=f^(m)；\hat{h}(n) h(n,m)+h^(m)>h^(n)定理2的推论 与其他可采纳的A算法相比，A*是最优的算法，因为其找最短路的过程中拓展的节点数最少
推论1：
推论2：
|
【本文地址】