湘潭大学-人工智能课件-确定性推理-part2

1、Artificial Intelligence (AI)人工智能,第二章：知识表示与推理,内容提要,第二章：知识表示与推理,1.推理的基本概念,2.搜索策略,3.自然演绎推理,4.消解演绎推理,5.基于规则的演绎推理,搜索策略,搜索策略 搜索的基本概念 状态空间的搜索策略 与/或树的搜索策略 搜索的完备性与效率,状态空间的搜索策略,状态空间的搜索策略 状态空间搜索的基本思想 图搜索的一般过程 状态空间的盲目搜索 广度优先搜索 深度优先搜索 代价树搜索 状态空间的启发式搜索 启发性信息和估价函数 A算法和A*算法,状态空间的搜索策略,状态空间搜索算法的数据结构和符号约定 OPEN表：未扩展节点表

2、，用于存放刚生成节点 CLOSED表：已扩展节点表，用于存放已经扩展或将要扩展的节点 S：用表示问题的初始状态 G：表示搜索过程所得到的搜索图 M：表示当前扩展节点新生成的且不为自己先辈的子节点集,状态空间的搜索策略,图搜索的一般过程 (1) 把初始节点S放入未扩展节点表OPEN表，并建立目前仅包含S的图G； (2) 检查OPEN表是否为空，若为空，则问题无解，失败退出； (3) 把OPEN表的第一个节点取出放入已扩展节点表CLOSED表，并记该节点为节点n； (4)考察节点n是否为目标节点。若是则得到了问题的解，成功退出。此时的解为追踪图G中沿着指针（步骤6中设置的指针）从n到初始节点S的路

3、径。,状态空间的搜索策略,图搜索的一般过程 (5) 扩展节点n，生成一组子节点。把这些子节点中不是节点n先辈的那部分子节点记入集合M，并把这些子节点作为节点n的子节点加入G中 (6) 针对M中子节点的不同情况，分别作如下处理： 对那些没有在G中出现过的M成员设置一个指向其父节点（即节点n）的指针，并把它放入OPEN表。（新生成的） 对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改它指向父节点的指针。（原生成但未扩展的） 对于那些先前已在G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。（原生成也扩展过的）,图搜索的一般过程 (7) 按某种策略对OP

4、EN表中的节点进行排序。 (8) 转第(2)步。,状态空间的搜索策略,广度优先搜索,状态空间的广度优先搜索 广度优先搜索的基本思想： 从初始节点S开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。 未扩展节点表OPEN表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。,广度优先搜索,状态空间的广度优先搜索 广度优先搜索算法流程： (1)把初始节点S放入OPEN表中； (2)如果OPEN表为空，则问题无解，失败退出； (3)把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n； (4)考察节点n是否为目标节点。若是，则得到问题的解

5、，成功退出； (5)若节点n不可扩展，则转第(2)步； (6)扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。,广度优先搜索,广度优先搜索的例子：八数码难题 在33的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0，目标状态Sg，如下图所示。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径。,S0,Sg,广度优先搜索,八数码难题的宽度优先搜索树,广度优先搜索,在上述广度优先算法中需要注意两个问题： 对于任意一个可扩展的节点，总是按照固定的操作符的顺序对其进行扩展（空格左移、上移、右移、下移）。 在对任

6、一节点进行扩展的时候，如果所得的某个子节点（状态）前面已经出现过，则立即将其放弃，不再重复画出（不送入OPEN表）。 因此，广度优先搜索的本质是，以初始节点为根节点，在状态空间图中按照广度优先的原则，生成一棵搜索树。,广度优先搜索,广度优先搜索的特点： 优点： 只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。 缺点： 广度优先搜索盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索效率低。,状态空间的搜索策略,状态空间的搜索策略 状态空间搜索的基本思想 图搜索的一般过程 状态空间的盲目搜索 广度优先搜索 深度优先搜索 代价树搜索 状态空间的启发式搜索 启发性信息

7、和估价函数 A算法和A*算法,深度优先搜索,状态空间的深度优先搜索 深度优先搜索的基本思想： 从初始节点S开始，在其子节点中选择一个最新生成的节点进行考察 如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察 依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。,深度优先搜索,状态空间的深度优先搜索 深度优先搜索算法流程： (1) 把初始节点S放入OPEN表中； (2) 如果OPEN表为空，则问题无解 ，失败退出； (3) 把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n； (4) 考察节

