问题求解及搜索技术要点-copy课件.ppt

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

2、人类进行推理所需要的各种知识知识。问题求解基本原理一、问一、问 题题 求求 解解 的的 基基 本本 方方 法法二、搜二、搜 索索 技技 术术问题求解基本原理n问题求解方法：问题求解方法：w基于基于状态空间状态空间的问题求解方法的问题求解方法w基于基于问题空间问题空间的问题求解方法的问题求解方法 w基于博弈搜索的问题求解方法问题实例问题实例 桌上固定了桌上固定了 3 根柱子，按根柱子，按 1，2，3 次序排例。有次序排例。有 n n 个大小全不一样大个大小全不一样大的盘子的盘子d1，dn，按从小到大，小的在上的次序依次插在第一根柱子上，按从小到大，小的在上的次序依次插在第一根柱子上，要把这要把这

3、 n 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 i大大C C,j,j中中B B,k,k小小A A ）:设向量下标分别表示小盘A、中盘B、大盘C；

4、向量值分别表示盘子所在柱子的编号。状态描述状态描述 -大盘 C 在第 i 根柱子上；中号盘 B 在第 j 根柱子上，小号盘 A 在第 k 根柱子上。基于基于问题空间问题空间的问题求解方法的问题求解方法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 柱子上。问题分解合法规则：问题

5、分解合法规则：（3 3，1 1，3 3）-（2 2，1 1，2 2）(1(1，1 1，3 3）（2 2，2 2，3 3）。基于基于问题空间问题空间的问题求解方法的问题求解方法状态空间法状态空间法有关概念有关概念n 状态空间法状态空间法:从问题的从问题的初始状态初始状态出发，通过一系列的出发，通过一系列的状态变换状态变换找到找到目标状态目标状态的的问题求解方法。问题求解方法。n 状态状态：描述问题中事物形状或状况的符号或数据结构。描述问题中事物形状或状况的符号或数据结构。n 状态空间状态空间：所有状态的全体构成的集合；用所有状态的全体构成的集合；用四元组四元组（S,SS,S0 0,O,G),O,

6、G)表示表示:S:S:非空状态子集，非空状态子集，S S0 0=初始状态（非空）。初始状态（非空）。G:G:非空目标状态子集。非空目标状态子集。O:O:操作算子集合，一个状态操作算子集合，一个状态合法合法转换为转换为另一个状态的描述规则另一个状态的描述规则n 问题求解过程问题求解过程：隐含隐含求一个求一个普通有向图普通有向图，节点节点 -状态，状态，边边 算子算子 n 搜索空间搜索空间：问题求解过程中问题求解过程中到达到达过的所有状态（节点）的集合过的所有状态（节点）的集合。状态空间法状态空间法有关概念有关概念状态空间、搜索空间及解径的关系：状态空间、搜索空间及解径的关系：n 问题的解（解径）

7、问题的解（解径）：初始状态初始状态到到目标状态目标状态通路上的每一条通路上的每一条规则规则（或（或 状态）构成状态）构成序列，称为序列，称为解径解径。解不唯一。解不唯一。S S0 0 R R1 1 S S2 2 R R2 2 S Sk.k.R Rk k G Gn问题有解问题有解：从代表从代表初始状态初始状态 s s 节点出发，节点出发，存在一条通向存在一条通向目标节点目标节点的路径的路径。问题空间法问题空间法有关概念有关概念n问题空间法问题空间法：首先产生待证问题的首先产生待证问题的所有所有子问题，而后通过解决所有子问题达到子问题，而后通过解决所有子问题达到问题求解目的的方法。问题求解目的的方

