人工智能 第3章 推理技术1分析

第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路径。

第三章搜索推理技术3-1什么是图搜索过程?其中，重排OPEN表意味着什么，重排的原则是什么?图搜索的一般过程如下：(1) 建立一个搜索图G(初始只含有起始节点S)，把S放到未扩展节点表中（OPEN表）中。

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

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

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

称此节点为节点n，它是CLOSED表中节点的编号(5) 若n为一目标节点，则有解并成功退出。

此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)(6) 扩展节点n，生成不是n的祖先的那些后继节点的集合M。

将M添入图G中。

(7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针，并将它们加进OPEN表。

对已经在OPEN或CLOSED表上的每个M成员，确定是否需要更改通到n的指针方向。

对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。

(8) 按某一任意方式或按某个探试值，重排OPEN表。

(9) GO LOOP。

重排OPEN表意味着，在第(6)步中，将优先扩展哪个节点，不同的排序标准对应着不同的搜索策略。

重排的原则当视具体需求而定，不同的原则对应着不同的搜索策略，如果想尽快地找到一个解，则应当将最有可能达到目标节点的那些节点排在OPEN表的前面部分，如果想找到代价最小的解，则应当按代价从小到大的顺序重排OPEN表。

3-2 试举例比较各种搜索方法的效率。

宽度优先搜索(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。

(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。

(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。

(4) 扩展节点n。

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

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

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

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

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

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

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

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

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

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.推理机制
推理机制是归结推理过程中，根据已有的输入，对知识进行推理以及解决问题的一种机制。

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

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

人工智能推理技术人工智能（Artificial Intelligence，简称AI）作为一门涉及计算机科学、数学、逻辑学等多个领域的研究领域，近年来取得了显著进展。

其中，人工智能推理技术作为人工智能的核心技术之一，对于实现机器智能化具有重要意义。

本文将从基本概念、应用领域和发展趋势三个方面来阐述人工智能推理技术的关键内容。

一、基本概念1.1 人工智能推理的定义人工智能推理（Artificial Intelligence Reasoning）是指机器通过分析、推断和推理过程，模拟人类的思维方式，从而得出一定的结论或解决问题的过程。

1.2 推理的基本原理推理的基本原理包括逻辑推理、概率推理和模糊推理。

逻辑推理依据事实和规则进行推理；概率推理依据概率统计进行推理；模糊推理依据模糊逻辑进行推理。

二、应用领域2.1 专家系统专家系统是人工智能推理技术的重要应用之一。

通过将专家的知识和经验用规则的形式储存起来，并结合推理引擎实现对问题的分析和解决，专家系统在医疗、金融、工程等领域得到广泛应用。

2.2 自动驾驶人工智能推理技术在自动驾驶领域的应用越来越广泛。

通过分析和推论来判断周围环境的情况，自动驾驶汽车能够实现避免障碍物、规划最佳路径等功能。

2.3 智能机器人智能机器人是人工智能推理技术的典型应用。

机器人通过对环境的感知、语音识别和推理能力，可以与人类进行交互，并执行相应的任务。

三、发展趋势3.1 深度学习与推理技术的结合深度学习作为人工智能的一个重要分支，与推理技术相结合，将会进一步提升人工智能的推理能力。

3.2 强化学习与推理技术的融合强化学习通过试错反馈机制，使机器可以根据环境的变化不断提升自己的推理水平。

3.3 推理技术在决策支持系统中的应用推理技术在决策支持系统中具有广泛的应用前景。

通过分析决策者的需求和信息，系统可以提供决策者最佳的决策方案。

总结：人工智能推理技术作为人工智能的核心技术之一，在专家系统、自动驾驶、智能机器人等领域具有重要应用。

人工智能的逻辑推理技术人工智能（Artificial Intelligence，简称AI）的逻辑推理技术在近年来得到了快速的发展和应用。

逻辑推理是指通过分析和判断给定的前提条件，并利用逻辑规则和规范的推理方法来得到结论的过程。

在人工智能领域，逻辑推理技术被广泛应用于问题求解、决策制定和知识推理等方面。

本文将从逻辑推理的基本原则和方法入手，介绍人工智能中的逻辑推理技术及其应用。

第一部分逻辑推理的基本原则和方法1.1 逻辑推理的基本原则逻辑推理的基本原则包括前提-结论关系、规则的可信度、逻辑范式等。

前提-结论关系要求结论必须根据前提进行推断，并且推断的过程必须符合规则和规范。

规则的可信度是指推理过程中对于规则的使用和使用的结果的可信程度。

逻辑范式是指将推理过程中的严格逻辑转化为数学形式，以便计算机进行计算和推理。

1.2 逻辑推理的方法逻辑推理的方法主要包括演绎推理和归纳推理两种。

演绎推理是指从一般到特殊的推理过程，根据已知的规则和条件来推断出结论。

归纳推理是指从特殊到一般的推理过程，根据已知的个别事实和实例推断出一般规律和结论。

第二部分人工智能中的逻辑推理技术2.1 基于规则的推理技术基于规则的推理技术是指通过描述和表示规则，利用规则的推理能力进行推理和决策。

基于规则的推理技术主要包括规则库、推理引擎和推理机制等。

规则库是存储和管理规则的系统，推理引擎是执行和控制推断过程的组件，推理机制是通过规则的匹配和应用来得到结论的方法。

基于规则的推理技术在专家系统、决策支持系统和自然语言处理等领域有着广泛的应用。

2.2 基于搜索的推理技术基于搜索的推理技术是指通过搜索和探索问题空间，找到问题的解空间，并从中选择最优解的一种推理方式。

基于搜索的推理技术主要包括深度优先搜索、广度优先搜索、A*算法和剪枝策略等。

深度优先搜索是从根节点开始，先搜索到最深的节点，然后再回溯回来，广度优先搜索是按层次来搜索节点，A*算法是综合利用启发函数和代价函数来进行搜索的。