人工智能原理第3章-图搜索技术课件.pptx

1、第3章图搜索技术3.1问题的提出3.2状态图搜索3.3与或图搜索3.4博弈图搜索3.1问题的提出【例例3-1】图3-3两个四边形【例例3-2】有如图3-3所示的两个四边形ABCD和ABCD，要求证明他们全等。我们将本例问题设为我们将本例问题设为Q。为解决该问题，分别在两个图形中。为解决该问题，分别在两个图形中做辅助线做辅助线B、D和和B、D，如果我们能证明问题，如果我们能证明问题Q1：ABD ABD，并且能证明问题，并且能证明问题Q2：BCD BCD，则，则问题问题Q得到证明。得到证明。【例【例3-3】3.2状态图搜索3.2.1状态图搜索分类3.2.2穷举式搜索3.2.3启发式搜索3.2.4A

2、算法及A*算法3.2.1状态图搜索 有两种最基本的搜索方式：树式搜索线式搜索3.2.1状态图搜索 盲目搜索盲目搜索就是无向导的搜索。启发式搜索启发式搜索就是有向导的搜索。是利用“启发性信息”引导的搜索。所谓启发性信息就是与问题有关的有利于尽快找到问题解的信息或知识。3.2.1状态图搜索树式搜索的一般算法：Step1 把初始节点S0 放入OPEN表中；Step2 若OPEN表为空，则搜索失败，退出。Step3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以顺序编号n；Step4 若N是目标节点，则搜索成功，结束。Step5 若N不可扩展，则转Step2；Step6 扩展N，生成一组子节

3、点，对这组子节点作如下处理：3.2.2穷举式搜索1.广度优先搜索算法2.深度优先搜索3.有界深度优先搜索1.广度优先搜索算法 广度优先搜索算法：Step1 把初始节点S0 放入OPEN表中；Step2 若OPEN表为空，则搜索失败，退出；Step3 取OPEN表中前面第一个节点N放在CLOSED表中，并冠以顺序编号n；Step4 若N为目标节点，则搜索成功，结束。Step5 若N不可扩展，则转Step2；Step6 扩展N，将其所有未在OPEN及CLOSED表中出现过的子节点针依次放入OPEN表尾部，转Step2。【例【例3-4】用广度优先算法，求解八数码问题。初始状态：S0 目标：Sg 2.

4、深度优先搜索深度优先搜索算法：深度优先搜索算法：Step1 把初始节点把初始节点S0 放入放入OPEN表中；表中；Step2 若若OPEN表为空，则搜索失败，退出；表为空，则搜索失败，退出；Step3 取取OPEN表中前面第一个节点表中前面第一个节点N放在放在CLOSED表中，并冠以顺表中，并冠以顺序编号序编号n；Step4 若若N是目标节点是目标节点Sg，则搜索成功，结束。，则搜索成功，结束。Step5 若若N不可扩展，则转不可扩展，则转Step2；Step6 扩展扩展N，将其所有未在，将其所有未在OPEN及及CLOSED表中出现过的子节点表中出现过的子节点配上指向配上指向N的返回指针依次放

5、入的返回指针依次放入OPEN表的首部，转表的首部，转Step2。2.深度优先搜索【例【例3-5】对于八数码问题，应用深度优先搜索策略，可得如图3-8所示的部分搜索树（由于篇幅限制，这里未给出完整的搜索树）。OPEN表及CLOSED表的变化过程从略。2.深度优先搜索3.有界深度优先搜索有界深度优先搜索就是给出了搜索树深度限制，当从初始节点出发沿某一分枝扩展到一限定深度时，就不能再继续向下扩展，而只能改变方向继续搜索。节点x的深度（即其位于搜索树的层数）通常用d(x)表示，则有界深度优先搜索算法如下：3.有界深度优先搜索Step1 把把S0 放入放入OPEN表中，置表中，置S0 的深度的深度d(S

6、0)=0；Step2 若若OPEN表为空，则搜索失败，退出；表为空，则搜索失败，退出；Step3 取取OPEN表中前面第一个节点表中前面第一个节点N，放在，放在CLOSED表表中，并冠以顺序编号中，并冠以顺序编号n；Step4 若若N是目标节点，则搜索成功，结束。是目标节点，则搜索成功，结束。Step5 若若N的深度的深度d(N)=dm(深度限制值深度限制值)，或，或N无子节点，无子节点，则转则转Step2；Step6 扩展扩展N，将其所有子节点，将其所有子节点Ni配上指向配上指向N的返回指的返回指针后依次放入针后依次放入OPEN表中前部，置表中前部，置d(Ni)=d(N)+1，转，转Step

