第3章 图搜索及问题求解

1、LOGO主讲：李 辉Email：第第3 3章章图搜索与问题求解图搜索与问题求解第第3章章 图搜索与问题求解图搜索与问题求解3.5 3.5 博弈树搜索博弈树搜索3.1 3.1 状态图搜索状态图搜索3.2 3.2 状态图搜索问题求解状态图搜索问题求解3.3 3.3 与或图搜索与或图搜索3.4 3.4 与或图搜索问题求解与或图搜索问题求解主要内容主要内容3.1 状态图搜索状态图搜索-搜索与求解搜索与求解 搜索搜索是人工智能技术中进行问题求解的基本技术，不管是是人工智能技术中进行问题求解的基本技术，不管是符号智能符号智能还是还是计算智能计算智能，最终往往都归结为某种搜索，用，最终往往都归结为某种搜索，

2、用某种搜索算法去实现。某种搜索算法去实现。 图搜索模拟图搜索模拟的是人脑分析问题、解决问题的过程，是基于的是人脑分析问题、解决问题的过程，是基于领域知识的问题求解技术。领域知识的问题求解技术。计算智能计算智能是借鉴或模拟某些自是借鉴或模拟某些自然现象或生命现象而实现的搜索和问题求解技术。然现象或生命现象而实现的搜索和问题求解技术。图搜索技术是人工智能中的核心技术之一。图搜索技术是人工智能中的核心技术之一。 3.1.1 状态图状态图例例3.1走迷宫走迷宫走迷宫问题就是从该有向图的初始节点出发，走迷宫问题就是从该有向图的初始节点出发，寻找目寻找目标节点标节点的问题，或者是的问题，或者是寻找寻找通向

3、目标节点的通向目标节点的路径路径问题。问题。3.1.1 状态图状态图例例3.2八数码难题八数码难题(重排九宫问题重排九宫问题) 2 83147 6512384765初始棋局目标棋局以上两个问题抽象来看，都是某个有向图中寻找目标以上两个问题抽象来看，都是某个有向图中寻找目标或路径的问题，在人工智能技术中，把这种描述问题或路径的问题，在人工智能技术中，把这种描述问题的有向图称为的有向图称为状态空间图，状态空间图，简称简称状态图状态图。棋局作为节点，相邻节点通过移动数码一个一个产生棋局作为节点，相邻节点通过移动数码一个一个产生出来，所有节点由它们的相邻关系连成一个有向图。出来，所有节点由它们的相邻关

4、系连成一个有向图。3.1.2 状态图搜索状态图搜索n搜索搜索：从初始节点出发，沿着与之相连的边试探：从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程。地前进，寻找目标节点的过程。n搜索过程中经过的节点和边，按原图的连接关系，搜索过程中经过的节点和边，按原图的连接关系，便会构成一个树型的有向图，这种树型有向图称便会构成一个树型的有向图，这种树型有向图称为为搜索树搜索树。n搜索进行中，搜索树会不断增长，直到当搜索树搜索进行中，搜索树会不断增长，直到当搜索树中出现目标节点，搜索便停止。这时从搜索树中中出现目标节点，搜索便停止。这时从搜索树中就可很容易地找出从初始节点到目标节点的路径就可

5、很容易地找出从初始节点到目标节点的路径（解解）来。）来。3.1.2 状态图搜索状态图搜索1 1 搜索方式搜索方式n树式搜索树式搜索 在搜索过程中记录所经过的在搜索过程中记录所经过的所有节点和边所有节点和边。树式搜。树式搜索所记录的索所记录的轨迹轨迹始终是一棵始终是一棵树树，这棵树也就是搜索过，这棵树也就是搜索过程中所产生的搜索树。程中所产生的搜索树。n线式搜索线式搜索 在搜索过程中只记录那些在搜索过程中只记录那些当前当前认为在所找路径上的认为在所找路径上的节点和边节点和边。n不回溯线式搜索不回溯线式搜索n可回溯线式搜索可回溯线式搜索3.1.2 状态图搜索状态图搜索2 2 搜索策略搜索策略n盲目

6、搜索盲目搜索 无向导的搜索，树式盲目搜索就是穷举搜索，不无向导的搜索，树式盲目搜索就是穷举搜索，不回溯的线式搜索是随机碰撞式搜索，回溯的线式搜回溯的线式搜索是随机碰撞式搜索，回溯的线式搜索也是穷举式搜索。索也是穷举式搜索。n启发式搜索启发式搜索 是利用是利用“启发性信息启发性信息”引导的搜索策略。引导的搜索策略。“启发启发性信息性信息”就是与问题有关的有利于尽快找到问题解就是与问题有关的有利于尽快找到问题解的信息或知识。启发式搜索分为不同的策略，如全的信息或知识。启发式搜索分为不同的策略，如全局择优，局部择优，最佳图搜索。局择优，局部择优，最佳图搜索。n按按扩展顺序扩展顺序不同分为不同分为广度

7、优先广度优先和和深度优先深度优先。3.1.2 状态图搜索状态图搜索3 3 搜索算法搜索算法n搜索的目的是为了搜索的目的是为了寻找初始节点到目标节点的路径寻找初始节点到目标节点的路径，搜索过程中就得随时记录搜索轨迹。搜索过程中就得随时记录搜索轨迹。nClOSEDClOSED表表动态数据结构来动态数据结构来记录考察过的节点记录考察过的节点。nOPENOPEN表表的动态数据结构来专门的动态数据结构来专门登记当前待考查的节登记当前待考查的节点点。节点父节点编号编号节点父节点编号OPEN表CLOSED表3.1.2 状态图搜索状态图搜索n树式搜索算法树式搜索算法 步步1 1 把初始节点把初始节点S S0

