人工智能问题求解基本原理及搜索技术.ppt
《人工智能问题求解基本原理及搜索技术.ppt》由会员分享,可在线阅读,更多相关《人工智能问题求解基本原理及搜索技术.ppt(59页珍藏版)》请在三一文库上搜索。
1、人 工 智 能 ( 问题求解基本原理及搜索技术 ),问题求解基本原理,问题求解:在给定条件下,寻求一个能解决某类问题且能在有限步骤内完成的算法。,问题求解特征: 传统软件: 求解的问题是能够用数学精确描述的良结构的问题(如,解方程); 计算机执行的繁杂的统计计算任务一般不能看成是人工智能活动。,AI软件: 求解的是不可直接用数学模型描述的所谓不良结构问题(如,几何证明、求不定积分、逻辑演算等),通常需要采用弱方法进行搜索求解; AI程序中符号的内涵不仅局限于数值计算和数据处理中的一般数据信息,应表现人类进行推理所需要的各种知识。,问题求解基本原理,一、问 题 求 解 的 基 本 方 法 二、搜
2、 索 技 术,问题求解基本原理,问题求解方法: 基于状态空间的问题求解方法 基于问题空间的问题求解方法 基于博弈搜索的问题求解方法,问题实例,桌上固定了 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) 。,状态合法变换
3、规则(满足约束条件):,状态定义 -(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
4、,1,2) (1,1,3) (2,2,3) 。,基于问题空间的问题求解方法,状态空间法有关概念,状态空间法: 从问题的初始状态出发,通过一系列的状态变换找到目标状态的问题求解方法。,状态:描述问题中事物形状或状况的符号或数据结构。,状态空间:所有状态的全体构成的集合;用四元组(S, S0, O, G) 表示: S: 非空状态子集,S0 = 初始状态(非空)。 G: 非空目标状态子集。 O: 操作算子集合,一个状态合法转换为另一个状态的描述规则,问题求解过程:隐含求一个普通有向图,节点 - 状态,边 算子,状态变换规则:一个状态向另一个状态合法转换的描述规则。,状态空间法有关概念,状态空间、搜索
5、空间及解径的关系:,问题有解:从代表初始状态 s 节点出发, 存在一条通向目标节点的路径,搜索空间:问题求解过程中到达过的所有状态(节点)的集合。,问题空间法有关概念,问题空间法: 首先产生待证问题的所有子问题,而后通过解决所有子问题达到问题求解目的的方法。,问题:描述问题及其子问题的符号或数据结构。,问题空间:初始问题以及其所有子问题的全体构成的集合,用四元组(S, S0, F, G) 表示: S: 问题和子问题; S0 : 初始问题。 G: 具有平凡解的本原问题集合。 F: 操作算子集合,用于将问题分解成其若干个子问题的描述规则,问题分解规则:将一个问题(子问题)分解成其若干个子问题。,问
6、题空间法的有关概念(2),问题空间分解过程:隐含求一个与或图 节点 问题, 边 - 分解问题的算子。,“与” 节点:如果节点 A 有边通向一组节点 B1,B2,Bn ,问题 A 的解决有待于 A 的子问题组 B1,B2Bn 的全部解决,则称 A 为“与” 节点。如图 a 所示。,“或” 节点:若节点有边通向一组节点,2,n,问题的解决有待于子问题或2或或n中某一个子问题的解决,则称 A 为“或” 节点。如图 b 所示。,问题空间法有关概念(2),问题的解(解图):从代表初始问题的节点出发,搜索到一个完整的与或 子图,图中所有叶节点均满足问题求解的结束条件。,例:(C,B,Z) -(M,M) 重
7、写规则: R1: C ( D, L ) R2: C ( B, M ) R3: B ( M, M) R4: Z ( B, B,M ),小结 问题求解方法比较,问题求解基本原理,一、问 题 求 解 的 基 本 方 法 二、搜 索 技 术 (一),搜索技术预备 状态空间搜索 有关概念 盲目搜索策略 启发式搜索策略,问题求解基本原理,搜索策略预备,盲目搜索: 不考虑给定问题所具有的特定知识,系统按照事先确定好的某种固定顺序调用规则,或是随机地调用规则。,常用的盲目搜索算法: 深度优先搜索策略; 宽度优先搜索策略,搜索策略预备,启发式信息: 与问题求解有关的信息和知识。 由于信息的片面性和不准确性,应用
8、启发式信息不能百分之百地保证找到问题的解,但能提高问题求解的可能性。,启发式信息在问题求解过程中的作用: 有助于加速求解过程; 有助于找到“较优”解。,启发式搜索策略: 考虑给定问题领域具有的特定知识(启发式信息),系统动态地规定规则调用顺序,优先使用“较”合适的规则。,搜索策略预备,常用的基于状态图的启发式搜索策略 : 爬山搜索策略 (Hill Climbing) 大英博物馆搜索策略 (British Museum) 启发式图搜索策略 ( A ) 最佳启发式图搜索策略 ( A* ),常用的基于与或图及博弈的启发式搜索策略: 最佳启发式与或图搜索策略 ( AO* ) 极大极小搜索策略 (Min
9、imax) 剪枝搜索策略 (Alpha-Beta Pruning),基于状态空间的搜索技术: 有关搜索概念 盲目搜索策略 启发式搜索策略,问题求解基本原理,状态空间搜索有关概念,状态图特点:多条路径通向同一节点。例:,状态空间搜索有关概念,状态图搜索及生成过程: 从S节点开始,不断搜索规则,动态生成节点; 扩展局部图;最终求得 S - G 的可达路径。,隐含生成有重复节点的树搜索过程 特殊的图搜索,状态空间搜索有关概念,节点深度: 根节点的深度为0,其它节点的深度规定为其父节 点的深度加 1,即dn+1 = dn + 1 。,标记节点 n:用指针将后继节点连接到父节点 n 的操作 。,节点:对
10、应状态图中有关状态的描述。,扩展节点n:称生成节点 n 的所有后继节点并计算生成这些后继节点所造成的花费的过程( 即,计算各后继节点的优劣且将其连接到节点 n 等操作造成的开销 )叫做扩展节点 n 。,后继节点:称将规则作用于节点 n 生成的新节点为节点 n 的后 继节点。,路径:对于一个节点序列(n0, n1, , nl, , nk),如若每一节点 ni-1都有一个后继节点 ni(i = 1, 2, , k),则称该节点序列为一条从节点 n0 到节点 nk、长度为 k 的路径;路径还可表示为与节点序列对应的规则序列 。,状态空间搜索有关概念,路径花费:设 C(ni,nj)为节点 ni 到 n
11、j 这段路径(或弧线)的花费。一条路径的花费等于连接这条路径各节点间所有弧线花费值的总和。路径 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表
12、中出现过的已扩展节点。,宽度优先搜索算法,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
13、表为队 操 作: 先进先出!,节点扩展顺序,宽度优先搜索算法,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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 问题 求解 基本原理 搜索 技术
链接地址:https://www.31doc.com/p-3187858.html