人工智能第3章确定性推理课件

人工智能ArtificialIntelligence(AI)人工智能1第3章确定性推理

3.1图的搜索策略3.2盲目搜索3.3启发式搜索3.4与或树搜索（补充）3.5博弈树搜索（补充）3.6消解原理第3章确定性推理3.1图的搜索策略2解决实际问题的两个关键之处：①问题的表达状态空间法问题归约法谓词逻辑法②问题的求解搜索技术推理技术解决实际问题的两个关键之处：①问题的表达②问题的求解3盲目与启发式搜索：状态空间法、图的搜索技术与或树搜索：问题归约法、与或图的特例的搜索技术博弈树搜索：状态空间法＋问题归约法、双人博弈的特殊搜索技术消解原理：谓词逻辑法、推理技术盲目与启发式搜索：状态空间法、图的搜索技术43.1图搜索策略

状态空间中：状态初始状态目标状态操作符图中有：节点初始节点目标节点有向弧状态空间法与图的对应关系3.1图搜索策略状态空间中：图中有：状态空间法与图的对应5在状态空间中，解是从初始状态到目标状态的操作符序列在图中，解是从初始节点到目标节点的一条路径解的含义：在状态空间中，解是从初始状态到目标状态的操作符序列解的含义：6状态：(城市名)算子：常德→益阳 益阳→常德 益阳汨罗 益阳宁乡 益阳娄底

…？？？？必须记住哪些点走过了必须记住下一步还可以走哪些点必须记住从目标返回的路径状态：(城市名)？？？？必须记住哪些点走过了必须记住下一步还7必须记住哪些点走过了必须记住下一步还可以走哪些点必须记住从目标返回的路径OPEN表(记录还没有扩展的点)CLOSED表(记录已经扩展的点)每个表示状态的节点结构中必须有指向父节点的指针必须记住哪些点走过了必须记住下一步还可以走哪些点必须记住从目8图的搜索策略：图搜索过程的一般步骤（基本思路、框架），经过细化后得到具体算法：盲目搜索技术（深度、宽度、代价优先算法）启发式搜索技术（有序算法、A*算法）图的搜索策略：图搜索过程的一般步骤（基本思路、框架），经过细9图搜索中的两个重要记号（符号）：OPEN表：存放待扩展的节点CLOSED表：存放已扩展的节点注意：在与或树搜索中也要用到这两张表图搜索中的两个重要记号（符号）：10数据结构中图的遍及：从图某一个节点出发，访问遍图中其余节点，且每一个节点仅仅被访问一次。当前图的搜索技术中，有两个特殊之处：搜索前，图并没有生成好，需要边生成图边搜索搜索从起始节点（初始状态）开始，到目标节点（目标状态）结束，不需要搜索所有可能的节点数据结构中图的遍及：从图某一个节点出发，访问遍图中其余节点，11盲目搜索是指无问题先验信息的搜索技术特点：OPEN表中节点的排列是人为规定的一般只适合于求解比较简单的一些问题3.2盲目搜索盲目搜索是指无问题先验信息的搜索技术3.2盲目搜索12图的盲目搜索技术分成：宽度优先搜索技术深度优先搜索技术等代价（代价优先）搜索技术图的盲目搜索技术分成：133.2.1宽度优先搜索

宽度优先搜索：以接近起始节点的程度依次扩展节点的搜索技术（即：离起始节点近的节点先被扩展）扩展节点的原则：先扩展出来的节点随后优先被扩展（生成其所有的后继节点）3.2.1宽度优先搜索宽度优先搜索：以接近起始节点的程14人工智能第3章确定性推理课件15①

把起始节点放到OPEN表中(如果该起始节点为一目标节点，则得到解)②