8、法。n 问题问题：描述问题及其子问题的符号或数据结构描述问题及其子问题的符号或数据结构。n 问题空间问题空间：初始问题以及其所有子问题的全体构成的集合，用初始问题以及其所有子问题的全体构成的集合，用四元四元组组（S,SS,S0 0,F,G),F,G)表示表示:w S:S:问题和子问题；问题和子问题；S S0 0:初始问题。初始问题。w G:G:具有具有平凡解平凡解的的本原问题本原问题集合。集合。w F:F:操作算子集合，用于将问题分解成其若干个子问题的描述规则操作算子集合，用于将问题分解成其若干个子问题的描述规则问题空间法问题空间法的有关概念（的有关概念（2 2）n问题空间分解过程问题空间分解

9、过程：隐含求一个隐含求一个与或图与或图w 节点节点 问题，问题，边边 -分解问题的算子。分解问题的算子。w “与与”节点：节点：如果节点 A 有边通向一组节点 B1，B2，.Bn，问题 A 的解决有待于 A 的子问题组 B1,B2.Bn 的全部解决全部解决，则称 A 为“与”节点。如图 a 所示。w “或或”节点：节点：若节点有边通向一组节点,2，n，问题的解决有待于子问题或2或或n中某一个子问某一个子问题的解决题的解决，则称 A 为“或”节点。如图 b 所示。.a:AB1B2Bn.b:AB1B2Bn问题空间法问题空间法有关概念（有关概念（2 2）n问题的解（解图）问题的解（解图）：从代表从代

10、表初始问题初始问题的节点出发，搜索到一个完的节点出发，搜索到一个完整的整的与或与或 子图子图，图中所有叶节点均满足问题求解的结束条件。，图中所有叶节点均满足问题求解的结束条件。例：例：（C,B,Z)-（M,M)重写规则:R1:C (D,L)R2:C (B,M)R3:B (M,M)R4:Z (B,B,M)解图解图小结小结 问题求解方法比较问题求解方法比较 状态空间法状态空间法 问题空间法问题空间法问题求解问题求解 状态变换 问题分解搜索过程搜索过程隐含构建普通有向图普通有向图隐含构建与或图与或图 节点节点 状态 问题 边边状态变换规则（算子）问题分解规则（算子）求解求解 解径 解图问题求解基本原

11、理问题求解基本原理一、问一、问 题题 求求 解解 的的 基基 本本 方方 法法二、搜二、搜 索索 技技 术术 （一）（一）n搜索技术预备搜索技术预备n状态空间搜索状态空间搜索w 有关概念w 盲目搜索策略w 启发式搜索策略问题求解基本原理问题求解基本原理搜索策略预备搜索策略预备n盲目搜索：盲目搜索：不考虑给定问题所具有的特定知识，系统按照事先确定好的某种固定顺序固定顺序调用规则，或是随机地随机地调用规则。常用的常用的盲目盲目搜索算法搜索算法:深度优先搜索策略；深度优先搜索策略；宽度优先搜索策略宽度优先搜索策略搜索策略预备搜索策略预备启发式信息启发式信息：与问题求解有关的信息和知识。由于信息的信息

12、的片面性片面性和不准确性不准确性，应用启发式信息不能百分之百地保证找到问题的解，但能提高问题求解的可能性。启发式信息启发式信息在问题求解过程中的在问题求解过程中的作用作用：有助于有助于加速求解过程；加速求解过程；有助于有助于找到找到“较优较优”解。解。n 启发式搜索策略启发式搜索策略:考虑给定问题领域具有的特定知识（启发式信息启发式信息），系统动态地规定动态地规定规则调用顺序，优先使用优先使用“较较”合适合适的规则。搜索策略预备搜索策略预备n 常用的基于常用的基于状态图状态图的的启发式启发式搜索策略搜索策略:n 爬山搜索策略爬山搜索策略 (Hill Climbing)(Hill Climbin

13、g)n 大英博物馆搜索策略大英博物馆搜索策略 (British Museum)(British Museum)n 启发式图搜索策略启发式图搜索策略 (A A)n 最佳最佳启发式启发式图搜索策略图搜索策略 (A A*)n 常用的基于常用的基于与或图及博弈与或图及博弈的的启发式启发式搜索策略搜索策略：n 最佳最佳启发式启发式与或图搜索策略与或图搜索策略 (AOAO*)n 极大极小搜索策略极大极小搜索策略 (MinimaxMinimax)n 剪枝搜索策略剪枝搜索策略 (Alpha-Beta PruningAlpha-Beta Pruning)基于基于状态空间状态空间的的搜索技术：搜索技术：有关搜索概