8、0放入放入OPENOPEN表中。表中。 步步2 2 若若OPENOPEN表为空，则搜索失败，退出。表为空，则搜索失败，退出。 步步3 3 取取OPENOPEN表中表中第一个节点第一个节点N N放在放在CLOSEDCLOSED表中；表中；并冠以顺序编号并冠以顺序编号n n； 步步4 4 若目标节点若目标节点Sg=NSg=N，成功退出。，成功退出。 步步5 5 若若N N不可扩展，转步不可扩展，转步2 2。 步步6 6 扩展扩展N N，生成一组节点，对这组子节点作如，生成一组节点，对这组子节点作如下处理：下处理：3.1.2 状态图搜索状态图搜索（1 1）删除）删除N N的先辈节点的先辈节点（如果有

9、的话）。（如果有的话）。（2 2）对）对已存在于已存在于OPENOPEN表中的节点表中的节点（如果有的话）也删除（如果有的话）也删除之；删除之前要比较其返回初始节点的新路径与原路之；删除之前要比较其返回初始节点的新路径与原路径，如果新路径径，如果新路径“短短”，则修改这些节点在，则修改这些节点在OPENOPEN表中表中的原返回指针，使其沿新路径返回。的原返回指针，使其沿新路径返回。（3 3）对）对已存在于已存在于CLOSEDCLOSED表的节点表的节点，作与（，作与（2 2）同样的处）同样的处理，并且将其移出理，并且将其移出CLOSEDCLOSED表，放入表，放入OPENOPEN表中重新扩展表

10、中重新扩展。（4 4）对）对其余子节点其余子节点配上指向配上指向N N的返回指针后放入的返回指针后放入OPENOPEN表表中中某处某处，或对，或对OPENOPEN表进行表进行重新排序重新排序，转步，转步2 2。3.1.2 状态图搜索状态图搜索图 3-5 修改返回指针示例 n树式算法的几点说明树式算法的几点说明n返回指针返回指针指的是父节点在指的是父节点在CLOSEDCLOSED表中的编号。表中的编号。n步步6 6中中修改指针修改指针的原因是返回初始节点的路径有两的原因是返回初始节点的路径有两条，要选择条，要选择“短短”的那条路径。的那条路径。n这里这里路径长短路径长短以节点数来衡量，在后面将会

11、看到以以节点数来衡量，在后面将会看到以代价来衡量。按代价衡量修改返回指针的同时还要代价来衡量。按代价衡量修改返回指针的同时还要修改相应的代价值。修改相应的代价值。3.1.2 状态图搜索状态图搜索n树式搜索例树式搜索例n对于对于已存在于已存在于OPEN表中的节点表中的节点（如果有的话）也删除之；删（如果有的话）也删除之；删除之前要比较其返回初始节点的新路径与原路径，如果新路除之前要比较其返回初始节点的新路径与原路径，如果新路径短，则修改这些节点在径短，则修改这些节点在OPEN表中的原返回指针，使其沿原表中的原返回指针，使其沿原路径返回。路径返回。Path1Path2S0mnP先扩展后扩展P在n之

12、前已是某一节点m的后继如图所示：说明从如图所示：说明从S0P至至少有两条路，这时有两少有两条路，这时有两种情况：种情况：f（Path2） f（Path1），），当前路径较好，要修改当前路径较好，要修改P的指针，使其指向的指针，使其指向n，即，即搜索之后的最佳路径。搜索之后的最佳路径。否则，原路径好。否则，原路径好。3.1.2 状态图搜索状态图搜索n对对已存在于已存在于CLOSED表的节点表的节点，作与（，作与（2）同样的处理，并将）同样的处理，并将其移出其移出CLOSED表，放入表，放入OPEN表中重新扩展。表中重新扩展。S0过去生成P的路径现在生成P的路径过去对Ps的最优路径PsPmnka.

13、P在在n之前已是某一节点之前已是某一节点m的的后继，所以需要做如同（后继，所以需要做如同（2）同样的处理，如图右部所示。同样的处理，如图右部所示。b.P在在Closed表中，说明表中，说明P的后的后继也在继也在n之前已经生成，称为之前已经生成，称为Ps。对。对Ps而言同样可能而言同样可能 由于由于nP这一路径的加入，又必这一路径的加入，又必须比较多条路径之后而取代价须比较多条路径之后而取代价小的一条，如图左部所示。小的一条，如图左部所示。3.1.2 状态图搜索状态图搜索例：设当前搜索图和搜索树如图所示例：设当前搜索图和搜索树如图所示S0nPmPsPsS0nPmPsPsFF3.1.2 状态图搜索

14、状态图搜索n若启发函数若启发函数f(n)为从为从S0到节点到节点n的最短路径的长度，用的最短路径的长度，用边的数目来考察，当前扩展的节点是搜索图中的边的数目来考察，当前扩展的节点是搜索图中的n,P是是n的后继的后继S0nPmPsPsnPPsPsS0mFF3.1.2 状态图搜索状态图搜索n不回溯线式搜索算法不回溯线式搜索算法 步步1 把初始节点把初始节点S0放入放入CLOSED表中；表中； 步步2 令令N S0 ； 步步3 若若N是目标节点，则搜索成功，结束。是目标节点，则搜索成功，结束。 步步4 若若N不可扩展，则搜索失败，退出。不可扩展，则搜索失败，退出。 步步5 扩展扩展N，选取其一个未在

