经典逻辑推理3.ppt

《经典逻辑推理3.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、人工智能导论经典逻辑推理3311课程进度人工智能原理与应用前言绪论数学基础知识表示(1)知识表示(2)经典逻辑推理(1)经典逻辑推理(2)经典逻辑推理(3)经典逻辑推理(4)课程设计(1)课程设计(2)不确定推理(1)不确定推理(2)不确定推理(3)经典逻辑推理(5)312本节课的知识框架313搜索的作用知识的表示逻辑推理知识搜索知识的表示指导了推理的基本过程知识的搜索在这个过程的作用反馈搜索信息指导搜索过程知识的获取,推理技术,搜索技术,知识的表示314搜索的作用知识的表示形式逻辑推理搜索策略体现了知识的组织形式解题的大致思路加快和纠正求解过程3

2、15本节课的知识框架316搜索的基本概念什么是搜索人工智能所要解决的大部分问题是结构不良或非结构化的问题，对这样的问题一般不存在成熟的求解算法可供利用，而只能是利用已有的知识一步步摸索着前进。在此过程中，存在着如何寻找可用知识的问题，即如何确定推理路线，使其付出的代价尽可能的少，而问题又能得到较好的解决。例如:在正向推理中，对已知的初始事实，需要在知识库中寻找可使用的知识，这就存在按何种线路进行寻找的问题。另外，可能存在多条线路都可实现对问题的求解，这就又出现按哪一条线路进行求解以获得较高的运行效率的问题。像这样根据问题的实际情况不断寻找可利用的知

3、识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。317搜索分类搜索分为盲目搜索和启发式搜索。盲目搜索——按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。这种搜索具有盲目性，效率不高，不便于复杂问题的求解。启发式搜索——在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。318本节课的知识框架319状态空间表示法用搜索策略求解问题，首先要解决的问题也是：用什么样的形式把问题表示出来.一般来说，有两种方法：状态空间表示法；与/或树表示法；3110状态空间

4、表示法状态空间表示法是用来表示问题及其搜索过程的一种方法，它是人工智能中最基本的形式化方法。状态空间表示法是用“状态”和“算符”来表示问题的一种方法。其中:“状态”——用以描述问题求解过程中不同时刻的状况；“算符”——表示对状态的操作，算符的每一次使用就使问题由一种状态变换为另一种状态;“解”——当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题的一个解。3111状态空间表示法3112状态空间表示法3113状态空间表示法上述问题的状态空间“三元组”为：（{S5},{f1,f2,f3},{s0,s7}）相应的状态空间图：从图中看出：从S5不

5、可能经三次翻转到达S0,从S5可经三次翻转到达S7,且有七种操作方式。3114本节课的知识框架3115状态空间的一般过程Ⅰ.给出初始状态（初始节点）；Ⅱ.选择选择适用的算符对其进行操作，生成一组子状态(或称后继状态、后继节点、子节点)；Ⅲ.检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。3116状态空间的一般过程(4)搜索过程中要用到的两个数据结构OPEN表：用于存放刚生成的节点。对于不同的搜索策略

6、，节点在OPEN表中的排列顺序是不同的。CLOSED表：用于存放将要扩展或者已扩展的节点，所谓对节点进行“扩展”是指：用合适的算符对该节点进行操作，生成一组子节点。状态节点父节点OPEN表编号状态节点父节点CLOSED表3117状态空间的一般过程5)状态空间法搜索策略•广度优先搜索•深度优先搜索•有界深度优先搜索•代价树的广度优先搜索•代价树的深度优先搜索（以上属于盲目搜索策略）•局部择优搜索•全局择优搜索（以上搜索属于启发式搜索）3118本节课的知识框架3119广度优先搜索(1)基本思想从初始节点开始，按照某种生成规则（算符）逐步生成下一级各子节

7、点，顺序（先生成的子节点优先检查，优先扩展）地检查是否出现目标节点，在该级全部节点中沿广度进行“横向”扫描，即：沿“广度”遍历所有节点，故称“广度优先搜索法”。(2)广度优先搜索法搜索过程Ⅰ.把初始节点S0放人OPEN表，若S0为目标节点，则得到问题的解，退出；Ⅱ.如果OPEN表为空，则问题无解，退出；Ⅲ.把OPEN表的第一个节点(记为节点n)取出放入CLOSED表；Ⅳ.考察节点n，若节点n不可扩展，则转第Ⅱ步；Ⅴ.扩展节点n，将其子节点放入0PEN表的尾部，并为每一个子节点都配置指向父节点的指针；Ⅵ.如果n的任一个后继节点是目标节点，则找到问题的

8、解，成功退出，否则转向第Ⅱ步。3120开始把S0送入OPEN表把OPEN表的第一个节点(记为节点n)从表中移出，放入CLO