第一章搜索问题

1、第一章第一章 搜索问题搜索问题2基本概念基本概念1.什么是搜索？ 根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的求解路线，使问题得到圆满解决的过程称为搜索搜索。2.盲目搜索 盲目搜索盲目搜索是按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。基本概念基本概念 启发式搜索启发式搜索是在搜索中加入了与问题有关的启发式信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。 3. 启发式搜索 由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，所以这种搜索具有盲目性，效率不高，不便于复杂问题的求解。启发式搜索优于盲目搜索。但由于启发式搜

2、索需要具有与问题本身特性有关的信息，而这并非对每一类问题都可方便地抽取出来,因此盲目搜索仍不失为一种应用较多的搜索策略。 1.11.1 状态空间表示法状态空间表示法 状态空间表示法状态空间表示法是人工智能中最基本的形式化方法，是讨论问题求解技术的基础。状态空间表示法是用“状态”和“算符”来表示问题的一种方法。其中“状态”用以描述问题求解过程中不同时刻的状况；“算符”表示对状态的操作，算符的每一次使用就使问题由一种状态变换为另一种状态。当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题的一个解。 1. 1. 状态状态 状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量或多维

3、数组S Sk k=(S=(Sk0k0,S,Sk1k1,S,Sknkn)表示，当给每个分量以确定的值时，就得到了一个具体的状态。 2. 2. 算符算符 引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。操作可以是一个机械的步骤、过程、规则或算子，指出了状态之间的关系。3. 3. 状态空间状态空间 由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用一个三元组表示：（S,F,G）其中S是问题求解过程中所有可达的合法状态构成的集合；F是算符的集合；G是目标状态的集合。问题的状态空间可以用一个赋值有向图来表示，称为状态空间图。其中，节点表示状态；有向边（弧）

4、表示算符。 传教士与野人问题传教士与野人问题 例：例：设N个传教士带领N个野人划船渡河，且为安全起见，渡河需遵循两个约束：（1）船上的人数不得超过载重限量，设为K个人；（2）为预防野人攻击，任何时刻（包括两岸、船上）野人数目不得超过传教士数目。应如何规划渡河方案？ 为便于理解状态空间表示法，可简化该问题到一个特例：N=3，K=2。 解：解：首先选取描述问题状态的方法。在这个问题中，需要首先选取描述问题状态的方法。在这个问题中，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸。从而可用一个三元组来表示状态右岸。从而可用一个三元组

5、来表示状态 S=(m, c, b)其中，其中，m表示左岸的修道士人数，表示左岸的修道士人数，c表示左岸的野人数，表示左岸的野人数，b表示表示左岸的船数。左岸的船数。 右岸的状态可由下式确定：右岸的状态可由下式确定： 右岸修道士数右岸修道士数 m=3-m 右岸野人数右岸野人数 c=3-c 右岸船数右岸船数 b=1-b 在这种表示方式下，在这种表示方式下，m和和c都可取都可取0、1、2、3中之一，中之一，b可取可取0和和1中之一。因此，共有中之一。因此，共有442=32种状态。种状态。 这这32种状态并非全有意义，除去不合法状态和修道士被野人吃种状态并非全有意义，除去不合法状态和修道士被野人吃掉的

6、状态，掉的状态，有意义的状态只有有意义的状态只有16种：种： S0=(3, 3, 1) S1=(3, 2, 1) S2=(3, 1, 1) S3=(2, 2, 1) S4=(1, 1, 1) S5=(0, 3, 1) S6=(0, 2, 1) S7=(0, 1, 1) S8=(3, 2, 0) S9=(3, 1, 0) S10=(3, 0, 0) S11=(2, 2, 0) S12=(1, 1,0) S13=(0, 2, 0) S14=(0, 1, 0) S15=(0, 0, 0)有了这些状态，还需要考虑可进行的操作。有了这些状态，还需要考虑可进行的操作。 操作操作是指用船把修道士或野人从河的

7、左岸运到右岸，或从河的是指用船把修道士或野人从河的左岸运到右岸，或从河的右岸运到左岸。右岸运到左岸。 每个操作都应当满足如下条件：每个操作都应当满足如下条件： 一是一是船至少有一个人（船至少有一个人（m或或c）操作，离开岸边的）操作，离开岸边的m和和c的减少数的减少数目应该等于到达岸边的目应该等于到达岸边的m和和c的增加数目；的增加数目； 二是二是每次操作船上人数不得超过每次操作船上人数不得超过2个；个； 三是三是操作应保证不产生非法状态。操作应保证不产生非法状态。 因此，因此，操作应由条件部分和动作部分：操作应由条件部分和动作部分： 条件：条件：只有当其条件具备时才能使用只有当其条件具备时才

8、能使用 动作：动作：刻划了应用此操作所产生的结果。刻划了应用此操作所产生的结果。 操作的表示：操作的表示： 用符号用符号Pij表示从左岸到右岸的运人操作表示从左岸到右岸的运人操作 用符号用符号Qij表示从右岸到左岸的操作表示从右岸到左岸的操作其中：其中： i表示表示船上的修道士人数船上的修道士人数 j表示表示船上的野人数船上的野人数操作集操作集 本问题有本问题有10种操作可供选择：种操作可供选择： F=P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20 下面以下面以P01和和Q01为例来说明这些操作的条件和动作。为例来说明这些操作的条件和动作。 操作

9、符号操作符号 条件条件 动作动作 P01 b=1, m=0或或3, c1 b=0, c=c-1 Q01 b=0, m=0或或3，c2 b=1, c=c+1 于是，从初始状态出发，可画出该问题的状态空间有向图，见图1.1。 o(220) (110)o o(021)o(220) (110)o o(021) 11 10 20 11 01 02 11 10 20 11 01 02(331)o 01 o(320) o(321) o(311) o(221)(031)o 02 o(010)(011)o 01 o(000)(331)o 01 o(320) o(321) o(311) o(221)(031)o

10、02 o(010)(011)o 01 o(000) 02 01 02 01 20 01 10 11 02 01 02 01 20 01 10 11 o(310) o(300) o(020) o(111) o(310) o(300) o(020) o(111) 图1.1 传教士与野人问题的状态空间图 13二阶梵塔问题二阶梵塔问题 ABABAB 1 2 3 1 2 3 1 2 3二阶梵塔问题的初始状态和目标状态二阶梵塔问题的初始状态和目标状态问题的初始状态集合为问题的初始状态集合为S=S0 目标状态集合为目标状态集合为G=S4, S5 初始状态初始状态S0和目标状态和目标状态S4、S8如图所示如图

11、所示 S0=(1, 1)S4=(2, 2)S8=(3, 3) 操作分别用操作分别用A(i, j)和和B(i, j)表示表示 A(i, j)表示把金片表示把金片A从第从第i号钢针移到号钢针移到j号钢针上；号钢针上； B(i, j)表示把金片表示把金片B从第从第i号钢针一到第号钢针一到第j号钢针上。共有号钢针上。共有12种种操作，它们分别是：操作，它们分别是： A(1, 2) A(1, 3) A(2, 1) A(2, 3) A(3, 1) A(3, 2) B(1, 2) B(1, 3) B(2, 1) B(2, 3) B(3, 1) B(3, 2) 根据上述根据上述9种可能的状态和种可能的状态和1

12、2种操作，可构成二阶梵塔问题的种操作，可构成二阶梵塔问题的状态空间图，如下图所示。状态空间图，如下图所示。(3,3) (1,3) (1,2) (2,2) 二阶梵塔的状态空间图 从初始节点从初始节点(1, 1)到目标节点到目标节点(2, 2)及及(3, 3)的任何一条路径都是问题的一的任何一条路径都是问题的一个解。其中，最短的路径长度是个解。其中，最短的路径长度是3，它由，它由3个操作组成。例如，从个操作组成。例如，从 (1, 1)开始，开始，通过使用操作通过使用操作A(1, 3)、B(1, 2)及及A(3, 2)，可到达，可到达 (3, 3)。A(1,2)B(1,3)A(2,3)(1,1)(3

13、,1)(3,2)(2,1)(2,3)A(1,3)B(1,2)A(3,2)状态空间表示法的几点说明状态空间表示法的几点说明 用状态空间方法表示问题时，首先必须定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来。其次，还要定义一组算符，通过使用算符可把问题由一种状态转变为另一种状态。 问题的求解过程是一个不断把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用算符构成的序列。 算符的一次使用，就使问题由一种状态转变为另一种状态。可能有多个算符序列都可使问题从初始状态变到目标状态，这就得到了多个解。把其中使用算符

14、最少的解称为最优解。例如在上例中，问题有无数条解答路径(因为划船操作可逆),但只有4个最优解，都包含了11个操作算子。这只是从解中算符的个数来评价解的优劣，今后将会看到评价解的优劣不仅要看使用算符的数量，还要看使用算符时所付出的耗散值，只有总耗散值最小的解才是最优解。 对任何一个状态，可使用的算符可能不止一个，这样由一个状态所生成的后继状态就可能有多个。当对这些后继状态使用算符生成更进一步的状态时，首先应对哪个状态进行扩展呢？这取决于搜索策略，不同的搜索策略的扩展顺序是不同的，这正是本章要讨论的问题。 除了少数像“传教士与野人”这样的简单的问题外，描述状态空间的图一般都很大，无法直观地画出，只

15、能将其视为隐含图，在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的搜索图。状态空间、搜索图和解答路径之间的关系，可以用下图表示。状态空间、搜索图和解答路径的关系图状态空间、搜索图和解答路径的关系图 S0Sg问题全部状态空间问题全部状态空间搜索空间搜索空间解路径解路径搜索问题（续）搜索问题（续）1.21.2 回溯策略回溯策略 回溯策略回溯策略是一种试探性策略，属于盲目搜索盲目搜索的一种。它首先将规则给出一个固定的排序，在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可应用规则，应用于当前状态，得到的新状态重新设置为

16、当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一状态设置为当前状态。重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。回溯策略的实现方法回溯策略的实现方法 回溯策略有多种实现的方法，其中递归法是一种最直接的实现方法。 下面定义一个递归过程BACKTRCK，实现回溯策略。其功能是：如果从当前状态DATA到目标状态有路径存在，则返回以规则序列表示的从DATA到目标状态的路径；如果从当前状态到目标状态没有路径存在，则返回FAIL。递归的思想从前有座山 从前有座山 从前有座山回溯搜索算法回溯搜索算法回溯搜索算法的符号

17、说明回溯搜索算法的符号说明 DATADATA:变量，表示当前状态； TERM( )TERM( ):谓词函数，当状态变量DATA满足结束条件时，TERM(DATA)取真。 DEADEND( )DEADEND( ):谓词函数，当状态变量DATA为非法状态时，DEADEND(DATA)取真. APPRULES( )APPRULES( ):函数，计算出适用于DATA的规则集，并依据某种原则(任意排列或按启发式准则)排列后赋给RULES(规则集序列表)。 FIRST(RULES)FIRST(RULES):函数，取出规则列表RULES中的第一条规则。 TAIL(RULES)TAIL(RULES):函数，删

18、去RULES中的第一条规则。 GEN(R,DATA)GEN(R,DATA):函数，调用规则R作用于当前状态DATA，生成一个新的状态RDATA。 CONS(R,PATH)CONS(R,PATH):函数，构造新表，把规则R加到当前解路径表的前头。 NILNIL:常量,表示空表；LOOPLOOP:常量,循环标号； FAILFAIL: :常量，回溯点标记；回溯搜索算法回溯搜索算法递归的思想（图）递归的思想（图）当前状态n目标状态gm1m2mkmir1r2rkri递归的思想递归的思想(续续) 递归过程BACKTRACK是将循环与递归结合在一起的。求从当前状态当前状态n到目标状态目标状态g的路径，一是要

19、探索n的i个子状态m1,m2,mi中，通过哪一个子状态可以到达目标状态目标状态g。这一点是通过循环实现的，每次从n的可应用规则中，选一个规则rk(k=1,2, ,i)作用于n，生成子状态mk，体现的是“横向”探索。二是“纵向”探索。为了探索n的某一个子状态mk是否可以到达目标状态目标状态g，算法通过递归来完成，即把mk又当成当前状态，探索mk的子状态到g是否有路径存在，如此进行下去。 Q Q Q Q 四皇后问题四皇后问题Q Q Q Q 不合法状态不合法状态合法状态合法状态 每个状态由1至4个元素的集合构成，每个元素可表示为一对数ij，1i，j4，表示在第i行第j列的一个棋子。例如上图的两个布局

20、可表示为(11 23 31 44)和(12 24 31 43)。问题的初始状态表示为( )，问题的目标状态应满足问题的要求。 规则集规则集:if 1i4 且Length(DATA)=i1 then APPEND(DATA(ij) (1j4)共有16条规则，每条规则Rij表示满足前提条件下，在ij处放一棋子。规则按先行后列从小到大排列。( )( )Q(1,1)( )QQ(1,1)(1,1) (2,3)( )Q(1,1)(1,1) (2,3)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3

21、.2)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )Q(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1)