14、念有关搜索概念 盲目搜索策略盲目搜索策略 启发式启发式搜索策略搜索策略问题求解基本原理状态空间状态空间搜索搜索有关概念有关概念 n状态状态图图特点：特点：多条路径通向同一节点。例：E状态空间状态空间搜索搜索有关概念有关概念状态空间状态空间搜索有关概念搜索有关概念n 节点深度节点深度：根节点根节点的深度深度为0，其它节点其它节点的深度深度规定为其父节点的深度加 1，即dn+1=dn +1。n 标记节点标记节点 n：利用指针指针把后继节点连接到父节点 n 的操作。n 节点节点：对应状态图中有关状态状态的描述。n扩展节点扩展节点n：算符（规则）作用于节点 n 生成生成的新节点称为节点 n 的后继节点

15、。后继节点。生成生成节点 n 的所有后继节点后继节点并计算计算生成这些后继节点所使用的花费花费的过程叫做扩展节点扩展节点 n。n 路径路径：对于一个节点序列（n0,n1,nl,nk），如若每一节点 ni-1都有一个后继节点 ni（i=1,2,k），则称该节点序列为一条从节点 n0 到节点 nk、长度为 k 的路径；路径还可表示为与节点序列对应的规则序列。状态空间状态空间搜索有关概念搜索有关概念n路径花费路径花费：设 C（ni，nj）为节点 ni 到 nj 这段路径（或弧线）的花费。一条路径的花费等于连接这条路径各节点间所有弧线花费值的总和。路径 ni nj t 的花费值C（ni，t）可递归计算

16、如下:C（ni，t）=C(ni，nj)+C（nj，t)。基于基于状态空间状态空间的的盲目盲目搜索算法搜索算法:宽宽度优先搜索策略度优先搜索策略深深度优先搜索策略度优先搜索策略问题求解基本原理盲目搜索盲目搜索算法的算法的符号符号及及数据结构数据结构 s：初始节点；n n：当前节点。open：已被生成已被生成但未被扩展未被扩展的节点序列表；closed：已被生成已被生成且已被扩展已被扩展的节点序列表；mi=mj mk mlmi=mj mk ml：扩展 n 后所得的 n 的后继节点后继节点 其中，mk：在OPEN表中出现过的待扩展节点待扩展节点，ml：在CLOSED表中出现过的已扩展节点已扩展节点。

17、mj：第一次生成的节点，mj OPEN 且 mj 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 );add(open,mj);exit(fail);宽度宽度优先搜索算法优先搜索算法 1、S,A,D2、A,D,B,D3、D,B,A,EOpen 表为表为队队 操操 作作：先进先出！先进先出！G节点节点扩展扩展

18、顺序顺序宽度宽度优先搜索算法优先搜索算法 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 );add(mj,open);exit(fail);深度深度优先搜索算法优先搜索算法深度深度优先搜索算法优先搜索算法 1、S2、A,D3、B,D,DOpen表为表为栈栈 操操 作作：后进先出

19、！后进先出！4、C,E,D节点节点扩展扩展顺序顺序深度深度优先搜索算法优先搜索算法 盲目盲目搜索搜索算法应用实例算法应用实例-8 8数码问题数码问题描述描述状态状态：矩阵矩阵(S(Sijij)，其中，其中 1 1i,ji,j3 3，S Sijij0,1,0,1,8;,8;盲目搜索算法应用实例盲目搜索算法应用实例 -n 合法走步规则：合法走步规则：设设(i0i0、j0)j0)为空格所在行列数值，为空格所在行列数值，S Si0j0i0j0=0=0R1:if j-1R1:if j-11 then S1 then Si0j0i0j0:=S:=Si0(j0-1)i0(j0-1),S,Si0(j0-1)i

