6第六讲-第三章(盲目、启发搜索)

人工智能技术第三章搜索技术课程主要内容第一章绪论第二章知识表示

第三章搜索技术第四章推理技术第五章机器学习

第六章专家系统

第三章搜索技术搜索概念搜索：搜索什么？在哪里搜索？适用范围？在状态空间，寻找一条从初始节点到目标节点的路径。A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51搜索分类1、盲目式摸索：无信息搜索，搜索时按规定顺序逐个考察节点，直到找到目标。通用性强，但效率低；适用于简单树状结构问题。

包括：宽度优先、深度优先、等代价搜索2、启发式搜索：用到自身的某些信息，指导搜索朝着最有希望的方向进行，搜索效率高。第三章搜索技术盲目搜索只是可以区分出哪个是目标状态。一般是按预定的搜索策略进行搜索。没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。启发式搜索是在搜索过程中参加了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。第三章搜索技术搜索分类本章内容3.1盲目搜索3.2启发式搜索3.3博弈树搜索3.4遗传算法3.5模拟退火算法3.6免疫算法A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51例3.1从王某家族的四代中找王A的后代且其寿命为X=57的人一、

图搜索策略王A:寿命47，有儿子王B1、王B3、王B2王B1:寿命77，有儿子王C1、王C2王B3:寿命52，有儿子王1王B2:寿命65，有儿子王E1、王E2王C1:寿命96王C2:寿命87，有儿子王F1王D1:寿命77，没有儿子王E1：寿命57，有儿子王G1王E2：寿命92，有儿子王H1王F1：寿命32王G1：寿命27，没有儿子王H1：寿命51A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51例3.1从王某家族的四代中找王A的后代且其寿命为X的人(设X=57)一、

图搜索策略搜索目标搜索空间搜索策略3.1盲目搜索一、图搜索策略—在图中寻找路径的方法两种数据结构〔1〕OPEN表存放已生成但还没考察的节点，即待考察节点。〔2〕CLOSED表存放考察过的节点，以及节点之间的关系，如每个节点指向父节点的编号〔返回指针〕。CLOSED表中存放的就是一定搜索策略下的搜索树。

2.搜索树搜索过程中经过〔考察过〕的节点和边，按原图的连接关系，所构成一个树型的有向图，称为搜索树。搜索树是一个搜索过程的搜索轨迹，或称之为搜索空间。A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51一、图搜索策略3.图搜索的一般过程(1)建立一个只含有起始节点S的搜索图G，把S放到OPEN表中。(2)建立一个CLOSED表，其初始为空表。(3)LOOP：假设OPEN表是空表，那么失败退出。

A,47A一、图搜索策略3.图搜索的一般过程(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5)假设n为一目标节点，那么成功退出。此解是搜索图G中沿着指针从n到S这条路径而得到的(指针在第7步中设置)。

A,47A一、图搜索策略3.图搜索的一般过程(6)扩展节点n，生成后继节点。(7)把n的后继节点放入OPEN表的末端，提供返回节点n的指针AA,47B1,77B3,52B2,65B1B2B33.图搜索的一般过程(6)扩展节点n，生成后继节点。(7)把n的后继节点放入OPEN表的末端，提供返回节点n的指针

(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GOLOOP。

3.1盲目搜索4.搜索过程框图开始S0放入OPEN表OPEN表空？将OPEN表中第一个节点(n)移至CLOSE表n是目标节点？修改指针方针，重排OPEN表扩展节点n，把n的后继节点放入OPEN表末端，提供指向节点n的指针失败成功是是否否5.图搜索方法分析：〔1〕策略：各种搜索策略的区别主要表达在OPEN表排序准那么的不同。〔2〕成功：每当扩展节点为目标节点时，宣告成功结束。这时，能够重现这条成功路径，〔3〕失败：当搜索树不再剩有未被扩展的端节点时，过程就以失败告终。在失败终止的情况下，从起始节点出发，一定达不到目标节点。一、图搜索策略(GraphSearch)A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51二、宽度优先搜索A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51例3.1从王某家族的四代中找王A的后代且其寿命为X的人(设X=57)搜索8步找到3.1盲目搜索二、宽度优先搜索宽度优先搜索搜索是以接近起始节点的程度依次扩展节点。宽度优先搜索的根本思想深度优先搜索是严格按节点在树中的出现位置一层一层向下的搜索过程。通过将OPEN表设计为一个队列来实现，将新生成的子节点放在OPEN表的后面，保证先生成的节点先考察〔FIFO〕。

A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51宽度优先搜索示意图OPEN表节点父节点ANULLB1AB3AB2AC2B1C1B1D1B3E1B2E2B2CLOSE表编号节点父节点1ANULL2B1A3B3A4B2AAB1B3B2C2C1D1E1E2搜索图〔搜索树〕二、宽度优先搜索宽度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，那么求得一个解答)。(2)如果OPEN是空表，那么没有解，失败退出；否那么继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。假设没有后继节点，那么转向第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，那么找到一个解答，成功退出；否那么转向第(2)步。例3.2八数码问题