22、 (2,4) (3.2)Q(1,2)Q(1,2) (2,4)Q(1,2) (2,4) (3,1)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)Q(1,2) (2,4) (3,1)Q(1,2) (2,4) (3,1) (4,3)存在问题及解决办法存在问题及解决办法当前状态 问题：问题：深度问题死循环问题存在的问题存在的问题 深度问题深度问题: : 某些问题的某个(或某些)分支具有无穷个状态，算法可能会落入某一个“深渊”，久远也回溯不回来，这样，就不可能找到问题的解。 死循环问题死循环问题: : 某些问题在某一个分

23、支上具有环路，搜索会在这个环路中一直进行下去，同样也回溯不出来，从而找不到问题的解。 在前面的回溯算法BACKTRACK中，设置了两个回溯点，一个是当遇到非法状态时回溯，一个是当试探了一个状态的所有子状态后，仍然找不到解时回溯。解决的办法解决的办法 为了解决这两个问题，下面将给出回溯算法BACKTRACK1将增加两个回溯点两个回溯点：一个一个是用一个常量BOUND来限制算法所能够搜索的最大深度，当当前状态的深度达到了限制深度时，算法将进行回溯，从而可以避免可以落入“深渊”；另一个另一个是将过程的参数用从初始状态到当前状态的表来替代原来的当前状态，当新的状态产生时，查看是否已经在该表中出现了。如

