1、北京航空航天大学软件开发环境国家重点实验室 Slide 1人 工 智 能( 问题求解 基本原理及 搜索技术 )北京航空航天大学软件开发环境国家重点实验室 Slide 2问题求解基本原理n 问题求解： 在给定条件下，寻求一个能解决 某类 问题 且能在有限步骤内完成的算法。n 问题求解特征：w 传统软件 ： 求解的问题是能够用 数学精确描述 的 良结构的问题 （如，解方程） ； 计算机执行的繁杂的统计计算任务一般不能看成是人工智能活动。w AI软件 ： 求解的是 不可直接用数学模型描述 的所谓 不良结构问题 （如，几何证明、求不定积分、逻辑演算等） ，通常需要采用 弱方法 进行搜索求解； AI程序
2、 中符号的内涵不仅局限于数值计算和数据处理中的一般数据信息，应表现人类进行推理所需要的各种 知识 。北京航空航天大学软件开发环境国家重点实验室 Slide 3问题求解基本原理一、问 题 求 解 的 基 本 方 法二、搜 索 技 术北京航空航天大学软件开发环境国家重点实验室 Slide 4问题求解基本原理n问题求解方法：w基于 状态空间 的问题求解方法w基于 问题空间 的问题求解方法 w基于 博弈 搜索 的问题求解方法北京航空航天大学软件开发环境国家重点实验室 Slide 5问题实例桌上固定了 3 根柱子，按 1， 2， 3 次序排例。有 n 个大小全不一样大的盘子 d1， ， dn ， 按从小
3、到大，小的在上的次序依次插在第一根柱子上，要把这 n 个盘子全部搬到第三根柱子上，每次只许搬一个，任何时候都不允许把大盘子放在小盘子上面，问该 如何搬法。 设 n = 3， 该 如何搬法 ？1 2 3 1 2 3梵塔问题北京航空航天大学软件开发环境国家重点实验室 Slide 6基于 状态空间 的问题求解方法（ 1， 1， 1） （ 1， 1， 2）（ 1， 1， 1） （ 1， 1， 3）（ 1， 1， 2） （ 1， 3， 2）。状态 合法 变换规则（满足约束条件）：状态定义 -（ i大 , j中 , k小 ） : 设向量下标分别表示大盘、中盘、小盘；向量值分别表示盘子所在柱子的编号。状态描
4、述 - 大盘在第 i 根柱子上；中号盘在第 j 根柱子上，小号盘在第 k 根柱子上。 北京航空航天大学软件开发环境国家重点实验室 Slide 7基于 问题空间 的问题求解方法n 问题： 如何将 i 柱子上的 m 个盘子搬到 k 柱子上 ?w 将 i 柱子上的 m 1 个盘子搬到 j 柱子上；w 将 i 柱子上的 第 m 个盘子搬到 k 柱子上；w 将 j 柱子上的 m 1 个盘子搬到 k 柱子上。n 问题描述：问题（ a, b, c): 将 b 柱子上的 a 个盘子搬到 c 柱子上。问题分解合法规则：（ 3， 1， 3） - （ 2， 1， 2） (1， 1， 3） （ 2， 2， 3）。北京
5、航空航天大学软件开发环境国家重点实验室 Slide 8基于 问题空间 的问题求解方法北京航空航天大学软件开发环境国家重点实验室 Slide 9状态空间法 有关概念n 状态空间法 :从问题的 初始状态 出发，通过一系列的 状态变换 找到 目标状态 的问题求解方法。n 状态 ： 描述问题中事物形状或状况的符号或数据结构。n 状态空间 ： 所有状态的全体构成的集合；用 四元组 （ S, S0, O, G) 表示 :S: 非空状态子集， S0 = 初始状态（非空）。G: 非空目标状态子集。O: 操作算子集 合 ，一个状态 合法 转换为 另一个状态的 描述 规则n 问题求解过程 ： 隐含 求一个 普通有向图 ， 节点 - 状态， 边 算子 n 搜索空间 ： 问题求解过程中 到达 过的所有状态（节点）的集合 。北京航空航天大学软件开发环境国家重点实验室 Slide 10状态空间法 有关概念状态空间、搜索空间及解径的关系：n 问题的解（解径） ： 初始状态 到 目标状态 通路上的每一条规则 （或 状态）构成 序列，称为 解径 。 解不唯一。S0 R1 S2 R2 Sk . Rk Gn 问题有解 ： 从代表 初始状态 s 节点出发， 存在一条通向 目标节点 的路径。