操作规定:允许空格四周上、下、左、右的数码块移入空格中，不许斜方向移动，不许返回先辈结点。

二、宽度优先搜索123857461123856748138257461012384576712384576613825746111238457621238574631382574641237854612231857461312384765141234587615128537461713582746188132574619123785462023185746211284376522123857465128537469161238567428314765283147652318476528314765283164758321476528371465281437652831647583214765231847652831457628316475832147652837461581324765283714652837146523184765281437652836417523418765283145762831675412384765123847651234567891011121314151617181920212223242526教材P.78图错误。宽度优先搜索的特点：OPEN表是一个队列，先进先出〔FIFO〕。CLOSED表是一个顺序表，表中各节点按顺序编号，正被考察的节点在表中编号最大。宽度优先搜索的特点：宽度优先搜索又称为广度优先或横向搜索。宽度优先策略是完备的，即只要问题的解存在，那么一定可以找到最优解。宽度优先搜索策略与问题无关，具有通用性。缺点搜索效率低。深度优先搜索A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51例3.1从王某家族的四代中找王A的后代且其寿命为X的人(设X=57)搜索9步找到三、深度优先搜索节点扩展：最深节点根本思想一种自上向下的搜索过程，优先自己子节点集合中选择下一个被考察的节点，不断向纵深方向前进，直到到达叶子节点或受到深度限制时，才返回到上一级节点沿另一方向继续前进。与宽度优先搜索算法根本不同在于：将扩展的后继节点放在OPEN表的前端〔LIFO〕。A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51深度优先搜索示意图OPEN表节点父节点CLOSE表编号节点父节点1ANULL2B1A3C2B14F1C25C1B16B3A7D1B38B2AAB1B3B2C2C1D1E1E2搜索图〔搜索树〕ANULLB1AF11、深度优先算法步骤：(1)初始结点S放到未扩展节点OPEN中；(2)假设OPEN为空，那么搜索失败，问题无解；(3)弹出OPEN表中最顶端结点放到CLOSE表中，并给出顺序编号n；(4)假设n为目标结点D，那么搜索成功，问题有解；(5)假设n无子结点，转(2)；(6)扩展n结点，将其所有子结点配上返回n的指针，并按次序压入OPEN堆栈，转(2)。12385746112384576312384576

12384576138257461238574612384765412843765123857462123847655深度优先搜索深度优先搜索的特点OPEN表为堆栈，操作是后进先出〔LIFO〕深度优先又称纵向搜索。一般不容易保证找到最优解〔如以下图所示〕防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度——深度界限。2、有界深度优先搜索引入搜索深度限制值d，使深度优先搜索具有完备性。〔1〕深度界限的选择很重要d假设太小，那么达不到解的深度，得不到解；假设太大，既浪费了计算机的存储空间与时间，降低了搜索效率。由于解的路径长度事先难以预料，要恰当地给出d的值是比较困难的。〔2〕即使能求出解，它也不一定是最优解。例3.3：设定搜索深度限制d=5的八数码问题。

有界深度优先搜索例如有界深度优先算法步骤：(1)初始结点S放入堆栈OPEN中；(2)假设OPEN为空，那么搜索失败，问题无解；(3)弹出OPEN中栈顶结点n，放入CLOSE表中，并给出顺序编号n；(4)假设n为目标结点D，那么搜索成功，问题有解；(5)假设n的深度d(n)=d，那么转(2)；(6)假设n无子结点，即不可扩展，转(2)；(7)扩展结点n，将其所有子结点配上返回n的指针，并压入OPEN堆栈，转(2)。代价搜索：寻找从起始状态至目标状态的具有最小代价的路径问题。如果连接弧线具有相同的代价〔等代价〕，即转换为宽度优先搜索。等代价搜索中记号规定起始节点记为S；从节点i到它的后继节点j的连接弧线代价,记为c(i，j)；起始节点S到任一节点i的路径代价记为g(i)。g(j)=g(i)+c(i,j)主要思想：OPEN表中节点按其代价从小至大排序四、等代价搜索3.2启发式搜索盲目搜索的缺乏：效率低，消耗空间与时间。启发式搜索：利用问题本身特性信息〔启发信息〕指导搜索过程。是有序搜索。一、启发式搜索策略启发式信息主要用途：〔1〕用于确定要扩展的下一个节点，防止盲目扩展。〔2〕用于确定应该从搜索树中抛弃或修剪的节点。估价函数f(n):估算节点n的希望程度。f(n)可以是节点n到目标节点的距离；或包括节点n的路径长度。