8、点n是否为目标节点。若是，则得到问题的解，成功退出； (5) 若节点n不可扩展，则转第(2)步； (6) 扩展节点n，将其子节点放入OPEN表的首部，并为每一个子节点设置 指向父节点的指针，然后转第(2)步。,深度优先搜索,深度优先搜索： 八数码难题 八数码难题的深度优先搜索如右图 首先扩展最新产生的(最深的)节点 如果目标节点不在当前搜索的分支上？,深度优先搜索,深度优先搜索与广度优先搜索的唯一区别是：广度优先搜索是将节点n的子节点放入到OPEN表的尾部，而深度优先搜索是把节点n的子节点放入到OPEN表的首部。 在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点

9、恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。 深度优先搜索本质：以初始节点为根节点，在状态空间图中按照深度优先的原则，生成一棵搜索树。,有界深度优先搜索,有界深度优先搜索： 动机：为了防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度，即深度界限。 思想：对状态空间的深度优先搜索引入搜索深度界限，设为dm，当搜索深度达到了深度界限而仍未出现目标节点时，就换一个分支进行搜索。,有界深度优先搜索,八数码难题：dm=4,有界深度优先搜索,有界深度优先搜索：

10、问题：如果问题有解，且其路径长度 dm ，则上述搜索过程一定能求得解。但是，若解的路径长度 dm,则上述搜索过程就得不到解。这说明在有界深度优先搜索中，深度界限的选择是很重要的。 要恰当地给出dm的值是比较困难的。即使能求出解，它也不一定是最优解。,状态空间的搜索策略,状态空间的搜索策略 状态空间搜索的基本思想 图搜索的一般过程 状态空间的盲目搜索 广度优先搜索 深度优先搜索 代价树搜索 状态空间的启发式搜索 启发性信息和估价函数 A算法和A*算法,代价树搜索,代价树：边上标有代价(或费用)的树称为代价树 在代价树中，若用g(x)表示从初始节点S到节点x的代价，用c(x1,x2)表示从父节点x

11、1到子节点x2的代价，则有： g(x2)=g(x1)+c(x1,x2) 代价树搜索：考虑边的代价的搜索方法，代价树搜索的目的是为了找到一条代价最小的解路径。代价树搜索方法包括： 代价树的广度优先搜索 代价树的深度优先搜索,代价树的广度优先搜索,代价树的广度优先搜索 基本思想：每次从OPEN表中选择节点往CLOSED表传送时，总是选择其中代价最小的节点。也就是说，OPEN表中的节点在任一时刻都是按其代价从小到大排序的。代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什么位置上。 如果问题有解，代价树的广度优先搜索一定可以求得解，并且求出的是最优解。 该算法应用的条件：该算法是

12、针对代价树的算法。为了采用该算法对图进行搜索，必须先将图转换为代价树。,代价树的广度优先搜索,代价树的广度优先搜索算法流程： (1) 把初始节点S放入OPEN表中，置S的代价g(S)=0； (2) 如果OPEN表为空，则问题无解 ，失败退出； (3) 把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n； (4) 考察节点n是否为目标。若是，则找到了问题的解，成功退出； (5) 若节点n不可扩展，则转第(2)步；否则转第(6)步； (6)扩展节点n，为每一个子节点都配置指向父节点的指针，计算各子节点的代价，并将各子节点放入OPEN表中。并根据各子结点的代价对OPEN表中的全部结点按由

13、小到大的顺序排序。然后转第(2)步。,代价树的广度优先搜索,例子：城市交通问题。设有5个城市，它们之间的交通线路如下方左图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从A市出发到E市，费用最小的交通路线。,城市交通图,代价树的广度优先搜索,解：首先将交通图转化为代价树。具体转化方法如下： 从起始节点A开始，把与它直接相邻的节点作为它的子节点 对其他节点也做相同的处理 若一个节点已经为某节点的直系先辈节点时，就不能作为这个节点的子节点。 图中除了起始节点A之外，其它节点都可能要在代价树中出现多次，为了区分它们的多次出现，分别用下标1,2，标出,城市交通图的代价树

