人工智能及专家系统第3章-图搜索技术课件.ppt

1、第第3章章 图搜索技术图搜索技术 31 图搜索及其分类 311 图搜索的概念 312 图搜索的分类 313 状态图搜索树 314 状态空间搜索算法 315 搜索效率 32 穷举式搜索 321 广度优先搜索 322 深度优先搜索 323 有界深度优先搜索 324 代价驱动搜索 第第3章章 图搜索技术图搜索技术 33 启发式搜索 331 启发式搜索的基本概念 332 局部择优搜索 333 全局择优搜索 334 与/或图的启发式搜索 335 博弈树的启发式搜索 336-剪枝技术 第第3章章 图搜索技术图搜索技术 3.1.1 图搜索的概念图搜索的概念 图是节点及连接它们的弧的集合。搜索具有寻找、搜查、

2、扫描、检索的意义。它是在图中寻找目标或路径的基本方法；也就是说，利用已有知识逐步摸索求解,根据问题的实际情况，不断寻找可利用知识，使问题得以解决的过程称为搜索。搜索的目的是以尽可能低的耗费求得所需要的解。图搜索，就是从初始节点出发，沿着与之相连的弧试探地前进，寻找目标节点的过程(也可以反向进行)。树式搜索和线式搜索 树式搜索就是以“画树”的方式进行搜索。即从树根(初始节点)出发，一笔一笔地描出一棵树来。线式搜索就是以“画线”的方式进行搜索。线式搜索所记录的轨迹始终是一条线或折线。一般情况下，树式搜索成功后，还需再从搜索树中找出所求路径，而线式搜索只要搜索成功，则“搜索线”就是所找的路径，即问题

3、的解。312 图搜索的分类图搜索的分类 1 从求解要求看，可分为三种情况：从求解要求看，可分为三种情况：最佳值搜索。在这种情况下，值附在图的各终节点，搜索的目的就是去找出具有最佳值的终节点，例如博弈问题的搜索就是属于这一类问题。最短路径搜索。搜索的目的是找出从初始节点到目标节点的最短路径。例如，巡回售货员问题。满足性搜索。有些问题可能有多个解，有些问题只有一个解，采用满足性搜索，即只要找到一个解即可。例如，定理证明和大多数问题求解。2.按搜索方向分，有三种情况：正向搜索：是从初始状态向目标状态的方向搜索，有时也称为数据驱动搜索。搜索的过程即应用规则从给定条件产生新条件，再用规则从新条件产生更多

4、的新条件。反向搜索：是从目标状态向初始状态的方向搜索，即目标驱动搜索。方法是先从目标入手，看哪些规则或合法移动能产生该目标以及应用这些规则产生目标时需要哪些条件。搜索就通过反向的、连续的子目标不断地进行，一直到找到问题给定的条件为止。双向搜索：同时从目标状态和初始状态出发进行搜索。正向搜索可用于下列情况:l l 问题的初始说明给出了全部或大部分数据问题的初始说明给出了全部或大部分数据的系统。解释程序常常如此，它提供一批的系统。解释程序常常如此，它提供一批采集的数据，要求系统对此作出进一步的采集的数据，要求系统对此作出进一步的解释。解释。l l 存在大量可能的目标，但对实际问题的条存在大量可能的

5、目标，但对实际问题的条件及给定的信息加以运用的方法很少的系件及给定的信息加以运用的方法很少的系统。统。l l 难以形成一个目标或假设的系统。难以形成一个目标或假设的系统。对下列情况建议采用反向搜索:l l问题的说明中给出了目标或假设，或者很容问题的说明中给出了目标或假设，或者很容易用公式来表示它们的系统。易用公式来表示它们的系统。l l有大量的规则适用于问题的条件的系统。在有大量的规则适用于问题的条件的系统。在这种情况下，可以推出许多结论和结果，较这种情况下，可以推出许多结论和结果，较早地选好目标可剪掉空间中许多分枝，使反早地选好目标可剪掉空间中许多分枝，使反向搜索的效率更高。向搜索的效率更高

6、。l l问题没有给出数据，必须在求解中获取的系问题没有给出数据，必须在求解中获取的系统。这种情况下，反向搜索可以帮助指导数统。这种情况下，反向搜索可以帮助指导数据的获取。据的获取。l l分析特定数据的系统。分析特定数据的系统。3按照搜索的内容分 穷举式搜索穷举式搜索 图搜索图搜索广度优先搜索广度优先搜索深度优先搜索深度优先搜索有界深度优先搜索有界深度优先搜索一致代价搜索一致代价搜索 启发式搜索启发式搜索局部择优搜索局部择优搜索全局择优搜索全局择优搜索与与/或图启发式搜索或图启发式搜索极大极小搜索极大极小搜索、剪枝搜索剪枝搜索 313 状态图搜索树状态图搜索树 图图3-1 状态图搜索树状态图搜索

