人工智能ArtificialIntelligence(AI)

1、2022-5-1人人 工工 智智 能能Artificial Intelligence (AI)许建华许建华南京师范大学计算机科学系南京师范大学计算机科学系2006年年9-12月月2022-5-12.1 知识表示的一般方法知识表示的一般方法2.1.1 状态空间法状态空间法2.1.2 问题归约法问题归约法2.2.3 谓词逻辑法谓词逻辑法2022-5-1用计算机技术解决实际问题的一般思路用计算机技术解决实际问题的一般思路:实际实际问题问题问题表达问题表达知识表达知识表达数学建模数学建模求解的方法求解的方法或者算法或者算法结果的解释结果的解释2022-5-1例：求侧面积为例：求侧面积为150平方米的体

2、积最大的长方体？平方米的体积最大的长方体？设长、宽、高分别为设长、宽、高分别为 x, y, z侧面积为：侧面积为：2(xy + yz + xz)体积为：体积为：xyz数学模型数学模型 max xyz s.t. 2(xy + yz + xz)=150 xyz2022-5-1利用最优化技术中的算法，可以得到结果：利用最优化技术中的算法，可以得到结果：x = y = z = 5.0解释解释：长、宽、高都等于：长、宽、高都等于5米时，体积最大米时，体积最大说明说明：在计算数学的课程中，主要关心求解的：在计算数学的课程中，主要关心求解的具体算法具体算法2022-5-1在人工智能中，重点关注两个方面的内容

3、在人工智能中，重点关注两个方面的内容：问题的表示问题的表示（知识的表示）（知识的表示）：即要找到问题的一：即要找到问题的一种合适的表示方法种合适的表示方法在符号主义的人工智能中，有：在符号主义的人工智能中，有：状态空间法状态空间法问题归约法问题归约法谓词逻辑法谓词逻辑法其它表示方法其它表示方法2022-5-1问题的求解问题的求解：从问题表示方法出发，找到一个：从问题表示方法出发，找到一个合理的办法来求解合理的办法来求解在符号主义的人工智能中，常有的方法有：在符号主义的人工智能中，常有的方法有：搜索法搜索法推理法推理法2022-5-12.1.1 状态空间法状态空间法 1 问题的状态描述问题的状态

4、描述2 状态图示法状态图示法3 例子例子2022-5-1在日常的一些智力游戏（八数码、走八卦阵、走在日常的一些智力游戏（八数码、走八卦阵、走迷宫等）中，我们采用的迷宫等）中，我们采用的策略策略：试着向前走，如试着向前走，如果走不通，则往后退，不停地试、试、试，直到果走不通，则往后退，不停地试、试、试，直到成功成功12457836123456782022-5-1类似地，在人工智能中，一种最基本的类似地，在人工智能中，一种最基本的求解方法求解方法就就是试探搜索法，即，通过在某个可能的是试探搜索法，即，通过在某个可能的解空间解空间（例（例如，所有可能的走法）中寻找一个解（如，一种走如，所有可能的走法

5、）中寻找一个解（如，一种走法）法）这种基于解空间的这种基于解空间的问题表示问题表示和和求解方法求解方法就是就是状态空间法状态空间法，其基础是，其基础是状态状态和和算符算符（算子）（算子）2022-5-11 问题的状态描述问题的状态描述状态状态：描述某一类不同事物间的描述某一类不同事物间的差别差别而引入的一而引入的一组组最少最少变量变量q0 ,q1 , qn的的有序有序集合集合2022-5-1例：例：描述在坐的同学描述在坐的同学变量可以有变量可以有年级年级专业专业姓名姓名性别性别学号学号2022-5-1矢量形式矢量形式： Q= q0, q1, , qn T 其中，元素其中，元素 qi ( i=0

6、, 1, n)为集合的分为集合的分量，称为量，称为状态变量状态变量。具体状态具体状态：给每一个状态变量一个具体的：给每一个状态变量一个具体的值（符号、数值等）。值（符号、数值等）。2022-5-1矩阵形式矩阵形式1111.nmmnqqQqq2022-5-1例：例：八数码问题八数码问题矢量形式的状态表示：矢量形式的状态表示：12347865矩阵形式的状态表示：矩阵形式的状态表示：1, 2, 3, 4, 7, 8, 6, 5, 01234786502022-5-1算符（操作符）算符（操作符）：使问题从一个状态使问题从一个状态变换到另一状态的手段。变换到另一状态的手段。例如：走步、规则、数学算子、运

