经典逻辑推理3

1、模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/61人工智能导论经典逻辑推理3模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/62课程进度人工智能原理与应用人工智能原理与应用前言前言绪论绪论数学数学基础基础知识知识表示表示(1)知识知识表示表示(2)经典经典逻辑逻辑推理推理(1)经典经典逻辑逻辑推理推理(2)经典经典逻辑逻辑推理推理(3)经典经典逻辑逻辑推理推理(4)课程课程设计设计(1)课程课程设计设计(2)不确不确定推定推理理(1)不确不确定推定推理理(2)不确不确定推定推理

2、理(3)经典经典逻辑逻辑推理推理(5)模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/63本节课的知识框架搜索策略搜索策略什么是搜索什么是搜索状态空间表示法状态空间表示法状态空间的一般过程状态空间的一般过程广度优先搜索广度优先搜索深度优先搜索深度优先搜索模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/64搜索的作用搜索的作用知识的表示知识的表示逻辑推理逻辑推理知知识识搜搜索索知识的表示知识的表示指导了推理指导了推理的基本过程的基本过程知识的搜索在知识的搜索在这个过程的作用这个过程

3、的作用反馈搜索信息反馈搜索信息指导搜索过程指导搜索过程知识的获取,推理技术 ,搜索技术 ,知识的表示 模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/65搜索的作用搜索的作用知识的表示形式知识的表示形式逻辑推理逻辑推理搜索策略搜索策略体现了知识的组织形式体现了知识的组织形式加快和纠正求解过程加快和纠正求解过程模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/66本节课的知识框架搜索策略搜索策略什么是搜索什么是搜索状态空间表示法状态空间表示法状态空间的一般过程状态空间的一般过程广度优

4、先搜索广度优先搜索深度优先搜索深度优先搜索模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/67搜索的基本概念什么是搜索什么是搜索 人工智能所要解决的大部分问题是结构不良或非结构化的人工智能所要解决的大部分问题是结构不良或非结构化的问题，对这样的问题一般不存在成熟的求解算法可供利用，问题，对这样的问题一般不存在成熟的求解算法可供利用，而只能是利用已有的知识一步步摸索着前进。而只能是利用已有的知识一步步摸索着前进。 在此过程中，存在着如何寻找可用知识的问题，即如何确在此过程中，存在着如何寻找可用知识的问题，即如何确定推理路线，使其付出的代价

5、尽可能的少，而问题又能得定推理路线，使其付出的代价尽可能的少，而问题又能得到较好的解决。到较好的解决。例如例如: 在正向推理中，对已知的初始事实，需要在知识库中寻找可使用的知识，在正向推理中，对已知的初始事实，需要在知识库中寻找可使用的知识，这就存在按何种线路进行寻找的问题。这就存在按何种线路进行寻找的问题。 另外，可能存在多条线路都可实现对问题的求解，这就又出现按哪一条线另外，可能存在多条线路都可实现对问题的求解，这就又出现按哪一条线路进行求解以获得较高的运行效率的问题。路进行求解以获得较高的运行效率的问题。像这样根据问题的实际情况不断寻找可利用的知识，从而像这样根据问题的实际情况不断寻找可

6、利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过构造一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。程称为搜索。模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/68搜索分类搜索分类搜索分为盲目搜索和启发式搜索。搜索分为盲目搜索和启发式搜索。 盲目搜索盲目搜索按预定的控制策略进行搜索，在搜索过程中按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。这种搜索具有盲目获得的中间信息不用来改进控制策略。这种搜索具有盲目性，效率不高，不便于复杂问题的求解。性，效率不高，不便于复杂问题的求解。 启发式

7、搜索启发式搜索在搜索中加入了与问题有关的启发性信息，在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。过程并找到最优解。模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/69本节课的知识框架搜索策略搜索策略什么是搜索什么是搜索状态空间表示法状态空间表示法状态空间的一般过程状态空间的一般过程广度优先搜索广度优先搜索深度优先搜索深度优先搜索模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021

8、/8/610 用搜索策略求解问题，首先要解决的问题也是：用搜索策略求解问题，首先要解决的问题也是：用什么样的形式把问题表示出来用什么样的形式把问题表示出来. 一般来说，有一般来说，有两种方法：两种方法：状态空间表示法；状态空间表示法；与与/或树表示法；或树表示法；模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/611状态空间表示法状态空间表示法 状态空间表示法是用来表示问题及其搜索过程的一种方法，状态空间表示法是用来表示问题及其搜索过程的一种方法，它是人工智能中最基本的形式化方法。它是人工智能中最基本的形式化方法。 状态空间表示法是用状