7、树 L M E F G H I J K B C D A 树根树根树枝树枝叶节点叶节点I、J、K是是D的子节点的子节点D是是I、J、K的父节点的父节点A是是I、J、K的先辈节点的先辈节点中间节点中间节点一层一层二层二层三层三层例、巡回推销员问题。B A D C 4 7 10 6 10 5图图3-2 4城市路线城市路线图图3-3 巡回推销员问题状态图搜索树巡回推销员问题状态图搜索树 A 4 6 10AB AC AD 7 10 7 5 10 5ABC ABD ACB ACD ADB ADC 5 5 10 10 7 7ABCD ABDC ACBD ACDB ADBC ADCB 10 6 10 4 6

8、4ABCDA ABDCAACBDAACDBA ADBCA ADCBA 26 25 33 25 33 26路径长度路径长度314 状态空间搜索算法状态空间搜索算法 解决问题时，有以下的因素需要考虑解决问题时，有以下的因素需要考虑:1计算机无法保存其全部状态空间；计算机无法保存其全部状态空间；2与解有关的状态空间一般仅是全部状态空间的一与解有关的状态空间一般仅是全部状态空间的一部分。部分。3是否一定能找到一个解？是否一定能找到一个解？4是否能终止运行，或是否会陷入一个死循环？是否能终止运行，或是否会陷入一个死循环？5是否找到的是最好解？是否找到的是最好解？6搜索过程的时间与空间复杂性如何？搜索过程

9、的时间与空间复杂性如何？7怎样才能最有效地降低搜索的复杂性？怎样才能最有效地降低搜索的复杂性？8 怎样设计才能最有效地利用描述语言怎样设计才能最有效地利用描述语言?Open表和Closed表 Closed表表编号节点父节点编号编号节点父节点编号12345 Open表表节点节点 父节点父节点 编号编号315 搜索效率搜索效率 搜索效率搜索效率P定义为：定义为：P=L/T L从初始状态到目标状态的路长从初始状态到目标状态的路长 T节点的总数节点的总数(不包括初始节点不包括初始节点)另一种度量方法称有效的分枝因素另一种度量方法称有效的分枝因素B。它代表它代表在搜索过程中每个有效节点平均生成子节点在搜

10、索过程中每个有效节点平均生成子节点数目。设数目。设L是节点的深度是节点的深度(或路长或路长)，则，则 T=B+B+B+B=(BBB)/(1 B)从而可得从而可得P=L/T=L(1 B)/(B BB)32 穷举式搜索穷举式搜索 特点特点搜索效率低，控制策略差，占用较搜索效率低，控制策略差，占用较大的存储空间；但它控制性知识简单，是启大的存储空间；但它控制性知识简单，是启发式搜索的基础。为了简化问题的讨论，对发式搜索的基础。为了简化问题的讨论，对下面几种穷举式搜索方法作如下假设：下面几种穷举式搜索方法作如下假设：1搜索空间是一棵树，即只有一个初始节搜索空间是一棵树，即只有一个初始节点，任意两个节点

11、之间的路径是唯一的。点，任意两个节点之间的路径是唯一的。2.任何一个节点扩展时，其后继节点包含任何一个节点扩展时，其后继节点包含有返回父节点的指针。当目标节点产生时，有返回父节点的指针。当目标节点产生时，利用此特征很易求得解答。利用此特征很易求得解答。321 广度优先搜索广度优先搜索 概念与特点概念与特点 广度优先搜索也称为宽度优先搜索，它是一种按广度优先搜索也称为宽度优先搜索，它是一种按“先产生的节点先扩展先产生的节点先扩展”原则进行的搜索，也即一原则进行的搜索，也即一层一层进行的搜索。搜索过程是层一层进行的搜索。搜索过程是:从初始节点从初始节点So开始开始逐层向下扩展，先生成下一级各子节点

12、，按顺序逐层向下扩展，先生成下一级各子节点，按顺序(先先生成的子节点，优先检查，优先扩展生成的子节点，优先检查，优先扩展)检查是否出现检查是否出现目标节点目标节点Sg。按此方法，若在第按此方法，若在第n层节点（此层无目层节点（此层无目标节点）还没有全部搜索完之前，不进入第标节点）还没有全部搜索完之前，不进入第n+1层节层节点的搜索。也就是说，广度优先的搜索树是自顶向点的搜索。也就是说，广度优先的搜索树是自顶向下一层一层逐渐生成的，一直到找到目标节点为止。下一层一层逐渐生成的，一直到找到目标节点为止。广度优先搜索节点的扩展顺序广度优先搜索节点的扩展顺序 图3-5 节点扩展顺序G H Sg C D

