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

北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 1问题求解基本原理n问题求解：问题求解：在给定条件下，寻求一个能解决某类某类问题问题且能在有限步骤内完成的算法n 问题求解特征：问题求解特征：w传统软件传统软件：求解的问题是能够用数学精确描述的良结构良结构的问题的问题（如，解方程）；计算机执行的繁杂的统计计算任务一般不能看成是人工智能活动wAI软件软件：求解的是不可直接用数学模型描述的所谓不良不良结构问题结构问题（如，几何证明、求不定积分、逻辑演算等），通常需要采用弱方法进行搜索求解；AI程序程序中符号的内涵不仅局限于数值计算和数据处理中的一般数据信息，应表现人类进行推理所需要的各种知识知识北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 2问题求解基本原理一、问一、问 题题 求求 解解 的的 基基 本本 方方 法法二、搜二、搜 索索 技技 术术北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 3问题求解基本原理n问题求解方法：问题求解方法：w基于基于状态空间状态空间的问题求解方法的问题求解方法w基于基于问题空间问题空间的问题求解方法的问题求解方法 w基于博弈搜索的问题求解方法北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 4问题实例问题实例 桌桌上上固固定定了了 3根根柱柱子子，按按 1，2，3次次序序排排例例。

有有 n n 个个大大小小全全不不一一样样大大的的盘盘子子d1，dn，按按从从小小到到大大，小小的的在在上上的的次次序序依依次次插插在在第第一一根根柱柱子子上上，要要把把这这 n n 个个盘盘子子全全部部搬搬到到第第三三根根柱柱子子上上，每每次次只只许许搬搬一一个个，任任何何时时候候都都不不允许把大盘子放在小盘子上面，问该允许把大盘子放在小盘子上面，问该如何搬法如何搬法设设n=3，该该如何搬法如何搬法？1 2 3 1 2 3梵塔问题北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 5基于基于状态空间状态空间的问题求解方法的问题求解方法（1，1，1）（1，1，2）（1，1，1）（1，1，3）（1，1，2）（1，3，2）状态状态合法合法变换规则（满足约束条件）：变换规则（满足约束条件）：状态定义状态定义 -（i i大大,j,j中中,k,k小小 ）:设向量下标分别表示大盘、中盘、小盘；向量值分别表示盘子所在柱子的编号状态描述状态描述 -大盘在第 i 根柱子上；中号盘在第 j 根柱子上，小号盘在第 k 根柱子上北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 6基于基于问题空间问题空间的问题求解方法的问题求解方法n问题：问题：如何将如何将 i i 柱子上的柱子上的 m m 个盘子搬到个盘子搬到 k k 柱子上柱子上?w 将 i 柱子上的 m 1 个盘子搬到 j 柱子上；w 将 i 柱子上的 第 m 个盘子搬到 k 柱子上；w 将 j 柱子上的 m 1 个盘子搬到 k 柱子上。

n 问题描述：问题描述：问题（问题（a,b,c):a,b,c):将 b 柱子上的 a 个盘子搬到 c 柱子上问题分解合法规则：问题分解合法规则：（3 3，1 1，3 3）-（2 2，1 1，2 2）(1(1，1 1，3 3）（2 2，2 2，3 3）北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 7基于基于问题空间问题空间的问题求解方法的问题求解方法北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 8状态空间法状态空间法有关概念有关概念n 状态空间法状态空间法:从从问问题题的的初初始始状状态态出出发发，通通过过一一系系列列的的状状态态变变换换找找到到目目标标状状态态的的问问题求解方法题求解方法n 状态状态：描述问题中事物形状或状况的符号或数据结构描述问题中事物形状或状况的符号或数据结构n 状态空间状态空间：所有状态的全体构成的集合；用所有状态的全体构成的集合；用四元组四元组（S,SS,S0 0,O,G),O,G)表示表示:S:S:非空状态子集，非空状态子集，S S0 0=初始状态（非空）初始状态（非空）。

G:G:非空目标状态子集非空目标状态子集O:O:操作算子集合，一个状态操作算子集合，一个状态合法合法转换为转换为另一个状态的描述规则另一个状态的描述规则n 问题求解过程问题求解过程：隐含隐含求一个求一个普通有向图普通有向图，节点节点 -状态，状态，边边 算子算子 n 状态变换规则状态变换规则：一个状态向另一个状态一个状态向另一个状态合法转换合法转换的描述规则的描述规则北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 9状态空间法状态空间法有关概念有关概念状态空间、搜索空间及解径的关系：状态空间、搜索空间及解径的关系：n 问题的解（解径）问题的解（解径）：初始状态初始状态到到目标状态目标状态通路上的每一条通路上的每一条规则规则（或（或 状态）构成状态）构成序列，称为序列，称为解径解径解不唯一解不唯一S S0 0 R R1 1 S S2 2 R R2 2 S Sk k.R Rk k G Gn问题有解问题有解：从代表从代表初始状态初始状态 s s 节点出发，节点出发，存在一条通向存在一条通向目标节点目标节点的路径的路径n 搜索空间搜索空间：问题求解过程中问题求解过程中到达到达过的所有状态（节点）的集合。

