1、第第3章章 图搜索策略图搜索策略同学们，大家好，这节课我们继续学习图通用搜索算法或图通用搜索算法具有通用性，可以演变为多种搜索策略。在算法的第4步，如果约定每次取出Open表的第一个节点，然后在7.1步中，若生成的后继节点放于：Open表的尾部，算法相当于广度有限；Open表的首部，算法相当于深度优先；根据启发式函数f的估计值确定最佳者，放于Open表的首部，算法相当于最佳优先。下面我们给出衍生出的这些算法的实际跟踪步骤在或图通用搜索算法的第4步，每次取出Open表的第一个节点，然后在7.1步中，若生成的后继节点放于Open表的尾部。下面我们对上述第（1）种情况进行算法步骤的跟踪。例例3.2
2、假定下图的搜索目标是图中的G节点，跟踪广度优先搜索的搜索过程。11.产生仅由S0组成的Open表，即Open(A)；21.产生一个空的Closed表；31.Open(A)，不为空；41.在Open表取出第一个结点A称为n，放n到Closed表中，此时Open()，Closed(A)51.n=A，不是目标；61.产生A的后继B和C，此时M=(B，C)71.对M中的元素B、C，它们不在Open表中，也不在Closed表中，加入到Open表，此时Open(B，C)，再将反向边(B，A)、(C，A)加入到Tree中，Tree=(B，A),(C，A)。81.转3。l第一轮开始和结束后，算法搜索的结果为：
3、第二轮搜索为：32.Open(B，C)，不为空；42.在Open表取出第一个结点B，放到Closed表中，并从Open表中去掉B，此时Open(C)，Closed(A，B)52.n=B，不是目标；62.产生B的后继D、E，此时M=(D，E)72.对M中的元素D、E，它们不在Open表中也不在Closed表中，加入到Open表，Open(C，D，E)，反向边(D,B),(E，B)加入到Tree中，Tree=(B，A),(C，A),(D,B),(E，B)。82.转3。11.产生仅由S0组成的Open表，即Open(A)；21.产生一个空的Closed表；31.Open(A)，不为空；41.在Ope
4、n表取出第一个结点A称为n，放n到Closed表中，此时Open()，Closed(A)在或图通用搜索算法的第4步，每次取出Open表的第一个节点，然后在7.1步中，若生成的后继节点放于Open表的尾部。下面我们对上述第（1）种情况进行算法步骤的跟踪。例例3.2 假定下图的搜索目标是图中的G节点，跟踪广度优先搜索的搜索过程。在或图通用搜索算法的第4步，每次取出Open表的第一个节点，然后在7.1步中，若生成的后继节点放于Open表的尾部。下面我们对上述第（1）种情况进行算法步骤的跟踪。例例3.2 假定下图的搜索目标是图中的G节点，跟踪广度优先搜索的搜索过程。在或图通用搜索算法的第4步，每次取出
5、Open表的第一个节点，然后在7.1步中，若生成的后继节点放于Open表的尾部。下面我们对上述第（1）种情况进行算法步骤的跟踪。例例3.2 假定下图的搜索目标是图中的G节点，跟踪广度优先搜索的搜索过程。在或图通用搜索算法的第4步，每次取出Open表的第一个节点，然后在7.1步中，若生成的后继节点放于Open表的尾部。下面我们对上述第（1）种情况进行算法步骤的跟踪。例例3.2 假定下图的搜索目标是图中的G节点，跟踪广度优先搜索的搜索过程。3.1 或或图搜索策略图搜索策略在或图通用搜索算法的第4步，每次取出Open表的第一个节点，然后在7.1步中，若生成的后继节点放于Open表的尾部。下面我们对上
6、述第（1）种情况进行算法步骤的跟踪。3.1 或或图搜索策略图搜索策略在或图通用搜索算法的第4步，每次取出Open表的第一个节点，然后在7.1步中，若生成的后继节点放于Open表的尾部。下面我们对上述第（1）种情况进行算法步骤的跟踪。在或图通用搜索算法的第4步，每次取出Open表的第一个节点，然后在7.1步中，若生成的后继节点放于Open表的尾部。下面我们对上述第（1）种情况进行算法步骤的跟踪。例例3.2 假定下图的搜索目标是图中的G节点，跟踪广度优先搜索的搜索过程。在或图通用搜索算法的第4步，每次取出Open表的第一个节点，然后在7.1步中，若生成的后继节点放于Open表的尾部。下面我们对上述
7、第（1）种情况进行算法步骤的跟踪。例例3.2 假定下图的搜索目标是图中的G节点，跟踪广度优先搜索的搜索过程。在或图通用搜索算法的第4步，每次取出Open表的第一个节点，然后在7.1步中，若生成的后继节点放于Open表的尾部。下面我们对上述第（1）种情况进行算法步骤的跟踪。例例3.2 假定下图的搜索目标是图中的G节点，跟踪广度优先搜索的搜索过程。3.1 或或图搜索策略图搜索策略l说明:(1)若PM且在open表中，这说明P在n之前已是某一结点m的后继,但本身尚未被考察(未生成P的后继)，S0Path1Path2nm后扩展p先扩展P在n之前已是某一结点m的后继作者朱福喜朱三元3.1 或或图搜索策略
8、图搜索策略这说明从S0p至少有两条路径，这时有两种情况：a若Path1的代价Path2的代价时，当前路径较好，要修改p的指针，使其指向n，即标出搜索之后的最好路径；b若Path1的代价Path2的代价时，原路径较好，不改变p的指针。3.1 或或图搜索策略图搜索策略(2）若pM且在closed表中，这说明:a.p在n之前已是某一节点m的后继，所以需要作如(1)同样的处理，如下图右部。bp在closed表中，说明p的后继也在n之前已生成，我们称为Ps，那么对Ps同样可能由于np这一路径的加入又必须比较多条路径代价后而取代价小的一条，如下图左部。3.1 或或图搜索策略图搜索策略S0过去对Ps所选现在
9、生成P过去生成的最优路径的路径P的路径knPsmP图3-2pM且在closed表中时不同的最优路径3.1 或或图搜索策略图搜索策略l即 过 去 对 S0P而 言 的 最 优 路 径 为S0mp，现在要从S0mp与S0np中求最优路径。l同理，若过去对S0Ps而言的最优路径为S0kPs,现在要从S0pPs,S0kPs中选最优路径。3.1.2 A算法与算法与A*算法算法 1A算法与算法与A*算法定义算法定义或图通用算法第（4）步“在open表上按某一原则选出一个结点”定义为：按启发式函数f的值的从小到大排列，然后取出第一个节点，并采用如下形式的估计函数时,称为A算法。f(n)=g(n)+h(n)其
10、中g(n)表示从S0到n点费用的估计，因为n为当前节点，搜索已达到n点，所以g(n)可计算出。h(n)表示从n到Sg接近程度的估计，因为尚未找到解路径，所以h(n)仅仅是估计值。3.1.2 A算法与算法与A*算法算法进一步，若规定h(n)0，并且定义：f*(n)=g*(n)+h*(n)表示S0经点n到Sg最优路径的费用，或实际最小费用。其中g*(n)为S0到n的最小费用,h*(n)为n到Sg的实际最小费用。在下例中，双虚线表示的路径就可以作为h(n），显然有：g(n）g*(n）h(n）h*(n）l例：在地图上寻找城市A至B的最短路径，双虚线表示ni与Sg的直线距离(可以从地图上量出）,虚线表示
11、ni与Sg的可选择的路径，实线表示从S0出发已经走过的路径为g(n);则实线表示的路径为g(n),粗实线表示g*(n)，虚线和双虚线表示的路径为h(n)。h*(n)?在f(n)中若令：lh(n）0，则A算法相当于广度优先，因为上一层节点的搜索费用一般比下一层的小。lg(n）h(n）0，则相当于随机算法。lg(n）0，则相当于最佳优先算法。特别是当要求：lh(n）h*(n）就称为这种A算法为A*算法算法。A*算法算法设S0：初态,Sg：目标状态1.open=S0；2.closed=；3.如果open=，失败退出；4.在open表上取出f最小的结点n，n放到closed表中；其中：f(n)=g(n
12、)+h(n)h=h*5.若nSg，则成功退出；6.产生n的一切后继，将后继中不是n的先辈点的一切点构成集合M7.对M中的元素P，分别作两类处理：7.1若PG，则P对P进行估计加入open表，记入G和Tree。7.2PG，则决定更改Tree中P到n的指针并且更改P的子节点n的指针和费用。8.转3。l2A*算法的性质算法的性质lA*算法与一般的最佳优先比较，有其特有的性质：如果问题有解，即S0Sg存在一条路径，A*算法一定能找到最优解。这一性质称为可可采采纳纳性性(admissibility）。（例3.4).野人传教士问题作者朱福喜朱三元3.2 与与/或图搜索或图搜索3.2.1 3.2.1 问题归
13、约求解方法问题归约求解方法与与“与与/或图或图”l 在问题求解过程中在问题求解过程中,将一个大的问题变换成将一个大的问题变换成若干子问题若干子问题,子问题又可分解成更小的子问题，子问题又可分解成更小的子问题，这样一直分解到可以直接求解为止这样一直分解到可以直接求解为止,全部子问题全部子问题的解即为大的问题的解的解即为大的问题的解,这样的过程称为问题的这样的过程称为问题的规约规约(Problem Reduction)。并称大的问题为。并称大的问题为初始问题初始问题，可直接求解的问题为，可直接求解的问题为本原问题本原问题。一般说来，归约方法求解问题需要三大要素：1初试问题的描述。2一组将问题变换成
14、子问题的变换规则。3一组本原问题的描述。例3.6符号积分问题分解时有三种可能:1.and2.or3.and,or都有从初始问题出发,建立子问题以及子问题的子问题,直至把初始问题规约为一个本原问题的集合,这就是问题规约的实质。3.2.2 3.2.2“与与/或图或图”的构造方法的构造方法将问题求解归约为与/或图的时，作如下规定：1根节点为原始问题描述;本原问题的节点为叶节点。2可解节点为：2.1终叶节点是可解节点；2.2若n为一非终叶节点，且含有“或”后继节点，则只有当后继节点中至少有一个是可解节点时，n才可解；2.3若n为非终叶节点，且含“与”后继节点，则只有当后继节点全部可解时，n才可解。3不
15、可解节点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(n)=c1+c2+ci+h(n1)+h(n2)+h(ni)4.3若n既有“与”又有“或”弧，则“与”弧算作一个“或”后继，再取各or弧后继中费用最小者为n的费用。3.2.3 与与/或图搜
16、索的过程或图搜索的过程1与与/或图搜索搜索费用的估计或图搜索搜索费用的估计 对与/或图则不同，其费用计算的规则是：ln未生成后继节点时，费用由n本身决定;ln已生成后继节点时，费用由n的后继节点的费用决定。因为后继节点代表分解的子问题,子问题的难易程度决定原问题求解的难易程度，所以不再考虑n本身的难易程度。因此当决定了某个路径时，要将后继节点的估计值往回传送。例3.7图3-9为一个与/或图的搜索过程。l第一步，A是唯一节点；l第二步，扩展A后，得到节点B,C和D,因为B，C的耗费为9，D的耗费为6，所以把列D的弧标志为出自A最有希望的弧；l第三步，选择对D的扩展，得到E和F的与弧，其耗费估计值
17、为10。此时回退一步后，发现与弧BC比D更好，所以将弧BC标志为目前最佳路径；第四步，在扩展B后,再回传值发现弧BC的耗费为12（6+4+2），所以D再次成为当前最佳路径。l最后求得的耗费为:lf(A)=min(12,4+4+2+1)=11。l以上搜索过程由两大步组成：l（1)自顶向下，沿当前最优路产生后继节点。l（2）由底向下，作估计值修正，再重新选择最优路。2.与与/或图搜索的限制或图搜索的限制与/或图搜索仅对不含回路的图进行操作。例如：xy表示求了x就可以求y.，求了y就可以求x，两者都不可能求解。3.2.4 与与/或图搜索算法或图搜索算法AO*AO*算法算法：1.令G=Init,计算h
18、(Init)。2.在Init标志solved之前或h(Init)变成大于Futility之前，执行以下步骤：2.1沿始于Init的已带标志的弧，选出当前沿标志路上未扩展的节点之一扩展（即求后继节点），此节点称为node。2.2生成node的后继节点。若无后继节点，则令h(node)=Futility,说明该节点不可解；若有后继节点，称为successor,对每个不是node祖先的后继节点（避免回路），执行下述步骤：2.2.1将successor加入G。2.2.2若successorSg,则标志successor为solved，且令h(successor)=0。2.2.3若successorSg
19、,则求h(successor)2.3由底向上作评价值修正，重新挑选最优路径。/令S为一节点集。/S已标志为solved的点，或h值已/改变,需回传至其先辈节点的节点令S初值node,重复下述过程，直到S为空时停止。2.3.1从S中挑选一节点,该节点的后辈点均不在S中(保证每一正在处理的点都在其先辈节点之前作处理),此节点称为current,并从S中删除;2.3.2计算始于current的每条弧的费用,即每条弧本身的费用加上弧末端节点h的值(注意区分与,或弧的 计 算 方 法),并 从 中 选 出 极 小 费 用 的 弧 作 为h（current）的新值。2.3.3将费用最小弧标志为出自curr
20、ent的最优路径。2.3.4若current与新的带标志的弧所连接的点均标志solved,则current标志solved.。2.3.5若current已标志为solved或current的费用已改变，则需要往回传，因此要把current的所有先辈节点加入S中。ABCDstep2.3.1S=Astep2.3.2current：A由于有ABandC的弧，current的费用=1+1+h(B)+h(C)=9由 于 有 AD的 弧，current的费用=1+5=6A的费用=min(9,6)=6;（3）（4）（5）ADEFh(E)=4h(F)=4106node=D，由step2.2.3，扩展D得successor=E,F，D的耗费估计已经改变，向上回传，导致A的耗费为min（9，11）=9，所以，最优路径为ABC弧。3.2.5 用用AO*算法求解一个智力问题算法求解一个智力问题l有这样一个智力问题：有12枚硬币，凡轻于或重于真币者，即为假币(只有一枚假币)，要设计一个搜索算法来识别假币并指出它是轻于还是重于真币，且利用天平的次数不多于3次。演示l该问题的困难之处在于问题要求只称三次就要找到假币，否则就承认失败。如果称法不得当，使得留下的未知币太多，就不可能在3次内称出假币。因此，每称一次，我们希望尽可能地得到关于假币的信息。