7、2。3.2.3启发式搜索 1.全局择优搜索 2.局部择优搜索算法 3.分支界限搜索算法 4.最近择优1.全局择优搜索全局择优搜索算法如下：Step1 把初始节点S0 放入OPEN表中，计算h(S0)；Step2 若OPEN表为空，则搜索失败，退出；Step 3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号n；Step 4 若N是目标节点，则搜索成功，结束。Step 5 若N不可扩展，则转Step 2；Step 6 扩展N，计算每个子节点x的函数值h(x)，并将所有子节点配以指向N的返回指针后放入OPEN表中，再对OPEN表中的所有子节点按其函数值大小以升序排序，转Step 2。

8、1.全局择优搜索【例【例3-6】用全局择优搜索法解八数码难题。初始棋局S0，目标棋局Sg.解解 设启发函数h(x)为节点x的格局与目标格局相比数码位置不同的个数。由图可见此八数问题的解为：S0 S1 S2 S3Sg图3-9全局择优搜索法搜索树2.局部择优搜索算法扩展节点N 后仅对N的子节点按启发函数值大小以升序排序，再将它们依次放入OPEN表的首部。即：Step 1 把初始节点S0 放入OPEN表中，计算h(S0)；Step 2 若OPEN表为空，则搜索失败，退出；Step 3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号n；Step 4 若N是目标节点，则搜索成功，结束。St

9、ep 5 若N不可扩展，则转Step 2；Step 6 扩展N，计算每个子节点x的函数值h(x)，并将N所有子节点配以指向N的返回指针，按函数值大小以升序排序，依次放入OPEN表首部，转Step 2。3.分支界限搜索算法如图3-10是一个交通图，设A城是出发地，E城是目的地，边上的数字代表两城之间的交通费。试求从A到E最小费用的旅行路线。ABCE324643D3.分支界限搜索算法分支界限搜索算法步骤描述如下：Step 1 把初始节点S0 放入OPEN表中，计算h(S0)；Step 2 若OPEN表为空，则搜索失败，退出；Step 3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号

10、n；Step 4 若N是目标节点，则搜索成功，结束。Step 5 若N不可扩展，则转Step 2；Step 6 扩展N，计算每个子节点x的函数值g(x)，并将所有子节点配以指向N的返回指针后放入OPEN表中，再对OPEN表中的所有子节点按其函数值大小以升序排序，转Step2。3.分支界限搜索算法在搜索过程中会产生一颗不断增长的搜索树，一个节点x的代价值g(x)是从该树初始节点S0方向计算而来的，其计算方法为：g(S0)=0g(xj)=g(xi)+c(xi，xj)其中xj是xi的子节点，c(xi，xj)表示节点xi到节点xj的代价。代价又称为耗散耗散。3.分支界限搜索算法【例例3-7】如图3-1

11、0是一个五城市交通图，设A城是出发地，E城是目的地，用分支界限搜索算法求A到E的最小费用路径。解：解：根据算法可得如图3-11所示的搜索树，可见最小费用路径为：A C D E。OPEN表及CLOSED表的变化过程从略。解路径为A C DE。BABCDEEG=3G=4G=5G=10G=8G=9G=04.最近择优算法步骤描述如下：Step 1 把初始节点S0 放入OPEN表中，计算h(S0)；Step 2 若OPEN表为空，则搜索失败，退出；Step 3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号n；Step 4 若N是目标节点，则搜索成功，结束。Step 5 若N不可扩展，则转