15、，选取其一个未在CLOSED表中出现过的表中出现过的 子节点子节点N1放入放入 CLOSED表中，令表中，令NN1，转步，转步3。3.1.2 状态图搜索状态图搜索n可回溯的线式搜索可回溯的线式搜索步步1 把初始节点把初始节点S0放入放入CLOSED表中；表中；步步2 令令N S0 ；步步3 若若N是目标节点，则搜索成功，结束。是目标节点，则搜索成功，结束。步步4 若若N不可扩展，则移出不可扩展，则移出CLOSED表中的末端节点表中的末端节点Ne ，若，若NeS0， 则搜索失败，退出。否则以则搜索失败，退出。否则以CLOSED表新的末端节点表新的末端节点Ne作为作为 N，即令，即令N Ne，转步

16、，转步4；步步5 扩展扩展N，选取其一个未在，选取其一个未在CLOSED表中出现过的子节点表中出现过的子节点N1放入放入 CLOSED表中，令表中，令N N1 ，转步，转步3。3.1.3 穷举式搜索穷举式搜索n广度优先搜索广度优先搜索n策略策略 始终在始终在同一级节点同一级节点中考查，当同一级节点考查完了之中考查，当同一级节点考查完了之后，才考查下一级节点。搜索树后，才考查下一级节点。搜索树自顶向下一层一层自顶向下一层一层逐渐逐渐生成。生成。n算法算法开始开始把S把S0 0送入OPEN表送入OPEN表OPEN表空OPEN表空？把OPEN表的第一个节把OPEN表的第一个节点（节点N）从表中移点（

17、节点N）从表中移出，放入CLOSED表中出，放入CLOSED表中节点N为目标节点？节点N为目标节点？节点N可扩展？节点N可扩展？扩展节点N，将其子节扩展节点N，将其子节点放入OPEN表点放入OPEN表尾部尾部，并为每个子节点配置并为每个子节点配置指向节点N的指针。指向节点N的指针。失败，退出失败，退出成功，退出成功，退出YNYNYNABCDEFGHIJKLMNOPQRSTU广度优先搜索广度优先搜索OPENCLOSEDOPENCLOSEDABCDEFGHIJKLMNOPQRSTUA广度优先搜索广度优先搜索22OPENCLOSEDABCDEFGHIJKLMNOPQRSTUAB C DA广度优先搜索

18、广度优先搜索23OPENCLOSEDABCDEFGHIJKLMNOPQRSTUAB C DABE F广度优先搜索广度优先搜索24OPENCLOSEDABCDEFGHIJKLMNOPQRSTUAB C DABE FCG H广度优先搜索广度优先搜索25OPENCLOSEDABCDEFGHIJKLMNOPQRSTUAB C DABE FCG HDI J广度优先搜索广度优先搜索26OPENCLOSEDABCDEFGHIJKLMNOPQRSTUAB C DABE FCG HDI JEK L广度优先搜索广度优先搜索3.1.3 穷举式搜索穷举式搜索n广度优先搜索的特点广度优先搜索的特点n广度优先中广度优先中

19、OPEN表表是一个是一个队列队列，CLOSED表表是一是一个个顺序表顺序表，表中各节点按顺序编号，正被考察的节，表中各节点按顺序编号，正被考察的节点在表中编号最大。点在表中编号最大。n广度优先策略是广度优先策略是完备完备的，即如果问题的解存在，则的，即如果问题的解存在，则它一定可以找到解，并且找到的解还是最优解。它一定可以找到解，并且找到的解还是最优解。n广度优先搜索策略与问题无关，具有通用性。广度优先搜索策略与问题无关，具有通用性。n缺点搜索缺点搜索效率低效率低。3.1.3 穷举式搜索穷举式搜索n八数码问题2 8 31 47 6 5初始状态8 1 32 47 6 5目标状态3.1.3 穷举式

20、搜索穷举式搜索2 8 31 47 6 51 2 3 1 8 47 6 592 31 8 47 6 582 81 4 37 6 5102 8 37 1 4 6 57 8 32 1 47 6 562 8 31 4 57 6112 8 3 1 47 6 522 31 8 47 6 532 8 31 47 6 542 8 31 6 4 7 5122 8 31 6 47 5138 32 1 47 6 5142 8 37 1 46 5152 3 41 87 6 5161 2 3 8 47 6 5172 81 4 37 6 5182 8 31 4 57 6192 8 3 6 41 7 5202 8 31 6

21、 7 5 4218 32 1 47 6 5222 8 31 6 47 558 1 32 47 6 523八数码广度优先搜索八数码广度优先搜索3.1.3 穷举式搜索穷举式搜索n深度优先搜索深度优先搜索n搜索策略搜索策略 在搜索树的每一层始终先扩展一个子节点，不断地向纵深前进，在搜索树的每一层始终先扩展一个子节点，不断地向纵深前进，直到不能再前进，才从当前节点返回到上一级节点，从另一方向直到不能再前进，才从当前节点返回到上一级节点，从另一方向继续前进。继续前进。n算法算法 开始开始把S把S0 0送入OPEN表送入OPEN表OPEN表空OPEN表空？把OPEN表的第一个节把OPEN表的第一个节点（节

22、点N）从表中移点（节点N）从表中移出，放入CLOSED表中出，放入CLOSED表中节点N为目标节点？节点N为目标节点？节点N可扩展？节点N可扩展？扩展节点N，将其子节扩展节点N，将其子节点放入OPEN表点放入OPEN表首部首部，并为每个子节点配置并为每个子节点配置指向节点N的指针。指向节点N的指针。失败，退出失败，退出成功，退出成功，退出YNYNYNABCDEFGHIJKLMNOPQRSTU深度优先搜索深度优先搜索OPENCLOSEDABCDEFGHIJKLMNOPQRSTUOPENCLOSEDA深度优先搜索深度优先搜索ABCDEFGHIJKLMNOPQRSTUOPENCLOSEDABCD深度