24、果出现过，则表明有环路存在，算法将进行回溯，从而解决了环路问题。回溯搜索算法回溯搜索算法1 1回溯搜索算法回溯搜索算法1 1回溯搜索算法回溯搜索算法1 1（续）（续）一些深入的问题一些深入的问题QQ一些深入问题（续） 回溯搜索中知识的利用 基本思想基本思想(以皇后问题为例): 充分利用问题的信息对RULES中的操作排序，可获得更高的效率。例如使用函数diag(i,j) ，其定义是通过位置ij的最长的对角线的长度。如果diag(i,j) 其中为大于0的常数A*算法的性质（续1）102证明：103A*算法的性质（续2）A*算法的性质（续3） 存在一个节点n，n在最佳路径上。f(n) = g(n)

25、+ h(n) = g*(n)+h(n) g*(n)+h*(n) = f*(n) = f*(s)A*算法的性质（续4）引理1.1: A*如果不结束，则OPEN中所有的n有f(n) f*(s)引理1.2: 在A*结束前，必存在节点n，使得f(n) f*(s)所以，如果A*不结束，将导致矛盾。A*算法的性质（续5） 由定理1.2，知A*一定结束，由A*的结束条件，OPEN表中f(t)最小时才结束。而f(t) f*(t) f*(s) 所以f(n)f*(s)的n，均被扩展。得证。A A* *算法的性质（续算法的性质（续6 6）可采纳性的证明可采纳性的证明A*算法的性质（续7）l由引理2.2知在A*结束前