20、0(j0-1):=0:=0 空格左移；空格左移；R2:if i-1R2:if i-11 then S1 then Si0j0i0j0:=S:=S(i0-1)j0(i0-1)j0,S,S(i0-1)j0(i0-1)j0:=0:=0 空格上移；空格上移；R3:if j+1R3:if j+13 then S3 then Si0j0i0j0:=S:=Si0(j0+1)i0(j0+1),S,Si0(j0+1)i0(j0+1):=0:=0 空格右移；空格右移；R4:if i+1R4:if i+13 then S3 then Si0j0i0j0:=S:=S(i0+1)j0(i0+1)j0,S,S(i0+1)

21、(i0+1)j0:=0 j0:=0 空格下移。空格下移。8 8数码问题数码问题宽度优先策略宽度优先策略求解求解8 8数码问题数码问题：目标目标R1R2R3R2R1R2R3R2R2R3R2R4R1R3深度优先策略深度优先策略求解求解8 8数码问题：数码问题：n 说明：说明：设规则固定使用顺序：设规则固定使用顺序：R1-左移、左移、R2-上移、上移、R3-右移、右移、R4-下移；下移；设节点深度限制值：设节点深度限制值：6；合法的走步合法的走步规则规则重复节点重复节点 造成循环造成循环问题求解基本原理基于基于状态空间状态空间的的启发式启发式搜索算法搜索算法:A A 算法；算法；A A*算法算法启发

22、式启发式图搜索算法图搜索算法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)：迄今

23、为止搜索到迄今为止搜索到的从的从初始节点初始节点 s 到当前节点到当前节点 n 最佳路径分段的最佳路径分段的已知费用已知费用，是对是对g*(n)的一个估计。的一个估计。f*(n)=g*(n)+h*(n)：从初始节点从初始节点 s 出发，经过出发，经过最佳路径最佳路径上任意上任意节点节点 n，到达目标节点，到达目标节点 t 的的最小最小费用。费用。h*(n)：n t 最佳路径最佳路径的的分段费用分段费用。g*(n)：sn 最佳路径最佳路径的的分段费用。分段费用。s：初始节点；初始节点；n：当前节点；当前节点；t：目标节点。目标节点。启发式启发式图搜索算法图搜索算法-A 算算 法法 n 定义定义：

24、按照按照 f(n)=g(n)+h(n)f(n)=g(n)+h(n)估价函数值由小到大估价函数值由小到大地排列待扩展节点顺序的图搜索算法，称为地排列待扩展节点顺序的图搜索算法，称为A A 算法。算法。n A 算法流程算法流程。nA算法应用实例算法应用实例:n 普通有向图普通有向图 A 算法搜索实例算法搜索实例；n 8数码问题数码问题A 算法搜索实例算法搜索实例。启发式图搜索算法启发式图搜索算法 -A-A算法算法n算法中符号：算法中符号：s：初始节点；G：搜索图的节点集合；OPEN表：已生成但尚未被扩展的节点序列表；CLOSED表：已生成且已被扩展的节点序列表；n：待扩展的当前节点；mi=mj m

25、k ml：扩展 n 后生成的后继节点其中，mj：第一次生成的节点，mj OPEN 且 mj CLOSED表，mk：在OPEN表中出现过的待扩展节点，ml：在CLOSED表中出现过的已扩展节点。A算法算法n 为目标为目标t?取当前节点取当前节点 nn:=first(OPEN),从从OPEN中删除中删除n,CLOSED:=CLOSEDn初初 始始 化化 G:=G0S,OPEN:=(S)CLOSED:=(),f(S):=g(S)+h(S)OPEN=未发现目标未发现目标tReturn(Fail)AyesNoyesNoBExit(Success)输出解径输出解径扩展扩展节点节点n：生成：生成n的后继节点