23、优先搜索深度优先搜索ABCDEFGHIJKLMNOPQRSTUOPENCLOSEDA DC BIJ深度优先搜索深度优先搜索ABCDEFGHIJKLMNOPQRSTUOPENCLOSEDA DC BIR深度优先搜索深度优先搜索J3.1.3 穷举式搜索穷举式搜索n深度优先搜索的特点深度优先搜索的特点nOPEN表为一个表为一个堆栈堆栈。n深度优先又称深度优先又称纵向搜索纵向搜索。n一般一般不能保证找到最优解不能保证找到最优解。n当深度限制不合理时，可能找不到解，可以将算法当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制，即有界深度优先搜索。改为可变深度限制，即有界深度优先搜索。3.1.3

24、 穷举式搜索穷举式搜索2 31 8 47 6 52 8 31 47 6 52 8 3 1 47 6 52 8 31 6 47 52 8 31 47 6 512 8 31 6 47 532 8 31 6 7 5 442 8 31 6 47 522 8 31 6 7 5 42 81 6 37 5 45八数码深度优先搜索3.1.4 启发式搜索启发式搜索 启发式搜索的目的启发式搜索的目的利用知识来引导搜索，达到利用知识来引导搜索，达到减少搜索范围减少搜索范围，降低问题复，降低问题复杂度。杂度。 启发性信息的强弱启发性信息的强弱 强：强：降低搜索的工作量，但可能导致找不到最优解。降低搜索的工作量，但可能

25、导致找不到最优解。 弱：弱：一般导致工作量加大，极限情况下变为盲目搜索，一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。但可能可以找到最优解。3.1.4 启发式搜索启发式搜索n启发函数启发函数n启发函数启发函数是用来估计搜索树节点是用来估计搜索树节点x与目标节点接近与目标节点接近程度的一种函数，通常记为程度的一种函数，通常记为h（x）。）。n定义启发函数的参考思路定义启发函数的参考思路n一个节点到目标节点的某种距离或差异的量度。一个节点到目标节点的某种距离或差异的量度。n一个节点处在最佳路径上的概率一个节点处在最佳路径上的概率n根据主观经验的主观打分等。根据主观经验的主观打分

26、等。n启发式搜索算法启发式搜索算法n启发式搜索要用启发函数来导航，其搜索算法就要启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。扩展顺序。3.1.4 启发式搜索启发式搜索n全局择优搜索全局择优搜索n全局择优搜索就是利用启发函数制导的一种启发式全局择优搜索就是利用启发函数制导的一种启发式搜索方法。该方法亦称为搜索方法。该方法亦称为最好优先搜索法最好优先搜索法。n基本思想：在基本思想：在OPEN表中表中保留所有已生成而

27、未考察保留所有已生成而未考察的节点，并用启发函数的节点，并用启发函数h(x)对它们对它们全部全部进行估价，进行估价，从中选出最优节点进行扩展，而不管这个节点出现从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。在搜索树的什么地方。3.1.4 启发式搜索启发式搜索n全局择优搜索算法全局择优搜索算法 步步1 把初始节点把初始节点S0放入放入OPEN表中，计算表中，计算h（ S0 ）；）； 步步2 若若OPEN表为空，则搜索失败，退出。表为空，则搜索失败，退出。 步步3 移出移出OPEN表中第一个节点表中第一个节点N放入放入CLOSED表中，表中， 并冠以序号并冠以序号n； 步步4 若

28、目标节点若目标节点Sg N，则搜索成功结束。，则搜索成功结束。 步步5 若若N不可扩展，则转步不可扩展，则转步2。 步步6 扩展扩展N，计算每个子节点，计算每个子节点x的函数值的函数值h（x），并将），并将所有子节点配以指向所有子节点配以指向N的返回指针后放入的返回指针后放入OPEN表中，表中，再对再对OPEN表中所有子节点表中所有子节点按其函数值的大小以升序按其函数值的大小以升序排列，转步排列，转步2。A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2 P-3QRST全局择优算法全局择优算法OPENCLOSEDA-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2

29、 P-3QRSTOPENCLOSEDA-5全局择优算法全局择优算法A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2 P-3QRSTOPENCLOSEDB-4A-5C-4 D-6全局择优算法全局择优算法A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2 P-3QRSTOPENCLOSEDB-4A-5C-4 E-5 F-5 D-5全局择优算法全局择优算法A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2 P-3QRSTOPENCLOSEDB-4A-5C-4D-6E-5 F-5H-3 G-4全局择优算法全局择优算法A-5B-4C-4D-6E-5F-5

30、G-4IJKLMNO-2 P-3QRSTOPENCLOSEDB-4A-5C-4D-6E-5 F-5O-2G-4H-3H-3P-3全局择优算法全局择优算法A-5B-4C-4D-6E-5F-5G-4IJKLMNO-2 P-3QRSTOPENCLOSEDB-4A-5C-4D-6E-5 F-5O-2G-4H-3H-3P-3全局择优算法全局择优算法3.1.4 启发式搜索启发式搜索-全局择优搜索算法全局择优搜索算法启发函数启发函数h(x)为节点为节点x与目标格局相比与目标格局相比数码不同的位置个数。数码不同的位置个数。从图看出解为：从图看出解为： S0 ，S1 ，S2 ，S3， Sg。3.1.4 启发式搜

