第三章 推理技术

第三章确定性推理按所用知识的确定性，推理可以确定性和不确定性推理。

所谓确定性推理指的是推理所用的知识都是精确的，推出的结论也是精确的。

比如一个事件是否为真，其推理的结果只能是真或者假，绝对不可能出现第三种可能性。

确定性推理的方法有很多，具体有图搜索策略、盲目搜索、启发式搜索、消解原理、规则演绎系统、产生式系统等等第一节图搜索策略●搜索的基本概念➢搜索分为盲目搜索和启发式搜索⏹盲目搜索：无信息搜索，在搜索过程中只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略，效率不高，只适合求解简单问题⏹启发式搜索：有信息搜索，在搜索求解问题的过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解●图搜索策略在人工智能中，搜索问题一般包括两个重要的问题：➢搜索什么：搜索什么通常指的就是目标。

➢在哪里搜索：在哪里搜索就是“搜索空间”。

搜索空间通常是指一系列状态的汇集，因此称为状态空间。

所以，人工智能中的搜索可以分成两个阶段：➢状态空间的生成阶段➢在该状态空间中对所求问题状态的搜索一般图搜索（状态空间搜索）的基本思想1.问题状态用图数据结构的结点表示；2.从初始状态（结点）开始，对选定的结点选择满足条件的操作符，操作符作用后产生新的结点（状态）；3.检查新产生的子结点中是否有目标结点：有则找到了问题的解；4.否则重复上述过程直至产生目标结点，或全部结点处理完无解。

状态空间搜索的基本思想➢节点扩展的概念⏹扩展：就是用合适的算符对某个节点进行操作生成一组后继节点，扩展过程实际上就是求后继节点的过程⏹已扩展节点：对状态空间图中的某个节点，如果求出了它的后继节点，则此节点为已扩展的节点⏹未扩展节点：对状态空间图中的某个节点，如果尚未求出它的后继节点，则此节点称为未扩展节点在对状态空间图搜索求解时，将为扩展的节点存于一个名为OPEN的表中，而将已扩展的节点存于一个名为CLOSED的表中搜索的目的是为了寻找初始节点到目标节点的路径，所以在搜索过程中就得随时记录搜索轨迹。

人工智能第三章搜索推理技术教学内容：本章在上一章知识表示的基础上研究问题求解的方法，是人工智能研究的又一核心问题。

内容包含早期搜索推理技术，如图搜索策略与消解原理；与高级搜索推理技术，如规则演绎系统、产生式系统、系统组织技术、不确定性推理与非单调推理。

教学重点：图搜索策略、消解原理、规则演绎系统、产生式系统。

教学难点：启发式搜索、规则双向演绎系统等。

教学方法：课堂教学为主，辅以恰当的实验。

注意结合前面所学知识表示的基础内容，将其与问题求解方法融为一体。

及时提问、收集学生学习情况。

尽量使用实例与网络课程中的多媒体素材进行讲解。

教学要求：重点掌握通常图搜索策略与消解原理，掌握各类搜索方法与产生式系统原理，熟悉规则演绎系统的基本原理，对系统组织技术、不确定性推理与非单调推理等高级推理技术作通常性熟悉。

3.1 图搜索策略教学内容：本节介绍图搜索的通常策略，作为各类图搜索技术的基础。

教学重点：图搜索的通常过程、OPEN表与CLOSE表的概念。

教学难点：OPEN表与CLOSE表的物理意义。

教学方法：课堂教学为主，通过提问完全弄清图搜索的基本概念。

教学要求：重点掌握图搜索通常策略，掌握OPEN表与CLOSE表的构成及作用。

1、图搜索策略的定义图搜索策略可看作一种在图中寻找路径的方法。

初始节点与目标节点分别代表初始数据库与满足终止条件的数据库。

求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。

研究图搜索的通常策略，能够给出图搜索过程的通常步骤。

2、图搜索算法中的几个重要名词术语（1）OPEN表与CLOSE表（2）搜索图与搜索树3、图搜索(GRAPHSEARCH)的通常过程(1) 建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。

(2) 建立一个叫做CLOSED的已扩展节点表，其初始为空表。

(3) LOOP：若OPEN表是空表，则失败退出。