用估价函数f来排列OPEN表上的节点。应用某个算法选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索或最正确优先搜索(best-firstsearch)，而其算法就叫做有序搜索算法或最正确优先算法。

二、有序搜索(1)把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。(2)如果OPEN是个空表，那么失败退出，无解。(3)从OPEN表扩展节点中选择一个f值最小的节点i。如扩展节点中有一个为目标节点时，那么选择此目标节点。(4)把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中。(5)如果i是个目标节点，那么成功退出，求得一个解。

1、有序状态空间搜索算法：(6)扩展节点i，生成其全部后继节点。对于i的每一个后继节点j，〔a)计算f(j)。(b)如果j既不在OPEN表中，又不在CLOSED表中，那么用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。(c)如果j已在OPEN表上或CLOSED表上，那么比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小，那么:(i)以此新值取代旧值。(ii)从j指向i，而不是指向它的父辈节点。(iii)如果节点j在CLOSED表中，那么把它移回OPEN表(7)转向(2)。

1、有序状态空间搜索算法：

开始把S放入OPEN表OPEN为空表？失败选取OPEN表中f值最小的节点i，放入CLOSED表i=Sg？成功是是扩展i得后继节点j，计算f(j)，提供返回i的指针，利用f(j)对OPEN表重新排序调整父子关系及指针2、有序搜索算法框图3、有序搜索算法讨论〔1〕盲目搜索是有序搜索的特例：启发信息为零〔2〕估价函数f的选择f的选择直接决定有序搜索的有效性。如果选择的f不适宜，有序搜索就可能失去一个最好的解甚至全部的解。f的选择涉及两个内容：一是一个时间和空间之间的折衷方案；二是保证有一个最优的解或任意解。例3.4：八数码难题估价函数估价函数取：

f(n)=d(n)+W(n)其中：d(n)是搜索树中节点n的深度；

W(n)是节点n的中错放的棋子个数。对于起始节点棋局，f=0+4=4。

4、有序搜索算法举例286128316475283164752831476528316475283147652318476528314765832147652837146523184765233184765123847651238476512378465f=0+4=4f=1+5=6f=1+3=4f=1+5=6f=2+3=5f=2+3=5f=2+4=6f=3+3=6f=3+4=7f=3+2=5f=3+4=7f=4+1=5f=5+0=5f=5+2=7

f(n)=d(n)+W(n)启发函数是对当前节点到达目标节点要付出的代价的估计。在全局择优和局部择优搜索算法中，都没有考虑从初始节点到当前节点已经付出的实际代价。在很多实实际问题中，已经付出的实际代价是必须考虑的。将两者同时考虑，用于指导搜索的算法称为A算法和A*算法。

三、A*算法1.A算法估价函数f〔x〕:为了防止单独利用启发函数误入歧途，将启发函数h〔x〕与代价函数g〔x〕相结合，即：f〔x〕＝g〔x〕＋h〔x〕g〔x〕代价函数：初始节点S0到达节点x处已付出的代价，有利于搜索纵向开展，提高搜索效率，但影响完备性。h〔x〕启发函数：节点x到达目标节点Sg的接近程度估计值，有利于搜索横向开展，提高搜索的完备性，但影响搜索效率。三、A*算法代价g〔x〕的计算g〔x〕表示从初始节点S0到节点x的代价：g〔S0〕＝0g〔xj〕＝g〔xi〕＋c〔xi，xj〕其中，c〔xi，xj〕表示父节点xi到子节点xj的代价ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B33.2启发式搜索3.2启发式搜索f〔x〕＝g〔x〕＋h〔x〕g〔x〕：对某一确定的节点，是确定的值。h〔x〕：不同的问题启发函数的定义不同，相同的问题也可以定义出不同的启发函数。衡量h〔x〕优劣的标准是看其是否能够准确反映出节点x到达目标的难易程度〔距离〕。估价函数定义探讨2.A*算法对A算法再限制其估价函数中的启发函数h(x)满足：对所有的节点x均有：h〔x〕h*〔x〕其中h*〔x〕是从节点x到目标节点的最小代价，这就称为A*算法。A*算法也称为最正确图搜索算法，利用A*算法，如果问题存在最优解，就保证能找到最优解。A*算法的估价函数f(n)=g(n)+h(n)，是估价函数f*(n)=g*(n)+h*(n)，是自S经节点n到标Sg的最正确路径。恒有：(1)g(n)≥g*(n)，算法执行过程中g(n)值呈下降趋势；(2)h(n)≤h*(n)，保证A*算法可找到最优解。h(n)称为启