31、索启发式搜索-局部择优搜索算法局部择优搜索算法 基本思想是当每一个节点被扩展后，按基本思想是当每一个节点被扩展后，按h(x)对每一个子节对每一个子节点计算启发值，并选择最小者作为下一个要考察的节点，点计算启发值，并选择最小者作为下一个要考察的节点，由于每次都只是在由于每次都只是在子节点的范围内子节点的范围内选择下一个要考察的节选择下一个要考察的节点，范围比较狭窄，所以称为点，范围比较狭窄，所以称为局部择优局部择优搜索。搜索。步步6 扩展扩展N，计算，计算N每个子节点每个子节点x的函数值的函数值h（x），并将并将N的子节点按估计值升序排列的子节点按估计值升序排列放入放入OPEN表的首部，为每表的

32、首部，为每个子节点配置指向节点个子节点配置指向节点N的指针，转步的指针，转步2。3.1.5 加权状态图搜索加权状态图搜索例例3.6 3.6 交通图交通图A A城是出发地，城是出发地，E E是目的地，数字表示两城是目的地，数字表示两城之间交通费用。求之间交通费用。求A A到到E E的最小费用的旅行路线。的最小费用的旅行路线。ADCEB464332边上附有数值的状态图称为边上附有数值的状态图称为加权状态图加权状态图或或赋权状态图赋权状态图，这种数值称为这种数值称为权值权值。3.1.5 加权状态图搜索加权状态图搜索n加权状态图的搜索加权状态图的搜索加权状态图的搜索与权值有关，并且要用权值来导航。具体

33、加权状态图的搜索与权值有关，并且要用权值来导航。具体来讲，加权状态图的搜索算法，要在一般状态图搜索算法基来讲，加权状态图的搜索算法，要在一般状态图搜索算法基础上再础上再增加权值的计算与传播过程增加权值的计算与传播过程，并且要由权值来确定节，并且要由权值来确定节点的扩展顺序。点的扩展顺序。n代价的计算代价的计算 g（x）表示从初始节点）表示从初始节点S0到节点到节点x的代价。的代价。 c（xi，xj）表示父节点）表示父节点xi到子节点到子节点xj的代价的代价 g（ xj ）g（ xi ） c（xi，xj） g（ x0 ）03.1.5 加权状态图搜索加权状态图搜索n加权状态图转换为代价树搜索加权状

34、态图转换为代价树搜索n从初始节点出发，先把每一个与初始节点相邻的从初始节点出发，先把每一个与初始节点相邻的节点作为该节点的子节点。节点作为该节点的子节点。n然后对其他节点依次类推，但对其他节点然后对其他节点依次类推，但对其他节点x，不，不能将其父节点及祖先再作为能将其父节点及祖先再作为x的子节点。的子节点。ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B33.1.5 加权状态图搜索加权状态图搜索n分支界限法分支界限法n其基本思想是：每次从其基本思想是：每次从OPEN表中选出表中选出g(x)值最小值最小的节点进行考察，而不管这个节点在搜索树的什么

35、的节点进行考察，而不管这个节点在搜索树的什么位置上。位置上。n与全局择优法的区别与全局择优法的区别选取扩展节点标准选取扩展节点标准计算方法计算方法分支界限分支界限法法代价值代价值g（x）g（x）与节点所处的位置有）与节点所处的位置有关，与边也有关系，从初始节关，与边也有关系，从初始节点点S0计算而来。计算而来。全局择优全局择优法法启发函数值启发函数值h（x） h（x）与节点有关，与边可）与节点有关，与边可能有关或无关，从目标节点方能有关或无关，从目标节点方向计算而来。向计算而来。3.1.5 加权状态图搜索加权状态图搜索n最近择优法最近择优法（瞎子爬山法）（瞎子爬山法）n基本思想：每次仅考察基本

36、思想：每次仅考察N的子节点的的子节点的g（x），选取），选取N的子节点中代价最小的子节点进行扩展。的子节点中代价最小的子节点进行扩展。n最近择优法与局部择优法的区别：最近择优法与局部择优法的区别：选取扩展节点标选取扩展节点标准准计算方法计算方法最近择优法最近择优法代价值代价值g（x）g（x）与节点所处的位置有关，）与节点所处的位置有关，与边也有关系，从初始节点与边也有关系，从初始节点S0计算而来。计算而来。局部择优法局部择优法启发函数启发函数h（x）h（x）与节点有关，与边可能）与节点有关，与边可能有关或无关，从目标节点方向有关或无关，从目标节点方向计算而来。计算而来。内容回顾：树式搜索策略比

37、较内容回顾：树式搜索策略比较全局全局局部局部深度深度d(x)d(x)宽度优先搜索宽度优先搜索 深度优先搜索深度优先搜索启发值启发值h(x)h(x)全局择优搜索全局择优搜索 局部择优搜索局部择优搜索代价值代价值g(x)g(x)分支界限法分支界限法瞎子爬山法瞎子爬山法范围范围标准标准S S0 0S Sg g2 23 3a ab b4 46 61 15 5c cd dg gf fh hi ij jk k5 5f f5 54 43 37 78 89 9h（x），有利于搜索纵向发展，有利于搜索纵向发展，提高搜索效率，但影响完备性。提高搜索效率，但影响完备性。g（x），有利于搜索横向发展，有利于搜索横向发