14、,代价树的广度优先搜索,解：对此代价树进行广度优先搜索，可得到最优解，如图红线部分为最优解，其代价为8,代价树的深度优先搜索,代价树的深度优先搜索 基本思想：与代价树的广度优先搜索不同，代价树的深度优先搜索是从刚扩展出的子节点中选择一个代价最小的节点送入CLOSED表进行考察，而不是在整个OPEN表中选择代价最小的。,代价树的深度优先搜索,代价树的深度优先搜索算法流程： (1) 把初始节点S放入OPEN表中，置S的代价g(S)=0； (2) 如果OPEN表为空，则问题无解 ，失败退出； (3) 把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n； (4) 考察节点n是否为目标节点。

15、若是，则找到了问题的解，成功退出； (5) 若节点n不可扩展，则转第(2)步； (6) 扩展节点n，生成其子节点，将这些子节点按边代价由小到大放入Open表的首部，并为每一个子节点设置指向父节点的指针。然后转第(2)步。,状态空间的盲目搜索,状态空间的盲目搜索 上述几种搜索方法的本质是，以初始节点为根节点，按照既定的策略对状态空间图进行遍历，并希望能够尽早发现目标节点。 由于对状态空间图遍历的策略是既定的，因此这些方法统称为盲目搜索方法。 盲目搜索具有较大的盲目性，产生的无用节点较多，效率不高。,状态空间的搜索策略,状态空间的搜索策略 状态空间搜索的基本思想 图搜索的一般过程 状态空间的盲目搜

16、索 广度优先搜索 深度优先搜索 代价树搜索 状态空间的启发式搜索 启发性信息和估价函数 A算法和A*算法,启发性信息和估价函数,启发式搜索：采用问题自身的特性信息，以指导搜索朝着最有希望的方向前进。 启发性信息的概念：启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。启发信息的启发能力越强，扩展的无用结点越少。 启发性信息的种类 有效地帮助确定扩展节点的信息 有效的帮助决定哪些后继节点应被生成的信息 能决定在扩展一个节点时哪些节点应从搜索树上删除的信息,启发性信息和估价函数,估价函数：用于评估节点重要性的函数称为估价函数。估价函数的一般形式为： f(x

17、) = g(x)+h(x) g(x)表示从初始节点S0到节点x的代价； h(x)是从节点x到目标节点Sg的最优路径的代价的估计，它体现了问题的启发性信息。 h(x)称为启发函数。,启发性信息和估价函数,例子：八数码难题 设问题的初始状态S0和目标状态Sg如图所示 估价函数为： f(n)=d(n)+W(n) d(n)：表示节点n在搜索树中的深度 W(n)：表示节点n中“错放”的棋子个数 请计算初始状态S0的估价函数值f(S0),S0,Sg,启发性信息和估价函数,计算初始状态S0的估价函数值f(S0) 解：取g(n)=d(n)，h(n)=W(n) 它说明是用从S0到n的路径上的单位代价表示实际代价

18、 用结点n中“错放”的棋子个数作为启发信息。 一般来说，某节点中的“错放”的棋子个数越多，说明它离目标节点越远（代价的估计）。 对初始节点S0，d(S0)=0，W(S0)=3。因此， f(S0)=0+3=3,S0,Sg,状态空间的搜索策略,状态空间的搜索策略 状态空间搜索的基本思想 图搜索的一般过程 状态空间的盲目搜索 广度优先搜索 深度优先搜索 代价树搜索 状态空间的启发式搜索 启发性信息和估价函数 A算法和A*算法,A算法,A算法：在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对OPEN表中的节点进行排序，则该搜索算法为A算法。 由于估价函数中带有问题自身的

19、启发性信息，因此，A算法也被称为启发式搜索算法。 A算法的类型：可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为： 全局择优搜索算法： 从OPEN表的所有节点中选择一个估价函数值最小的一个进行扩展。 局部择优搜索算法：仅从刚生成的子节点中选择一个估价函数值最小的一个进行扩展。,A算法,全局择优搜索算法流程 (1)把初始节点S0放入OPEN表，计算f(S0)。 (2)如果OPEN表为空，则问题无解，退出。 (3)把OPEN表的第一个节点（记为节点n）取出放入CLOSED表。 (4)考察节点n是否为目标节点。若是，则求得了问题的解，退出。 (5)若节点n不可扩展，则转第2步。 (6)扩展节点n，用估价函数f(x)计算每个子