人工智能第三章_搜索策略-2

2019/9/71启发式搜索启发式知识指导OPEN表排序的一般图搜索：全局排序——对OPEN表中的所有节点排序，使最有希望的节点排在表首。A算法，A*算法（掌握！）局部排序——仅对新扩展出来的子节点排序，使这些新节点中最有希望者能优先取出考察和扩展；爬山法（了解，对深度优先法的改进）；2019/9/72简单的搜索策略：g(n)≡0,f(n)=h(n),局部排序——只排序新扩展出来的子节点，即局部排序简单易行，适用于不要求最优解答的问题求解任务。1）爬山法——实现启发式搜索的最简单方法。类似于人爬山——只要好爬，总是选取最陡处，以求快速登顶。求函数极大值问题——非数值解法，依赖于启发式知识，试探性地逐步向顶峰逼近适用于能逐步求精的问题。爬山法特点：只能向上，不准后退，从而简化了搜索算法；体现在：*从当前状态节点扩展出的子节点（相当于找到上爬的路径）中，将h(n)最小的子节点（对应于到顶峰最近的上爬路径）作为下一次考察和扩展的节点，其余子节点全部丢弃。不需设置OPEN和CLOSE表，因为没有必要保存任何待扩展节点；爬山法对于单一极值问题（登单一山峰）十分有效而又简便,对于具有多极值的问题无能为力——会错登上次高峰而失败：不能到达最高峰。回溯策略和爬山法2019/9/732）回溯策略可以有效地克服爬山法面临的困难——保存了每次扩展出的子节点，并按h(n)值从小到大排列。相当于爬山的过程中记住了途经的岔路口——路径搜索失败时回溯（后退），向另一路径方向搜索回溯策略和爬山法2019/9/742）回溯策略递归过程——实现回溯策略的有效方式算法就取名为BACKTRACK(n),参数n为当前被扩展的节点，初次调用时n即为初始状态节点s；分二个部分：*判断当前节点n的状态，*作搜索工作——扩展节点n，递归调用该算法，处理返回结果。回溯策略和爬山法2019/9/75令PATH、SNL、n、n'为局部变量：·PATH--节点列表，指示解答路径；·SNL--当前节点扩展出的子节点列表；·MOVE-FIRST(SNL)--把SNL表首的节点移出，作为下一次要加以扩展的节点；·n、n‘--分别指示当前考察和下一次考察的节点。该递归过程的算法就取名为BACKTRACK(n),参数n为当前被扩展的节点，算法的初次调用式是BACKTRACK(s),s即为初始状态节点。算法的步骤如下：（1）若n是目标状态节点，则算法的本次调用成功结束，返回空表；（2）若n是失败状态，则算法的本次调用失败结束，返回'FAIL'；（3）扩展节点n，将生成的子节点置于列表SNL，并按评价函数f(k)=h(k)的值从小到大排序（k指示子节点）；（4）若SNL为空，则算法的本次调用失败结束，返回'FAIL'；（5）n'=MOVE-FIRST(SNL)；（6）PATH=BACKTRACK(n')；（7）若PATH='FAIL',返回到语句（4）；（8）将n'加到PATH表首，算法的本次调用成功结束，返回PATH。2019/9/762）回溯策略三种失败状态：不合法状态（如传教士和野人问题中所述的那样）旧状态重现（如八数码游戏中某一棋盘布局的重现，会导致搜索算法死循环），状态节点深度超过预定限度（例如八数码游戏中，指示解答路径不超过6步）。回溯条件失败状态，由算法第（2）句指示；搜索进入“死胡同”，由该算法的第(4)句定义。回溯策略和爬山法2019/9/772）回溯策略解答路径的生成——从相应于目标状态节点的空表开始，递归返回PATH。影响回溯算法效率的关键因素——回溯次数。回溯——搜索到失败状态时的一种弥补行为，准确选择下一步搜索考察的节点——大幅度减少甚至避免回溯。设计好的启发式函数h(n)是至关重要的。回溯策略和爬山法2019/9/78课堂练习:提高题在应用递归回溯算法解决四皇后的问题中，若按行的序号从小到大试探性放置各列的皇后，请画出搜索图，并指出分别从算法第2步和第4步回溯的次数。2019/9/79定义L，为表示清晰起见,L表中只记载皇后所在列,皇后所在行可由在L表中的先后位置指示,例如L=(13)指示两个皇后位置分别为第1行第1列和第2行第3列。搜索图(树)如右图所示:共回溯22次,其中算法第2步的回溯18次,算法第4次的回溯4次。2019/9/7103.4问题归约和与或图启发式搜索问题归约是人求解问题常用的策略：把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解只有子问题全部解决时，问题才算解决；问题的解答由子问题的解答联合构成。本节主要内容：问题归约的描述（理解）与或图搜索的基本过程（理解）与或图的启发式搜索（掌握）2019/9/711问题归约法（ProblemReductionRepresentation）子问题1子问题n原始问题子问题集本原问题2019/9/712问题归约可以用三元组表示：（S0，O，P），其中S0是初始问题，即要求解的问题；P是本原问题集，其中的每一个问题是不用证明的，自然成立的，如公理、已知事实等，或已证明过的问题；O是操作算子集，它是一组变换规则，通过一个操作算子把一个问题化成若干个子问题。2019/9/713问题归约表示方法就是由初始问题出发，运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的子问题，这样一直进行到产生的问题均为本原问题，则问题得解。2019/9/714看如下符号积分问题：初始问题——∫f(x)dx变换规则——积分规则本原问题——可直接求原函数和积分，如∫sin(x)dx，∫cos(x)dx等。所有问题归约的最终目的是产生本原问题。2019/9/715符号积分问题∫（sin3x+x4/(x2+1)）dx=∫sin3xdx+∫(x4/(x2+1))dx=∫-(1-cos2x)dcosx+∫(x2-1+1/(1+x2))dx=(∫-dcosx+cos2xdcosx)+(∫x2dx-∫dx+∫(1/(1+x2))dx）=-cosx+cos3x/3+x3/3-x+arctgx2019/9/716分子结构识别问题如何区分分子式相同但分子结构不同的有机化合物成为重要而又困难的问题。著名的专家系统DENDRAL能用于有效地识别分子结构，该系统建立了一套重写规则去把分子式重写为原子数较少的分子式和原子间结合关系的混合结构2019/9/717问题归约的实质：★从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2019/9/718应用问题归约策略得到的状态空间图，也称为“与或图”逻辑“与”关系——用圆弧将几条节点间关联弧连接在一起表示问题分解为子问题；子问题的状态联合起来构成问题状态。子问题全部解决才会导致问题的解决；逻辑“或”关系：①问题可以有多种分解方式；②问题（子问题）可能激活多个状态变迁操作；只要一种分解方式或状态变迁操作能导致最终的解答成功即可；导致多个可能的解答。与或图2019/9/719用AND-OR图把问题归约为子问题替换集合。如，假设问题A既可通过问题C1与C2，也可通过问题C3、C4和C5，或者由单独求解问题C6来解决，如下图所示。图中各节点表示要求解的问题或子问题。与或图2019/9/720梵塔问题问题描述：初始状态下三个盘按A、B、C顺序堆放在1号柱子上；目标状态下三个盘以同样次序顺序堆放在3号柱子上；盘子的搬移规则：每次只能搬一个盘子；较大盘不能压放在较小盘之上；CAB初始状态(111)目标状态(333)CAB132132与或图2019/9/721梵塔问题——状态空间图(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(2,2,1)132CAB(2,2,3)123ABC目标状态(333)CAB1322019/9/722梵塔问题——状态空间图(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)2019/9/723梵塔问题(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)123456789子问题间有交互作用，问题分解注意正确的顺序2019/9/724与或图搜索与或图视为对一般图(或图)的扩展；★引入K-连接父子节点间可以存在“与”关系结果——解图。解答路径往往不复存在，代之以广义的解路径——解图。问题归约求解问题的过程表示为与或图搜索2019/9/725与或图搜索1)与或图搜索的基本概念1、K-连接★从父节点到K个子节点的连接，子节点间有“与”关系；以圆弧指示这些子节点间的“与”关系；一个父节点可以有多个K-连接K-连接间——”或”关系当所有的K都等于1时，与或图蜕化为一般图（或图）。3个子节点2个子节点2019/9/726与或图搜索1)与或图搜索的基本概念2、根、叶、终节点★根节点——无父节点的节点用于指示问题初始状态（和一般图一样）叶节点——无子节点的节点终节点——能用于联合表示目标状态的节点终节点必定是叶节点，反之不然；目标状态——终结点的集合。2019/9/727一些关于与或图的术语HMBCDEFGAN父节点与节点弧线或节点子节点终节点2019/9/728与或图搜索1)与或图搜索的基本概念3、解图的生成★解图纯粹是一种“与”图解图中，节点或节点组间不存在“或”关系；所有叶节点都是终节点2019/9/729与或图搜索1)与或图搜索的基本概念3、解图的生成★自根节点开始选K-连接;从该K-连接指向的每个子节点出发，再选一K-连接;如此反复进行，直到所有K-连接都指向终节点为止.2019/9/7302019/9/731与或图搜索1)与或图搜索的基本概念3、解图的生成★解图纯粹是一种“与”图解图中，节点或节点组间不存在“或”关系；所有叶节点都是终节点与或图中存在“或”关系，搜索到多个解图；2019/9/732与或图搜索2)解图、解图代价、能解节点和不能解节点的定义(1)解图——与或图（记为G）任一节点（记为n）到终节点集合的解图（记为G‘）是G的子图。(1)若n是终节点，则G‘就由单一节点n构成；(2)若n有一K-连接指向子节点n1，n2，…nk,且每个子节点都有到终节点集合的解图，则G‘由该k-连接和所有这些相应于子节点的解图构成;(3)否则不存在n到终节点集合的解图。2019/9/733与或图搜索2)解图、解图代价、能解节点和不能解节点的定义(2)解图代价★——以C(n)指示节点n到终节点集合解图的代价，并令K-连接的代价就为K,则(1)若n是终节点，则C(n)=0；(2)若n有一K-连接指向子节点n1，n2，…nk,且这些子节点每个都有到终节点集合的解图,则C(n)=K+C(n1)+C(n2)+…+C(nk)352019/9/734与或图搜索2)解图、解图代价、能解节点和不能解节点的定义(3)能解节点★(1)终节点是能解节点；(2)若节点n有一K-连接指向子节点n1，n2，…nk,且这些子节点都是能解节点，则n是能解节点；能解节点能解节点能解节点能解节点2019/9/735与或图搜索2)解图、解图代价、能解节点和不能解节点的定义(4)不能解节点★(1)非终节点的叶节点是不能解节点；(2)若节点n的每一个K-连接都至少指向一