38、展，提高完备性，但影响搜索效率。提高完备性，但影响搜索效率。穷举式搜索穷举式搜索启发式搜索启发式搜索加权状态图搜索加权状态图搜索3.1.6 A算法算法估价函数估价函数 将启发函数与代价函数相结合，为了防止在单独利将启发函数与代价函数相结合，为了防止在单独利用启发函数的时候误入歧途。用启发函数的时候误入歧途。 f（x） g（x）h（x）f f（x x）是初始节点是初始节点S S0 0到达节点到达节点x x处已付出的处已付出的代价与代价与节点节点x x到达目标节点到达目标节点S Sg g的的接近程度估计值总和接近程度估计值总和。是是g g（x x）与）与h h（x x）的折中）的折中。3.2 状态

39、图搜索问题求解状态图搜索问题求解3.2.1 问题的状态图表示问题的状态图表示 1. 状态状态状态就是问题在任一确定时刻的状况状态就是问题在任一确定时刻的状况,它表征了问题特征它表征了问题特征和结构等。状态在状态图中表示为和结构等。状态在状态图中表示为节点节点。状态一般用一组数。状态一般用一组数据表示。在程序中用字符、数字、记录、数组、结构、对象据表示。在程序中用字符、数字、记录、数组、结构、对象等表示。等表示。 2. 状态转换规则（操作状态转换规则（操作 operator）n引起状态中某些分量发生改变，从而使一个具体状态引起状态中某些分量发生改变，从而使一个具体状态变化到另一个具体状态的作用。

40、变化到另一个具体状态的作用。n描述了状态之间的关系。描述了状态之间的关系。n状态转换规则在状态图中表示为状态转换规则在状态图中表示为边边。在程序中状态转。在程序中状态转换规则可用数据对、条件语句、规则、函数、过程等换规则可用数据对、条件语句、规则、函数、过程等表示。表示。 3.2.1 问题的状态图表示问题的状态图表示n状态空间（状态空间（State Space）n问题的状态空间是一个表示该问题全部的可能状态问题的状态空间是一个表示该问题全部的可能状态及相互关系的图。及相互关系的图。n状态空间一般用赋值有向图表示，记为：状态空间一般用赋值有向图表示，记为： （S，F，G）nS：问题的可能有的初始

41、状态的集合；：问题的可能有的初始状态的集合；nF：操作的集合；：操作的集合；nG：目标状态的集合。：目标状态的集合。3.2.1 问题的状态图表示问题的状态图表示例例 3.7 迷宫问题的状态图表示。迷宫问题的状态图表示。 S：SoF：(So, S4), (S4, So), (S4, S1), (S1, S4), (S1,S2), (S2, S1), (S2, S3), (S3, S2), (S4, S7), (S7, S4), (S4, S5), (S5, S4), (S5, S6), (S6, S5), (S5, S8), (S8, S5), (S8, S9), (S9, S8), (S9,

42、Sg)G：Sg 迷宫问题规则集描述了图中所有节点和边。类似于迷宫问题规则集描述了图中所有节点和边。类似于这样罗列出全部节点和边的状态图称为这样罗列出全部节点和边的状态图称为显式状态图显式状态图，或者说或者说状态图状态图的的显式显式表示。表示。3.2.1 问题的状态图表示问题的状态图表示补充例补充例1 三枚钱币，能否从下面状态翻动三次后三枚钱币，能否从下面状态翻动三次后出现全正或全反状态。出现全正或全反状态。反正反正正正反反反初始状态s目标状态集合0, 73.2.1 问题的状态图表示问题的状态图表示引入一个三元组引入一个三元组(q0,q1,q2)来描述总状态，钱币正面为来描述总状态，钱币正面为0

43、，反面，反面为为1，全部可能的状态为：，全部可能的状态为： Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0) Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,1)。翻动钱币的操作抽象为改变上述状态的算子，翻动钱币的操作抽象为改变上述状态的算子， 即即Fa, b, c a:把钱币把钱币q0翻转一次翻转一次 b:把钱币把钱币q1翻转一次翻转一次 c:把钱币把钱币q2翻转一次翻转一次 问题的状态空间为问题的状态空间为3.2.1 问题的状态图表示问题的状态图表示状态空间图（0，0，0）（1，0，1）（0，0，1）（

44、0，1，0）（1，1，0）（1，0，0）（0，1，1）（1，1，1）acabacabcbbc3.2.1 问题的状态图表示问题的状态图表示 例例3.9 二阶梵塔问题二阶梵塔问题 一号杆有一号杆有A、B两个金盘，两个金盘，A小于小于B。要求将。要求将AB移至三号杆，每次只可移动一个盘子，任移至三号杆，每次只可移动一个盘子，任何时刻何时刻B不能在不能在A上。上。 用二元组（用二元组（SA，SB）表示状态，）表示状态，SA表示表示A所在杆号，所在杆号，SB表示表示B所在杆号，全部状态如下：所在杆号，全部状态如下： （1，1），（），（1，2），（），（1，3） （2，1），（），（2，2），（），（2

45、，3） （3，1），（），（3，2），（），（3，3）3.2.1 问题的状态图表示问题的状态图表示AB123S0：（：（1，1）123S1：（：（1，2）123S2：（：（1，3）AA123S5：（：（2，3）123S4：（：（2，2）123S3：（：（2，1）123S8：（：（3，3）123S7：（：（3，2）123S6：（：（3，1）AAAAABABBBBB3.2.1 问题的状态图表示问题的状态图表示转换规则：转换规则：A（i，j）表示金盘）表示金盘A从第从第i号杆移到号杆移到j号杆号杆 B（i，j）表示金盘）表示金盘B从第从第i号杆移到号杆移到j号杆号杆 A（1，2），），A（1，3），