7、算例如：走步、规则、数学算子、运算符号等等。符号等等。2022-5-1例：例：描述在坐的同学（续）描述在坐的同学（续）状态变量状态变量可以有可以有年级年级专业专业姓名姓名性别性别学号学号操作符操作符入学入学正常升级正常升级毕业毕业2022-5-1例：例：八数码问题八数码问题12347865算符算符：1、数字的上、下、左、右移动、数字的上、下、左、右移动2、空格的上、下、左、右移动、空格的上、下、左、右移动2022-5-1问题的状态空间问题的状态空间：一个表示问题全部可能状一个表示问题全部可能状态及其关系的图，它包含了三个集合：态及其关系的图，它包含了三个集合：1. 所有可能的问题初始状态集合所

8、有可能的问题初始状态集合S2. 操作符集合操作符集合F3. 目标状态集合目标状态集合G状态空间记作三元状态（状态空间记作三元状态（S, F, G） 2022-5-1例：例：十五数码问题十五数码问题 123456789101112131415 119415131275861321014初始状态初始状态：左图：左图目标状态目标状态：右图：右图操作符集合操作符集合F空格的左移、上移、右移、下移空格的左移、上移、右移、下移 2022-5-1可能的求解过程可能的求解过程注注：在程序和图示求解过程中，需要规定好操作符：在程序和图示求解过程中，需要规定好操作符的使用顺序的使用顺序2022-5-1要完成某一个

9、具体问题的状态描述，必须完要完成某一个具体问题的状态描述，必须完成成三项工作三项工作：如何描述状态，特别是初始状态如何描述状态，特别是初始状态操作符集合及其对状态描述的作用操作符集合及其对状态描述的作用如何描述目标状态如何描述目标状态即定义好三元状态（即定义好三元状态（S, F, G）中的三个成分中的三个成分 2022-5-1状态空间法状态空间法：从某一个初始状态开始，每次施加一个操作符，递从某一个初始状态开始，每次施加一个操作符，递增地建立操作符序列，直到达到目标状态为止增地建立操作符序列，直到达到目标状态为止2022-5-1状态空间法的问题状态空间法的问题：寻找从初始状态到目标状态的某一个

10、操作符序列寻找从初始状态到目标状态的某一个操作符序列状态空间法的解状态空间法的解：从初始状态变换到目标状态的操作符序列从初始状态变换到目标状态的操作符序列1194151312758613210 14123456789101112131415 2022-5-12 状态图示法状态图示法 图图是由节点（不一定是有限个的节点）的集合是由节点（不一定是有限个的节点）的集合构成的构成的注意注意：在图论中，图的定义中还包括边的集合：在图论中，图的定义中还包括边的集合状态空间法（求解过程）的表示方法：用图来表状态空间法（求解过程）的表示方法：用图来表示（借助于图论中某些技术）示（借助于图论中某些技术）2022

11、-5-1有向图和无向图：有向图和无向图：2022-5-1无向图无向图：一对节点可能互为后裔，边用线段：一对节点可能互为后裔，边用线段来表示来表示2022-5-1有向图有向图：一对节点用弧线连接起来，并且从一一对节点用弧线连接起来，并且从一个节点指向另一个节点个节点指向另一个节点 父辈节点或祖先父辈节点或祖先n i后继节点或后裔后继节点或后裔nj 2022-5-1对于某一个节点序列对于某一个节点序列（ni1, ni2, nij, , nik） 如果每一个节点如果每一个节点nij-1都有一个都有一个后继节点后继节点 nij 存在，则将这一存在，则将这一序列称为从节点序列称为从节点 ni1 到到 n

12、ik 的的长度为长度为 k 的路径。的路径。 nikni12022-5-1如果从节点如果从节点 ni 到到 nj 存在存在一条路径，则称节点一条路径，则称节点 nj 是是从节点从节点 ni 可到达的节点，可到达的节点，或者称或者称 nj 是是 ni 的后裔节的后裔节点、称点、称 ni 是是 nj 的祖先。的祖先。 njni2022-5-1当用有向图来表示状态空间法时，对应关系：当用有向图来表示状态空间法时，对应关系：图中的一个图中的一个节点节点对应于某一个对应于某一个状态状态图中的一个图中的一个有向弧有向弧对应于某一个对应于某一个算符算符 注注：有向：有向弧的旁边可以标以具体算符弧的旁边可以标