13、 E F A BSo搜索算法流程图搜索算法流程图 否否否否否否是是是是是是 启动启动 把把So放入放入Open表中表中取取Open表中最前面的节点表中最前面的节点N放入放入Closed表中，并冠以顺序号表中，并冠以顺序号Open为空吗？为空吗？N=Sg？成功成功N可扩展可扩展 吗？吗？扩展扩展N，将其子节点依次放入将其子节点依次放入Open表的末表的末尾，并配上指向尾，并配上指向N的返回指针的返回指针失败失败图图3-6 广度优先搜索流程图广度优先搜索流程图示例 例例3-2 重排九宫问题：如图重排九宫问题：如图3-7所示，在所示，在33的方格棋盘上，放置的方格棋盘上，放置8个标有数码的纸个标有数

14、码的纸牌牌(1、2、8)，并留下一个空格。只允许，并留下一个空格。只允许把空格上、下、左、右的纸牌移入空格。把空格上、下、左、右的纸牌移入空格。要求寻找一条从初始状态要求寻找一条从初始状态So到目标状态到目标状态Sg的最短移动路线。的最短移动路线。初始状态初始状态So 目标状态目标状态Sg图图3-7 重排九宫问题重排九宫问题生成的搜索树 2348 9 10 11 12616 17 18 19 20Sg图图3-8 重排九宫问题的广度优先搜索搜索树重排九宫问题的广度优先搜索搜索树 24322 深度优先搜索深度优先搜索深度优先搜索法的概念深度优先搜索法的概念 深度优先搜索是一种后生成的节点先扩展、不

15、撞墙不回头的搜索方法。在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进。图图3-9 3-9 深度优先搜索深度优先搜索 节点扩展顺序节点扩展顺序前已搜索前已搜索 无无解解 SgSg6 6 C 7 5 3C 7 5 34 24 2A B 1 A B 1 SoSo搜索算法流程图搜索算法流程图 24否否否否否否是是是是是是 启动启动把把So放入放入Open表中表中取取Open表中最前面的节点表中最前面的节点N放入放入Closed表中，并冠以顺序号表中，并冠以顺序号Open为空吗？为空吗？N=Sg？成功成功N可扩展可扩展 吗？吗？扩展扩展N，将其子节点依次放入，将其子节点依次放入Open表的首表

16、的首部，并配上指向部，并配上指向N的返回指针的返回指针失败失败图图3-10 深度优先搜索流程图深度优先搜索流程图示例示例 例例3-3 利用深度优先搜索求解如图利用深度优先搜索求解如图3-11所示所示的重排九宫问题。的重排九宫问题。初始状态初始状态So 目标状态目标状态Sg图图3-11 重排九宫问题重排九宫问题生成的搜索树图图3-12 3-12 重排九宫问题的深度优先搜索树重排九宫问题的深度优先搜索树 深度优先搜索策深度优先搜索策略是不完备的，略是不完备的，带有一定的冒险带有一定的冒险性。另外，应用性。另外，应用此策略得到的解此策略得到的解不一定是最佳解不一定是最佳解(最短路径最短路径)。323

