第3章(搜索推理技术1-图盲目搜索)

第3章搜索推理原理3.1图的搜索策略3.2盲目搜索3.3启发式搜索3.4与或树搜索（补充）3.5博弈树搜索（补充）3.6消解原理解决实际问题的两个关键之处：①问题的表达状态空间法问题归约法谓词逻辑法②问题的求解搜索技术推理技术盲目与启发式搜索：状态空间法、图的搜索技术与或树搜索：问题归约法、与或图的特例的搜索技术博弈树搜索：状态空间法＋问题归约法、双人博弈的特殊搜索技术消解原理：谓词逻辑法、推理技术3.1图搜索策略状态空间中：状态初始状态目标状态操作符图中有：节点初始节点目标节点有向弧状态空间法与图的对应关系在状态空间中，解是从初始状态到目标状态的操作符序列在图中，解是从初始节点到目标节点的一条路径解的含义：图的搜索策略：图搜索过程的一般步骤（基本思路、框架），经过细化后得到具体算法：盲目搜索技术（深度、宽度、代价优先算法）启发式搜索技术（有序算法、A*算法）图搜索中的两个重要记号（符号）：OPEN表：存放待扩展的节点CLOSED表：存放已扩展的节点注意：在与或树搜索中也要用到这两张表数据结构中图的遍及：从图某一个节点出发，访问遍图中其余节点，且每一个节点仅仅被访问一次。当前图的搜索技术中，有两个特殊之处：搜索前，图并没有生成好，需要边生成图边搜索搜索从起始节点（初始状态）开始，到目标节点（目标状态）结束，不需要搜索所有可能的节点盲目搜索是指无问题先验信息的搜索技术特点：OPEN表中节点的排列是人为规定的一般只适合于求解比较简单的一些问题3.2盲目搜索图的盲目搜索技术分成：宽度优先搜索技术深度优先搜索技术等代价（代价优先）搜索技术3.2.1宽度优先搜索宽度优先搜索：以接近起始节点的程度依次扩展节点的搜索技术（即：离起始节点近的节点先被扩展）扩展节点的原则：先扩展出来的节点随后优先被扩展（生成其所有的后继节点）①把起始节点放到OPEN表中(如果该起始节点为一目标节点，则得到解)②如果OPEN是个空表，则无解，失败退出；否则继续下一步宽度优先搜索算法：③把第一个节点(记作节点n)从OPEN表移出，并把它放入CLOSED的已扩展节点表中④扩展节点n。如果没有后继节点，则转向第②步⑤把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针⑥如果n的任一个后继节点是个目标节点，则找到一个解（反向追踪得到从目标节点到起始节点的路径），成功退出，否则转向第②步OPEN表是存放待扩展的节点，从数据结构上来说，它是一个先进先出的队列CLOSED表是存放已被扩展过的节点（包括有后继节点的非端节点和无后继节点的端节点）说明：流程图①搜索过程产生的节点和指针构成一棵隐式定义的状态空间树的子树，称之为搜索树注意几点：②宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径（所用操作符最少）例：八数码问题初始状态目标状态操作符：2831476512384765空1243状态：长度为9的一维数组（q1,q2,…,q9）其中，qi取0,1,…,8个数，0表示空格，且取值互不相同如果记空格的位置为P，这时空格的移动规则是：123456789123456789PP-3P+1P+3P-1数字表示位置顺序规则前提条件应用结果1左移P≠1,4,7P位置与P-1位置上的元素互换2上移P≠1,2,3P-33下移P≠7,8,9P+34右移P≠3,6,9P+1空格移动规则P-3PP+3P-1P+1123456789为了记录后继节点与父节点之间的指针，我们将长度为9的数组扩大到长度为11的数组，其中一个元素记录该节点的父节点标志，另一个元素记录操作符的序号操作符父节点状态OPEN表的存储形式：队列插入端（队尾）删除端（队头）队列：一种先进先出的线性表，允许在表的一端进行插入、另一端进行删除CLOSED表的存储形式：也可以用队列父符插入端（队尾）特殊的队列：只进不出的队列，只允许在表的一端进行插入某一个节点的父节点标志：记录CLOSED表中的父节点的序号起始节点的父节点标志和操作符：不作记录或记录为负搜索过程（按照程序运行方式）①起始节点放到OPEN表283104765②OPEN不为空，继续28314765③将第一个节点n从OPEN表中移出，并放到CLOSED表中00283104765OPEN表CLOSED表节点n1④扩展节点n28301476520318476528316470528314076500283104765扩展28314765⑤将节点n的所有后继节点放到OPEN表的末端，并提供这些后继节点回到n的指针11283014765122031847651328316470514283140765OPEN表符父00283104765CLOSED⑥后继节点中无目标节点，转到②②OPEN表不为空，继续③将第一个节点n从OPEN表中移出，并放到CLOSED表中OPEN表CLOSED表1220318476513283164705142831407650028310476511283014765节点n12④扩展节点n0832147652837140651128301476528314765⑤将节点n的所有后继节点放到OPEN表的末端，并提供这些后继节点回到n的指针122031847651328316470514283140765OPEN表2208321476523283714065………………….一直继续下去，而且不产生已经产生过的节点（状态），防止死循环。在程序中每一个新产生的节点必须与OPEN和CLOSED表中状态进行比较，判断是否已经产生过，只保留从未产生过的节点最后的OPEN表：93234180765103283064175112283160754121208143765131283145706144830214765143813204765152283704615154283714650163123784065164123804765目标节点12384765最后的CLOSED表：28310476511283014765122031847651328316470514283140765220832147652328371406531023184765342301847651234567894128316407544283164750522801437505328314576064803214765742837146058312308476510111213141516164123804765目标节点83123084765164123804765目标节点3102318476516812203184765283104765312831476528314765231847652831647528314765214383214765283714652318476523184765281437652831647528316475283145768321476528371465123847652341876528364175283167542814376528314576832147658132476512378465123847652837461528371465先生成的节点在左目标节点（先扩展的节点画在左边）生成后继节点的顺序OPEN与CLOSED表的存储形式的简化CLOSEDOPEN加入扩展节点状态：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人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例：迷宫问题例：四皇后问题QQQQQQQQQQQQQQQQQQQXQQQQQQQQQXQQQQX大家听懂了“宽度优先算法”？基本听懂（85％以上）大概听懂（70％以上）似懂非懂（50％左右）没有听懂（25％以下）课堂作业（写上学号与姓名）根据下列迷宫，用宽度优先搜索算法寻找出从入口到出口的一条路径状态：用极坐标表示的人的位置操作符：人向左方、前方、右方前进提示：不要产生已有的状态(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)向左1(4,0)前右(4,45)(2,0)前前(2,45)右(4,90)(0,0)前右(6,90)出口宽度优先搜索算法先在左X人向右3向前2课堂作业存在主要问题：1、搜索过程画成图的形式，将导致反向追踪路径出现歧义2、操作符使用混乱，搜索树不规范。3、画出整棵搜索树3.2.2深度优先搜索深度优先搜索策略是先扩展最新产生的(即最深的)节点节点的深度；①、起始节点(即根节点)的深度为0。②、任何其它节点的深度等于其父辈节点深度加上1。深度优先搜索的基本思路：先扩展最深的节点。当出现没有后继节点时，换到旁边的次深节点后生成的节点画在左边①把起始节点S放到未扩展节点的OPEN表中。如果此节点为一目标节点，则得到解②如果OPEN为一空表，则无解、失败退出含有深度界限的深度优先搜索算法：深度界限的设置：为了避免出现过深的路径，搜索过程要设置一个深度界限对于等于深度界限的任何节点，当作没有后继节点的节点来看待缺点：可能丢失解③把第一个节点(记作节点n)从OPEN表移到CLOSED表④如果节点n的深度等于最大深度，则转向②⑤扩展节点n，产生其全部后继节点，并把它们放入OPEN表的前头。如果没有后继节点，则转向②⑥如果后继节点中有任一个节点为目标节点，则求得一个解（反向追踪从目标节点到起始节点的路径），成功退出；否则，转向②说明：现在的OPEN表是一个堆栈，后进先出例：八数码问题深度界限为5后生成的节点画在左边深度界限为4后生成的节点画在左边说明：状态旁边的数字表示该节点生成后继节点的顺序，即CLOSED节点的存放顺序，不是本身被生成的顺序解是图中的虚线扩展过程中没有生成已有的节点人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,2)E(3,2)(3,1)S例：迷宫问题(3,3)(3,4)(4,4)目标节点ENE后生成的节点在左边没有已有节点宽度优先（先在左）深度优先（后在左）人4321例：四皇后问题QQQQQQQQQQXQQQQQQXQQQQ后在左课堂作业根据下列迷宫，用深度优先搜索算法寻找出从入口到出口的一条路径状态：用极坐标表示的人的位置操作符：人向左方、前方、右方前进提示：不要产生已有的状态(6,0)人向左1向右3向前2(4,0)前右(6,45)(4,45)前前(2,45)右(4,90)左(2,90)右(6,90)出口深度优先搜索算法（没有产生已有的节点）后在左(6,0)(4,0)前右(4,45)前(2,45)右(4,90)右(6,90)出口深度优先搜索算法（没有产生已有的节点）后在左人向右3向前2思考题：（每人独立完成）利用宽度优先与深度优先算法解决八数码问题？（要求用C/C++语言编写出核心代码，考核的指标分成零、一、二、五、多步）3.2.3等代价搜索宽度优先搜索技术找到了应用算符数目最少或者深度最浅的解如果认为每一个操作符的代价相等，则宽度优先搜索技术就可以找到了代价最小的路径或解所有操作符代价相等找到最短的路径宽度优先算法操作符的代价不相等找到代价最小的路径等代价(代价优先)搜索技术问题推广推广宽度优先搜索：按照先后顺序取待扩展节点等代价搜索：将初始节点到所有端节点（OPEN中的节点）的局部路径中代价