(4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。

人工智能第三章归结推理方法
第三章主要讨论归结推理方法，归结推理方法是人工智能领域中的一种重要技术。

归结推理是一种推理过程，它从一个给定的知识库出发，将给定的输入推断，得出想要的结果。

归结推理是一种推断过程，它把已有的规则和数据应用到新的数据中，来解决新问题。

归结推理可以从三个层面来分析：
1.处理模型
在归结推理中，首先要建立一个处理模型，这个模型是一种结构，它描述了归结推理的步骤，以及归结推理过程中用到的数据和知识。

2.知识表示
归结推理过程是基于知识库，而知识的表示是归结推理中最重要的环节。

知识的表示是一种在计算机中存储、表示和管理数据的方法，它决定了归结推理过程中的正确性和性能。

3.推理机制
推理机制是归结推理过程中，根据已有的输入，对知识进行推理以及解决问题的一种机制。

它可以把归结推理分为计算环节和决策环节，从而实现和可靠的知识表示，实现更精确的推理过程。

基于上述三个层面，归结推理方法可以有效的解决知识表示、理解和存储问题，实现可靠的推理过程，从而解决复杂的问题。

《人工智能及其应用》教学讲义第三章知识推理技术§3.1 知识推理的概念和类型一、知识推理的概念所谓“知识推理（Knowledge Inference）”，是指在计算机或智能机器中，在知识表达的基础上，进行机器思维，求解问题，实现知识推理的智能操作过程。

因此推理的过程就是问题求解的过程，使问题从初始状态转移到目标状态的方法和途径。

知识推理是“知识利用（Knowledge Utilization）”的基础。

各种人工智能应用领域，如知识库专家系统、智能机器人、模式识别与物景分析、自然语言理解与生成、机器博弈、定理证明、数据库智能检索、自动程序设计等，都是利用知识进行广义的问题求解的知识工程系统。

它们都需要以知识表达、知识获取、知识推理为基础。

其中知识表达和知识获取是必要的前提条件，而知识推理是问题求解的主要手段。

研究人工智能的知识推理技术，目的是寻求解决问题、实现状态转移的智能操作序列。

如搜索路线、演算步骤、符号串、语句集等，以便从初始状态，沿着最优或最经济的途径，有效地转移到所要求的目标状态，实现问题求解过程的智能机械化或计算机化。

二、知识推理的类型1．根据知识表达方式的特点，可将知识推理方法分为：“图搜索”方法：基于图的知识表达，问题求解的知识推理过程，就是从图中相当于初始状态的根结点到相当于目标状态的终止结点的路线搜索过程，即搜索从初始状态有效地转移到目标状态，所经历的最优的或最经济的路线。

“逻辑论证”方法：当知识表达采用谓词逻辑或其他形式逻辑方法时，知识推理也可以采取逻辑论证方法。

此时，问题求解的知识推理过程，相当于用数理逻辑方法进行定理证明的过程。

2．根据问题求解过程是否完备，可将知识推理方法分为：推理算法：若问题求解的知识推理过程是完备的，则对于可解的问题，从任意初始状态出发，通过这种推理过程，总可以找到一条求解路线，经过有限的、确定性的操作序列，转移到所要求的目标状态，保证推理过程的收敛性，求得问题的解答。

第3章确定性推理3.1 图搜索策略3.2 盲目搜索3.3 启发式搜索3.4 消解原理3.5 规则演绎系统3.6 产生式系统3.7 非单调推理概述(1)问题求解§AI中每个研究领域都有其各自的特点和规律,但就求解问题的过程看,都可抽象为一个问题求解过程。

§问题求解过程实际上是一个搜索,广义地说,它包含了全部计算机科学。

§任何问题求解技术都包括两个重要的方面:表示和搜索§表示是基本的,搜索必须要在表示的基础上进行。

表示关系到搜索的效率。

§本章讨论的表示主要包括:§状态空间表示§问题空间表示概述(2)q1974年，Nilsson归纳出的AI研究的基本问题知识的模型化和表示常识性推理、演绎和问题解决启发式搜索人工智能系统和语言q搜索是人工智能中的一个基本问题,是推理不可分割的一部分,直接关系到智能系统的性能和运行效率q AI为什么要研究search?问题没有直接的解法;需要探索地求解;搜索(3)什么是搜索§根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索包括两个方面：---找到从初始事实到问题最终答案的一条推理路径---找到的这条路径在时间和空间上复杂度最小搜索(4)§盲目搜索:也称为无信息搜索，即只按预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略§启发式搜索: 在搜索中加入了与问题有关的启发性信息,用于指导搜索朝着最有希望的方向进行,加速问题的求解过程并找到最优解要考虑的因素u完备性：当问题有解时，这个算法是否能保证找到一个解？u最优性：这个搜索策略是否能找到最优解？u时间复杂度：找到一个解需要花费多长时间？u空间复杂度：在执行搜索过程中需要有多少内存？无信息的搜索策略•广度优先搜索(Breadth-first search)•代价一致搜索(Uniform-cost search)•深度优先搜索(Depth-first search)•深度有限搜索(Depth-limited search)•双向搜索(Bidirectional search)•迭代深度优先搜索(Iterative deepening depth-first search)有信息的搜索策略贪婪最佳优先搜索(Greedy best-first search)A*搜索(A* search: Minimizing the total estimated solution cost)递归最佳优先搜索(Recursive best-first search)爬山法搜索(Hill-climbing search)模拟退火搜索(Simulated annealing search)局部剪枝搜索(Local beam search)遗传算法(Genetic algorithm)联机搜索(Online search)Heuristic search Beyond Classical Search状态空间表示法(1)q状态空间表示法：用来表示问题及其搜索过程的一种方法q状态：状态是描述问题求解过程中任一时刻状况的数据结构.23751486（2, 3,7 ,0 , 5, 1, 4, 8, 6）状态空间表示法(2)q状态空间:由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间.一般表示为:(S, F, G)S:问题所有的初始状态集合;F:算符集合; G:目标状态集合q算符: 引起状态中某些分量发生变化, 从而使问题由一个状态变为另一个状态的操作称为算符.q状态空间表示法是用“状态”和“算符”表示问题的一种方法q状态空间图:状态空间的图式表示,称为状态空间图.其中节点表示状态,有向边(弧)表示算符.状态空间表示法(3)路径状态序列搜索寻找从初始状态到目标状态的路径;S0Sg状态空间表示法（4）例1:二阶梵塔问题§设有三个钢针,在一号钢针上穿有A,B两个金片,A小于B,A位于B的上面.要求把这两个金片全部移到另一个钢针上,而且规定每次只能移动一片,任何时刻都不能使B位于A的上面§设用Sk=(Sk0,Sk1)表示问题的状态,SK0表示金片A所在的钢针号,SK1表示金片B所在的钢针号,全部可能的状态为:S0=(1,1), S1=(1,2), S3=(1,3)S4=(2,1), S5=(2,2), S6=(2,3)S7=(3,1), S8=(3,2), S9=(3,3)§问题初始状态集合S={S0},§目标状态集合G={S4,S8}.§算符:A( i,j):表示把金片A从第i号针移到第j号针上B(i,j):表示把B从第i号针移到第j号针上§共12个算符:§A(1,2), A(1,3), A(2,1) ,A(2,3), A(3,1),A(3,2)§B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2)状态空间表示法（5）用状态空间表示,首先必须定义状态的描述形式,把问题的一切状态都表示出来,其次定义算符,完成状态的转换问题的求解过程就是一个把算符不断地作用于状态的过程.如果在使用某个算符后得到的状态就是目标状态,就得到了问题的解.这个解就是从初始状态到目标状态所用算符构成的序列.算符的一次使用,就使问题由一种状态转变为另一种状态.可能有多个算符序列都可使问题从初始状态变到目标状态,这就得到了多个解.对任何一个状态,可使用的算符可能不止一个,这样由一个状态所生成的后继状态可能有多个.如何选择下一步的操作,由搜索策略决定.搜索控制策略（1）q搜索控制策略不可撤回的控制策略;试探性控制策略回溯型图搜索搜索控制策略（2）不可撤回的控制策略例：八数码问题评价函数:f：（规定: 评价函数非增）2831647512384765与的差异为4搜索控制策略（3）不可撤回的控制策略2831647528314765231847651123847651238476523184765 f=4f=3f=3f=0f=1f=2搜索控制策略（4）不可撤回的控制策略28314765283147658321476583214765 28132476581324765 f=3f=3f=3f=3f=3f=313824765f=213824765f=1搜索控制策略（5）不可撤回的控制策略可能无解1251238476384765目标f=2回溯策略((1,1))((1,1))((1,1))((1,1))Q ((1,1))((1,1))((1,1))((1,1))((1,1))((1,1))Q ((1,1))Q ((1,1))3.1 图搜索策略¾一些基本概念节点深度：根节点深度=0其它节点深度=父节点深度+11233.1 图搜索策略¾一些基本概念路径设一节点序列为(n0, n1,…,n k)，对于i=1,…,k，若节点n具有一个后继节点n，则该序列称为从n到n的i-1i0k路径。