12、Step 2；Step 6 扩展N，计算每个子节点x的函数值g(x)，并将N所有子节点配以指向N的返回指针，按g(x)函数值大小以升序排序，依次放入OPEN表首部，转Step 2。3.2.4A算法及A*算法1.估价函数2.A算法3.A*算法1.估价函数估价函数的一般形式为：f(x)=g(x)+h(x)当状态图中所有边的代价都是1（单位耗散）时，估价函数还可以表示为：f(x)=d(x)+h(x)2.A算法A算法是基于估价函数f(x)的一种加权状态图启发式搜索算法。算法描述如下：Step 1 把附有f(S0)的初始节点S0 放入OPEN表；Step 2 若OPEN表为空，则搜索失败，退出；Step

13、 3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以顺序编号n；Step 4 若N是目标节点，则搜索成功，结束。Step 5 若N不可扩展，则转Step 2；Step 6 扩展N，生成一组附有f(x)的子节点，对这组子节点作如下处理：2.A算法(1)考察是否有已在OPEN表或CLOSED表中存在的节点；由于它们被第二次生成，因而需要考虑是否修改已经存在于OPEN表或COLSED表中的这些节点及其后裔的返回指针和f(x)值，修改原则是“抄f(x)值小的路走”；(2)对其余子节点配上指向N的返回指针后放入OPEN表中，并对OPEN表按f(x)值以升序排序，转Step2。算法中节点x估价函

14、数f(x)的计算方法是f(xj)=g(xj)+h(xj)=g(xi)+c(xi，xj)+h(xj)(xj是xi的子节点)至于h(x)的计算公式则需由具体问题而定。2.A算法【例【例3-8】使用A算法求解八数码问题。取f(x)=d(x)+h(x)。其中d(x)为节点深度，h(x)为不在位数码个数。初始状态为S0，目标状态为Sg（如图3-12）。解路径为S0S2S5S9S11Sg2.A算法3.A*算法如果对A算法限制其估价函数中的启发函数h(x)满足：对所有的节点x均有：h(x)h*(x)其中h*(x)是从节点x到目标节点的最小代价。此时的A算法就称为A*算法，A*算法是完备的。A*算法也称为最佳

15、图搜索算法。它是著名的人工智能学者Nilsson提出的。3.3与或图搜索3.3.1与或图3.3.2与或图搜索举例3.3.1与或图因此，一般称这种路径为解图解图或解树解树。所以，求解与或图问题就是在与或图中搜索解图或解树的问题。N1N4N3N5N7N0N2N63.3.1与或图为了叙述方便，下面引入一些新概念：本原问题本原问题 终止节点终止节点 端节点端节点 与节点与节点 或节点或节点注意：终止节点一定是端节点，但端节点不一定是终止节点。K连接符连接符3.3.1与或图例如，图3-13中节点n2有两个连接符，1连接符指向n3，2连接符指向节点集n1，n5可解节点：可解节点：不可解节点：不可解节点：与

16、图：与图：3.3.2与或图搜索举例1.基本概念2.AO*搜索算法1.基本概念解图（树）的代价：分为和代价和最大代价两种。c(x,y)表示节点x到其子节点y的代价（即边xy的代价），则节点x到节点集N的解图G的代价记为g(x)，则和代价可递归定义如下：（1）若x是终止节点，g(n)=0；（2）若x是与节点，有一个外向n连接符连至y1、y2、yn，则有两种计算公式：c(x,yi)+g(yi)上式称为和代价；g(x)=MAXc(x,yi)+g(yi)1in 上式称为最大代价。对非终止的端节点x，g(x)=解图（树）的代价定义为树根S0的代价。最佳（优）解图：最佳（优）解图：是具有最小代价的解图。【例

17、3-9】1.基本概念解：解：由右边的解树：按和代价：g(A)=11，g(S0)=13按最大代价：g(A)=6，g(S0)=8由左边的解树：按和代价：g(G)=3，g(D)=4，g(B)=6，g(S0)=8按最大代价：g(G)=2，g(D)=3，g(B)=5，g(S0)=7显然，若按和代价计算，左边的解树是最优解树，其代价为8；若按最大代价计算，左边的解树仍然是最优解树，其代价是7。但使用不同的计算代价方法得到的最优解树有可能不相同。1.基本概念下面给出希望树的定义：（1）初始节点S0在希望树T中。（2）如果节点x在T中，则：如果x只有一个k连接符，则k连接符所连接的所有子节点都在T中如果x具有