9、态空间表示法是用“状态状态”和和“算符算符”来表示问题的来表示问题的一种方法。其中一种方法。其中: “状态状态”用以描述问题求解过程中不同时刻的状况；用以描述问题求解过程中不同时刻的状况； “算符算符”表示对状态的操作，算符的每一次使用就表示对状态的操作，算符的每一次使用就使问题由一种使问题由一种 状态变换为另一种状态状态变换为另一种状态; “ 解解 ” 当到达目标状态时，由初始状态到目标状当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题的一个解。态所用算符的序列就是问题的一个解。模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/

10、8/612状态空间表示法状态空间表示法模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/613状态空间表示法状态空间表示法模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/614状态空间表示法状态空间表示法上述问题的状态空间上述问题的状态空间“三元组三元组”为：为： （S5, f1,f2,f3, s0,s7） 相应的状态空间图：相应的状态空间图：从图中看出：从图中看出：从从S5不可能经三次翻转到不可能经三次翻转到达达S0, 从从S5 可经三次翻转到达可经三次翻转到达S7 , 且有七种

11、操作方式。且有七种操作方式。模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/615本节课的知识框架搜索策略搜索策略什么是搜索什么是搜索状态空间表示法状态空间表示法状态空间的一般过程状态空间的一般过程广度优先搜索广度优先搜索深度优先搜索深度优先搜索模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/616状态空间的一般过程状态空间的一般过程 .给出初始状态（初始节点）；给出初始状态（初始节点）； .选择选择适用的算符对其进行操作，生成一组选择选择适用的算符对其进行操作，生成一组子状态子

12、状态( (或称后继状态、后继节点、子节点或称后继状态、后继节点、子节点) )； .检查目标状态是否在其中出现。若出现，则搜检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若不出现，则按某种索成功，找到了问题的解；若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当搜索策略从已生成的状态中再选一个状态作为当前状态。前状态。 重复上述过程，直到目标状态出现或者不再有可重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。供操作的状态及算符时为止。模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/617状态

13、空间的一般过程状态空间的一般过程(4) (4) 搜索过程中要用到的两个数据结构搜索过程中要用到的两个数据结构 用于存放刚生成的节点。对于不同的搜索策略，节点在用于存放刚生成的节点。对于不同的搜索策略，节点在OPENOPEN表中的排列顺序表中的排列顺序是不同的。是不同的。 用于存放将要扩展或者已扩展的节点，所谓对节点进行用于存放将要扩展或者已扩展的节点，所谓对节点进行“扩展扩展”是指：用是指：用合适的算符对该节点进行操作，生成一组子节点。合适的算符对该节点进行操作，生成一组子节点。状态节状态节点点父节父节点点OPEN表表编号编号状态节状态节点点父节父节点点CLOSED表表模式识别与智能系统研究所

14、模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/618状态空间的一般过程状态空间的一般过程5) 状态空间法搜索策略状态空间法搜索策略 广度优先搜索广度优先搜索 深度优先搜索深度优先搜索 有界深度优先搜索有界深度优先搜索 代价树的广度优先搜索代价树的广度优先搜索 代价树的深度优先搜索代价树的深度优先搜索 （以上属于盲目搜索策略）（以上属于盲目搜索策略） 局部择优搜索局部择优搜索 全局择优搜索全局择优搜索 （以上搜索属于启发式搜索）（以上搜索属于启发式搜索）模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/6

15、19本节课的知识框架搜索策略搜索策略什么是搜索什么是搜索状态空间表示法状态空间表示法状态空间的一般过程状态空间的一般过程广度优先搜索广度优先搜索深度优先搜索深度优先搜索模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/620广度优先搜索(1) 基本思想基本思想 从初始节点开始，按照某种生成规则（算符）逐步生成下一级各子节点，从初始节点开始，按照某种生成规则（算符）逐步生成下一级各子节点，顺序（先生成的子节点优先检查，优先扩展）地检查是否出现目标节点，在顺序（先生成的子节点优先检查，优先扩展）地检查是否出现目标节点，在该级全部节点中沿广度进

16、行该级全部节点中沿广度进行“横向横向”扫描，即：沿扫描，即：沿“广度广度”遍历所有节点，遍历所有节点，故称故称“广度优先搜索法广度优先搜索法”。 (2) 广度优先搜索法搜索过程广度优先搜索法搜索过程 .把初始节点把初始节点S0放人放人OPEN表，若表，若S0为目标节点，则得到问题的解，退为目标节点，则得到问题的解，退出；出； .如果如果OPEN表为空，则问题无解，退出；表为空，则问题无解，退出； .把把OPEN表的第一个节点表的第一个节点(记为节点记为节点n)取出放入取出放入CLOSED表；表； .考察节点考察节点n，若节点，若节点n不可扩展，则转第不可扩展，则转第步；步； .扩展节点扩展节点