过的所有状态（节点）的集合北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 10问题空间法问题空间法有关概念有关概念n问题空间法问题空间法：首首先先产产生生待待证证问问题题的的所所有有子子问问题题，而而后后通通过过解解决决所所有有子子问问题题达达到到问问题求解目的的方法题求解目的的方法n 问题问题：描述问题及其子问题的符号或数据结构描述问题及其子问题的符号或数据结构n 问题空间问题空间：初始问题以及其所有子问题的全体构成的集合，用初始问题以及其所有子问题的全体构成的集合，用四元四元组组（S,SS,S0 0,F,G),F,G)表示表示:w S:S:问题和子问题；问题和子问题；S S0 0:初始问题初始问题w G:G:具有具有平凡解平凡解的的本原问题本原问题集合w F:F:操作算子集合，用于将问题分解成其若干个子问题的描述规则操作算子集合，用于将问题分解成其若干个子问题的描述规则n 问题分解规则问题分解规则：将一个问题（子将一个问题（子问题问题）分解成其若干个子问题分解成其若干个子问题北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 11问题空间法问题空间法的有关概念（的有关概念（2 2）n问题空间分解过程问题空间分解过程：隐含求一个隐含求一个与或图与或图w 节点节点 问题，问题，边边 -分解问题的算子。

分解问题的算子w “与与”节点：节点：如果节点 A 有边通向一组节点 B1，B2，.Bn，问题 A 的解决有待于 A 的子问题组 B1,B2.Bn 的全部解决全部解决，则称 A 为“与”节点如图 a 所示w “或或”节点：节点：若节点有边通向一组节点,2，n，问题的解决有待于子问题或2或或n中某一个子问某一个子问题的解决题的解决，则称 A 为“或”节点如图 b 所示a:AB1B2Bn.b:AB1B2Bn北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 12问题空间法问题空间法有关概念（有关概念（2 2）n问题的解（解图）问题的解（解图）：从代表从代表初始问题初始问题的节点出发，搜索到一个完的节点出发，搜索到一个完整的整的与或与或 子图子图，图中所有叶节点均满足问题求解的结束条件图中所有叶节点均满足问题求解的结束条件例：例：（C,B,Z)-（M,M)重写规则:R1:C (D,L)R2:C (B,M)R3:B (M,M)R4:Z (B,B,M)解图解图北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 13小结小结 问题求解方法比较问题求解方法比较 状态空间法状态空间法 问题空间法问题空间法问题求解问题求解 状态变换 问题分解搜索过程搜索过程隐含构建普通有向图普通有向图隐含构建与或图与或图 节点节点 状态 问题 边边状态变换规则（算子）问题分解规则（算子）求解求解 解径 解图北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 14问题求解基本原理问题求解基本原理一、问一、问 题题 求求 解解 的的 基基 本本 方方 法法二、搜二、搜 索索 技技 术术 （一）（一）北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 15n搜索技术预备搜索技术预备n状态空间搜索状态空间搜索w 有关概念w 盲目搜索策略w 启发式搜索策略问题求解基本原理问题求解基本原理北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 16搜索策略预备搜索策略预备n盲目搜索：盲目搜索：不考虑给定问题所具有的特定知识，系统按照事先确定好的某种固定顺序固定顺序调用规则，或是随机地随机地调用规则。

常用的常用的盲目盲目搜索算法搜索算法:深度优先搜索策略；深度优先搜索策略；宽度优先搜索策略宽度优先搜索策略北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 17搜索策略预备搜索策略预备启发式信息启发式信息：与问题求解有关的信息和知识由于信息的信息的片面性片面性和不准确性不准确性，应用启发式信息不能百分之百地保证找到问题的解，但能提高问题求解的可能性启发式信息启发式信息在问题求解过程中的在问题求解过程中的作用作用：有助于有助于加速求解过程；加速求解过程；有助于有助于找到找到“较优较优”解n 启发式搜索策略启发式搜索策略:考虑给定问题领域具有的特定知识（启发式信息启发式信息），系统动态地规定动态地规定规则调用顺序，优先使用优先使用“较较”合适合适的规则北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 18搜索策略预备搜索策略预备n常用的基于常用的基于状态图状态图的的启发式启发式搜索策略搜索策略:n 爬山搜索策略爬山搜索策略 (Hill Climbing)(Hill Climbing)n 大英博物馆搜索策略大英博物馆搜索策略 (British Museum)(British Museum)n 启发式图搜索策略启发式图搜索策略 (A A)n 最佳最佳启发式启发式图搜索策略图搜索策略 (A A*)n常用的基于常用的基于与或图及博弈与或图及博弈的的启发式启发式搜索策略搜索策略：n 最佳最佳启发式启发式与或图搜索策略与或图搜索策略 (AOAO*)n 极大极小搜索策略极大极小搜索策略 (MinimaxMinimax)n 剪枝搜索策略剪枝搜索策略 (Alpha-Beta PruningAlpha-Beta Pruning)北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 19基于基于状态空间状态空间的的搜索技术：搜索技术：有关搜索概念有关搜索概念 盲目搜索策略盲目搜索策略 启发式启发式搜索策略搜索策略问题求解基本原理北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 20状态空间状态空间搜。