copy北航系人工智能课件.ppt

《copy北航系人工智能课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、题求解方法：基于状态空间的问题求解方法基于问题空间的问题求解方法基于博弈搜索的问题求解方法问题实例桌上固定了3根柱子，按1，2，3次序排例。有n个大小全不一样大的盘子d1，…，dn，按从小到大，小的在上的次序依次插在第一根柱子上，要把这n个盘子全部搬到第三根柱子上，每次只许搬一个，任何时候都不允许把大盘子放在小盘子上面，问该如何搬法。设n=3，该如何搬法？123123梵塔问题基于状态空间的问题求解方法（1，1，1）→（1，1，2）（1，1，1）→（1，1，3）（1，1，2）→（1，3，2）。。。。。状态合法变换规则（满足约束条件）：状态定义-（i大,j中,k小）:设向量下标

3、分别表示大盘、中盘、小盘；向量值分别表示盘子所在柱子的编号。状态描述-大盘在第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）。。。。。。基于问题空间的问题求解方法状态空间法有关概念状态空间法:从问题的初始状态出发，通过一系列的状态变换找到目

4、标状态的问题求解方法。状态：描述问题中事物形状或状况的符号或数据结构。状态空间：所有状态的全体构成的集合；用四元组（S,S0,O,G)表示:S:非空状态子集，S0=初始状态（非空）。G:非空目标状态子集。O:操作算子集合，一个状态合法转换为另一个状态的描述规则问题求解过程：隐含求一个普通有向图，节点-状态，边–算子搜索空间：问题求解过程中到达过的所有状态（节点）的集合。状态空间法有关概念状态空间、搜索空间及解径的关系：问题的解（解径）：初始状态到目标状态通路上的每一条规则（或状态）构成序列，称为解径。解不唯一。S0R1S2R2Sk…..RkG问题有解：从代表初始状态s节点出

5、发，存在一条通向目标节点的路径。问题空间法有关概念问题空间法：首先产生待证问题的所有子问题，而后通过解决所有子问题达到问题求解目的的方法。问题：描述问题及其子问题的符号或数据结构。问题空间：初始问题以及其所有子问题的全体构成的集合，用四元组（S,S0,F,G)表示:S:问题和子问题；S0:初始问题。G:具有平凡解的本原问题集合。F:操作算子集合，用于将问题分解成其若干个子问题的描述规则问题空间法的有关概念（2）问题空间分解过程：隐含求一个与或图节点–问题，边-分解问题的算子。“与”节点：如果节点A有边通向一组节点{B1，B2，…..Bn}，问题A的解决有待于A的子问题组{B

6、1,B2…..Bn}的全部解决，则称A为“与”节点。如图a所示。“或”节点：若节点Ａ有边通向一组节点{{Ｂ１},{Ｂ2}，…{Ｂn}}，问题Ａ的解决有待于子问题Ｂ１或Ｂ2或…或Ｂn中某一个子问题的解决，则称A为“或”节点。如图b所示。…...a:AB1B2Bn…...b:AB1B2Bn问题空间法有关概念（2）问题的解（解图）：从代表初始问题的节点出发，搜索到一个完整的‘与或’子图，图中所有叶节点均满足问题求解的结束条件。例：（C,B,Z)-〉（M,…M)重写规则:R1:C(D,L)R2:C(B,M)R3:B(M,M)R4:Z(B,B,M)解图小结–问题求解方法比较状

7、态空间法问题空间法问题求解状态变换问题分解搜索过程隐含构建普通有向图隐含构建与或图节点状态问题边状态变换规则（算子）问题分解规则（算子）求解解径解图问题求解基本原理一、问题求解的基本方法二、搜索技术（一）搜索技术预备状态空间搜索有关概念盲目搜索策略启发式搜索策略问题求解基本原理搜索策略预备盲目搜索：不考虑给定问题所具有的特定知识，系统按照事先确定好的某种固定顺序调用规则，或是随机地调用规则。常用的盲目搜索算法:深度优先搜索策略；宽度优先搜索策略搜索策略预备启发式信息：与问题求解有关的信息和知识。由于信息的片面性和不