人工智能 3课件

1、人 工 智 能 ( 问题求解基本原理及搜索技术 ),问题求解基本原理,问题求解：在给定条件下，寻求一个能解决某类问题且能在有限步骤内完成的算法。,问题求解特征： 传统软件： 求解的问题是能够用数学精确描述的良结构的问题（如，解方程）； 计算机执行的繁杂的统计计算任务一般不能看成是人工智能活动。,AI软件： 求解的是不可直接用数学模型描述的所谓不良结构问题（如，几何证明、求不定积分、逻辑演算等），通常需要采用弱方法进行搜索求解； AI程序中符号的内涵不仅局限于数值计算和数据处理中的一般数据信息，应表现人类进行推理所需要的各种知识。,问题求解基本原理,一、问 题 求 解 的 基 本 方 法 二、搜

2、 索 技 术,问题求解基本原理,问题求解方法： 基于状态空间的问题求解方法 基于问题空间的问题求解方法,基于状态空间的问题求解方法,1、状态空间表示法 状态空间表示法是人工智能中最基本的形式化方法，也是讨论问题求解技术的基础。状态空间表示法是用“状态”和“算符”来表示问题的一种方法。 1、状态：状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：SK=（SK0,SK1，）当给每一个分量以确定的值时，就得到了一个具体的状态。 2、算符：算符引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。当到达目标状态时，由初始状态到目标状态所用算符的序列就

3、是问题的一个解。,1、基于状态空间的问题求解方法,3、状态空间：由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间。状态空间是一个四元组：（S，O，S0，G），其中S为状态集合，O为算符集合，S0为初始状态集合，G为目标状态集合。 4、状态空间的图示形式称为状态空间图。其中，节点表示状态；有向边（弧）表示算符,问题实例,例1 二阶梵塔问题。 设有1、2、3三根钢针，在1号钢针上穿有A、B两个金片，A小于B，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一片，任何时刻都不能使B位于A的上面。,解1：A、B都搬到3上：,A(1,2),B(1,3),A(2,3)

4、,解2：A、B都搬到2上：,A(1,3),B(1,2),A(3,2),状态空间法有关概念,问题求解过程：隐含求一个普通有向图，节点 - 状态,搜索空间：问题求解过程中到达过的所有状态（节点）的集合。,问题有解：从代表初始状态 s 节点出发， 存在一条通向目标节点的路径。,状态空间、搜索空间及解径的关系：,状态空间方法求解问题特点： （a）用状态空间方法表示问题时，首先必须定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来。其次，还要定义一组算符，通过使用算符可把问题由一种状态转变为另一种状态。 （b）问题的求解过程是一个不断把算符作用于状态的过程。 （c）算符的一次使用，就使

5、问题由一种状态转变为另一种状态。可能有多个算符序列都可使问题从初始状态变到目标状态，这就得到了多个解。 （d）对任何一个状态，可使用的算符可能不止一个，这样由一个状态所生成的后继状态就可能有多个。当对这些后继状态使用算符生成更进一步的状态时，首先应对哪一个状态进行操作呢？这取决于搜索策略，不同搜索策略的操作顺序是不相同的。,2、问题空间法有关概念,问题空间法： 首先产生待证问题的所有子问题，而后通过解决所有子问题达到问题求解目的的方法。对于一个复杂问题，直接求解往往比较困难。此时，可通过下述方法进行简化：分解和等价变换。,1、分解：把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续

6、分解为若干个更为简单的子问题，重复此过程，直到不需要再分解或者不能再分解为止。然后对每个子问题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。问题的这一分解过程可用一个图表示出来。,2、问题空间法有关概念,例如，把问题P分解为三个子问题P1，P2，P3，可用图表示。如图：P1，P2，P3是问题P的三个子问题，只有当这三个子问题都可解时，问题P才可解，称P1，P2，P3之间存在“与”关系；称节点P为“与”节点；由P，P1，P2，P3所构成的图称为“与”树。在图中，为了标明某个节点是“与”节点，通常用一条弧把各条边连接起来。,2、问题空间法有关概念,2、等价变换：对于一个复杂问题，除了

