西电人工智能9 确定性推理 part2概要

西安电子科技大学ArtificialIntelligence(AI)人工智能主讲：戚玉涛Email：[e-mail]第三章：确定性推理西安电子科技大学内容提要第三章：确定性推理1.推理的基本概念2.搜索策略3.自然演绎推理4.归结演绎推理5.基于规则的演绎推理西安电子科技大学搜索策略搜索策略搜索的基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性与效率西安电子科技大学状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想图搜索的一般过程状态空间的盲目搜索广度优先搜索深度优先搜索代价树搜索状态空间的启发式搜索启发性信息和估价函数A算法和A*算法西安电子科技大学状态空间的搜索策略状态空间搜索算法的数据结构和符号约定OPEN表：未扩展节点表，用于存放刚生成节点CLOSED表：已扩展节点表，用于存放已经扩展或将要扩展节点的S：用表示问题的初始状态G：表示搜索过程所得到的搜索图M：表示当前扩展节点新生成的且不为自己先辈的子节点集西安电子科技大学状态空间的搜索策略图搜索的一般过程(1)把初始节点S放入未扩展节点表OPEN表，并建立目前仅包含S的图G；(2)检查OPEN表是否为空，若为空，则问题无解，失败退出；(3)把OPEN表的第一个节点取出放入已扩展节点表CLOSED表，并记该节点为节点n；(4)考察节点n是否为目标节点。若是则得到了问题的解，成功退出。此时的解为追踪图G中沿着指针（步骤6中设置的指针）从n到初始节点S的路径。西安电子科技大学状态空间的搜索策略图搜索的一般过程(5)扩展节点n，生成一组子节点。把这些子节点中不是节点n先辈的那部分子节点记入集合M，并把这些子节点作为节点n的子节点加入G中(6)针对M中子节点的不同情况，分别作如下处理：①对那些没有在G中出现过的M成员设置一个指向其父节点（即节点n）的指针，并把它放入OPEN表。（新生成的）②对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改它指向父节点的指针。（原生成但未扩展的）③对于那些先前已在G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。（原生成也扩展过的）西安电子科技大学图搜索的一般过程(7)按某种策略对OPEN表中的节点进行排序。(8)转第(2)步。状态空间的搜索策略西安电子科技大学广度优先搜索状态空间的广度优先搜索广度优先搜索的基本思想：从初始节点S开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。未扩展节点表OPEN表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。西安电子科技大学广度优先搜索状态空间的广度优先搜索广度优先搜索算法流程：•(1)把初始节点S放入OPEN表中；•(2)如果OPEN表为空，则问题无解，失败退出；•(3)把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n；•(4)考察节点n是否为目标节点。若是，则得到问题的解，成功退出；•(5)若节点n不可扩展，则转第(2)步；•(6)扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。西安电子科技大学广度优先搜索广度优先搜索的例子：八数码难题在3×3的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0，目标状态Sg，如下图所示。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径。1238476528314765S0Sg西安电子科技大学广度优先搜索八数码难题的宽度优先搜索树西安电子科技大学广度优先搜索在上述广度优先算法中需要注意两个问题：对于任意一个可扩展的节点，总是按照固定的操作符的顺序对其进行扩展（空格左移、上移、右移、下移）。在对任一节点进行扩展的时候，如果所得的某个子节点（状态）前面已经出现过，则立即将其放弃，不再重复画出（不送入OPEN表）。因此，广度优先搜索的本质是，以初始节点为根节点，在状态空间图中按照广度优先的原则，生成一棵搜索树。西安电子科技大学广度优先搜索广度优先搜索的特点：优点：只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。缺点：广度优先搜索盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索效率低。西安电子科技大学状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想图搜索的一般过程状态空间的盲目搜索广度优先搜索深度优先搜索代价树搜索状态空间的启发式搜索启发性信息和估价函数A算法和A*算法西安电子科技大学深度优先搜索状态空间的深度优先搜索深度优先搜索的基本思想：从初始节点S开始，在其子节点中选择一个最新生成的节点进行考察如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。西安电子科技大学深度优先搜索状态空间的深度优先搜索深度优先搜索算法流程：•(1)把初始节点S放入OPEN表中；•(2)如果OPEN表为空，则问题无解，失败退出；•(3)把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n；•(4)考察节点n是否为目标节点。若是，则得到问题的解，成功退出；•(5)若节点n不可扩展，则转第(2)步；•(6)扩展节点n，将其子节点放入OPEN表的首部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。西安电子科技大学深度优先搜索深度优先搜索：八数码难题八数码难题的深度优先搜索如右图首先扩展最新产生的(最深的)节点如果目标节点不在当前搜索的分支上？西安电子科技大学深度优先搜索深度优先搜索与广度优先搜索的唯一区别是：广度优先搜索是将节点n的子节点放入到OPEN表的尾部，而深度优先搜索是把节点n的子节点放入到OPEN表的首部。在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。深度优先搜索本质：以初始节点为根节点，在状态空间图中按照深度优先的原则，生成一棵搜索树。西安电子科技大学有界深度优先搜索有界深度优先搜索：动机：为了防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度，即深度界限。思想：对状态空间的深度优先搜索引入搜索深度界限，设为dm，当搜索深度达到了深度界限而仍未出现目标节点时，就换一个分支进行搜索。西安电子科技大学有界深度优先搜索八数码难题：dm=4西安电子科技大学有界深度优先搜索有界深度优先搜索：问题：如果问题有解，且其路径长度≤dm，则上述搜索过程一定能求得解。但是，若解的路径长度dm,则上述搜索过程就得不到解。这说明在有界深度优先搜索中，深度界限的选择是很重要的。要恰当地给出dm的值是比较困难的。即使能求出解，它也不一定是最优解。西安电子科技大学状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想图搜索的一般过程状态空间的盲目搜索广度优先搜索深度优先搜索代价树搜索状态空间的启发式搜索启发性信息和估价函数A算法和A*算法西安电子科技大学代价树搜索代价树：边上标有代价(或费用)的树称为代价树在代价树中，若用g(x)表示从初始节点S到节点x的代价，用c(x1,x2)表示从父节点x1到子节点x2的代价，则有：g(x2)=g(x1)+c(x1,x2)代价树搜索：考虑边的代价的搜索方法，代价树搜索的目的是为了找到一条代价最小的解路径。代价树搜索方法包括：代价树的广度优先搜索代价树的深度优先搜索西安电子科技大学代价树的广度优先搜索代价树的广度优先搜索基本思想：每次从OPEN表中选择节点往CLOSED表传送时，总是选择其中代价最小的节点。也就是说，OPEN表中的节点在任一时刻都是按其代价从小到大排序的。代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什么位置上。如果问题有解，代价树的广度优先搜索一定可以求得解，并且求出的是最优解。该算法应用的条件：该算法是针对代价树的算法。为了采用该算法对图进行搜索，必须先将图转换为代价树。西安电子科技大学代价树的广度优先搜索代价树的广度优先搜索算法流程：•(1)把初始节点S放入OPEN表中，置S的代价g(S)=0；•(2)如果OPEN表为空，则问题无解，失败退出；•(3)把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n；•(4)考察节点n是否为目标。若是，则找到了问题的解，成功退出；•(5)若节点n不可扩展，则转第(2)步；否则转第(6)步；•(6)扩展节点n，为每一个子节点都配置指向父节点的指针，计算各子节点的代价，并将各子节点放入OPEN表中。并根据各子结点的代价对OPEN表中的全部结点按由小到大的顺序排序。然后转第(2)步。西安电子科技大学代价树的广度优先搜索例子：城市交通问题。设有5个城市，它们之间的交通线路如下方左图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从A市出发到E市，费用最小的交通路线。ABCDE434523城市交通图西安电子科技大学代价树的广度优先搜索解：首先将交通图转化为代价树。具体转化方法如下：从起始节点A开始，把与它直接相邻的节点作为它的子节点对其他节点也做相同的处理若一个节点已经为某节点的直系先辈节点时，就不能作为这个节点的子节点。图中除了起始节点A之外，其它节点都可能要在代价树中出现多次，为了区分它们的多次出现，分别用下标1,2，……标出城市交通图的代价树245AC1B1D1D2E1E2B2C2E3E43434235西安电子科技大学代价树的广度优先搜索解：对此代价树进行广度优先搜索，可得到最优解，如图红线部分为最优解，其代价为8ABCDE434523245AC1B1D1D2E1E2B2C2E3E43434235西安电子科技大学代价树的深度优先搜索代价树的深度优先搜索基本思想：与代价树的广度优先搜索不同，代价树的深度优先搜索是从刚扩展出的子节点中选择一个代价最小的节点送入CLOSED表进行考察，而不是在整个OPEN表中选择代价最小的。西安电子科技大学代价树的深度优先搜索代价树的深度优先搜索算法流程：•(1)把初始节点S放入OPEN表中，置S的代价g(S)=0；•(2)如果OPEN表为空，则问题无解，失败退出；•(3)把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n；•(4)考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；•(5)若节点n不可扩展，则转第(2)步；•(6)扩展节点n，生成其子节点，将这些子节点按边代价由小到大放入Open表的首部，并为每一个子节点设置指向父节点的指针。然后转第(2)步。西安电子科技大学状态空间的盲目搜索状态空间的盲目搜索上述几种搜索方法的本质是，以初始节点为根节点，按照既定的策略对状态空间图进行遍历，并希望能够尽早发现目标节点。由于对状态空间图遍历的策略是既定的，因此这些方法统称为盲目搜索方法。盲目搜索具有较大的盲目性，产生的无用节点较多，效率不高。西安电子科技大学状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想图搜索的一般过程状态空间的盲目搜索广度优先搜索深度优先搜索代价树搜索状态空间的启发式搜索启发性信息和估价函数A算法和A*算法西安电子科技大学启发性信息和估价函数启发式搜索：采用问题自身的特性信息，以指导搜索朝着最有希望的方向前进。启发性信息的概念：启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。启发信息的启发能力越强，扩展的无用结点越少