经典逻辑推理3

31,.,1,人工智能导论,经典逻辑推理3,31,.,2,课程进度,人工智能原理与应用,31,.,3,本节课的知识框架,31,.,4,搜索的作用,知识的表示,逻辑推理,知识搜索,知识的表示指导了推理的基本过程,知识的搜索在这个过程的作用,反馈搜索信息,指导搜索过程,知识的获取,推理技术,搜索技术,知识的表示,31,.,5,搜索的作用,知识的表示形式,逻辑推理,搜索策略,体现了知识的组织形式,解题的大致思路,加快和纠正求解过程,31,.,6,本节课的知识框架,31,.,7,搜索的基本概念,什么是搜索人工智能所要解决的大部分问题是结构不良或非结构化的问题，对这样的问题一般不存在成熟的求解算法可供利用，而只能是利用已有的知识一步步摸索着前进。在此过程中，存在着如何寻找可用知识的问题，即如何确定推理路线，使其付出的代价尽可能的少，而问题又能得到较好的解决。,例如:在正向推理中，对已知的初始事实，需要在知识库中寻找可使用的知识，这就存在按何种线路进行寻找的问题。另外，可能存在多条线路都可实现对问题的求解，这就又出现按哪一条线路进行求解以获得较高的运行效率的问题。,像这样根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。,31,.,8,搜索分类,搜索分为盲目搜索和启发式搜索。盲目搜索按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。这种搜索具有盲目性，效率不高，不便于复杂问题的求解。启发式搜索在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。,31,.,9,本节课的知识框架,31,.,10,状态空间表示法,用搜索策略求解问题，首先要解决的问题也是：用什么样的形式把问题表示出来.一般来说，有两种方法：,状态空间表示法；与/或树表示法；,31,.,11,状态空间表示法,状态空间表示法是用来表示问题及其搜索过程的一种方法，它是人工智能中最基本的形式化方法。状态空间表示法是用“状态”和“算符”来表示问题的一种方法。其中:“状态”用以描述问题求解过程中不同时刻的状况；“算符”表示对状态的操作，算符的每一次使用就使问题由一种状态变换为另一种状态;“解”当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题的一个解。,31,.,12,状态空间表示法,31,.,13,状态空间表示法,31,.,14,状态空间表示法,上述问题的状态空间“三元组”为：（S5,f1,f2,f3,s0,s7）相应的状态空间图：,从图中看出：从S5不可能经三次翻转到达S0,从S5可经三次翻转到达S7,且有七种操作方式。,31,.,15,本节课的知识框架,31,.,16,状态空间的一般过程,.给出初始状态（初始节点）；.选择选择适用的算符对其进行操作，生成一组子状态(或称后继状态、后继节点、子节点)；.检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。,31,.,17,状态空间的一般过程,(4)搜索过程中要用到的两个数据结构OPEN表：用于存放刚生成的节点。对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。CLOSED表：用于存放将要扩展或者已扩展的节点，所谓对节点进行“扩展”是指：用合适的算符对该节点进行操作，生成一组子节点。,OPEN表,CLOSED表,31,.,18,状态空间的一般过程,5)状态空间法搜索策略广度优先搜索深度优先搜索有界深度优先搜索代价树的广度优先搜索代价树的深度优先搜索（以上属于盲目搜索策略）局部择优搜索全局择优搜索（以上搜索属于启发式搜索）,31,.,19,本节课的知识框架,31,.,20,广度优先搜索,(1)基本思想从初始节点开始，按照某种生成规则（算符）逐步生成下一级各子节点，顺序（先生成的子节点优先检查，优先扩展）地检查是否出现目标节点，在该级全部节点中沿广度进行“横向”扫描，即：沿“广度”遍历所有节点，故称“广度优先搜索法”。(2)广度优先搜索法搜索过程.把初始节点S0放人OPEN表，若S0为目标节点，则得到问题的解，退出；.如果OPEN表为空，则问题无解，退出；.把OPEN表的第一个节点(记为节点n)取出放入CLOSED表；.考察节点n，若节点n不可扩展，则转第步；.扩展节点n，将其子节点放入0PEN表的尾部，并为每一个子节点都配置指向父节点的指针；.如果n的任一个后继节点是目标节点，则找到问题的解，成功退出，否则转向第步。,31,.,21,31,.,22,OPEN表,CLOSED表,(a),(b),(c),(d),S0,S0,1,1,2,1,2,0,0,0,3,4,2,0,3,3,5,6,7,8,9,4,1,1,1,1,2,2,3,3,4,4,5,S0,1,0,2,0,3,1,4,1,Sg(9),31,.,23,广度优先搜索,例：重排九宫问题。在3X3的方格棋盘上放置分别标有数字1，2，3，4，5，6，7，8的八张牌，初始状态为50，目标状态为S，如下图所示。可使用的算符有：空格左移，空格上移，空格右移，空格下移即，它们只允许把位于空格左，上，右，下边的牌移入空格。要求寻找从初始状态到目标状态的路径。应用广度优先搜索，可得到如图所示的搜索树。,31,.,24,由图可以看出，解的路径是:S0381626(Sg)小结：缺点：广度优先搜索的盲目性较大，当目标节点距离初始节点较远时将会产生许多无用节点，搜索效率低，这是它的缺点。优点：只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解，这是它的优点。,31,.,25,本节课的知识框架,31,.,26,深度优先搜索,(1)基本思想从初始节点S0开始，按生成规则生成下一级各子节点，若目标节点未出现，则按“最晚生成的子节点优先扩展”的原则，生成再下一级的子节点，如此下去，沿着最晚生成的子节点分支，逐级向“纵向”深入发展，故称为“深度优先搜索法”。(2)深度优先搜索法搜索过程该过程与广度优先搜索的唯一区别是：广度优先搜索是将节点n的子节点放入到OPEN表的尾部，而深度优先搜索是把节点n的子节点放入到OPEN表的首部。仅此一点不同，就使得搜索的路线完全不一样。,31,.,27,31,.,28,OPEN表,CLOSED表,(a),(b),(c),S0,S0,1,2,3,4,5,(d),0,2,0,2,2,2,0,3,2,4,2,4,2,5,4,6,4,6,4,7,6,8,6,1,Sg(8),(e),31,.,29,例：对上节所示的重排九宫问题进行深度优先按索，可得如下图所示的搜索树。这只是搜索树的一部分，尚未到达目标节点，仍可继续往下搜索。,小结：在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所