17、n，将其子节点放入，将其子节点放入0PEN表的尾部表的尾部，并为每一个子节点都配，并为每一个子节点都配置指向父节点的指针；置指向父节点的指针； .如果如果n的任一个后继节点是目标节点，则找到问题的解，成功退出，否的任一个后继节点是目标节点，则找到问题的解，成功退出，否则转向第则转向第步。步。模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/621开始开始把把S0送入送入OPEN表表 把把OPEN表的第一个节点表的第一个节点(记为节点记为节点n) 从表中移出，放入从表中移出，放入CLOSED表表 OPEN表为空？表为空？ 扩展节点扩展节点n

18、,将其子节点放入将其子节点放入，并为每个子节点配置指向节点并为每个子节点配置指向节点n的指针。的指针。 是否有任何后继是否有任何后继 节点为目标节点？节点为目标节点？ 节点节点n可扩展？可扩展？失败，退出失败，退出成功，退出成功，退出YNYNYNS0为目标节点？为目标节点？ 成功，退出成功，退出YN模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/622状态节状态节点点父节父节点点OPEN表表编号编号状态节状态节点点父节父节点点CLOSED表表S012S012634 5S012634 5789(a)(b)(c)(d)S0S01121200

19、034203356789411112233445S010203141Sg(9)S0491模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/623广度优先搜索例：例： 重排九宫问题。在重排九宫问题。在3X3的方格棋盘上放置分别标有数字的方格棋盘上放置分别标有数字1，2，3，4，5，6， 7，8的八张牌，初始状态为的八张牌，初始状态为50，目标状态为，目标状态为S，如下图所示。，如下图所示。 可使用的算符有：可使用的算符有： 空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移，空格下移 即，它们只允许把位于空格左，上，右，下边

20、的牌移入空格。即，它们只允许把位于空格左，上，右，下边的牌移入空格。 要求寻找从初始状态到目标状态的路径。要求寻找从初始状态到目标状态的路径。 应用广度优先搜索，可得到如图所示的搜索树。应用广度优先搜索，可得到如图所示的搜索树。2 8 31 47 6 51 2 38 47 6 5模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/624 由图可以看出，解的路径是由图可以看出，解的路径是: S03 8 16 26 (Sg) 广度优先搜索的盲目性较大，当目标节点距离初始节点较远时将会产生许广度优先搜索的盲目性较大，当目标节点距离初始节点较远时将

21、会产生许 多无用节点，搜索效率低，这是它的缺点。多无用节点，搜索效率低，这是它的缺点。 只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的 解，这是它的优点。解，这是它的优点。模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/625本节课的知识框架搜索策略搜索策略什么是搜索什么是搜索状态空间表示法状态空间表示法状态空间的一般过程状态空间的一般过程广度优先搜索广度优先搜索深度优先搜索深度优先搜索模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻

22、辑推理经典逻辑推理-22021/8/626深度优先搜索 (1) 基本思想基本思想 从初始节点从初始节点S0开始，按生成规则生成下一级各子节点，开始，按生成规则生成下一级各子节点，若目标节点未出现，则按若目标节点未出现，则按“最晚生成的子节点优先扩展最晚生成的子节点优先扩展”的原则，生成再下一级的子节点，如此下去，沿着最晚生的原则，生成再下一级的子节点，如此下去，沿着最晚生成的子节点分支，逐级向成的子节点分支，逐级向“纵向纵向”深入发展，故称为深入发展，故称为“深深度优先搜索法度优先搜索法”。 (2) 深度优先搜索法搜索过程深度优先搜索法搜索过程 广度优先搜索是将节点广度优先搜索是将节点n的子节

23、点放入到的子节点放入到OPEN表的尾部，表的尾部，而深度优先搜索是把节点而深度优先搜索是把节点n的子节点放入到的子节点放入到OPEN表的首表的首部。部。仅此一点不同，就使得搜索的路线完全不一样。仅此一点不同，就使得搜索的路线完全不一样。模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/627开始开始把把S0送入送入OPEN表表 把把OPEN表的第一个节点表的第一个节点(记为节点记为节点n) 从从表中移出，放入表中移出，放入CLOSED表表 OPEN表为空？表为空？扩展节点扩展节点n,将其子节点放入将其子节点放入，并为，并为每个子节点配置指向节点每个子节点配置指向节点n的指针。的指针。 是否有任何后继是否有任何后继 节点为目标节点？节点为目标节点？ 节点节点n可扩展？可扩展？失败，退出失败，退出成功，退出成功，退出YNYNYNS0为目标节点？为目标节点？ 成功，退出成功，退出YN模式识别与智能系统研究所模式识别与智能系统研究所版权所有版权所有经典逻辑推理经典逻辑推理-22021/8/628状态节状态节点点父节父节点点OPEN表表编号编号状态节状态节点点父节父节点点CLOSED表表S012S01234(a)(b)(c)S0S012345S0123465S012346578(d)02022203242425