18、多个k连接符k1，k2，kn，设kj所连接的子节点为yj1，yjkj则：kjc(x，yji)+g(yji)j=1ni=1 1.基本概念2.AO*搜索算法 Step1 把初始节点S0放入OPEN表；Step2 从当前生成的搜索树(图)，构造以S0为根的希望树(图)T。Step3 选一个OPEN表和T共有的节点N，并将N从OPEN表移出放入CLOSED表(即选中T中的待扩展节点进行扩展)；Step4 若N为终止节点，则做下列工作：（1）标记N为可解节点；（2）把N的先辈节点中的可解节点标记为可解.（3）如果初始节点S0被标记为可解，则T为最优解树(图)，成功退出。（4）删去OPEN表中这样的节点:

19、其先辈节点已经可解；Step5 若N不是终止节点且不可扩展，则做下列工作：（1）标记N为不可解节点。（2）把N的先辈节点中的不可解节点标记为不可解（3）如果初始节点S0被标记为不可解，失败退出。（4）删去OPEN表中这样的节点：其先辈节点中存在不可解节点；Step6 若N不是终止节点但可扩展，则做下列工作:（1）扩展N，产生N的所有子节点。（2）把这些子节点放入OPEN表中，并为每个子节点配以指向父节点的指针.（3）计算这些子节点的g值及先辈节点的g值(递归地)Step7 转Step2；同状态图搜索一样，搜索成功后，解树已经记录在CLOSED表中。这时需按指向父节点的指针找出整个解树。【例【例

20、3-10】如图3-16中（1）所示的与或图，设初始节点为N0，目标节点为N6、N7。假设在扩展过程中生成的各节点的启发函数值分别是：g(N0)=3、g(N1)=1、g(N2)=2、g(N3)=3、g(N4)=1、g(N5)=2、g(N6)=0、g(N7)=0，边为单位耗散，请使用AO*搜索算法求解最佳解图。解：解：第一次循环：第二次循环：第三次循环：第四次循环：第五次循环：第六次循环：通过本例我们可以看出，在本算法生成希望图的过程中，希望图是动态变化的（如图3-16中（3）和（4）。另外，根据本算法所得到的最佳解图也不一定是唯一的，这可以留给读者思考。3.4博弈图搜索3.4.1博弈图3.4.2

21、极大极小分析法3.4.3剪枝技术3.4.1博弈图3.4.1博弈图（1）博弈的初始格局是初始节点。（2）博弈树中，“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系，对方扩展的节点之间是“与”关系。双方轮流地扩展节点。（3）max必胜的节点对应的是终止节点（本原问题），即可解节点；所有使对方必胜的节点对应的都是不可解节点。3.4.1博弈图3.4.2极大极小分析法 基本思想：（1）假设我方max，即为max寻找最优方案。（2）对各种方案产生的后果进行量化分析，即计算可能得分。为计算得分，需要根据问题的特性信息定义一个估价函数f(x)，用来估算当前博弈树端节点的得分。此时估算

22、出来的得分称为静态估值静态估值。3.4.2极大极小分析法（4）当端节点的估值计算出来后，再推算出父节点的得分，推算的方法是：对“或”节点，选其子节点中一个最大的得分和为父节点的得分；对“与”节点选其子节点中一个最小的得分作为父节点的得分。这样计算出的父节点的得分称为倒推值倒推值。（5）如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。3.4.2极大极小分析法【例【例3-11】324-124-2634546-56-59632632-122-23324-543-5323minmaxminmax7max3图3-18 求博弈图的倒推值3.4.2极大极小分析法【例【例3-12】设A的棋子用“”表示，B的棋子用“”表示。为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下：设棋局为P，估价函数为e(P)。（1）若P是A必胜的棋局，则e(P)=+。（2）若P是B必胜的棋局，则e(P)=-。（3）若P是胜负未定的棋局，则e(P)=e(+P)-e(-P)3.4.2极大极小分析法3.4.3剪枝技术【例3-13】如图3-21，按照从左到右的扩展顺序，使用-剪枝，标出所发生的剪枝位置及及剪枝类型。