人工智能问题求解基本原理及搜索技术.ppt

人 工 智 能 ( 问题求解基本原理及搜索技术 ),问题求解基本原理,问题求解：在给定条件下，寻求一个能解决某类问题且能在有限步骤内完成的算法。,问题求解特征： 传统软件： 求解的问题是能够用数学精确描述的良结构的问题（如，解方程）； 计算机执行的繁杂的统计计算任务一般不能看成是人工智能活动。,AI软件： 求解的是不可直接用数学模型描述的所谓不良结构问题（如，几何证明、求不定积分、逻辑演算等），通常需要采用弱方法进行搜索求解； AI程序中符号的内涵不仅局限于数值计算和数据处理中的一般数据信息，应表现人类进行推理所需要的各种知识。,问题求解基本原理,一、问 题 求 解 的 基 本 方 法 二、搜 索 技 术,问题求解基本原理,问题求解方法： 基于状态空间的问题求解方法 基于问题空间的问题求解方法 基于博弈搜索的问题求解方法,问题实例,桌上固定了 3 根柱子，按 1，2，3 次序排例。有 n 个大小全不一样大的盘子d1，dn ，按从小到大，小的在上的次序依次插在第一根柱子上，要把这 n 个盘子全部搬到第三根柱子上，每次只许搬一个，任何时候都不允许把大盘子放在小盘子上面，问该如何搬法。 设 n = 3，该如何搬法？,1 2 3 1 2 3,梵塔问题,基于状态空间的问题求解方法,（1，1，1） （1，1，2） （1，1，1） （1，1，3） （1，1，2） （1，3，2） 。,状态合法变换规则（满足约束条件）：,状态定义 -（i大, j中, k小 ）: 设向量下标分别表示大盘、中盘、小盘；向量值分别表示盘子所在柱子的编号。 状态描述 - 大盘在第 i 根柱子上；中号盘在第 j 根柱子上，小号盘在第 k 根柱子上。,基于问题空间的问题求解方法,问题：如何将 i 柱子上的 m 个盘子搬到 k 柱子上 ? 将 i 柱子上的 m 1 个盘子搬到 j 柱子上； 将 i 柱子上的 第 m 个盘子搬到 k 柱子上； 将 j 柱子上的 m 1 个盘子搬到 k 柱子上。,问题描述： 问题（a, b, c): 将 b 柱子上的 a 个盘子搬到 c 柱子上。 问题分解合法规则： （3，1，3）-（2，1，2） (1，1，3） （2，2，3） 。,基于问题空间的问题求解方法,状态空间法有关概念,状态空间法: 从问题的初始状态出发，通过一系列的状态变换找到目标状态的问题求解方法。,状态：描述问题中事物形状或状况的符号或数据结构。,状态空间：所有状态的全体构成的集合；用四元组（S, S0, O, G) 表示: S: 非空状态子集，S0 = 初始状态（非空）。 G: 非空目标状态子集。 O: 操作算子集合，一个状态合法转换为另一个状态的描述规则,问题求解过程：隐含求一个普通有向图，节点 - 状态，边 算子,状态变换规则：一个状态向另一个状态合法转换的描述规则。,状态空间法有关概念,状态空间、搜索空间及解径的关系：,问题有解：从代表初始状态 s 节点出发， 存在一条通向目标节点的路径,搜索空间：问题求解过程中到达过的所有状态（节点）的集合。,问题空间法有关概念,问题空间法： 首先产生待证问题的所有子问题，而后通过解决所有子问题达到问题求解目的的方法。,问题：描述问题及其子问题的符号或数据结构。,问题空间：初始问题以及其所有子问题的全体构成的集合，用四元组（S, S0, F, G) 表示: S: 问题和子问题； S0 : 初始问题。 G: 具有平凡解的本原问题集合。 F: 操作算子集合，用于将问题分解成其若干个子问题的描述规则,问题分解规则：将一个问题（子问题）分解成其若干个子问题。,问题空间法的有关概念（2）,问题空间分解过程：隐含求一个与或图 节点 问题， 边 - 分解问题的算子。,“与” 节点：如果节点 A 有边通向一组节点 B1，B2，Bn ，问题 A 的解决有待于 A 的子问题组 B1,B2Bn 的全部解决，则称 A 为“与” 节点。如图 a 所示。,“或” 节点：若节点有边通向一组节点,2，n，问题的解决有待于子问题或2或或n中某一个子问题的解决，则称 A 为“或” 节点。如图 b 所示。,问题空间法有关概念（2）,问题的解（解图）：从代表初始问题的节点出发，搜索到一个完整的与或 子图，图中所有叶节点均满足问题求解的结束条件。,例：（C,B,Z) -（M,M) 重写规则: R1: C ( D, L ) R2: C ( B, M ) R3: B ( M, M) R4: Z ( B, B,M ),小结 问题求解方法比较,问题求解基本原理,一、问 题 求 解 的 基 本 方 法 二、搜 索 技 术 （一）,搜索技术预备 状态空间搜索 有关概念 盲目搜索策略 启发式搜索策略,问题求解基本原理,搜索策略预备,盲目搜索： 不考虑给定问题所具有的特定知识，系统按照事先确定好的某种固定顺序调用规则，或是随机地调用规则。,常用的盲目搜索算法: 深度优先搜索策略； 宽度优先搜索策略,搜索策略预备,启发式信息： 与问题求解有关的信息和知识。 由于信息的片面性和不准确性，应用启发式信息不能百分之百地保证找到问题的解，但能提高问题求解的可能性。,启发式信息在问题求解过程中的作用： 有助于加速求解过程； 有助于找到“较优”解。,启发式搜索策略: 考虑给定问题领域具有的特定知识（启发式信息），系统动态地规定规则调用顺序，优先使用“较”合适的规则。,搜索策略预备,常用的基于状态图的启发式搜索策略 : 爬山搜索策略 (Hill Climbing) 大英博物馆搜索策略 (British Museum) 启发式图搜索策略 ( A ) 最佳启发式图搜索策略 ( A* ),常用的基于与或图及博弈的启发式搜索策略： 最佳启发式与或图搜索策略 ( AO* ) 极大极小搜索策略 (Minimax) 剪枝搜索策略 (Alpha-Beta Pruning),基于状态空间的搜索技术： 有关搜索概念 盲目搜索策略 启发式搜索策略,问题求解基本原理,状态空间搜索有关概念,状态图特点：多条路径通向同一节点。例：,状态空间搜索有关概念,状态图搜索及生成过程: 从S节点开始，不断搜索规则，动态生成节点; 扩展局部图；最终求得 S - G 的可达路径。,隐含生成有重复节点的树搜索过程 特殊的图搜索,状态空间搜索有关概念,节点深度： 根节点的深度为0，其它节点的深度规定为其父节 点的深度加 1，即dn+1 = dn + 1 。,标记节点 n：用指针将后继节点连接到父节点 n 的操作 。,节点：对应状态图中有关状态的描述。,扩展节点n：称生成节点 n 的所有后继节点并计算生成这些后继节点所造成的花费的过程（ 即，计算各后继节点的优劣且将其连接到节点 n 等操作造成的开销 ）叫做扩展节点 n 。,后继节点：称将规则作用于节点 n 生成的新节点为节点 n 的后 继节点。,路径：对于一个节点序列（n0, n1, , nl, , nk），如若每一节点 ni-1都有一个后继节点 ni（i = 1, 2, , k），则称该节点序列为一条从节点 n0 到节点 nk、长度为 k 的路径；路径还可表示为与节点序列对应的规则序列 。,状态空间搜索有关概念,路径花费：设 C（ni，nj）为节点 ni 到 nj 这段路径（或弧线）的花费。一条路径的花费等于连接这条路径各节点间所有弧线花费值的总和。路径 ni nj t 的花费值C（ni，t）可递归计算如下: C（ni，t）= C (ni，nj) + C（nj，t )。,基于状态空间的盲目搜索算法: 宽度优先搜索策略 深度优先搜索策略,问题求解基本原理,盲目搜索算法的符号及数据结构,s： 初始节点； n：当前节点。,open： 已被生成但未被扩展的节点序列表；,closed：已被生成且已被扩展的节点序列表；,mi = mj mk ml：扩展 n 后所得的 n 的后继节点 其中，, mk ：在OPEN表中出现过的待扩展节点，, ml ：在CLOSED表中出现过的已扩展节点。,宽度优先搜索算法,open := S; closed := ; while open do n := first ( open ); remove ( first ( open ) ); add ( n, closed )； if n = goal then exit ( success ); expand ( n ) - mi ; delete ( (mi)( mi mk ( mi ml ) ); append ( open, mj) ; exit ( fail );,宽度优先搜索算法,1、S, A, D,2、A, D, B, D,3、D, B, A, E,Open 表为队 操 作： 先进先出！,节点扩展顺序,宽度优先搜索算法,open := S; closed := ; d = 深度限制值 while open do n := first ( open ); remove ( first ( open ) ); add ( n, closed )； if n = goal then exit ( success ); if depth ( n ) d then continue; expand ( n ) - mi ; delete ( (mi)( mi mk ( mi ml ) ); Insert ( mj, open ) ; exit ( fail );,深度优先搜索算法,深度优先搜索算法,1、S,2、A, D,3、B, D, D,Open表为栈 操 作：后进先出！,4、C, E, D,节点扩展顺序,深度优先搜索算法,盲目搜索算法应用实例-,8数码问题,描述状态： 矩阵(Sij)，其中 1i,j3，Sij0,1,8;,盲目搜索算法应用实例 -,合法走步规则：,设 (i0、j0)为空格所在行列数值， Si0j0 = 0 R1: if j-11 then Si0j0:= Si0(j0-1), Si0(j0-1):=0 空格左移； R2: if i-11 then Si0j0:= S(i0-1)j0, S(i0-1)j0:=0 空格上移； R3: if j+13 then Si0j0:= Si0(j0+1), Si0(j0+1):=0 空格右移； R4: if i+13 then Si0j0:= S(i0+1)j0, S(i0+1)j0:=0 空格下移。,8数码问题,宽度优先策略求解8数码问题：,深度优先策略求解8数码问题：,说明： 设规则固定使用顺序： R1- 左移、R2-上移、R3- 右移、R4-下移； 设节点深度限制值：6 ；,合法的走步规则,重复节点 造成循环,1、利用宽度优先法或深度优先法，程序实现 High-way map 问题求解，只考虑节点的连接和变换,不考虑边的权值;求出有向图的一条解径,给出求解过程（即，给出Open，Closed表中的内容）。,作业:,2、利用宽度优先法或深度优先法，程序实现 8数码问题。 - 隐含生成有向图,给定两个油桶,一个可装 4 公斤油,一个可装 3 公斤油,油桶上无任何度量标记。问：怎样才能使 4 公斤油桶里恰好只装 2 公斤油？ 设状态定义：(x,y)，其中， x： 4 公斤油桶中实际装油公斤数； y： 3 公斤油桶中实际装油公斤数。 问题表示： (0, 0) -(2, y) 要求定义合法的装油规则，利用盲目搜索策略画出状态图。,作业:,问题求解基本原理,基于状态空间的启发式搜索算法: A 算法； A* 算法,启发式图搜索策略,A算法、A*算法 核心思想： 1、盲目搜索： 根据节点连接情况，寻找s-t的解径（不一定最佳）； 2、启发式搜索：根据节点连接及其花费情况，较快地寻找 s-t 的最 佳（花费最小）的解径； 3、求解思路： 图搜索中，s-t 的路径总可以表示成 s-n-t； 若对图中每一个 n, 都设置一个f(n),唯一地表示s-n-t路径的 花费，即，在 n 与 f(n) =（s-n-t 路径的花费）之间建 立一对一的映射；每当从当前局部搜索树中选择扩展叶节点 n 时，以f(n)=s-n-t路径花费最少为衡量标准；以此保证每次选 择、扩展节点 n 都在当前局部最小花费的路径上进行。,4、需解决的问题：如何为图中节点 n 定义标志全程路径 s-n-t 的花 费评价函数值 f（n）？ 如何保证节点 n 的 f(n) 的唯一性。,启发式图搜索算法,假设：,f (n) = g (n) + h (n) 任意节点 n 的评价函数：指迄今为止已找到的从初始节点 s ，到达节点 n，再从节点 n 到达目标节点 t 的路径全程的最小费用，是对 f *(n ) 的一个估计。,h (n) ：迄今为止从节点 n 到目标节点 t 最佳分段路径将要花费的未知估计费用，是对 h* (n) 的一个估计，可视为启发式分量函数，有h (n) 0。,g (n) ：迄今为止搜索到的从初始节点 s 到当前节点 n 最佳路径分段的已知费用，是对g* (n) 的一个估计。,f *(n) = g* (n) + h* (n)：从初始节点 s 出发，经过最佳路径上任意节点 n，到达目标节点 t 的最小费用。,h* (n)：n t 最佳路径的分段费用。,g* (n)：sn 最佳路径的分段费用。,s：初始节点；n：当前节点；t：目标节点。,启发式图搜索算法 - A 算 法,定义：按照 f (n) = g (n) + h (n) 估价函数值由小到大地排列待扩展节点顺序的图搜索算法，称为A 算法。,A 算法流程。,A算法应用实例: 普通有向图 A 算法搜索实例； 8数码问题A 算法搜索实例。,启发式图搜索算法 - A算法,算法中符号： s：初始节点；G：搜索图的节点集合； OPEN表： 已生成但尚未被扩展的节点序列表； CLOSED表： 已生成且已被扩展的节点序列表； n： 待扩展的当前节点； mi = mj mk ml：扩展 n 后生成的后继节点 其中， mj：第一次生成的节点，mj OPEN 且 mj CLOSED表， mk：在OPEN表中出现过的待扩展节点， ml：在CLOSED表中出现过的已扩展节点。,A算法,搜索算法应用实例 - 8数码问题,状态描述： 矩阵(Sij)，其中 1i,j3，Sij0,1,8,搜索算法应用实例 - 8数码问题,合法走步规则：,设i0, j0为空格所在行列数值， Si0j0 = 0 R1: if j0-11 then Si0j0:= Si0(j0-1), Si0(j0-1):=0 空格左移； R2: if i0-11 then Si0j0:= S(i0-1)j0, S(i0-1)j0:=0 空格上移； R3: if j0+13 then Si0j0:= Si0(j0+1), Si0(j0+1):=0 空格右移； R4: if i0+13 then Si0j0:= S(i0+1)j0, S(i0+1)j0:=0 空格下移。,搜索算法应用实例 - 8数码问题,g(n): 搜索树中节点 n 所在层的深度，每层为单位花费,h(s) = w(s) = 4,h(n)= W(n)：相对于目标节点而言，节点 n 中 “不在位” 的将牌个数之和” (二者差异) 启发式分量函数。,f(n) = g(n) + h(n)：节点 n 的层次深度一定，n 与目标节点之间的差异越小，即 h(n) 越小，则 f(n) 越小，优先扩展。,搜索算法应用实例 - 8数码问题,括号中为 f 值,启发式最佳图搜索算法 - A*算法,A*算法定义： 若将A算法中评价函数 f (n)的启发式分量函数 h（n）的值限制在 h*（n）的下界范围内，亦即对所有节点 n，都满足h（n） h*（n），则称此时的 A 算法为 A* 算法。,A*算法作用： 问题有解时， A*算法一定能够找到从初始节点 s 到目标节点 t 的最佳解径。,信息度定理： 有两个A*算法A1和A2, 若A2比A1有较多的启发式信息（即对所有非目标节点均有： h1（n） h2（n） h*（n），则在具有一条从 s 到 t 的隐含状态图上，搜索结束时，由A2扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。,启发式最佳图搜索算法 - A*算法,A *算法应用验证: 8数码问题A * 算法搜索实例。,A* 算法应用实例 - 8数码问题,状态描述： 矩阵(Sij)，其中 1i,j3，Sij0,1,8,A* 算法应用实例 - 8数码问题,合法走步规则：,设i0, j0为空格所在行列数值， Si0j0 = 0 R1: if j0-11 then Si0j0:= Si0(j0-1), Si0(j0-1):=0 空格左移； R2: if i0-11 then Si0j0:= S(i0-1)j0, S(i0-1)j0:=0 空格上移； R3: if j0+13 then Si0j0:= Si0(j0+1), Si0(j0+1):=0 空格右移； R4: if i0+13 then Si0j0:= S(i0+1)j0, S(i0+1)j0:=0 空格下移。,A* 算法应用实例 - 8数码问题,g(n): 搜索树中节点n所在层的深度，每层为单位花费。,h(n)= P(n)：节点 n 中各将牌与目标节点中对应将牌相比归位的距离之和（不考虑夹在其间的将牌）。- 启发式分量函数,f(n)=g(n)+h(n)：节点 n 的层次深度一定，节点 n 与目标节点之间对应将牌的距离之和越小，即 h(n) 值越小，f(n) 越小，优先扩展,h(s) = P(s) = 5,A* 算法应用实例 - 8数码问题,启发式函数比较: h(n) = P(n): 指出了本节点中各将牌归位的步数之和，但未具体给出若考虑夹在其间的将牌，应如何移动将牌、搜索最小解径的指导信息，因此有 P(n)h(n)*。,对于任一节点n，至少要移动 P(n)步才能达到目标。实际的走步数要经过一定程度的搜索。,h(n) = W(n): 指出了本节点与目标节点的差异,但未具体给出如何移动将牌、搜索最小解径的指导信息：W(n)h(n)*,对于任一节点n，至少要移动 W(n)步才能达到目标。实际的走步数要经过一定程度的搜索。,两算法均为A*算法 W(n) P(n) h*(n),A* 算法应用实例 - 8数码问题,8数码问题搜索策略比较：,宽度优先 A算法 A*算法,小结,启发式搜索策略,g: 考虑当前路径已经花费的费用，及时抛弃已经经过的花费太大且距目标仍远的路径;,h: 估计当前路径上节点到目标节点还需要的费用，引导搜索向最有希望的路径前进。,A 算法：定义估计函数：f = g + h；,A* 算法：定义估计函数：f = g + h； 满足h（n） h*（n）。,作业:,1、设 h=0; f=g=边的标记值，程序求解 High-way map 问题，求出最短解径，给出求解过程（Open，Closed内容）。,2、设g=搜索深度，h=W或h=P，程序实现8数码问题。 打印搜索过程，即有向图生成过程； 给出解径。,