如果OPEN是个空表，则无解，失败退出；否则继续下一步宽度优先搜索算法：①把起始节点放到OPEN表中(如果该起始节点为一目标节16③

把第一个节点(记作节点n)从OPEN

表移出，并把它放入

CLOSED的已扩展节点表中④

扩展节点n。如果没有后继节点，则转向第②步③把第一个节点(记作节点n)从OPEN表移出，并17⑤

把n

的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n

的指针⑥

如果n

的任一个后继节点是个目标节点，则找到一个解（反向追踪得到从目标节点到起始节点的路径），成功退出，否则转向第②步⑤把n的所有后继节点放到OPEN表的末端，并提供从这些18OPEN表是存放待扩展的节点，从数据结构上来说，它是一个先进先出的队列CLOSED表是存放已被扩展过的节点（包括有后继节点的非端节点和无后继节点的端节点）说明：OPEN表是存放待扩展的节点，从数据结构上来说，它是一个先19流程图

流程图20①搜索过程产生的节点和指针构成一棵隐式定义的状态空间树的子树，称之为搜索树注意几点：①搜索过程产生的节点和指针构成一棵隐式定义的状态空间树的子树21②

宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径（所用操作符最少）②宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的22例：八数码问题初始状态目标状态操作符：2831476512384765空1243例：八数码问题初始状态目标状态操作符：2831476512323状态：长度为9的一维数组（q1,q2,…,q9）其中，qi

取0,1,…,8个数，0表示空格，且取值互不相同状态：长度为9的一维数组24

如果记空格的位置为P，这时空格的移动规则是：123456789123456789PP-3P+1P+3P-1数字表示位置如果记空格的位置为P，这时空格的移动规则是：25

顺序规则前提条件应用结果1左移P≠1,4,7P位置与P-1

位置上的元素互换2上移P≠1,2,3

P-33下移P≠7,8,9

P+34右移P≠3,6,9

P+1空格移动规则P-3PP+3P-1P+1123456789顺序规则前提条件应用结果1左移P≠1,4,726为了记录后继节点与父节点之间的指针，我们将长度为9的数组扩大到长度为11的数组，其中一个元素记录该节点的父节点标志，另一个元素记录操作符的序号操作符父节点状态为了记录后继节点与父节点之间的指针，我们将长度为9的数组27OPEN表的存储形式：队列插入端（队尾）删除端（队头）队列：一种先进先出的线性表，允许在表的一端进行插入、另一端进行删除OPEN表的存储形式：队列插入端（队尾）删除端（队头）队列：28CLOSED表的存储形式：也可以用队列父符插入端（队尾）特殊的队列：只进不出的队列，只允许在表的一端进行插入CLOSED表的存储形式：也可以用队列父符插入端（队尾）特殊29某一个节点的父节点标志：记录CLOSED表中的父节点的序号起始节点的父节点标志和操作符：不作记录或记录为负某一个节点的父节点标志：30搜索过程（按照程序运行方式）①

起始节点放到OPEN表283104765②

OPEN不为空，继续28314765搜索过程（按照程序运行方式）①起始节点放到OPEN表231③

将第一个节点n

从OPEN

表中移出，并放到CLOSED表中00283104765OPEN表CLOSED表节点n1③将第一个节点n从OPEN表中移出，并放到CLO32④

扩展节点n

283014765

203184765

283164705

28314076500283104765扩展28314765④扩展节点n28301476520318476533⑤将节点n的所有后继节点放到OPEN

表的末端，并提供这些后继节点回到n

的指针11283014765122031847651328316470514283140765OPEN表符父00283104765CLOSED⑤将节点n的所有后继节点放到OPEN表的末端，并34⑥

后继节点中无目标节点，转到②②

OPEN表不为空，继续⑥后继节点中无目标节点，转到②②OPEN表不为空，继35③

将第一个节点n

从OPEN

表中移出，并放到CLOSED表中OPEN表CLOSED表1220318476513283164705142831407650028310476511283014765节点n12③将第一个节点n从OPEN表中移出，并放到CLO36④

扩展节点n

083214765

2837140651128301476528314765④扩展节点n0832147652837140637⑤将节点n

的所有后继节点放到OPEN表的末端，并提供这些后继节点回到n的指针122031847651328316470514283140765OPEN表2208321476523283714065⑤将节点n的所有后继节点放到OPEN表的末端，并38….一直继续下去，而且不产生已经产生过的节点（状态），防止死循环。在程序中每一个新产生的节点必须与OPEN和CLOSED表中状态进行比较，判断是否已经产生过，只保留从未产生过的节点….39最后的OPEN表：93234180765103283064175112283160754121208143765131283145706144830214765143813204765152283704615154283714650163123784065164123804765目标节点12384765最后的OPEN表：93234180765103283064140最后的CLOSED表：2831047651128301476512203184765132831647051428314076522083214765232837140653102318476534230184765123456789最后的CLOSED表：2831047651128301476414128316407544283164750522801437505328314576064803214765742837146058312308476510111213141516164123804765目标节点4128316407544283164750522801434283123084765164123804765目标节点31023184765168122031847652831047653183123084765164123804765目标节点310432831476528314765231847652831647528314765214383214765283714652318476523184765281437652831647528316475283145768321476528371465123847652341876528364175283167542814376528314576832147658132476512378465123847652837461528371465先生成的节点在左目标节点28314765283147652318476528316444（先扩展的节点画在左边）生成后继节点的顺序（先扩展的节点画在左边）生成后继节点的顺序45OPEN与CLOSED表的存储形式的简化CLOSEDOPEN加入扩展节点OPEN与CLOSED表的存储形式的简化CLOSEDOPEN46状态：111状态：212状态：313状态：414状态：522状态：623状态：731状态：834状态：941状态：1044状态：1152状态：1253状态：1364状态：1474状态：1583状态：1693状态：17103状态：18112状态：19121状态：20131状态：21144状态：22143状态：23152状态：24154状态：25163状态：26164状态：27CO123456789101112131415161718192021222324252627CO状态：111状态：212状态：313状态：414状态：547人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,2)(1,4)(3,4)WE(3,2)(3,1)ES(3,3)(4,4)ES目标节点X例：迷宫问题人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,48例：四皇后问题QQQQQQQQQQQQQQQQQQQXQQQQQQQQQXQQQQX例：四皇后问题QQQQQQQQQQQQQQQQQQQXQQQ49练习：根据下列迷宫，用宽度优先搜索算法寻找出从入口到出口的一条路径状态：用极坐标表示的人的位置操作符：人向左方、前方、右方前进提示：不要产生已有的状态练习：根据下列迷宫，用宽度优先搜索算法寻找出从入口到出口的一50存在的问题：走步方向不符合人走路的习惯没有标注走步的方向中间改变走步方向的顺序多画搜索树，有解后还再往下扩展存在的问题：51(6,0)人向左1向右3向前2(4,0)前右(6,45)(4,45)(2,0)前右左(2,45)前(4,90)(0,0)前右(2,90)右(6,90)出口宽度优先搜索算法（没有生成已有的状态）先在左XX(6,0)人向左向右向前2(4,0)前右(6,45)(4,452(6,0)向左1(4,0)前右(4,45)(2,0)前前(2,45)右(4,90)(0,0)前右(6,90)出口宽度优先搜索算法先在左X人向右3向前2(6,0)向左(4,0)前右(4,45)(2,0)前前(2,533.2.2深度优先搜索

深度优先搜索策略是先扩展最新产生的(即最深的)节点

3.2.2深度优先搜索深度优先搜索策略是先扩展最新产生54节点的深度；①、起始节点(即根节点)的深度为0。②、任何其它节点的深度等于其父辈节点深度加上1。

节点的深度；55深度优先搜索的基本思路：先扩展最深的节点。当出现没有后继节点时，换到旁边的次深节点后生成的节点画在左边深度优先搜索的基本思路：后生成的节点画在左边56①

把起始节点S放到未扩展节点的OPEN表中。如果此节点为一目标节点，则得到解②

如果OPEN

为一空表，则无解、失败退出含有深度界限的深度优先搜索算法：①把起始节点S放到未扩展节点的OPEN表中。如果此57深度界限的设置：为了避免出现过深的路径，搜索过程要设置一个深度界限对于等于深度界限的任何节点，当作没有后继节点的节点来看待缺点：可能丢失解深度界限的设置：58③把第一个节点(记作节点n)从OPEN

表移到CLOSED

表④

如果节点n的深度等于最大深度，则转向②③把第一个节点(记作节点n)从OPEN表移到CL59⑤

扩展节点n，产生其全部后继节点，并把它们放入OPEN

表的前头。如果没有后继节点，则转向②⑥

如果后继节点中有任一个节点为目标节点，则求得一个解（反向追踪从目标节点到起始节点的路径），成功退出；否则，转向②⑤扩展节点n，产生其全部后继节点，并把它们放入OPE60人工智能第3章确定性推理课件61人工智能第3章确定性推理课件62说明：现在的OPEN表是一个堆栈，后进先出说明：63深度界限为4后生成的节点画在左边深度界限为4后生成的节点画在左边6428314765283147652318476528316475283147652143283164752831647528316754后生成的节点在左283167542816375428364175832641752836417528143765283145762831457628314576283157462814376528143765248137652318476523184765234187652341876523418576123847651238476512378465目标节点28314765283147652318476528316465例：八数码问题深度界限为5后生成的节点画在左边例：八数码问题深度界限为5后生成的节点画在左边66说明：状态旁边的数字表示该节点生成后继节点的顺序，即CLOSED节点的存放顺序，不是本身被生成的顺序解是图中的虚线扩展过程中没有生成已有的节点说明：67人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,2)E(3,2)(3,1)S例：迷宫问题(3,3)(3,4)(4,4)目标节点ENE后生成的节点在左边没有已有节点人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,68宽度优先（先在左）深度优先（后在左）人4321宽度优先（先在左）深度优先人432169例：四皇后问题QQQQQQQQQQXQQQQQQXQQQQ后在左例：四皇后问题QQQQQQQQQQXQQQQQQXQQQQ后70练习：根据下列迷宫，用深度优先搜索算法寻找出从入口到出口的一条路径状态：用极坐标表示的人的位置操作符：人向左方、前方、右方前进提示：不要产生已有的状态练习：根据下列迷宫，用深度优先搜索算法寻找出从入口到出口的一71深度优先算法存在问题：先后顺序有误，规定的先后顺序：左前右改变坐标系，极坐标直角坐标对于一个节点，按照规定的操作符顺序，使用所有可能的操作符，产生相应的后继节点深度优先算法存在问题：72(6,0)人向左1向右3向前2(4,0)前右(6,45)(4,45)前前(2,45)右(4,90)左(2,90)右(6,90)出口深度优先搜索算法（没有产生已有的节点）后在左(6,0)人向左向右向前2(4,0)前右(6,45)(4,473思考题：利用宽度优先与深度优先算法解决八数码问题？思考题：743.2.3等代价搜索宽度优先搜索技术找到了应用算符数目最少或者深度最浅的解如果认为每一个操作符的代价相等，则宽度优先搜索技术就可以找到了代价最小的路径或解3.2.3等代价搜索宽度优先搜索技术找到了应用算符数目最75所有操作符代价相等找到最短的路径宽度优先算法操作符的代价不相等找到代价最小的路径等代价(代价优先)搜索技术问题推广推广所有操作符代价相等操作符的代价不相等问题推广推广76宽度优先搜索：按照先后顺序取待扩展节点等代价搜索：将初始节点到所有端节点（OPEN中的节点）的局部路径中代价最小的端节点作为下一个要扩展的节点

推广的思路：宽度优先搜索：按照先后顺序取待扩展节点推广的思路：77宽度优先搜索算法等代价搜索算法注：圆圈中的数字表示从起始节点到当前节点的代价宽度优先搜索算法等代价搜索算法注：圆圈中的数字表示从起始节点78符号c(i,j)：从节点i

到它的直接后继节点j

的连接弧线上的代价g(i)：从起始节点S

到某一节点i

的路径的代价符号79选取待扩展节点的原则：以g(i)

的递增顺序排列OPEN表以g(i)

最小的节点作为下一个要扩展的节点选取待扩展节点的原则：80①

将起始节点S放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求得一个解。否则令g(S)＝0②如果OPEN是空表，则无解，失败退出等代价搜索算法：①将起始节点S放到未扩展节点表OPEN中。如果此起始节点为81③

从OPEN表中选择一个节点i

，使其g(i)

为最小。如果有几个节点都合格，则分两种情况，如果有目标节点，则选择一个目标节点作为节点i

；否则，从中任选一个节点作为节点i

。把节点i

从OPEN表移至扩展节点表CLOSED中③从OPEN表中选择一个节点i，使其g(i)为最小82④

如果节点i为目标节点，则求得一个解；否则，继续下一步⑤

扩展节点i。如果没有后继节点，则转向第②步④如果节点i为目标节点，则求得一个解；否则，继续下一步83⑥

对于节点i

的每个后继节点j

，计算

g(j)＝g(i)+c(i，j)并把所有后继节点j

放进OPEN表。提供回到节点i的指针⑦

转向第②步⑥对于节点i的每个后继节点j，计算84人工智能第3章确定性推理课件85说明几点：第一、上述算法实际是树的搜索算法。如果是图的搜索，则要检查新产生的后继节点是否已经在OPEN表或CLOSED表，若是，比较新、旧代价并调整指针（保留代价小的路径）说明几点：86第二、OPEN表是一张线性表，其元素按代价的递增顺序排列。表的基本操作：删除、定位与插入第二、OPEN表是一张线性表，其元素按代价的递增顺序排列。表87例：迷宫人4321代价：关键位置点之间的水平与垂直距离之和例：迷宫人4321代价：关键位置点之间的水平与垂直距离之和88人4S3E2N1W(1,1)N3(2,3)3(2,4)4N1S1(2,2)4(1,4)5(3,4)5W1E1(3,2)5(3,1)6E1S2(3,3)6(4,4)6E1S1XX可以扩展(3,1)6(3,3)6人4S3E2N1W(1,1)N3(2,3)3(2,4)489例：最小路程问题。下图是五个城市的交通路线图，图中的数字是公里数。问题是找到一条从A到E的最短路线。

操作符:从一个城市走向另一个城市（方向大体上从A指向E）例：最小路程问题。下图是五个城市的交通路线图，图中的数字是公90人工智能第3章确定性推理课件91人工智能第3章确定性推理课件92A(0)B(2)C(3)D(7)C(5)D(6)D(7)E(13)E(11)237344105CLOSEDA(0)B(2)C(3)D(7)C(5)D(6)D(7)E(93思考题对于下列迷宫，用等代价搜索算法寻找出从入口到出口的一条路径代价：关键位置之间的路程，其中π=3.0思考题对于下列迷宫，用等代价搜索算法寻找出从入口到出口的一条94等代价算法存在的问题：如果当前扩展出来的节点，已经存在，需要比较新旧代价，一般先画出节点，再删除代价大的节点。也可以不画代价大的节点。但是不能有的地方画，有点的地方不画。等代价算法存在的问题：95(6,0)0人向左1向右3向前2(4,0)2前2右4.5(6,45)4.5(4,45)5(2,0)4前2右3左2(2,45)7前3(4,90)8(0,0)

9前2右1.5(2,90)8.5右2(6,90)10出口等代价搜索算法XX24.531.5前2(4,45)6.5左2(2,90)10XX(4,90)10.5前2X右2(6,45)7X(6,0)0人向左向右向前2(4,0)2前2右4.5(696说明：当扩展某一个节点生成全部后继节点时出现搜索图中已经有的节点（在Open或者Closed表的节点），在等代价搜索中有两种处理策略：只保留新产生的节点，已有的节点都不保留借助于有序算法中的处理策略（上述例子中的方法）说明：当扩展某一个节点生成全部后继节点时出现搜索图中已经有的97三种盲目搜索技术的比较主要差别：在于挑选要扩展节点的规则不同宽度优先搜索技术：先扩展出来的节点随后先扩展，OPEN表是队列深度优先搜索技术：后扩展出来的节点随后先扩展，OPEN表是堆栈等代价搜索技术：选取OPEN表中代价最小的节点先扩展，OPEN表是线性表（以局部代价的递增顺序排列）三种盲目搜索技术的比较98宽度优先深度优先代价优先三种算法的比较（流程图）宽度优先深度优先代价优先三种算法的比较（流程图）99人工智能ArtificialIntelligence(AI)人工智能100第3章确定性推理

3.1图的搜索策略3.2盲目搜索3.3启发式搜索3.4与或树搜索（补充）3.5博弈树搜索（补充）3.6消解原理第3章确定性推理3.1图的搜索策略101解决实际问题的两个关键之处：①问题的表达状态空间法问题归约法谓词逻辑法②问题的求解搜索技术推理技术解决实际问题的两个关键之处：①问题的表达②问题的求解102盲目与启发式搜索：状态空间法、图的搜索技术与或树搜索：问题归约法、与或图的特例的搜索技术博弈树搜索：状态空间法＋问题归约法、双人博弈的特殊搜索技术消解原理：谓词逻辑法、推理技术盲目与启发式搜索：状态空间法、图的搜索技术1033.1图搜索策略

状态空间中：状态初始状态目标状态操作符图中有：节点初始节点目标节点有向弧状态空间法与图的对应关系3.1图搜索策略状态空间中：图中有：状态空间法与图的对应104在状态空间中，解是从初始状态到目标状态的操作符序列在图中，解是从初始节点到目标节点的一条路径解的含义：在状态空间中，解是从初始状态到目标状态的操作符序列解的含义：105状态：(城市名)算子：常德→益阳 益阳→常德 益阳汨罗 益阳宁乡 益阳娄底

…？？？？必须记住哪些点走过了必须记住下一步还可以走哪些点必须记住从目标返回的路径状态：(城市名)？？？？必须记住哪些点走过了必须记住下一步还106必须记住哪些点走过了必须记住下一步还可以走哪些点必须记住从目标返回的路径OPEN表(记录还没有扩展的点)CLOSED表(记录已经扩展的点)每个表示状态的节点结构中必须有指向父节点的指针必须记住哪些点走过了必须记住下一步还可以走哪些点必须记住从目107图的搜索策略：图搜索过程的一般步骤（基本思路、框架），经过细化后得到具体算法：盲目搜索技术（深度、宽度、代价优先算法）启发式搜索技术（有序算法、A*算法）图的搜索策略：图搜索过程的一般步骤（基本思路、框架），经过细108图搜索中的两个重要记号（符号）：OPEN表：存放待扩展的节点CLOSED表：存放已扩展的节点注意：在与或树搜索中也要用到这两张表图搜索中的两个重要记号（符号）：109数据结构中图的遍及：从图某一个节点出发，访问遍图中其余节点，且每一个节点仅仅被访问一次。当前图的搜索技术中，有两个特殊之处：搜索前，图并没有生成好，需要边生成图边搜索搜索从起始节点（初始状态）开始，到目标节点（目标状态）结束，不需要搜索所有可能的节点数据结构中图的遍及：从图某一个节点出发，访问遍图中其余节点，110盲目搜索是指无问题先验信息的搜索技术特点：OPEN表中节点的排列是人为规定的一般只适合于求解比较简单的一些问题3.2盲目搜索盲目搜索是指无问题先验信息的搜索技术3.2盲目搜索111图的盲目搜索技术分成：宽度优先搜索技术深度优先搜索技术等代价（代价优先）搜索技术图的盲目搜索技术分成：1123.2.1宽度优先搜索

宽度优先搜索：以接近起始节点的程度依次扩展节点的搜索技术（即：离起始节点近的节点先被扩展）扩展节点的原则：先扩展出来的节点随后优先被扩展（生成其所有的后继节点）3.2.1宽度优先搜索宽度优先搜索：以接近起始节点的程113人工智能第3章确定性推理课件114①

把起始节点放到OPEN表中(如果该起始节点为一目标节点，则得到解)②

如果OPEN是个空表，则无解，失败退出；否则继续下一步宽度优先搜索算法：①把起始节点放到OPEN表中(如果该起始节点为一目标节115③

把第一个节点(记作节点n)从OPEN

表移出，并把它放入

CLOSED的已扩展节点表中④

扩展节点n。如果没有后继节点，则转向第②步③把第一个节点(记作节点n)从OPEN表移出，并116⑤

把n

的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n

的指针⑥

如果n

的任一个后继节点是个目标节点，则找到一个解（反向追踪得到从目标节点到起始节点的路径），成功退出，否则转向第②步⑤把n的所有后继节点放到OPEN表的末端，并提供从这些117OPEN表是存放待扩展的节点，从数据结构上来说，它是一个先进先出的队列CLOSED表是存放已被扩展过的节点（包括有后继节点的非端节点和无后继节点的端节点）说明：OPEN表是存放待扩展的节点，从数据结构上来说，它是一个先118流程图

流程图119①搜索过程产生的节点和指针构成一棵隐式定义的状态空间树的子树，称之为搜索树注意几点：①搜索过程产生的节点和指针构成一棵隐式定义的状态空间树的子树120②

宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径（所用操作符最少）②宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的121例：八数码问题初始状态目标状态操作符：2831476512384765空1243例：八数码问题初始状态目标状态操作符：28314765123122状态：长度为9的一维数组（q1,q2,…,q9）其中，qi

取0,1,…,8个数，0表示空格，且取值互不相同状态：长度为9的一维数组123

如果记空格的位置为P，这时空格的移动规则是：123456789123456789PP-3P+1P+3P-1数字表示位置如果记空格的位置为P，这时空格的移动规则是：124

顺序规则前提条件应用结果1左移P≠1,4,7P位置与P-1

位置上的元素互换2上移P≠1,2,3

P-33下移P≠7,8,9

P+34右移P≠3,6,9

P+1空格移动规则P-3PP+3P-1P+1123456789顺序规则前提条件应用结果1左移P≠1,4,7125为了记录后继节点与父节点之间的指针，我们将长度为9的数组扩大到长度为11的数组，其中一个元素记录该节点的父节点标志，另一个元素记录操作符的序号操作符父节点状态为了记录后继节点与父节点之间的指针，我们将长度为9的数组126OPEN表的存储形式：队列插入端（队尾）删除端（队头）队列：一种先进先出的线性表，允许在表的一端进行插入、另一端进行删除OPEN表的存储形式：队列插入端（队尾）删除端（队头）队列：127CLOSED表的存储形式：也可以用队列父符插入端（队尾）特殊的队列：只进不出的队列，只允许在表的一端进行插入CLOSED表的存储形式：也可以用队列父符插入端（队尾）特殊128某一个节点的父节点标志：记录CLOSED表中的父节点的序号起始节点的父节点标志和操作符：不作记录或记录为负某一个节点的父节点标志：129搜索过程（按照程序运行方式）①

起始节点放到OPEN表283104765②

OPEN不为空，继续28314765搜索过程（按照程序运行方式）①起始节点放到OPEN表2130③

将第一个节点n

从OPEN

表中移出，并放到CLOSED表中00283104765OPEN表CLOSED表节点n1③将第一个节点n从OPEN表中移出，并放到CLO131④

扩展节点n

283014765

203184765

283164705

28314076500283104765扩展28314765④扩展节点n283014765203184765132⑤将节点n的所有后继节点放到OPEN

表的末端，并提供这些后继节点回到n

的指针11283014765122031847651328316470514283140765OPEN表符父00283104765CLOSED⑤将节点n的所有后继节点放到OPEN表的末端，并133⑥

后继节点中无目标节点，转到②②

OPEN表不为空，继续⑥后继节点中无目标节点，转到②②OPEN表不为空，继134③

将第一个节点n

从OPEN

表中移出，并放到CLOSED表中OPEN表CLOSED表1220318476513283164705142831407650028310476511283014765节点n12③将第一个节点n从OPEN表中移出，并放到CLO135④

扩展节点n

083214765

2837140651128301476528314765④扩展节点n08321476528371406136⑤将节点n

的所有后继节点放到OPEN表的末端，并提供这些后继节点回到n的指针122031847651328316470514283140765OPEN表2208321476523283714065⑤将节点n的所有后继节点放到OPEN表的末端，并137….一直继续下去，而且不产生已经产生过的节点（状态），防止死循环。在程序中每一个新产生的节点必须与OPEN和CLOSED表中状态进行比较，判断是否已经产生过，只保留从未产生过的节点….138最后的OPEN表：93234180765103283064175112283160754121208143765131283145706144830214765143813204765152283704615154283714650163123784065164123804765目标节点12384765最后的OPEN表：932341807651032830641139最后的CLOSED表：2831047651128301476512203184765132831647051428314076522083214765232837140653102318476534230184765123456789最后的CLOSED表：28310476511283014761404128316407544283164750522801437505328314576064803214765742837146058312308476510111213141516164123804765目标节点41283164075442831647505228014314183123084765164123804765目标节点31023184765168122031847652831047653183123084765164123804765目标节点3101422831476528314765231847652831647528314765214383214765283714652318476523184765281437652831647528316475283145768321476528371465123847652341876528364175283167542814376528314576832147658132476512378465123847652837461528371465先生成的节点在左目标节点283147652831476523184765283164143（先扩展的节点画在左边）生成后继节点的顺序（先扩展的节点画在左边）生成后继节点的顺序144OPEN与CLOSED表的存储形式的简化CLOSEDOPEN加入扩展节点OPEN与CLOSED表的存储形式的简化CLOSEDOPEN145状态：111状态：212状态：313状态：414状态：522状态：623状态：731状态：834状态：941状态：1044状态：1152状态：1253状态：1364状态：1474状态：1583状态：1693状态：17103状态：18112状态：19121状态：20131状态：21144状态：22143状态：23152状态：24154状态：25163状态：26164状态：27CO123456789101112131415161718192021222324252627CO状态：111状态：212状态：313状态：414状态：5146人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,2)(1,4)(3,4)WE(3,2)(3,1)ES(3,3)(4,4)ES目标节点X例：迷宫问题人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,147例：四皇后问题QQQQQQQQQQQQQQQQQQQXQQQQQQQQQXQQQQX例：四皇后问题QQQQQQQQQQQQQQQQQQQXQQQ148练习：根据下列迷宫，用宽度优先搜索算法寻找出从入口到出口的一条路径状态：用极坐标表示的人的位置操作符：人向左方、前方、右方前进提示：不要产生已有的状态练习：根据下列迷宫，用宽度优先搜索算法寻找出从入口到出口的一149存在的问题：走步方向不符合人走路的习惯没有标注走步的方向中间改变走步方向的顺序多画搜索树，有解后还再往下扩展存在的问题：150(6,0)人向左1向右3向前2(4,0)前右(6,45)(4,45)(2,0)前右左(2,45)前(4,90)(0,0)前右(2,90)右(6,90)出口宽度优先搜索算法（没有生成已有的状态）先在左XX(6,0)人向左向右向前2(4,0)前右(6,45)(4,4151(6,0)向左1(4,0)前右(4,45)(2,0)前前(2,45)右(4,90)(0,0)前右(6,90)出口宽度优先搜索算法先在左X人向右3向前2(6,0)向左(4,0)前右(4,45)(2,0)前前(2,1523.2.2深度优先搜索

深度优先搜索策略是先扩展最新产生的(即最深的)节点

3.2.2深度优先搜索深度优先搜索策略是先扩展最新产生153节点的深度；①、起始节点(即根节点)的深度为0。②、任何其它节点的深度等于其父辈节点深度加上1。

节点的深度；154深度优先搜索的基本思路：先扩展最深的节点。当出现没有后继节点时，换到旁边的次深节点后生成的节点画在左边深度优先搜索的基本思路：后生成的节点画在左边155①

把起始节点S放到未扩展节点的OPEN表中。如果此节点为一目标节点，则得到解②

如果OPEN

为一空表，则无解、失败退出含有深度界限的深度优先搜索算法：①把起始节点S放到未扩展节点的OPEN表中。如果此156深度界限的设置：为了避免出现过深的路径，搜索过程要设置一个深度界限对于等于深度界限的任何节点，当作没有后继节点的节点来看待缺点：可能丢失解深度界限的设置：157③把第一个节点(记作节点n)从OPEN

表移到CLOSED

表④

如果节点n的深度等于最大深度，则转向②③把第一个节点(记作节点n)从OPEN表移到CL158⑤

扩展节点n，产生其全部后继节点，并把它们放入OPEN

表的前头。如果没有后继节点，则转向②⑥

如果后继节点中有任一个节点为目标节点，则求得一个解（反向追踪从目标节点到起始节点的路径），成功退出；否则，转向②⑤扩展节点n，产生其全部后继节点，并把它们放入OPE159人工智能第3章确定性推理课件160人工智能第3章确定性推理课件161说明：现在的OPEN表是一个堆栈，后进先出说明：162深度界限为4后生成的节点画在左边深度界限为4后生成的节点画在左边16328314765283147652318476528316475283147652143283164752831647528316754后生成的节点在左283167542816375428364175832641752836417528143765283145762831457628314576283157462814376528143765248137652318476523184765234187652341876523418576123847651238476512378465目标节点283147652831476523184765283164164例：八数码问题深度界限为5后生成的节点画在左边例：八数码问题深度界限为5后生成的节点画在左边165说明：状态旁边的数字表示该节点生成后继节点的顺序，即CLOSED节点的存放顺序，不是本身被生成的顺序解是图中的虚线扩展过程中没有生成已有的节点说明：166人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,2)E(3,2)(3,1)S例：迷宫问题(3,3)(3,4)(4,4)目标节点ENE后生成的节点在左边没有已有节点人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,167宽度优先（先在左）深度优先（后在左）人4321宽度优先（先在左）深度优先人4321168例：四皇后问题QQQQQQQQQQXQQQQQQXQQQQ后在左例：四皇后问题QQQQQQQQQQXQQQQQQXQQQQ后169练习：根据下列迷宫，用深度优先搜索算法寻找出从入口到出口的一条路径状态：用极坐标表示的人的位置操作符：人向左方、前方、右方前进提示：不要产生已有的状态练习：根据下列迷宫，用深度优先搜索算法寻找出从入口到出口的一170深度优先算法存在问题：先后顺序有误，规定的先后顺序：左前右改变坐标系，极坐标直角坐标对于一个节点，按照规定的操作符顺序，使用所有可能的操作符，产生相应的后继节点深度优先算法存在问题：171(6,0)人向左1向右3向前2(4,0)前右(6,45)(4,45)前前(2,45)右(4,90)左(2,90)右(6,90)出口深度优先搜索算法（没有产生已有的节点）后在左(6,0)人向左向右向前2(4,0)前右(6,45)(4,4172思考题：利用宽度优先与深度优先算法解决八数码问题？思考题：1733.2.3等代价搜索宽度优先搜索技术找到了应用算符数目最少或者深度最浅的解如果认为每一个操作符的代价相等，则宽度优先搜索技术就可以找到了代价最小的路径或解3.2.3等代价搜索宽度优先搜索技术找到了应用算符数目最174所有操作符代价相等找到最短的路径宽度优先算法操作符的代价不相等找到代价最小的路径等代价(代价优先)搜索技术问题推广推广所有操作符代价相等操作符的代价不相等问题推广推广175宽度优先搜索：按照先后顺序取待扩展节点等代价搜索：将初始节点到所有端节点（OPEN中的节点）的局部路径中代价最小的端节点作为下一个要扩展的节点

推广