46、）， 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）初始状态初始状态（1，1），目标状态，目标状态（3，3）梵塔问题用状态图表示为梵塔问题用状态图表示为： 3.2.1 问题的状态图表示问题的状态图表示1,12,13,12,33,31,33,21,22,2A(1,2)A(1,2)B(3,2)A(3,1)B(1,3)A(2,3)3.2.1 问题的状态图表示问题的状态图表示例例3.8重排九宫问题（八数码难题）重排九宫问题（八数码难题）X1X2X3X8X0X4X7X6X5将棋局用向

47、量将棋局用向量A(X0，X1 ， X2 ， X3 ， X4 ， X5 ， X6 ， X7 ， X8)表示，其中表示，其中Xi为变量，值表示方格为变量，值表示方格Xi内的数字。内的数字。 初始状态初始状态 S0 （0，2，8，3，4，5，6，7，1） 目标状态目标状态 Sg （0，1，2，3，4，5，6，7，8）数码的移动规则就是该问题的状态变化规则。经分析，该问题共有数码的移动规则就是该问题的状态变化规则。经分析，该问题共有24条规则，分为条规则，分为9组。组。2 83147 6512384765初始棋局初始棋局目标棋局目标棋局3.2.1 问题的状态图表示问题的状态图表示0组规则组规则 r1(

48、X0=0 ) (X2=n ) X0 = n X2 =0； r2(X0=0 ) (X4=n ) X0 = n X4 =0； r3(X0=0 ) (X6=n ) X0 = n X6 =0； r4(X0=0 ) (X8=n ) X0 = n X8 =0；1组规则组规则 r5(X1=0 ) (X2=n ) X1 = n X2 =0； r6(X1=0 ) (X8=n ) X1 = n X8 =0；8组规则组规则: r22(X8=0 ) (X1=n ) X8 = n X1 =0； r23(X8=0 ) (X0=n ) X8 = n X0=0； r24(X8=0 ) (X7=n ) X8 = n X7 =0

49、；X1X2X3X8X0X4X7X6X5X1X2X3X8X0X4X7X6X5X1X2X3X8X0X4X7X6X53.2.1 问题的状态图表示问题的状态图表示八数码的状态图可表示为八数码的状态图可表示为 （S0, r1 , r2 , , r24 , Sg）八数码问题状态图仅给出了初始节点和目标八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规则来产生。节点，其余节点需用状态转换规则来产生。类似于这样表示的状态图称为类似于这样表示的状态图称为隐式状态图隐式状态图，或者说或者说状态图状态图的的隐式表示隐式表示。3.3 与或图搜索与或图搜索例例3.15 证明四边形全等。证明四边形全等。分

50、析：连接分析：连接BD， B D ，原来问题可以分解为两个子问题：，原来问题可以分解为两个子问题： Q1：证明：证明ABC ABC Q2：证明：证明BCD BCD原来问题可以原来问题可以分为两个子问题解决。分为两个子问题解决。ABDCA B D C 3.3.1 与或图与或图问题问题Q1还可以再被分解为：还可以再被分解为： Q11 ：证明：证明AB AB Q12 ：证明：证明AD AD Q13 ：证明：证明A A或或 Q11 ：证明：证明ABAB Q12 ：证明：证明ADAD Q13 ：证明：证明BDBD 问题问题Q2还可以再被分解为：还可以再被分解为： Q21 ：证明：证明BC BC Q22

51、：证明：证明CD CD Q23 ：证明：证明 C C 或或 Q21 ：证明：证明BC B C Q22 ：证明：证明CDC D Q23 ：证明：证明BD BD 3.3.1 与或图与或图将原问题用图的形式表示如下：将原问题用图的形式表示如下：QQ1Q2Q11Q12Q13Q11 Q12 Q13 Q21Q22Q23Q21 Q22 Q23 弧线表示所连边为弧线表示所连边为“与与”的关系的关系不带弧线的边不带弧线的边为或关系为或关系问题的解问题的解3.3.1 与或图与或图n与或图的几个概念与或图的几个概念n直接可解的问题称为直接可解的问题称为本原问题本原问题。n本原问题对应的节点称为本原问题对应的节点称为

52、终止节点终止节点。n无子节点的节点称为无子节点的节点称为端节点端节点。n子节点为与关系，则该节点为子节点为与关系，则该节点为与节点与节点。n子节点为或关系，则该节点为子节点为或关系，则该节点为或节点或节点。3.3.2 与或图搜索与或图搜索1. 1. 搜索方式搜索方式, ,解图解图( (树树) )与或图搜索也分为树式和“线”式两种类型。 与或图搜索解图(树),不只是寻找目标节点,而是边扩展节点边进行逻辑判断, 以确定初始节点是否可解。一旦能够确定初始节点的可解性,则搜索停止。根据返回指针便可从搜索树中得到一个解图(树)。解图(树)实际上是由可解节点形成的一个子图(树), 这个子图(树)的根为初始

53、节点, 叶为终止节点, 且这个子图(树)还一定是与图(树)。 3.3.2 与或图搜索与或图搜索2. 2. 可解性判别可解性判别怎样判断一个节点的可解性呢？ 下面给出判别准则。 (1) 一个节点是可解, 则节点须满足下列条件之一: 终止节点是可解节点。 一个与节点可解, 当且仅当其子节点全都可解。 一个或节点可解, 只要其子节点至少有一个可解。 (2) 一个节点是不可解, 则节点须满足下列条件之一: 非终止节点的端节点是不可解节点。 一个与节点不可解, 只要其子节点至少有一个不可解。 一个或节点不可解, 当且仅当其子节点全都不可解。 3.3.2 与或图搜索与或图搜索4. 4. 搜索算法搜索算法与