26、；计算后继节点的花费。的后继节点；计算后继节点的花费。mi:=Expand(n),计算计算:f(n,mi):=g(n,mi)+h(mi)比较花费，修改比较花费，修改连接标记连接标记 对于对于mj mi:OPEN:=OPEN mj,mj-n;对于对于mk mi:if f(n,mk)n;对于对于ml mi:if f(n,ml)n,OPEN:=OPEN ml将将OPEN表中节点按表中节点按f 值值从小到大重新排序从小到大重新排序AB启发式最佳启发式最佳图搜索算法图搜索算法-A*算法算法n A*算法定义：算法定义：若将若将A算法中评价函数算法中评价函数 f(n)的启发式分量函数的启发式分量函数 h（n

27、）的值）的值限制在限制在 h*（n）的下界范围内，亦即对所有节点）的下界范围内，亦即对所有节点 n，都满足，都满足h（n）h*（n），则称此时的），则称此时的 A 算法为算法为 A*算法。算法。n A*算法作用：算法作用：问题有解时，问题有解时，A A*算法算法一定能够找到一定能够找到从初始节点从初始节点 s s 到目标节到目标节点点 t t 的的最佳最佳解径。解径。n 信息性信息性定理：定理：有两个有两个A*算法算法A1和和A2,若若A2比比A1有较多的启发式信息（即对所有有较多的启发式信息（即对所有非目标节点均有：非目标节点均有：h1（n）h2（n）h*（n），则在具有一条从），则在具有一

28、条从 s 到到 t 的隐含状态图上，搜索结束时，由的隐含状态图上，搜索结束时，由A2扩展的每一个节点，也必扩展的每一个节点，也必定由定由A1所扩展，即所扩展，即A1扩展的节点数至少和扩展的节点数至少和A2一样多。一样多。启发式最佳启发式最佳图搜索算法图搜索算法-A*算法算法n A*算法应用验证算法应用验证:n 8数码问题数码问题A*算法搜索实例。算法搜索实例。8数码问题数码问题搜索策略比较：搜索策略比较：宽度优先宽度优先 A算法算法 A*算法算法小结小结n启发式搜索策略启发式搜索策略n g:n 考虑当前路径考虑当前路径已经花费的费用已经花费的费用，及时抛弃已经经过的花费太大，及时抛弃已经经过的

29、花费太大且距目标仍远的路径且距目标仍远的路径;n h:n 估计当前路径上节点到目标节点估计当前路径上节点到目标节点还需要的费用还需要的费用，引导搜索向最，引导搜索向最有希望的路径前进。有希望的路径前进。w A A 算法算法：定义估计函数：定义估计函数：f=g+hf=g+h；u A A*算法算法：定义估计函数：定义估计函数：f=g+hf=g+h；满足满足h（n）h*（n）。）。n 程序实现宽度优先法和深度优先程序实现宽度优先法和深度优先法求解法求解 High-way map High-way map 问题，给出问题，给出求解过程（求解过程（OpenOpen，ClosedClosed内容），内容）

30、，标出解径。标出解径。作业作业:n给定两个油桶给定两个油桶,一个可装一个可装 4 4 公斤油公斤油,一个可装一个可装 3 3 公公斤油斤油,油桶上无任何度量标记。问：怎样才能使油桶上无任何度量标记。问：怎样才能使 4 4 公斤油桶里恰好只装公斤油桶里恰好只装 2 2 公斤油？公斤油？设状态定义设状态定义：(x,y)(x,y)，其中，其中，x x：4 4 公斤油桶中实际装油公斤数；公斤油桶中实际装油公斤数；y y：3 3 公斤油桶中实际装油公斤数。公斤油桶中实际装油公斤数。问题表示：问题表示：(0,0)-(0,0)-(2,y)(2,y)要求定义合法的装油规则，利用盲目搜索策略画出要求定义合法的装油规则，利用盲目搜索策略画出状态图。状态图。作业作业: