1、2.4.2 A算法与A*算法 1A算法与算法与A*算法定义算法定义 或图通用算法在采用如下形式的估计函数时, 称为A算法。 f(n)=g(n)+h(n) 其中g(n)表示从S0到n点费用的估计，因为n为当前节点，搜索已达到n点，所以g(n)可计算出。h(n)表示从n到Sg接近程度的估计，因为尚未找到解路径，所以h(n)仅仅是估计值。 例2.10 在地图上寻找城市A至B的最短路径，双虚线表示ni与Sg的直线距离(可以从地图上量出）, 虚线表示ni与Sg的路径，则实线表示的路径为g(n），虚线表示的路径为h(n）。 A=S0B=Sgn1n2n3n4n52.4.2 A算法与A*算法 若规定h(n)0
2、，并且定义： f*(n)=g*(n)+h*(n) 表示S0经点n到Sg最优路径的费用，也有人将f*(n)定义为实际最小费用。其中g*(n)为S0到点n的最小费用, h*(n)为n到Sg的实际最小费用。在上例中，双虚线表示的路径就可以作为h*(n），显然有g(n）g*(n）。 h(n） h*(n） 若令 h(n）0，则A算法相当于广度优先，因为上一层节点的搜索费用一般比下一层的小。 g(n）h(n）0，则相当于随机算法。 g(n）0，则相当于最佳优先算法。 特别是当要求 h(n）h*(n）， 就称为这种A算法为A*算法算法。 A*算法算法 设S0 ：初态, Sg：目标状态 1. open=S0；
3、 2. closed= ； 3. 如果open=，失败退出； 4. 在open表上取出f最小的结点n， n放到closed表中； f(n)=g(n)+h(n) h=h* 5. 若nSg，则成功退出； 6. 产生n的一切后继，将后继中不是n的先辈点的一切点构成集合M 7. 对M中的元素P，分别作两类处理： 7.1 若PG，则P对P进行估计加入open表，记入G和Tree。 7.2 PG，则决定更改Tree中P到n的指针并且更改P的子节点n的指针和费用。 8. 转3。 2A*算法的性质算法的性质 A*算法与一般的最佳优先比较，有其特有的性质：如果问题有解，即S0Sg存在一条路径，A*算法一定能找到
4、最优解。这一性质称为可采纳性可采纳性(admissibility）。 （p35例2.11) 下面要证明A*算法的可采纳性，证明分两步： (1）证若问题有解，A*一定终止，由如下命题1-3证出。 (2）证若问题有解，A*终止时一定找到最优解，由如下命题4证出。命题命题1 对有限图而言，A*一定终止。证：考察A*算法，算法终止只有二处： 第一处 在第5步，找到解时成功终止。 第二处 在第3步，open为空时失败退出。 算法每次循环从open上去掉一个点，而有限图的open表只有有限个节点加入，所以找不到解也会因为open表为空而停止命题命题2 若A*不终止，则搜索图中open表上的点的f值将会越来
5、越大。 证：设n为open中任一节点，d*(n）为从S到n中最短路径长度，由于从某一点求出其后继的费用不小于某个小的正数e，所以 g*(n）d*(n）e 而 g(n）g*(n）d*(n）e 又因为 h(n）0 所以f(n）g(n）g*(n）d*(n）e (2-1） 命题命题3 若问题有解，在A* 终止前，open表上必存在一点n，n位于从S0Sg的最优路径上，且有 f(n）f*(S0） (2-2） f*(S0）表示从S0到Sg的最优路的实际最小费用。 f*(n）表示从S0经过n到Sg的最优路的实际最小费用。证：令S0=n0，n1，n2，nk=Sg为一条最优路径，设npath(n0，n1，nk）
6、中最后一个出现在open表上的元素。显然n一定存在，因为至少有S0=n0必然在open上，只考虑当nk还未在closed表中时，因为若nk已在closed表中时，则nk=Sg，A*算法将终止于成功退出。 由定义有 f(n）=g(n）+h(n）=g*(n）+h(n） (因为n在最优路径上） g*(n）+h*(n）=f*(n）=f*(S0）(由于A*的定义h(n) h*(n) 所以f(n）f*(S0）成立。 推论推论1 若问题有解，A*算法一定终止。 因为若A*算法不终止，则命题2的(2-1）与命题3的(2-1）同时成立，则产生矛盾。 命题命题4 若问题有解，A*算法终止时一定找到最优解, 即A*
7、算法是可采纳的。证：A*终止只有两种情况。 (1) 在第3步, 因open为空而失败退出 但由命题3可知：A*终止前，open表上必存在一点n，满足 f(n）f*(S0）即open表不会空，所以，不会终止于第3步。 推论推论2 凡open表中任一点n，若f(n） f*(S0），最终都将被A*算法挑选出来求后继，也即被挑选出来进行扩充。 证：用反证法，设f(n） f*(S0）且n没有被选出来作后继由命题4, A*算法将找到一条路S0=n0，n1，nk=Sg,为最优路径且f(ni) f(n)对一切i=0,1,k成立因为最优路径选择的是ni而不是n，又因为ni在最优路上,由f(ni)=f*(S0)所
8、以 f*(S0) f(n)与f(n)f*(S0)同时成立,这是一个矛盾。 命题命题5 凡A*算法挑选出来求后继的点n必定满足: f(n）f*(S0） (2-3) 证明:若n=Sg,由命题4 可知,A*一定找到最优解，所以 f(n）= f*(Sg）f*(S0）; 若nSg,由命题3可知:存在nopen且有f(n）f*(S0） 而现在A*算法选中了n而不是n,所以必有 f(n)f(n)f*(S0) 即 f(n）f*(S0） 定义定义1 若A1,A2均是A*算法, A1采用f1(x)=g1(x)+h1(x) 作为估计函数，A2采用f2=g2(x)+h2(x)作为估计函数。h1(x),h2(x)都满足
9、: hi(x)hi*(x),i=1,2 (2-4) 如果h1(x) AC分枝中任一点的值，则永远不会走B这条路，这将导致可能找不到解。BCASg实际是1, 估计21.51 另外搜索的费用并不完全由搜索节点数多少来确定，若f2(n)计算远比f1(n)复杂，则在比较两个搜索算法时，必须要考虑f的计算费用。一般来说要权衡如下三个因素： (1) 路径费用； (2) 寻找路径时所搜索的节点数； (3) 计算f所需的计算量。若h(x)满足一定限制,如单调性限制，则搜索路径几乎就是解路径，因而大大减小了搜索费用。 定义定义2 一个启发式函数中的h(x)满足单调限制，可定义为：如果对所有ni与nj，nj是ni
10、的后继，有h(ni)h(nj)+c(ni,nj)，并且h(Sg)=0, 即nj到目标的最佳费用估计不会大于ni到目标的最佳费用估计加上ni至nj的费用。这个要求相当一个三角不等式。命题命题7 估计函数若满足单调限制，那么A*所扩充的任一点(即用来求过后继的点）n必在最优路上。 证明思路：令g*(n）代表从S0n的最优路径费用，所以一般有 g(n）g*(n） (2-12）下面再利用单调限制能够证明： g(n）g*(n） (2-13）联立(2-12），(2-13），可得g(n）=g*(n），也就说明了n位于最佳路径上。3对对A*算法的评价算法的评价A*算法的优点有：（1）A*算法一定能保证找到最优
11、解。（2）若以搜索的节点数来估计它得效率，则当启发式函数h的值单调上升时，它的效率只会提高，不会降低。（3）有比较合理的渐近性质。A*算法的缺点是： 在不仅考虑搜索节点的多少，而且还要考虑搜索节点被搜索的次数的时候，则当h(n）过低估计h*(n）时，有时会显出很高的复杂性。 例题：走迷宫算法 假设某个精灵从A点走到B点，而A，B点之间隔着半堵墙。如下图所示，左边的浅色方块代表起点A，右边的浅色方块代表终点B，正中间的深灰色填充区域代表墙。 求从A点到B点的一条（最短）路径 算法总结 （1）添加起始位置到OpenList中 （2）重复下面的步骤： (2.1).在OpenList中寻找F值最低的节
12、点，这个节点称为当前位置。 (2.2) 把当前位置交换到CloseList中，即从OpenList中删除该节点并添加到CloseList中。 (2.3) 对于当前位置的8个邻域，操作如下： 如果该区域走不通或该区域已经在CloseList中，则忽略该区域。否则做下面的操作。 如果该区域不在OpenList中，则把该区域添加到OpenList中，并使该区域的父指针指向当前位置。 如果该区域已经在OpenList中，则计算一下当前区域到该区域的G累加值。如果这个G值比原来该区域的G值还小，则说明这条路径很好。如果是这样，将该区域的父指针指向当前区域，并重新计算该区域的G值和F值。如果OpenLis
13、t是按F值排序的，则现在需要重新排序。 (2.4) 当下面任意一个条件满足时，停止搜索。 目标区域已经被加入到OpenList中，即路径找到了。 没有找到目标区域，并且OpenList已经为空，即没有可达路径。 (3) 保存路径。利用父指针从目标区域往回走直到回到起始点。 2.5 问题归约与问题归约与AO*算法算法 2.5.1 问题归约求解方法与问题归约求解方法与“与与/或图或图”在问题求解过程中, 将一个大的问题变换成若干子问题, 子问题又可分解成更小的子问题，这样一直分解到可以直接求解为止, 全部子问题的解即为大的问题的解,这样的过程称为问题的规约(Problem Reduction)。并
14、称大的问题为初始问题，可直接求解的问题为本原问题。 一般说来，归约方法求解问题需要三大要素： 1 初试问题的描述。 2 一组将问题变换成子问题的变换规则。 3 一组本原问题的描述。 例2.13 符号积分问题 分解时有三种可能: 1. and 2. or 3. and, or 都有 从初始问题出发, 建立子问题以及子问题的子问题, 直至把初始问题规约为一个本原问题的集合, 这就是问题规约的实质。2.5.2 与与/或图搜索或图搜索将问题求解归约为与/或图的时，作如下规定：1与或图中始点(根)为原始问题描述;与或图中对应于本原问题的节点为终叶节点。2可解节点为： 2.1 终叶节点是可解节点； 2.2
15、 若n为一非终叶节点，且含有“或”后继节点，则只有当后继节点中至少有一个是可解节点时，n才可解； 2.3 若n为一非终叶节点，且含“与”后继节点，则只有当后继节点全部可解时，n才可解。 3 不可解节点： 3.1 没有后继节点的非终叶节点为不可解； 3.2 若n为一非叶节点含有“或”后继节点，则仅当全部后继节点为不可解时，n不可解。 3.3 若n为一非叶节点含有“与”后继节点，则只要有一个后继节点为不可解时，n为不可解。 4与或图中搜索费用的计算：设从当前节点n到目标集Sg费用估计为h(n). 4.1 若nSg, 则h(n)=0; 4.2 若n有一组由“与”弧连接的后继节点n1,n2,ni 则h
16、(n)=c1+c2+ci+h(n1)+h(n2)+h(ni)。其中ci为n到ni弧的费用。 4.3 若n既有“与”又有“或”弧，则“与”弧算作一个“或”后继，再取各or弧后继中费用最小者为n的费用。2.5.3 与与/或图搜索的特点或图搜索的特点1与与/或图搜索搜索费用的估计或图搜索搜索费用的估计 对与对与/或图则不同，其费用计算的规则是：或图则不同，其费用计算的规则是： n未生成后继节点时，费用由未生成后继节点时，费用由n本身决定本身决定; n已生成后继节点时，费用由已生成后继节点时，费用由n的后继节的后继节点的费用决定。点的费用决定。 因为后继节点代表分解的子问题因为后继节点代表分解的子问题
17、, 子问子问题的难易程度决定原问题求解的难易程度，题的难易程度决定原问题求解的难易程度，所以不再考虑所以不再考虑n本身的难易程度。因此当本身的难易程度。因此当决定了某个路径时，要将后继节点的决定了某个路径时，要将后继节点的估计估计值往回传送。值往回传送。 例2.14 图2-35为一个与/或图的搜索过程。 第一步，A是唯一节点； 第二步，扩展A后，得到节点B,C和D, 因为B，C的耗费为9，D的耗费为6，所以把列D的弧标志为出自A最有希望的弧； 第三步，选择对D的扩展，得到E和F的与弧，其耗费估计值为10。此时回退一步后，发现与弧BC比D更好，所以将弧BC标志为目前最佳路径； 第四步，在扩展B后
18、,再回传值发现弧BC的耗费为12（6+4+2），所以D再次成为当前最佳路径。 最后求得的耗费为: f(A)=min(12,4+4+2+1)=11。 以上搜索过程由两大步组成： （1) 自顶向下，沿当前最优路产生后继节点。 （2）由底向上，作估计值修正，再重新选择最优路。2. 与与/或图搜索路径的选择或图搜索路径的选择由于有“与”连接弧，所以不能像“或”弧那样只看从节点到节点的个别路径。有时路径长反而好一些。请看下例： 1 2 3 4 7 8 5 6 9 10目标不可解 搜索虽然从比更长，但由于走分枝的同时还必须走，而不可能通向解, 所以有时走长点的路径比短路径要好一些。 1 2 3 4 7 5
19、 6 9 10 8目标不可解3. 与与/或图搜索的限制或图搜索的限制 与/或图搜索仅对不含回路的图进行操作。 例如： x y 表示求了x就可以求y.，求了y就可以求x，两者都不可能求解。 2.5.4 与与/或图搜索算法或图搜索算法AO* AO*算法算法： 1. 令G=Init,计算h(Init)。 2. 在Init标志solved之前或h(Init)变成大于Futility之前，执行以下步骤： 2.1沿始于Init的已带标志的弧，选出当前沿标志路上未扩展的节点之一扩展（即求后继节点），此节点称为node。 2.2 生成node的后继节点。 若无后继节点，则令h(node)=Futility,说
20、明该节点不可解； 若有后继节点，称为successor,对每个不是node祖先的后继节点（避免回路）， 执行下述步骤： 2.2.1 将successor加入G。 2.2.2 若successorSg,则标志successor为solved，且令h(successor)=0。 2 . 2 . 3 若 s u c c e s s o r S g , 则 求h(successor)。 2.3 由底向上作评价值修正，重新挑选最优路径。 令S为一节点集。 S已标志为solved的点，或h值已改变, 需回传至其先辈节点的节点 令S初值node,重复下述过程，直到S为空时停止。 2.3.1 从S中挑选一节点
21、,该节点的后辈点均不在S中(保证每一正在处理的点都在其先辈节点之前作处理),此节点称为current,并从S中删除; 2.3.2 计算始于current的每条弧的费用,即每条弧本身的费用加上弧末端节点h 的值(注意区分与,或弧的计算方法),并从中选出极小费用的弧作为h（current）的新值。 2.3.3 将费用最小弧标志为出自current的最优路径。 2.3.4 若current与新的带标志的弧所连接的点均标志solved,则current标志solved.。 2.3.5 若current已标志为solved或current的费用已改变，则需要往回传，因此要把current的所有先辈节点加
22、入S中。 A B C Dstep2.3.1 S=A step2.3.2 current：A 由于有AB and C的弧， c u r r e n t 的 费 用=1+1+h(B)+h(C)=9 由 有 A D 的 弧 ，current的费用=1+5=6A的费用=min(9,6)=6;（3） （4） （5） A D E F h(E)=4 h(F)=4 106 n o d e = D ， 由step2.2.3，扩展D得successor=E,F，D的耗费估计已经改变，向上回传，导致A的耗费为min（9，11）=9，所以，最优路径为ABC弧。2.5.5 对对AO*算法的进一步观察算法的进一步观察 (
23、1) 算法中2.3.5步中要将费用已改变的某一节点所有祖先加入S, 然后修改祖先的费用。 例2.17 （7） A B C D E(10) (6) （3） （5）当从E往回传时，若实际上走A B这条路总是不好时，则从EB回传是浪费，是无用的回传，所以完全回传至一切祖先的费用很大。若仅沿标志往回传，又可能找不到最优解。如下图所示： C D A B C D E F G A B E F G H （11） （14） (13) (10) (13) (18) (15) 扩展G (11) (5) (6) (3) (5) (6) (3) (5) (10) (9) 由HG回传时,若只沿“ ”标志往上传至C，再回至
24、E, 则E仍为（6）而实际上应为（11），B仍为（13）而实际上应为（18）。这样导致A将又选择AB这条路，实际这条路径比AC更差。所以顺路径标志往上传递修正的AO*算法不一定保证能找到最优解。 （2）算法没有考虑子目标之间的相互依赖关系。 例2.18 美国总统候选人 美国出生美国公民 (5) (3) 移民（少数） (2) A B C D2.5.6 用AO*算法求解一个智力难题 设有12个硬币，凡轻于或重于真币者，即为假币（只有一枚假币），要设计一个算法来识别假币，并指出它是轻于还是重于真币，且利用天平的次数不多于3次。 1. 问题表示 将硬币的重量分为4种类型 标准型（Standart）标记
25、为S 轻标型（Light or Standard）标记为LS 重标型（Heavy or Standard）标记为HS 轻重标准型（Light or Heavy or Standard）标记为LHS 问题状态可以表示一个五元组： （LHS，LS，HS，S，T） 其中前4个元素表示当前这四种类型硬币的个数，T表示所剩称硬币的次数。 初始状态: (12, 0, 0, 0, 3) 目标状态: ( 0, 1, 0, 11, 0）或（0, 0, 1, 11, 0）2 如何利用AO*算法求解首先考虑如何取硬币的问题。设当前的状态为（lhs，ls，hs，s，t）, 用函数PICKUP(lhs1, ls1, h
26、s1,s1, lhs2,ls2,hs2,s2)表示本次分别从（lhs, ls, hs, s, t）中取出了lhs1,ls1,hs1,s1个硬币放在天平的左边,取出了 lhs2,ls2,hs2,s2个硬币放在天平的右边。对于PICKUP应默认有如下性质成立：0 lhs1+ls1+hs1+s1=lhs2+ls2+hs2+s26，即天平两边的硬币数相等且小于等于6 lhs1+ lhs2lhsls1+ ls2lshs1+hs2hss1+ s2s,即取出的硬币数小于等于相应类型原有的硬币数。 然后令PICKUP()等于1，0，1，分别表示天平左倾、平衡和右倾。这样，有以下规则：L规则：if PICKUP
27、(lhs1,ls1,hs1,s1, lhs2,ls2,hs2,s2 ) = -1（lhs, ls, hs, s, t）Then （lhs, ls, hs, s, t-1）其中：ss+ls-ls2+hs-hs1+lhs-(lhs1+lhs2); ls=ls2+lhs2; hs=lhs1+hs1; lhs=0这四个公式的含义分别是：若天平左倾，则在左天平的状态为LS的硬币，在右天平的状态为HS的硬币和未放在天平上的硬币都是标准的，即hs2+hs1+(lhs-lhs1-lhs2)+(ls-ls1-ls2)+ (hs-hs1-hs2)个硬币的状态都改变为标准型；右天平原有的ls2个轻标准型的硬币仍然为
28、轻标准型，右天平原有的lhs2个轻重标准型硬币改变为轻标准型；左天平原有的hs1个重标准型的硬币仍然为重标准型，左天平原有的lhs1个轻重标准型硬币改变为重标准型；只要不平衡，就不存在LHS型的硬币，所有的硬币都可以确定为LS，HS或S型，即lhs=0。 B规则：if PICKUP(lhs1,ls1,hs1,s1, lhs2,ls2,hs2,s2)= 0（lhs, ls, hs, s, t） Then （lhs, ls, hs, s, t-1）其中：ss+ls1+ls2+hs1+hs2+lhs1+lhs2; ls=ls- ls1-ls2; hs=hs- hs1-hs2; lhs= lhs- l
29、hs1- lhs2这四个公式的含义分别是：若天平平衡，则所有在天平上的硬币都是标准型，即ls1+ls2+hs1+hs2+lhs1+lhs2个硬币的状态都改变为标准型；左、右天平原有的轻标准型的硬币改变为标准型，所以从ls中减去ls1和ls2；左右天平原有的重标准型硬币改变为标准型，所以也要从hs中减去hs1和hs2；在平衡情况下，LHS型的硬币要减去左右天平原有的轻重标准型的硬币，即lhs=lhs-hs1-lhs2。 R规则：if PICKUP(lhs1,ls1,hs1,s1, lhs2,ls2,hs2,s2)= 1（lhs, ls, hs, s, t） Then （lhs, ls, hs,
30、s, t-1）其中：ss+ls-ls1+hs-hs2+lhs-(lhs1+lhs2); ls=ls1+lhs1; hs=lhs2+hs2; lhs=0这四个公式的含义于L规则的含义类似：若天平右倾，则在左天平的状态为HS的硬币和在右天平的状态为LS的硬币以及未放在天平上的硬币都是标准的，即hs1+hs2+(lhs-lhs1-lhs2)+(ls-ls1-ls2)+(hs-hs1-hs2)个硬币的状态都改变为标准型；左天平原有的ls1个轻标准型的硬币仍然为轻标准型，左天平原有的lhs1个轻重标准型硬币改变为轻标准型；右天平原有的hs2个重标准型的硬币仍然为重标准型，右天平原有的lhs2个轻重标准型
31、硬币改变为重标准型；因为不平衡， lhs=0。 3如何在问题空间中搜索 利用AO*算法对该问题搜索时，用PICKUP表示一种选取方法，不同的选取方法之间是“或”的关系，当选定一种PICKUP后，就必须考虑它的值为-1,0,1的情况下，下层的节点都可解，则三种情况之间的关系为“与”的关系。说明该问题的搜索图是与/或图，我们采取的搜索算法是AO*算法。 定义该算法的评价函数为： h(lhs, ls, hs, s, t) = lhs+ls+hs-1显然有h(0, 1, 0, 11, 0)=0 和 h(0, 0, 1, 11, 0)=0即 h(Sg1)= h(Sg2)=0 由于问题的本原问题对应的节点
32、是可解节点，因此Sg1和Sg2为可解节点。不可解节点可以定义为：如果节点n=(lhs, ls, hs, s, t)中t=0, 且(lhs, ls, hs, s)不属于(0, 1, 0, 11), (0, 0, 1, 11, 0)，则n为不可解节点。 4. 问题的推广从上述计算过程中观察到称硬币的次数与硬币枚数之间的关系有：称3次可在（333）/2=12个硬币中找出假币；称4次可在（343）/2=39个硬币中找出假币；称5次可在（353）/2=120个硬币中找出假币。定理：使用天平k次可从（3k3）/2个硬币中找出假币。 证明略 2.6 约束满足法2.6.1 约束满足问题 AI中许多问题(比如视
33、觉问题)可以归纳为约束满足问题：目标是找出某个状态，它能满足一个给定的约束集中的一切约束条件。 约束满足问题并没有引入新的搜索方法，还是使用已讨论过的方法求解，但搜索空间有两个：（1）问题状态空间；（2）随状态空间变化而变化的约束空间。 而且在两个空间中的搜索并行进行，并可以利用的搜索规则和启发式函数涉及约束空间的当前位置的信息。 2.6.2 约束满足问题求解 约束满足问题求解的一般过程：（1）从搜索图中挑选一个未求后继的节点；（2）将约束推理规则作用到新选节点，从而产生新的约束；（3）若约束集含有矛盾，则报告此路不通，从而结束此分支的搜索；（4）若约束已完全满足且到达一个完全解，则报告成功；（5）若约束即未找到矛盾，又未达到完全解，则产生新的与当前约束集相容的点并插入图中。 例题：密码算术问题 S E N D M O R EM O N E Y 要求：（1）每个字母赋一个十进制数。 （2）代入后使坐标加法成立。 The end!