13、以具体算符2022-5-1状态状态节点节点操作符操作符有向弧有向弧2022-5-1问题问题：寻找从初始状态到目标：寻找从初始状态到目标状态的某个操作符序列状态的某个操作符序列问题问题：寻找图中初始节点（对应初：寻找图中初始节点（对应初始状态）到目标节点（对应于目标始状态）到目标节点（对应于目标状态）的一条路径状态）的一条路径转化为转化为2022-5-1c (ni , nj) 表示从节点表示从节点 ni 指向节点指向节点 nj （相邻）的（相邻）的那一段弧的代价那一段弧的代价 n jn i在某些情况下，每个操作符作用、成本是不在某些情况下，每个操作符作用、成本是不一样的，需要引入一样的，需要引入

14、代价代价的概念的概念2022-5-1（不相邻的）两个节点（不相邻的）两个节点间路径的代价间路径的代价等于等于连接连接该路径的各个节点的所该路径的各个节点的所有弧线的代价之和有弧线的代价之和 nkn0C(n0,n1)C(nk-1,nk)2022-5-1引入代价的概念后，我们的问题可能是：引入代价的概念后，我们的问题可能是：寻找初始节点到目标节点之间的代价最小的寻找初始节点到目标节点之间的代价最小的路径路径对应的原始问题对应的原始问题：寻找从初始状态到目标状：寻找从初始状态到目标状态的操作符代价之和最小的操作符序列态的操作符代价之和最小的操作符序列2022-5-1利用图论的技术，我们要解决两个问题

15、：利用图论的技术，我们要解决两个问题：第一、找出初始节点到目标节点的一条路径。对应第一、找出初始节点到目标节点的一条路径。对应于于寻找初始状态到目标状态的操作符序列寻找初始状态到目标状态的操作符序列第二、找出初始节点到目标节点的一条代价最小的第二、找出初始节点到目标节点的一条代价最小的路径。对应于路径。对应于寻找将初始状态变换到目标状态所用寻找将初始状态变换到目标状态所用操作符代价之和最小的操作符序列操作符代价之和最小的操作符序列2022-5-13 例子例子 例例1：八数码问题八数码问题 八数码的任何一种摆法是一个八数码的任何一种摆法是一个状态状态，状态总数，状态总数为为9！。用一个长度为！。

16、用一个长度为9的一维数组来描述状态：的一维数组来描述状态：（q1, q2, ,q9）其中，其中，qi 取取0, 1, , 8个数，个数，0表示空格，且取值互表示空格，且取值互不相同。不相同。 算符算符是空格的上、下、左、右移动是空格的上、下、左、右移动2022-5-1 如果记空格的位置为如果记空格的位置为P，这时空格的，这时空格的移动规则移动规则是：是：12385674123856740PP-3P+1P+3P-1表示位置表示位置1 2 3 4 5 6 7 8 9P2022-5-1 代码代码规则规则前提条件前提条件应用结果应用结果1左移左移P1,4,7P 位置与位置与 P-1 位置上的元素互换位