54、或树的树式搜索过程可概括为以下步骤： 步1 把初始节点Qo放入OPEN表。 步2 移出OPEN表的第一个节点N放入CLOSED表, 并冠以序号n。 步3 若节点N可扩展, 则做下列工作： (1) 扩展N, 将其子节点配上指向父节点的指针后放入OPEN表。(2)考察这些子节点中是否有终止节点。 若有, 则标记它们为可解 节点, 并将它们也放入CLOSED表, 然后由它们的可解反向推断其先辈节点的可解性, 并对其中的可解节点进行标记。 如果初始节点也被标记为可解节点, 则搜索成功,结束。(3)删去OPEN表中那些具有可解先辈的节点(因为其先辈节点已经可解, 故已无再考察该节点的必要), 转步2。

55、3.3.2 与或图搜索与或图搜索步4 若N不可扩展, 则做下列工作： (1)标记N为不可解节点, 然后由它的不可解反向推断其先辈节点的可解性, 并对其中的不可解节点进行标记。如果初始节点So也被标记为不可解节点, 则搜索失败, 退出。(2)删去OPEN表中那些具有不可解先辈的节点(因为其先辈节点已不可解,故已无再考察这些节点的必要), 转步2。 3.3.2 与或图搜索与或图搜索例例 3.16设有与或树如图3-15所示, 其中1号节点为初始节点,t1、t2、t3、t4均为终止节点, A和B是不可解的端节点。采用广度(优先)搜索策略, 搜索过程如下： (1) 扩展1号节点, 得2号和3号节点, 依

56、次放入OPEN表尾部。由于这两个节点都非终止节点, 所以接着扩展2号节点。此时OPEN表中只有3号节点。 (2) 2号节点扩展后,得4号节点和t1节点。此时OPEN表中依次有3号、4号和t1节点。由于t1是终止节点,故标记它为可解节点, 并将它放入CLOSED表, 再判断其先辈节点的可解性,但t1的父节点2是一个与节点, 故仅由t1的可解还不能确定2号节点可解。所以, 就继续搜索。 3.3.2 与或图搜索与或图搜索 (3) 扩展3号节点,得5号节点和B节点。两者均非终止节点, 所以继续扩展4号节点。 (4) 4号节点扩展后得节点A和t2。t2是终止节点,标记为可解节点, 放入CLOSED表。这

57、时其先辈节点4和2也为可解节点, 但1号节点还不能确定。这时从OPEN表中删去节点A,因为其父节点4已经可解。 () 扩展5号节点得t3和t4。由于t3和t4都为终止节点(放入CLOSED表), 故可推得节点5、3、1均为可解节点。 搜索成功, 结束。 这时,由CLOSED表便得到由节点1、2、3、4、5和t1、t2、 t3、t4构成的解树，如图3-15 中的粗线所示。 3.3.3 启发式与或树搜索启发式与或树搜索3.3.3 3.3.3 启发式与或树搜索启发式与或树搜索广度优先搜索及深度优先搜索都是盲目搜索, 其共同点是： (1) 搜索从初始节点开始,先自上而下地进行搜索,寻找终止节点及端节点

58、, 然后再自下而上地进行可解性标记,一旦初始节点被标记为可解节点或不可解节点, 搜索就不再继续进行。 (2) 搜索都是按确定路线进行的,当要选择一个节点进行扩展时,只是根据节点在与或树中所处的位置,而没有考虑要付出的代价,因而求得的解树不一定是代价最小的解树, 即不一定是最优解树 。 为了求得最优解树，要在每次扩展节点时计算扩展该节点要付出的代价，并选择代价最小的节点进行扩展。像这样根据代价决定搜索路线的方法称为与或树的有序搜索，是一种重要的启发式搜索策略。3.3.3 启发式与或树搜索启发式与或树搜索1. 解树的代价解树的代价解树的代价就是树根的代价。树根的代价是从树叶开始自下而上逐层计算而求

59、得的。而解树的根对应的是初始节点Qo。 这就是说,在与或树的搜索过程中,代价的计算方向与搜索树的生长方向相反。这一点是与状态图不同的。具体来讲,有下面的计算方法：设g(x)表示节点x的代价,c(x,y)表示节点x到其子节点y的代价(即边xy的代价), 则 (1) 若x是终止节点, g(x)0。 3.3.3 启发式与或树搜索启发式与或树搜索(2) 若x是或节点, 。其中y1, y2, , yn是x的子节点。 (3) 若x是与节点x, 则有两种计算公式。 和代价法： 。 最大代价法： 。其中y1, y2, , yn是x的子节点。 (4) 对非终止的端节点x, g(x)。 )(),(min)(1ii

60、niygyxcxg)(),()(1iiniygyxcxg)(),(max)(1iiniygyxcxg例例3.17 如图3-16所示的与或树, 其中包括两棵解树, 一棵解树由Qo,A,t1和t2组成；另一棵解树由Qo,B,D,G,t4和t5组成。 在此与或树中,t1,t2,t3,t4,t5为终止节点；E,F是非终止的端节点, 其代价均为；边上的数字是该边的代价。 由右边的解树可得： 按和代价： g(A)=11,g(Qo)=13 按最大代价：g(A)=6, g(Qo)=8由左边的解树可得： 按和代价： g(G)=3, g(D)=4, g(B)=6, g(Qo)=8 按最大代价： g(G)=2, g