7、可用“分解”方法进行求解外，还可利用同构或同态的等价变换，把它变换为若干个较容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。问题的等价变换过程，也可用一个图表示出来，称为“或”树。,2、问题空间法有关概念,例如，问题P被等价变换为新问题P1，P2，P3。如左图所示。其中，新问题P1，P2，P3中只要有一个可解，则原问题就可解，称P1,P2，P3之间存在“或”关系；节点P称为“或”节点；由P，P1，P2，P3所构成的图是一个“或”树。上述两种方法也可结合起来使用，此时的图称为“与或”树。其中既有“与”节点，也有“或”节点。如右图所示。,2、问题空间法有关概念,3、基本概念： A、

8、本原问题：不能再分解或变换，而且直接可解的子问题称为本原问题。 B、端节点与终止节点：在与或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。显然，终止节点一定是端节点，但端节点不一定是终止节点。 C、可解节点：在与或树中，满足下列条件之一者，称为可解节点：(1）它不是一个终止节点。(2）它是一个“或”节点，且其子节点中至少有一个是可解节点。(3）它是一个“与”节点，且其子节点全部是可解节点。 D、不可解节点：关于可解节点的三个条件全部不满足的节点称为不可解节点 E、解树：由可解节点所构成，并且由这些可解节点可推出初始节点 （原始问题）为可解节点的子树称为解树。在解树中一定包

9、含初始节点。,分析实例,分析实例,分析实例,分析实例,实例分析,实例分析,S(3,3,1) S(3,3,3),小结 问题求解方法比较,搜索策略,一、状态空间的搜素策略 二、与或树的搜索策略,状态空间的搜索策略,与/或树的搜索策略,什么是搜索 1、搜索引起：人工智能所要解决的问题大部分是结构不良或非结构化的问题，对这样的问题一般不存在成熟的求解算法可供利用，而只能是利用已有的知识一步步地摸索着前进。在此过程中，存在着如何寻找可用知识的问题，即如何确定推理路线，使其付出的代价尽可能的少，而问题又能得到较好的解决。 2、搜索：根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使

10、问题得到圆满解决的过程称为搜索。,搜索分类：分为盲目搜索和启发式搜索。 A、盲目搜索：是按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，所以这种搜索具有盲目性，效率不高，不便于复杂问题的求解。常用的盲目搜索算法:广度优先搜索策略、宽度优先搜索策略 B、启发式搜索：是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。 （显然，启发式搜索优于盲目搜索。但由于启发式搜索需要具有与问题本身特性有关的信息，而这并非对每一类问题都可方便地抽取出来，因此盲目搜索仍不失为

11、一种应用较多的搜索策略。）,一、状态空间的一般搜索过程 一个复杂问题的状态空间一般都是十分宠大的。若把它们都存储到计算机中去，需占用巨大的存储空间。另一方面，对一个确定的具体问题来说，与解题有关的状态空间往往只是整个状态空间的一部分，因此只要能生成并存储这部分状态空间就可求得问题的解。对一个具体问题，如何生成它所需要的部分状态空间从而实现对问题的求解呢？,1、基本思想： A、把问题的初始状态（即初始节点）作为当前状态； B、选择适用的算符对其进行操作，生成一组子状态（或称后继状态、后继节点、子节点）； C、然后检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若不出现，则按某种搜

12、索策略从已生成的状态中再选一个状态作为当前状态； D、重复B、C，直到目标状态出现或者不再有可供操作的状态及算符时为止。,一、广度优先搜索 1、基本思想： 从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。,常用的盲目搜索算法:广度优先搜索策略、宽度优先搜索策略,例：重排九宫问题。在33的方格棋盘上放置分别标有数字1,2,3,4,5,6,7,8的八张牌，初始状态为S0，目标状态为Sg，如图所示。可使用的算符有：空格左移，空格上移，空格右移，空格下移。即，它们只允许把位于空格左，上，右，下边的牌移入空格。要求寻找从

13、初始状态到目标状态的路径。,由图3可以看出，解的路径是S0381626。,广度优先搜索的优劣： 缺点：盲目性较大，当目标节点距离初始节点较远时将会产生许多无用节点，搜索效率低。 优点：只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。,二、深度优先搜索： 1、基本思想： 从初始节点S0开始扩展，若没有得到目标节点，则选择最后产生的子节点进行扩展，若还是不能到达目标节点，则再对刚才最后产生的子节点进行扩展，一直如此向下搜索。当到达某个子节点，且该子节点既不是目标节点又不能继续扩展时，才选择其兄弟节点进行考察。,例3：重排九宫问题进行深度优先搜索。 （图中只是搜索树的一部分，尚未

14、到达目标节点，仍可继续往下搜索。）,深度优先搜索的特点： 在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。另外，用深度优先搜索求得的解，不一定是路径最短的解。,二、 与或树的搜索策略,一、与或树的一般搜索过程： 1、概念 对于一个“与”节点：只有当其子节点全部为可解节点时，它才为可解节点，只要子节点中有一个为不可解节点，它就是不可解节点。 对与一个“或”节点：只要子节点中有一个是可解节点，它就

15、是可解节点，只有当全部子节点都是不可解节点时，它才是不可解节点。 可解标示过程：由可解子节点来确定父节点、祖父节点等为可解节点的过程称为可解标示过程。 不可解标示过程：由不可解子节点来确定其父节点、祖父节点等为不可解节点的过程称为不可解标示过程。,2、与或树的广度搜索过程：举例说明,例:设有如图所示的与或树。其中标有t1，t2，t3，t4的节点均为终止节点，A和B为不可解的端节点。,搜索过程： (l）首先扩展1号节点，得到2号节点和3号节点，由于这两个子节点均不是终止节点，所以接着扩展2号节点。 (2）扩展2号节点后，得到4号节点和t1节点。由于t1是终止节点，则标示它为可解节点，并应用可解标

16、示过程，对其先辈节点中的可解节点进行标示。在此例中，t1的父节点是一个“与”节点，因此仅由t1可解尚不能确定2号节点是否为可解节点。,(3）扩展3号节点得到5号节点与B节点，两者均不是终止节点，所以接着扩展4号节点。 (4）扩展4号节点后得到节点A和t2。由于t2是终止节点，所以标示它为可解节点，并应用可解标示过程标示出4号节点、2号节点均为可解节点，但1号节点目前还不能确定它是否为可解节点，下一步扩展5号节点。 (5）扩展5号节点，得到t3和t4。由于t3和t4均为终止节点，所以被标示为可解节点，通过应用可解标示过程可得到5号、3号及1号节点均为可解节点。 (6）搜索成功，得到了由1，2，3

17、，4，5号节点及t1，t2，t3，t4节点构成的解树。如图中粗线所示。,与或树的深度搜索过程：举例说明,例1：其中标有t1，t2，t3，t4的节点均为终止节点，A和B为不可解的端节点。规定深度为4，对下述与/或树进行有界搜索为： (l）首先扩展1号节点，得到2号节点和3号节点，由于这两个子节点均不是终止节点，所以接着扩展3号节点。 (2）扩展3号节点后，得到5号和B节点，两者均不是终止节点，所以接着扩展5号节点。,(3）扩展5号节点得到t4节点与t3节点，t4节点与t3节点为终止节点则可解，则标识5可解，3可解，1不确定。B删除。 (4）扩展2号节点，得到节点4和t1节点, t1可解，2不确定

18、。 (5）扩展4号节点。t2可解，则 4可解，2可解，1可解。扩展节点的顺序：1,3,5,2,4。 自上向下搜索，自下向上标示，不一定是最优解树。,自然演绎推理 从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。 自然演绎推理最基本的推理规则是三段论推理，它包括： 假言推理P, PQ Q 假言三段论PQ, QR PR,人工智能的推理技术,例 设已知如下事实：(1) 只要是需要编程序的课，王程都喜欢。(2) 所有的程序设计语言课都是需要编程序的课。(3) C是一门程序设计语言课。求证：王程喜欢C这门课。 证明：1、C是程序设计课需要编程 2、 需要编程的课被王程喜欢 则 王程喜欢C这门课,归结演绎推理,1 知识背景 人工智能是一门新兴的学科，推理技术是实现人工智能的基本技术之一，其中自然演绎推理是基于常用逻辑等价式以及常用逻辑蕴含式(统称推理规则)的