17、置上的元素互换2上移上移P1,2,3 P-33右移右移P3,6,9 P+14下移下移P7,8,9 P+3空格移动规则空格移动规则123456789表示位置表示位置2022-5-1初始状态：初始状态：( (2，0，3，1，8，4，5，6，7）目标状态目标状态: :（1，2，3，8，0，4，7，6，5） 状态图状态图2022-5-1注意注意：事先规定操作符的前后顺序，便于编程事先规定操作符的前后顺序，便于编程不要生成已有的状态（节点），防止进入死循环不要生成已有的状态（节点），防止进入死循环2022-5-1例例2：迷宫问题：迷宫问题 2022-5-1给图上加一个坐标系，定义每一个分叉路口给图上加一

18、个坐标系，定义每一个分叉路口为一个状态。为一个状态。2022-5-1操作符为人的上、操作符为人的上、下、左、右走动下、左、右走动初始状态为（初始状态为（1，1）目标状态为（目标状态为（4，4）2022-5-1状态图状态图2022-5-1例例3：梵塔问题梵塔问题（三个盘）（三个盘） 对于对于 n 个盘的问题，我们用个盘的问题，我们用 n 维向量维向量 （a1 a2an）表示问题的一个状态表示问题的一个状态其中其中ai = 1, 2, 3 表示第表示第i个盘位于第一、二、个盘位于第一、二、三个柱子上，三个柱子上，a1 an中盘的大小从中盘的大小从大到小大到小21.naaa2022-5-1初始状态初

19、始状态为（为（11），目标状态为（），目标状态为（33）操作符操作符m(i, j)：表示一个盘从表示一个盘从 i 根柱子搬到第根柱子搬到第 j 根根柱子。柱子。T(k)：表示第表示第 k 根柱子上（最上面）的盘的大小。根柱子上（最上面）的盘的大小。操作符集合为：操作符集合为： O=m( i , j ) | T( i )T( j ) 2022-5-1状态图状态图2022-5-1例例4：猴子与香蕉问题：猴子与香蕉问题 a c b2022-5-1用一个四元组用一个四元组（W，x, Y, z）来表示来表示问题的状态问题的状态W：猴子的水平位置猴子的水平位置x： 当猴子爬到箱子顶上取当猴子爬到箱子顶上取

20、1，否则取，否则取0Y： 箱子的水平位置箱子的水平位置z： 当猴子摘到香蕉时取当猴子摘到香蕉时取1，否则取，否则取0初始状态初始状态是（是（a, 0, b, 0），），目标状态目标状态是（是（c, 1, c, 1）2022-5-1操作符操作符：猴子当前位置猴子当前位置W走到水平位置走到水平位置U：goto(U)： （W, 0 , Y, z）(U, 0 , Y, z)说明说明：猴子不能在箱子上：猴子不能在箱子上 猴 子 将 箱 子 从猴 子 将 箱 子 从 W 位 置 推 到 水 平 位 置位 置 推 到 水 平 位 置 V ：pushbox(V)： （W, 0, W, z） (V, 0, V,

21、 z)说明说明：猴子与箱子的位置同时变化：猴子与箱子的位置同时变化2022-5-1操作符操作符：猴子爬到箱子上：猴子爬到箱子上：climbbox： （W, 0, W, z） (W，1, W, z)猴子摘到香蕉：猴子摘到香蕉：grasp： （c, 1, c, 0） (c, 1, c, 1)2022-5-1a c bpushbox(c)(a, 0, b, 0)(b, 0, b, 0)(c, 0, c, 0)(b, 1, b, 0)(c, 1, c, 0)(c, 1, c, 1)goto(b)climbboxclimbboxgrasp状态空间图状态空间图2022-5-12.1.2 问题归约法问题归约

22、法 例：求积分例：求积分 解法解法1：解法解法2：解法解法3：2(cos)xexxdx223(cos)cossin3xxxexxdxe dxxdxx dxxex2022-5-1问问 题题解法解法1解法解法2解法解法3解法解法4子子问题问题1子子问题问题2子子问题问题3变换变换分解分解2022-5-1问题归约法问题归约法：从已知问题的描述出发，通过一系列从已知问题的描述出发，通过一系列变换变换或或分解分解将问题最终变为一个将问题最终变为一个子问题集合子问题集合，这些子问题的，这些子问题的解可以直接得到，从而解决初始问题解可以直接得到，从而解决初始问题 2022-5-1问题归约法由三个部分组成问题

23、归约法由三个部分组成： 一个初始问题描述一个初始问题描述 一套将问题变换或分解为子问题的操作符一套将问题变换或分解为子问题的操作符 一套本原问题（一套本原问题（解可以直接得到的简单问题解可以直接得到的简单问题）描述描述2022-5-11 问题归约描述问题归约描述 例：例：梵塔问题梵塔问题（三个盘）（三个盘） (a) 初始配置初始配置(b) 目标配置目标配置图图2.6 梵塔难题梵塔难题2022-5-1解决问题的思路解决问题的思路：第一第一、要将所有盘从第一个柱子搬到第三个、要将所有盘从第一个柱子搬到第三个柱子，根据游戏规则，首先要搬最大的柱子，根据游戏规则，首先要搬最大的 C 盘盘到第三个柱子上

24、到第三个柱子上(a) 初始配初始配置置(b) 目标配置目标配置图图2.6 梵塔难题梵塔难题2022-5-1解决问题的思路解决问题的思路：第二第二、要能够搬、要能够搬 C 盘，条件是：第三个柱盘，条件是：第三个柱子是空的，子是空的，A、B必须在第二个柱子上（这必须在第二个柱子上（这里没有考虑如何搬里没有考虑如何搬A、B盘）盘）(a) 初始配初始配置置(b) 目标配置目标配置图图2.6 梵塔难题梵塔难题2022-5-1解决问题的思路解决问题的思路：第三第三、搬、搬C盘到第三个柱子，然后想办法将盘到第三个柱子，然后想办法将A、B盘搬到第三个柱子上盘搬到第三个柱子上 (a) 初始配初始配置置(b) 目

25、标配置目标配置图图2.6 梵塔难题梵塔难题2022-5-1将问题简化为下列三个子问题：将问题简化为下列三个子问题：1. 移动园盘移动园盘A和和B到柱子到柱子2的双园盘难题的双园盘难题2. 移动移动C盘到柱子盘到柱子3的单园盘难题的单园盘难题3. 移动移动A和和B到柱子到柱子3的双园盘难题的双园盘难题2022-5-1图图2.8 梵塔问题的归约梵塔问题的归约从左到右表示盘从左到右表示盘从大到从大到小，数字表示柱子号小，数字表示柱子号小小盘：盘：13中盘：中盘：12小盘：小盘：32小小盘：盘：21中盘：中盘：23小盘：小盘：13与与中小盘中小盘1到到2大盘大盘1到到3中小盘中小盘2到到32022-5

26、-1问题归约法的问题归约法的基本思路基本思路是：应用一系列算符将原是：应用一系列算符将原始问题的描述始问题的描述变换或分解变换或分解成为子问题的描述成为子问题的描述问题的描述问题的描述可以采用各种数据结构，如表、树、可以采用各种数据结构，如表、树、矢量、数组等矢量、数组等对于梵塔问题，问题及子问题描述：对于梵塔问题，问题及子问题描述： (113)(333)2022-5-1问题归约法可以用一个三元组（问题归约法可以用一个三元组（S, O, P）来表示，来表示，其中：其中： S：原始问题，即要解决的问题原始问题，即要解决的问题 P：本原问题集，其中的每一个问题是不用证本原问题集，其中的每一个问题是

27、不用证明的或自然成立的，例如公理、已知事实等明的或自然成立的，例如公理、已知事实等 O：操作算子集，用于将问题化为子问题操作算子集，用于将问题化为子问题2022-5-12 与或图表示与或图表示 例例：有一个问题：有一个问题A，它可以通过三种途径来求解：它可以通过三种途径来求解：(1)、求解问题、求解问题 B 和和 C(2)、求解问题求解问题 D 、E 和和 F(3)、求解求解 H2022-5-1与与或或引入中间节点引入中间节点2022-5-1好处好处：任何一个节点的后继节点要么全是任何一个节点的后继节点要么全是“与节与节点点”，要么全是，要么全是“或节点或节点”。2022-5-1与或图的特例与

28、或图的特例： 所有节点都是或节点，这时就是一般的所有节点都是或节点，这时就是一般的图图，即，即状态空间法用到的图状态空间法用到的图 除了起始节点外，所有节点只有一个父节点，除了起始节点外，所有节点只有一个父节点，此时称为此时称为与或树与或树，前面的图，前面的图2.11就是与或树就是与或树 2022-5-1问题归约法、与或图表示之间的对应关系问题归约法、与或图表示之间的对应关系：问题归约法问题归约法原始问题原始问题本原问题本原问题操作符操作符中间问题中间问题与或图表示与或图表示起始节点起始节点终叶节点终叶节点与、或关系的弧线与、或关系的弧线非终叶节点非终叶节点2022-5-1在与或图中，问题在与或图中，问题有解的条件有解的条件是：起始节点是是：起始节点是可解可解的的 一般情况下：一般情况下：分解分解 操作符得到操作符得到 与节点与节点变换变换 操作符得到操作符得到 或节点或节点2022-5-1在