26、，OPEN中存在节点n， f(n)f*(s)l设此时A*选择n扩展。l如果nn，则f(n)f*(s)，得证。l如果n n，由于A*选择n扩展，而不是n，所以有f(n) f(n)f*(s)。得证。A*算法的性质（续8）A*算法的性质（续9）定理1.4的证明定理1.4的证明（续1）对对h h的评价方法的评价方法*1*1)1(bbNd对h的评价举例A*的复杂性 一般来说，A*的算法复杂性是指数型的，可以证明，当且仅当以下条件成立时：abs(h(n)-h*(n) O(log(h*(n) A*的算法复杂性才是非指数型的，但是通常情况下， h与h*的差别至少是和离目标的距离成正比的。3，A*算法的改进 问

27、题的提出：因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。119出现多次扩展节点的原因出现多次扩展节点的原因s(10)A(1)B(5)C(8)G 目标631118 在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。解决的途径解决的途径 对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。 对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展。改进的条件改进的条件 可采纳性不变 不多扩展节点 不增加算法的复杂性对h加以限制h(ni)ninjh(nj)c(ni,nj)

28、定义：一个启发函数h，如果对所有节点ni和nj，其中nj是ni的子节点，满足h(ni) - h(nj) c(ni, nj)h(t) = 0或 h(ni) c(ni, nj) + h(nj) h(t) = 0则称h是单调的。h h单调的性质单调的性质 定理1.5： 若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。即：当A*选n扩展时，有g(n)=g*(n)。定理定理1.51.5的证明的证明 设n是A*扩展的任一节点。当ns时，定理显然成立。下面考察n s的情况。 设P(n0=s, n1, n2, , nk=n)是s到n的最佳路径 P中一定有节点在CLOSED中，设P

29、中最后一个出现在CLOSED中的节点为nj，则nj+1在OPEN中。定理定理1.51.5的证明（续的证明（续1 1） 由单调限制条件，对P中任意节点ni有： h(ni) C(ni, ni+1)+h(ni+1) g*(ni)+h(ni) g*(ni)+C(ni, ni+1)+h(ni+1) 由于ni 、ni+1在最佳路径上，所以： g*(ni+1) = g*(ni)+C(ni, ni+1) 带入上式有： g*(ni)+h(ni) g*(ni+1)+h(ni+1) 从i=j到i=k-1应用上不等式，有： g*(nj+1)+h(nj+1) g*(nk)+h(nk) 即：f(nj+1) g*(n)+h

30、(n) 注意：(nj在CLOSED中，nj+1在OPEN中)定理定理1.51.5的证明（续的证明（续2 2） 重写上式：f(nj+1) g*(n)+h(n) 另一方面，A*选n扩展，必有： f(n) = g(n)+h(n) f(nj+1) 比较两式，有： g(n) g*(n) 但已知g*(n)是最佳路径的耗散值，所以只有：g(n) = g*(n)。得证。h h单调的性质（续）单调的性质（续） 定理1.6： 若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。即f(ni) f(nj)。定理定理1.61.6的证明的证明= f(ni)-g(ni)= f(nj)-g(nj) f(ni)-g(

31、ni) - f(nj)+g(nj) C(ni, nj)= g(ni)+C(ni, nj) f(ni)-g(ni) - f(nj)+ g(ni)+C(ni, nj) C(ni, nj) f(ni) - f(nj) 0，得证。h h单调的例子单调的例子 8数码问题： h为“不在位”的将牌数 1h(ni) - h(nj) = 0(nj为ni的后继节点) -1 h(t) = 0c(ni, nj) = 1满足单调的条件对算法加以改进对算法加以改进 一些结论： OPEN表上任以具有f(n) f*(s)的节点定会被扩展。 A*选作扩展的任一节点，定有f(n)f*(s)。改进的出发点改进的出发点f f* *(

32、s)(s)f值小于f*(s)的节点f值大于等于f*(s)的节点 f fm m: : 到目前为止已扩展节点的最大f值，用f fm m代替f*(s)修正过程修正过程A A134前面的例子前面的例子h的单调化方法 如果令：f(n) = max(f(n的父节点),g(n)+h(n)则容易证明，这样处理后的h是单调的。IDA*算法(Iterative Deepening A*)基本思想：回溯与A*的结合算法简介（非严格地） 1，设初始值f0； 2，集合SNULL； 3，用回溯法求解问题，如果节点n的f值大于f0，则将该节点放入集合S中，并回溯； 4，如果在3中找到了解，则结束；5，如果3以失败结束，则f

33、0S中节点的最小f值； 6，返回到2。137A A* *算法应用举例算法应用举例 P40 P404 4 其他的搜索算法其他的搜索算法爬山法（图示）爬山法（图示）爬山法爬山法 在g(n)0的情况下，若限制只用评价函数f(n)=h(n)去排序新扩展出来的子节点，即局部排序，就可实现较为简单的搜索策略：爬山法。爬山法适用于能逐步求精的问题，对于单一及值问题十分有效，但对于具有多及值的问题就无能为力了。 爬山法是实现启发式搜索的最简单方法,不需设置OPEN表和CLOSE表，因为没有必要保存任何待扩展节点，仅从当前状态节点扩展出的子节点中将h(n)最小的子节点作为下一次考察的节点，其余的节点全部丢弃。1

34、41爬山法(hill-climbing)就是向值增加的方向持续移动登高过程 / 如果相邻状态中没有比它更高的值，则算法结束于顶峰爬山算法爬山算法 Hill-climbingHill-climbing1, n=s; /s为初始节点2, LOOP: IF GOAL(n) THEN EXIT(SUCCESS);3, EXPAND(n)mi, 计算h(mi), nextn:=m(min h(mi)的节点);4, IF h(n)h(nextn) THEN EXIT(FAIL);5, n:=nextn;6, GO LOOP;分支界限法（思想）分支界限法（思想） 分支界限法是优先扩展当前具有最小耗散值分支路

35、径的端节点n(没有子节点的节点)，其评价函数为f(n)=g(n)。该算法的基本思想很简单，实际上是建立一个局部路径（或分支）的队列表，每次都选择耗散值最小的那个分支上的端节点进行扩展，直到生成含有目标节点的路径为止。分支界限算法分支界限算法 Branch-Bound1, QUEUE:=(s-s),g(s)=0;2, LOOP: IF QUEUE=( ) THEN EXIT(FAIL);3, PATH:=FIRST(QUEUE), n:=LAST(PATH);4, IF GOAL(n) THEN EXIT(SUCCESS);5, EXPAND(n)mi, 计算g(mi)=g(n,mi), REM

36、OVE(s-n,QUEUE), ADD(s-mi,QUEUE);6, QUEUE中局部路径g值最小者排在前面；7, GO LOOP;分支界限法例子分支界限法例子sDAEBFtC432455434八城市交通图 例: 求解右图从城市s到城市t的最短路径。分支界限搜索树分支界限搜索树sADBAFE1g=0g=3425g=73D6g=8C11g=11E12g=12EBg=47g=9g=6g=13B10g=11F9g=10DBFACtg=15g=15g=13g=14g=16 g=15 g=148g=10最短路径问题求解最短路径问题求解QUEUE结果结果 初始(s(0) 1, (A(3) D(4) 2, (D(4) B(7) D(8) 3, (E(6) B(7) D(8) A(9) 4, (B(7) D(8) A(9) F(10) B(11) 5, (D(8) A(9) F(10) B(11) C(11) E(12) 6, (A(9) E(10) F(10) B(11) C(11) E(12) 7, (A(9) F(10) B(11) C(11) E(12)B(13) 8, (F(10) B(11) C(11) E(12) F(14) B(15) 9, (B(11) C(11) E(12) t(13)