17、 有界深度优先搜索有界深度优先搜索 在深度优先搜在深度优先搜索法中，要给索法中，要给出一个深度限出一个深度限制制dm。当从初。当从初始节点出发沿始节点出发沿某一分枝扩展某一分枝扩展到到dm深度，但深度，但还没有找到目还没有找到目标时，就不能标时，就不能再继续向下扩再继续向下扩展，而只能改展，而只能改变方向继续搜变方向继续搜索。索。图图3-13 3-13 有界深度搜索节点扩展顺序有界深度搜索节点扩展顺序 SgSg C C 6 5 3 6 5 34 24 2A B 1 A B 1 SoSod d =d=dm m=3,=3,强迫返回强迫返回d(d(深度深度)1 12 2 3 3搜索算法流程图搜索算法

18、流程图图图3-14 3-14 有界深度优先搜索流程图有界深度优先搜索流程图是是否否否否是是启动启动把把SoSo放入放入OpenOpen表中，置深度表中，置深度d d（SoSo）=0=0取取OpenOpen表中最前面的节点表中最前面的节点N N放入放入ClosedClosed表中，并冠以顺序号表中，并冠以顺序号OpenOpen为空吗？为空吗？N=N=SgSg？成功成功失败失败是是否否d d（N N）=d=dm m？否否是是N N可扩展可扩展 吗？吗？扩展扩展N N，将其子节点依次放入，将其子节点依次放入OpenOpen表的表的首部，并配上指向首部，并配上指向N N的返回指针置的返回指针置 d d

19、（N N）=d=d（N N）+1+1示例示例 例例3-4 用有界深度优先搜索法求解图用有界深度优先搜索法求解图3-11重排重排九宫问题，取深度限界九宫问题，取深度限界dm=4。初始状态初始状态So 目标状态目标状态Sg图图3-11 重排九宫问题重排九宫问题生成的搜索树搜索效率搜索效率P=L/T=4/27 0.148 图图3-15 3-15 重排九宫问题的有界深度优先搜索搜索树重排九宫问题的有界深度优先搜索搜索树324 一致代价搜索一致代价搜索 1.1.一致代价搜索的概念一致代价搜索的概念 在状态空间中，通常把代价记在边在状态空间中，通常把代价记在边(弧弧)上在代价树中，用上在代价树中，用C(n

20、1，n2)表示从表示从父节点父节点n1到其子节点到其子节点n2的代价，用的代价，用g(n1)表示从初始节点表示从初始节点So 到节点到节点n1的代价。的代价。这样，对这样，对So到节点到节点n2的总代价为的总代价为 g(n2)=g(n1)十十C(n1，n2)2.一致代价广度优先搜索法一致代价广度优先搜索法 一致代价的广度优先搜索也称为分枝一致代价的广度优先搜索也称为分枝界限法，在同一级各节点中，取代价界限法，在同一级各节点中，取代价最小的节点优先扩展，从而求得总代最小的节点优先扩展，从而求得总代价最小的路径。价最小的路径。一致代价广度优先搜索方法是完备的。一致代价广度优先搜索方法是完备的。如果

21、问题有解，就一定能够找到解，如果问题有解，就一定能够找到解，并且找到的一定是最优解。并且找到的一定是最优解。搜索算法流程图搜索算法流程图 图图3-16 3-16 代价驱动广度优先搜索流程图代价驱动广度优先搜索流程图否否把把SoSo放入放入OpenOpen表中，置表中，置g(Sog(So)=0)=0否否否否是是是是是是 启动启动取取OpenOpen表中最前面的节点表中最前面的节点N N放入放入ClosedClosed表中，并冠以顺序号表中，并冠以顺序号OpenOpen为空吗？为空吗？N=N=SgSg？成功成功N N可扩展可扩展 吗？吗？失败失败扩展扩展N N，将其子节点，将其子节点N Ni i放

22、入放入OpenOpen表中，表中，配上指向配上指向N N的返回指针，计算并按的返回指针，计算并按g(Ng(Ni i)重新对重新对OpenOpen表排序表排序(小的在前小的在前)示例示例 2 23 34 43 36 62 25 5B BC CA AD DE E图图3-17 53-17 5城市交通路线城市交通路线图图3-18 53-18 5城市交通路线代价树城市交通路线代价树E E4 4B B1 1A AB BC CC C1 1E E1 1E E2 2 E E3 3D D1 1E E5 5D D2 2 3 32 26 6 6 63 32 25 54 4SoSo3 34 43.一致代价深度优先搜索一

23、致代价深度优先搜索 一致代价深度优先搜索和一致代价广度优一致代价深度优先搜索和一致代价广度优先搜索的区别在于每次选择最小代价节点先搜索的区别在于每次选择最小代价节点的方法不同。后者每次都是从的方法不同。后者每次都是从Open表的全表的全体节点中选择一个代价最小的节点，而前体节点中选择一个代价最小的节点，而前者则是从刚扩展的子节点中选择一个代价者则是从刚扩展的子节点中选择一个代价最小的节点。最小的节点。33 启发式搜索启发式搜索 3 33 31 1 启发式搜索的基本概念启发式搜索的基本概念 尽管有些问题是处在完备知识的环境中，尽管有些问题是处在完备知识的环境中，其解是完全确定了的，理论上也能找到

24、解其解是完全确定了的，理论上也能找到解决问题的算法，但在工程实践中，这些算决问题的算法，但在工程实践中，这些算法不是效率太低，就是无法实现。为此，法不是效率太低，就是无法实现。为此，不得不放弃理论性算法，改用经验性的启不得不放弃理论性算法，改用经验性的启发式方法。发式方法。1.启发式搜索的基本思想启发式搜索的基本思想 启发式搜索是在控制性知识中增加关于被解问启发式搜索是在控制性知识中增加关于被解问题和相应任务的某些特性，利用启发性信息来确题和相应任务的某些特性，利用启发性信息来确定节点的生成、扩展和搜索顺序，以便指导搜索定节点的生成、扩展和搜索顺序，以便指导搜索向最有希望的方向前进。向最有希望

25、的方向前进。下一步展开哪个节点？下一步展开哪个节点？是部分展开还是全部展开？是部分展开还是全部展开？使用哪个规则使用哪个规则(算子算子)？怎样决定舍弃还是保留新生成的节点？怎样决定舍弃还是保留新生成的节点？怎样决定舍弃还是保留一棵子树？怎样决定舍弃还是保留一棵子树？怎样决定停止或继续搜索？怎样决定停止或继续搜索？如何定义启发函数如何定义启发函数(估值函数估值函数)？如何决定搜索方向？如何决定搜索方向？2.启发式搜索的特点 大多是深度优先搜索的改进，即尽量沿着最有大多是深度优先搜索的改进，即尽量沿着最有希望的路径，向深度方向小范围前进；希望的路径，向深度方向小范围前进；在多条路可走时，建议该走哪

26、条路径，从而指在多条路可走时，建议该走哪条路径，从而指导搜索过程朝最有利的方向前进；导搜索过程朝最有利的方向前进；利用问题求解的先验知识，使问题尽快找到解；利用问题求解的先验知识，使问题尽快找到解；可采用估值的方法进行搜索指导；可采用估值的方法进行搜索指导；生成的状态空间小、搜索时间短且效率高、控生成的状态空间小、搜索时间短且效率高、控制性好，易于使问题得到解决。制性好，易于使问题得到解决。3.启发性信息的类型 启发性信息一般有以下三种启发性信息一般有以下三种:有效地帮助确定扩展节点的信息有效地帮助确定扩展节点的信息全全局择优搜索法局择优搜索法。有效的帮助决定哪些后继节点应被生成有效的帮助决定

27、哪些后继节点应被生成的信息的信息局部择优搜索法局部择优搜索法 能决定在扩展一个节点时哪些节点应从能决定在扩展一个节点时哪些节点应从搜索树上删除（或剪掉）的信息搜索树上删除（或剪掉）的信息剪枝技剪枝技术术。4.估价函数估价函数 一般形式是一般形式是:f(n)=g(n)+h(n)其中其中g(n)是从是从So到到n的实际代价，的实际代价，h(n)是从节点是从节点n到目标节点到目标节点Sg的估计代的估计代价。价。332 局部择优搜索局部择优搜索1.基本思想基本思想 局部择优搜索法又称爬山法，其基本思想是，局部择优搜索法又称爬山法，其基本思想是，搜索到一个节点后，只从其所有后继子节点搜索到一个节点后，只

28、从其所有后继子节点中，按中，按f(x)选择最优者，也就是在后继子节选择最优者，也就是在后继子节点的局部范围内选择最优者进行扩展，选取点的局部范围内选择最优者进行扩展，选取最有希望逼近目标节点的方向，逐级沿纵向最有希望逼近目标节点的方向，逐级沿纵向深度进行搜索。由于是小范围内的局部优选，深度进行搜索。由于是小范围内的局部优选，故称之为局部择优搜索法。故称之为局部择优搜索法。适用于单峰极值、单因素问题。局部择优搜适用于单峰极值、单因素问题。局部择优搜索法，是不完备的推理方法。索法，是不完备的推理方法。算法流程图 N N可扩展可扩展 吗？吗？N=N=SgSg？图图3-19 3-19 局部择优搜索流程

29、图局部择优搜索流程图是是否否是是否否失败失败 启动启动成功成功 把把SoSo放入放入ClosedClosed表，置表，置N=SoN=So扩展扩展N N，用，用f f（x x）选择）选择N N的最优子节点的最优子节点N N并放并放入入ClosedClosed表，设返回指针，令表，设返回指针，令N=NN=N示例示例 例例3-6 用局部择优搜索重排九宫问题用局部择优搜索重排九宫问题。定义估价函数定义估价函数f（n）=h（n）为：取）为：取节点节点n与目标节点与目标节点Sg两个格局中位置不两个格局中位置不符合的将牌数目。符合的将牌数目。初始状态初始状态So 目标状态目标状态Sg图图3-11 重排九宫问

30、题重排九宫问题生成的搜索树 图图3-20 3-20 重排九宫局部择优搜索树重排九宫局部择优搜索树搜索效率搜索效率 P=L/T P=L/T =8/17 =8/17 0.47 0.47333 全局择优搜索全局择优搜索 1.概念概念 全局择优搜索又称最好优先搜索和有序搜索。它避全局择优搜索又称最好优先搜索和有序搜索。它避免爬山法的缺点，不是在局部节点中择优，而是在免爬山法的缺点，不是在局部节点中择优，而是在全部节点中择优。它在全部节点中择优。它在OPEN表中保留了所有已生表中保留了所有已生成但尚未扩展的节点，并用估价函数成但尚未扩展的节点，并用估价函数f(n)对它们全对它们全部都进行估值。不管这个节

31、点出现在搜索树的任何部都进行估值。不管这个节点出现在搜索树的任何地方，都从中选出最优的节点进行扩展。地方，都从中选出最优的节点进行扩展。最好优先搜索法比爬山法更有希望接近找到最佳最好优先搜索法比爬山法更有希望接近找到最佳解；但也不一定完备。原因在于估价函数解；但也不一定完备。原因在于估价函数f(n)的设的设计不一定是最佳的，按计不一定是最佳的，按f（n）找出的最好解不一定）找出的最好解不一定是实际上的最佳解。是实际上的最佳解。算法流程图 图图3-21 3-21 全局择优搜索流程图全局择优搜索流程图否否否否否否是是是是是是 启动启动把把SoSo放入放入OpenOpen表中，计算表中，计算f(So

32、)f(So)取取OpenOpen表中最前面的节点表中最前面的节点N N放入放入ClosedClosed表中，并冠以顺序号表中，并冠以顺序号OpenOpen为空吗？为空吗？N=N=SgSg？成功成功N N可扩展可扩展 吗？吗？扩展扩展N N并用并用f(x)f(x)估计每个子节点估计每个子节点N Ni i，依次放入，依次放入OpenOpen表及配上指向表及配上指向N N的返回指针，利用的返回指针，利用f(x)f(x)对对OpenOpen表重新排序，小的在前表重新排序，小的在前失败失败示例示例 例例3-7 应用全局择优搜索法求解重应用全局择优搜索法求解重排九宫问题排九宫问题 初始状态初始状态So 目

33、标状态目标状态Sg图图3-11 重排九宫问题重排九宫问题算法流程图 图图3-22 重排九宫全局择优搜索树重排九宫全局择优搜索树估价函数的一个较好的定义 h(n)=P(n)+3S(n)其中其中P(n)是每个将牌离是每个将牌离“家家”（Sg格局中的位置）格局中的位置）最短距离的总和。如图最短距离的总和。如图3-22所示，所示，So格局格局P(n)得分得分为：为：So中的中的 1 2 3 4 5 6 7 8 P(So)=2+1+1+1+0+0+0+2=7(分分)初始状态初始状态So 目标状态目标状态Sg图图3-22 重排九宫问题重排九宫问题S（n）的计算 S（n）是这样来计算的，沿着周围那些非中心方

34、格上依顺）是这样来计算的，沿着周围那些非中心方格上依顺时针方向检查时针方向检查n格局中的每一个将牌，如果其后紧跟着的将格局中的每一个将牌，如果其后紧跟着的将牌正好是目标格局中该将牌的后续者的话，该将牌得牌正好是目标格局中该将牌的后续者的话，该将牌得0分，分，否则得否则得2分，在正中方格中的将牌得分，在正中方格中的将牌得1分。所有将牌得分之分。所有将牌得分之和为和为S（n）。如图）。如图3-22中，中，So格局格局S（So）得分为：）得分为：So中的将牌：中的将牌：1 2 3 4 5 6 7 8 S(So)=2+2+2+1+0+0+2+0=9(分分)所以所以 h(So)=P(So)+3S(So)

35、=7+3 9=34(分分)在更一般的情况下，估价函数可取以下形式：在更一般的情况下，估价函数可取以下形式：f(n)=g(n)+W h(n)其中其中W是一个起调整作用的正实数。是一个起调整作用的正实数。W提高则强调启发信息提高则强调启发信息的作用，的作用，W降低则强调先宽度搜索向后纵深的搜索趋势。降低则强调先宽度搜索向后纵深的搜索趋势。经验表明，经验表明，W值与树的深度成反比时可以提高搜索效率。值与树的深度成反比时可以提高搜索效率。334 与与/或图的启发式搜索或图的启发式搜索1.1.与与/或图一般搜索或图一般搜索 与与/或树的一般搜索过程实际上是一个不断寻找解或树的一般搜索过程实际上是一个不断

36、寻找解树的过程。其一般搜索过程如下树的过程。其一般搜索过程如下:把原始问题作为初始节点把原始问题作为初始节点So，并把它作为当前，并把它作为当前节点；节点；应用分解或等价变换操作，扩展当前节点或由应用分解或等价变换操作，扩展当前节点或由估计函数估计函数f指示的优先节点，如果其子节点是几组指示的优先节点，如果其子节点是几组具有与关系的子节点集合的或，就分二级扩展；具有与关系的子节点集合的或，就分二级扩展；为每个子节点设置指向父节点的指针；为每个子节点设置指向父节点的指针；选择合适的子节点作为当前节点，反复执行第选择合适的子节点作为当前节点，反复执行第2步和第步和第3步步。与或树的二级扩展 a a

37、1 1a a2 2a a3 3 b b1 1 b b2 2 b b3 3 b b4 4 b b5 5 b b6 6 b b7 7 b b8 8图图3-24 3-24 与与/或节点的扩展或节点的扩展b b1 1 b b2 2 b b3 3 b b4 4 b b5 5 b b6 6 b b7 7 b b8 8与或图的解树 由导致根节点为可解节点的有关可解由导致根节点为可解节点的有关可解节点及树枝所组成的子树，称为该问节点及树枝所组成的子树，称为该问题解树。题解树。与与/或树的启发式搜索过程是一种利用或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻找最搜索过程所得到的启发性信息寻找最优解树

38、的过程。即试图找到一个最有优解树的过程。即试图找到一个最有希望成为代价最小的那棵解树。希望成为代价最小的那棵解树。2.与/或图解树的代价 与节点代价的计算与节点代价的计算 若若n为与节点，且子节点为为与节点，且子节点为n1、n2、nk，则，则n的的代价有两种计算方法：代价有两种计算方法：最大代价最大代价其中其中c(n，ni)是节点是节点n到其子节点到其子节点ni的边代价，的边代价，h（ni)是对节点是对节点ni的估计代价。的估计代价。和代价和代价 取它们的和作为代价取它们的和作为代价h（n）。）。)(),(max)(1iikinhnncnh)(),()(1iikinhnncnh 或节点代价的计

39、算 若若n为或节点，且子节点为为或节点，且子节点为n1、n2、nk，则则n的代价为的代价为:即取它们的最小值作为代价即取它们的最小值作为代价h（n）。）。)(),(min)(1iikinhnncnh 其他特殊节点代价的计算 若若n是可解节点，即为终止节点，则其代是可解节点，即为终止节点，则其代价价h(n)=0。若端节点若端节点n为不可解节点，又不是终止节为不可解节点，又不是终止节点，不可扩展，其代价定义为点，不可扩展，其代价定义为h(n)=。根节点的代价即为解树的代价。根节点的代价即为解树的代价。示例 例3-8 求图3-25与/或图解树的总代价，其中t表示终止节点，表示不可解节点。S S0 0

40、 t t t t t tt t t t4 44 45 6 2 45 6 2 41 1 2 2 3 3 4 4图图3-25 3-25 与与/或图的解树或图的解树a ba bc d e fc d e fg pg p 2 4 4 3 2 1 5 73.希望解树 在与在与/或树的启发式搜索中，希望解树是对最佳解或树的启发式搜索中，希望解树是对最佳解树的近根部分的某种估计。树的近根部分的某种估计。0的定义如下：的定义如下：初始节点初始节点S0在希望解树在希望解树0中；中；如果如果n是具有子节点是具有子节点n1、n2、nk的或节点，的或节点，则则n的某个子节点的某个子节点ni在希望解树在希望解树0中的充分

41、必要条中的充分必要条件是：件是：如果如果n是与节点，则是与节点，则n的全部子节点的全部子节点n1、n2、nk都在希望解树都在希望解树0中。中。)(),(min)(1iikinhnncnh4.与/或图的启发式搜索算法流程图 图图3-26 3-26 与与/或图启发式搜索流程图或图启发式搜索流程图把把SoSo放入放入OpenOpen表中，估算表中，估算h(So)h(So)启动启动 依次把依次把OpenOpen表中表中0 0的端节点的端节点N N选出选出 放入放入ClosedClosed表中，并冠以顺序编号表中，并冠以顺序编号N N是终止节点吗？是终止节点吗？扩展扩展N N，将其子节点，将其子节点N

42、Ni i放放入入OpenOpen表中，配上指向表中，配上指向N N的返回指针，估算子的返回指针，估算子节点及父节点的节点及父节点的h h（x x）由由h(x)h(x)估算估算0 0标记标记N N为可解节点，并对为可解节点，并对0 0应用可解标记过程应用可解标记过程是是成功成功SoSo可解吗？可解吗？从从OpenOpen表中除去有表中除去有可解父节点的节点可解父节点的节点否否从从OpenOpen表中除去有不表中除去有不可解父节点的节点可解父节点的节点N N可扩展可扩展 吗？吗？标记标记N N为不可解节点，并对为不可解节点，并对0 0应用不可解标记过程应用不可解标记过程是是失败失败SoSo不可解吗

43、？不可解吗？否否否否否否是是是是5.与/或图启发式搜索示例 例例3-9 用启发式搜索法求图用启发式搜索法求图3-27所示与所示与/或或图最小代价的最优解树。规定每边的代价图最小代价的最优解树。规定每边的代价为为1，每次扩展深度为，每次扩展深度为2。0 0S S0 0 8 8A 8 D 7A 8 D 7B C E F B C E F 3 3 3 23 3 3 2(a)(a)扩展扩展S0S0后的与后的与/或树或树0 0S S0 0 9 9A 8 D 11A 8 D 11B C E 7 F B C E 7 F 3 3 23 3 2 7 67 6 3 2 2 23 2 2 2(b)(b)扩展扩展E E

44、后的与后的与/或树或树G GH HI IJ JK KL L5.与/或图启发式搜索示例 图3-27 与/或图启发式搜索产生的解树0S0 9A 8 D 11B 3 C E 7 F 2M 2 N 7 6P Q R S I J 0 0 2 2 3 2 2 2(c)扩展B后的与/或树P Q R S W X0 0 2 2 0 0 5 2 3 2 2 2 M 2 N 6 U 2 V 9 7 6B 3 C 3 E 7 F 2A 8 D 11S0 90(c)扩展C后的与/或树335 博弈树的启发式搜索博弈树的启发式搜索1.博弈的基本概念博弈的基本概念 博弈博弈(Game Playing)是一类富有智能行为的竞争

45、活动，是是一类富有智能行为的竞争活动，是一类对策性游戏。典型的博弈如下棋、打桥牌、竞技等。一类对策性游戏。典型的博弈如下棋、打桥牌、竞技等。广义的博弈涉及到人类各方面的对策问题，如军事冲突、广义的博弈涉及到人类各方面的对策问题，如军事冲突、政治斗争、经济竞争等。博弈树是一种特殊的与政治斗争、经济竞争等。博弈树是一种特殊的与/或树，或树，前面讨论的一些与前面讨论的一些与/或树搜索策略，都可以应用到博弈问或树搜索策略，都可以应用到博弈问题的求解中来。题的求解中来。简单的基本博弈为简单的基本博弈为“全信息、非偶然、二人零和全信息、非偶然、二人零和”博弈。博弈。即：即：1+2=0，其中，其中1表示我方

46、赢得的利益，表示我方赢得的利益，2表示敌方表示敌方赢得的利益；我胜或敌负时赢得的利益；我胜或敌负时10或或2=-10；反之我；反之我负或敌胜时负或敌胜时10或或2=-10；平局时，；平局时，1=2=0。赢得函数 我方对策的赢得函数为：我方对策的赢得函数为：敌方对策的赢得函数为：敌方对策的赢得函数为：),(maxmin(),(211*2*11dddd11Dd 22Dd),(maxmin(),(122*1*22dddd11Dd 22Dd 其中：是我方的对策；是敌方的对策；（，）是保险策略；是我方的对策的集合；是敌方的对策的集合。1d2d*2d*1d1D2D2.博弈树的主要特点“与与”节点、节点、“

47、或或”节点逐级交替出现，节点逐级交替出现，从我方观点，所以，所有敌方节点都是从我方观点，所以，所有敌方节点都是“与与”节点。节点。从我方的观点，所有属于我方的节点都是从我方的观点，所有属于我方的节点都是“或或”节点。节点。所有能使自己一方获胜的终局都是本原问题，所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。局都是不可解节点。先走步的一方的初始伏态对应着博弈树的先走步的一方的初始伏态对应着博弈树的“根根节点节点”。3.极大极小搜索法 2 9 3 1 -1 -1 3 6 8 -1 2 0 3 -5 7 4

48、-2 6 -1 8 -7 -1 0 3 2 A -1 -1 6 -1 0 -5 -2 -1 -7 -1 2 B 6 0 -1 -1 2 -1 2 S0 最佳最佳 图图3-28 极大极小搜索倒推值的计算极大极小搜索倒推值的计算MAXMAXMAXMINMIN4.示例 例例3-10 一字棋游戏。设有一个三行三列的一字棋游戏。设有一个三行三列的棋盘，两个棋手轮流走步，轮到谁走棋谁棋盘，两个棋手轮流走步，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自就往空格上放一只自己的棋子，谁先使自己的棋子成三子一线谁就取得了胜利。设己的棋子成三子一线谁就取得了胜利。设MAX方的棋子用方的棋子用标记，标记，MIN方

49、的棋子用方的棋子用标记，并规定标记，并规定MAX方先走步。试用极大极方先走步。试用极大极小搜索求双方的最佳策略。小搜索求双方的最佳策略。解解:这个问题的状态空间有这个问题的状态空间有9！个节点，令得！个节点，令得分的静态估值函数分的静态估值函数f(n)=h(n)。启发式函数的设计 若若n是非终局节点，则是非终局节点，则 h1(n)=(方所占据的路数方所占据的路数 方所占据的路数方所占据的路数)如图如图3-29（a）所示，）所示，h1(n)=4-2=2。若若n是和局，是和局，h1(n)=0，如图，如图3-29（b）所示。）所示。若若n是是方获胜的终局节点，方获胜的终局节点，h1(n)=+，如图，

50、如图3-29（c）。）。若若n是方获胜的终局节点，是方获胜的终局节点，h1(n)=-如图如图3-29（d）。）。图图3-29 3-29 一字棋几种典型格局静态得分估值函数一字棋几种典型格局静态得分估值函数h h1 1(n)(n)的计算的计算 （a）（b）（c）（d）h1(n)=2 h1(n)=0 h1(n)=+h1(n)=-h1(n)可得第一步走棋生成的博弈树 第二回合以S4为起点，MAX的走步 h(n)更精确的定义 h2(n)=（方的一阶路方的一阶路 方的一阶路）方的一阶路）+4（方的二阶路方的二阶路 方的二阶路）方的二阶路）+a +2 若若方出子占领了方的二阶路方出子占领了方的二阶路 其中