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

1、问题求解基本原理 问题求解：问题求解：在给定条件下，寻求一个能解决某类某类问题问题且能在有限步骤内完成的算法。n 问题求解特征：w 传统软件：求解的问题是能够用数学精确描述的良结构的问题（如，解方程）；计算机执行的繁杂的统计计算任务一般不能看成是人工智能活动。w 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

3、，2）。状态合法变换规则（满足约束条件）：状态定义状态定义-（i大大,j中中,k小小）:设向量下标分别表示大盘、中盘、小盘；向量值分别表示盘子所在柱子的编号。状态描述状态描述-大盘在第 i 根柱子上；中号盘在第 j 根柱子上，小号盘在第 k 根柱子上。基于问题空间的问题求解方法 问题：问题：如何将如何将 i 柱子上的柱子上的 m 个盘子搬到个盘子搬到 k 柱子上柱子上?将 i 柱子上的 m 1 个盘子搬到 j 柱子上；将 i 柱子上的 第 m 个盘子搬到 k 柱子上；将 j 柱子上的 m 1 个盘子搬到 k 柱子上。n 问题描述：问题（a,b,c):将 b 柱子上的 a 个盘子搬到 c 柱子上

4、。问题分解合法规则：（3，1，3）-（2，1，2）(1，1，3）（2，2，3）。基于问题空间的问题求解方法状态空间法有关概念n 状态空间法:从问题的初始状态出发，通过一系列的状态变换找到目标状态的问题求解方法。n 状态：描述问题中事物形状或状况的符号或数据结构。n 状态空间：所有状态的全体构成的集合；用四元组（S,S0,O,G)表示:S:非空状态子集，S0=初始状态（非空）。G:非空目标状态子集。O:操作算子集合，一个状态合法转换为另一个状态的描述规则n 问题求解过程：隐含求一个普通有向图，节点-状态，边 算子 n 状态变换规则：一个状态向另一个状态合法转换的描述规则。状态空间法有关概念状态空

5、间、搜索空间及解径的关系：n 问题的解（解径）：初始状态到目标状态通路上的每一条规则（或 状态）构成序列，称为解径。解不唯一。S0 R1 S2 R2 Sk.Rk G 问题有解问题有解：从代表从代表初始状态初始状态 s 节点出发，节点出发，存在一条通向存在一条通向目标节点目标节点的路径的路径n 搜索空间：问题求解过程中到达过的所有状态（节点）的集合。问题空间法有关概念问题空间法问题空间法：首先产生待证问题的首先产生待证问题的所有所有子问题，而后通过解决所有子问题达到子问题，而后通过解决所有子问题达到问题求解目的的方法。问题求解目的的方法。n 问题：描述问题及其子问题的符号或数据结构。n 问题空间

6、：初始问题以及其所有子问题的全体构成的集合，用四元组（S,S0,F,G)表示:w S:问题和子问题；S0:初始问题。w G:具有平凡解的本原问题集合。w F:操作算子集合，用于将问题分解成其若干个子问题的描述规则n 问题分解规则：将一个问题（子问题）分解成其若干个子问题。问题空间法的有关概念（2）问题空间分解过程问题空间分解过程：隐含求一个隐含求一个与或图与或图 节点节点 问题，问题，边边-分解问题的算子。分解问题的算子。w“与”节点：如果节点 A 有边通向一组节点 B1，B2，.Bn，问题 A 的解决有待于 A 的子问题组 B1,B2.Bn 的全部解决，则称 A 为“与”节点。如图 a 所示

7、。w“或”节点：若节点有边通向一组节点,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)解图小结 问题求解方法比较 状态空间法状态空间法

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

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

10、索策略(A*)n 常用的基于与或图及博弈的启发式搜索策略：n 最佳启发式与或图搜索策略(AO*)n 极大极小搜索策略(Minimax)n 剪枝搜索策略(Alpha-Beta Pruning)基于状态空间的搜索技术：有关搜索概念 盲目搜索策略 启发式搜索策略问题求解基本原理状态空间搜索有关概念 状态状态图图特点：特点：多条路径通向同一节点。例：E状态空间搜索有关概念状态图搜索及生成过程:从S节点开始，不断搜索规则，动态生成节点;扩展局部图；最终求得 S-G 的可达路径。隐含生成有重复节点的树搜索过程 特殊的图搜索状态空间搜索有关概念n 节点深度：根节点的深度为0，其它节点的深度规定为其父节 点的

11、深度加 1，即dn+1=dn +1。n 标记节点 n：用指针将后继节点连接到父节点 n 的操作。n 节点：对应状态图中有关状态的描述。扩展节点扩展节点n：称生成生成节点 n 的所有后继节点后继节点并计算计算生成这些后继节点所造成的花费花费的过程（即，计算各后继节点的优劣且将其连接到节点 n 等操作造成的开销）叫做扩展节点扩展节点 n。n 后继节点：称将规则作用于节点 n 生成的新节点为节点 n 的后继节点。n 路径：对于一个节点序列（n0,n1,nl,nk），如若每一节点 ni-1都有一个后继节点 ni（i=1,2,k），则称该节点序列为一条从节点 n0 到节点 nk、长度为 k 的路径；路径

12、还可表示为与节点序列对应的规则序列。状态空间搜索有关概念 路径花费路径花费：设 C（ni，nj）为节点 ni 到 nj 这段路径（或弧线）的花费。一条路径的花费等于连接这条路径各节点间所有弧线花费值的总和。路径 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 的后继节点 其

13、中，mk：在OPEN表中出现过的待扩展节点，ml：在CLOSED表中出现过的已扩展节点。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 );append(open,mj);exit(fail);宽度优先搜索算法 1、S,A,D2、A,D,B,D3、D,B,A,EOpen 表

14、为队 操 作：先进先出！G节点扩展顺序宽度优先搜索算法 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);深度优先搜索算法深度优先搜索算法 1、S2、A,D3、B,D,DOpen表为栈 操 作：后进先出！4、C,E,D节点扩

15、展顺序深度优先搜索算法 盲目搜索算法应用实例-8数码问题描述状态：矩阵(Sij)，其中 1i,j3，Sij0,1,8;盲目搜索算法应用实例-合法走步规则：合法走步规则：设(i0、j0)为空格所在行列数值，Si0j0=0R1:if j-11 then Si0j0:=Si0(j0-1),Si0(j0-1):=0 空格左移；R2:if i-11 then Si0j0:=S(i0-1)j0,S(i0-1)j0:=0 空格上移；R3:if j+13 then Si0j0:=Si0(j0+1),Si0(j0+1):=0 空格右移；R4:if i+13 then Si0j0:=S(i0+1)j0,S(i0+

16、1)j0:=0 空格下移。8数码问题宽度优先策略求解8数码问题：目标R1R2R3R2R1R2R3R2R2R3R2R4R1R3深度优先策略求解8数码问题：n 说明：设规则固定使用顺序：R1-左移、R2-上移、R3-右移、R4-下移；设节点深度限制值：6；合法的走步规则重复节点 造成循环1、利用宽度优先法或深度优先法，程序实现 High-way map 问题求解，只考虑节点的连接和变换,不考虑边的权值;求出有向图的一条解径,给出求解过程（即，给出Open，Closed表中的内容）。作业:2、利用宽度优先法或深度优先法，程序实现 8数码问题。-隐含生成有向图 给定两个油桶给定两个油桶,一个可装一个可

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

18、A*算法 核心思想：1、盲目搜索：根据节点连接情况，寻找s-t的解径（不一定最佳）；2、启发式搜索：根据节点连接及其花费情况，较快地寻找 s-t 的最 佳（花费最小）的解径；3、求解思路：图搜索中，s-t 的路径总可以表示成 s-n-t；若对图中每一个 n,都设置一个f(n),唯一地表示s-n-t路径的花费，即，在 n 与 f(n)=（s-n-t 路径的花费）之间建立一对一的映射；每当从当前局部搜索树中选择扩展叶节点 n 时，以f(n)=s-n-t路径花费最少为衡量标准；以此保证每次选择、扩展节点 n 都在当前局部最小花费的路径上进行。4、需解决的问题：如何为图中节点 n 定义标志全程路径 s

19、-n-t 的花 费评价函数值 f（n）？如何保证节点 n 的 f(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)：迄今为止搜索到的从初始节点 s 到当前节点 n 最佳路径分段的已知费用，是对g*(n)的一个估计。f*(n)=g*(n)+h*(n)：从初始节点 s

20、出发，经过最佳路径上任意节点 n，到达目标节点 t 的最小费用。h*(n)：n t 最佳路径的分段费用。g*(n)：sn 最佳路径的分段费用。s：初始节点；n：当前节点；t：目标节点。启发式图搜索算法-A 算 法 n 定义：按照 f(n)=g(n)+h(n)估价函数值由小到大地排列待扩展节点顺序的图搜索算法，称为A 算法。n A 算法流程。nA算法应用实例:n 普通有向图 A 算法搜索实例；n 8数码问题A 算法搜索实例。启发式图搜索算法-A算法 算法中符号：算法中符号：s：初始节点；G：搜索图的节点集合；OPEN表：已生成但尚未被扩展的节点序列表；CLOSED表：已生成且已被扩展的节点序列表

21、；n：待扩展的当前节点；mi=mj mk 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的后继节点；计算后继节点的花费。mi:

22、=Expand(n),(mi)计算: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搜索算法应用实例-8数码问题状态描述：矩阵(Sij)，其中 1i,j3，Sij0,1,8搜索算法应用实例-8数码问题 合法走步规则：合法走步规则：设i0,j0为空格所在行列数值，Si0j0=0R1:if j0-11 then Si0j0:=Si0(j0-1),Si0(j0-1):=0 空格

23、左移；R2:if i0-11 then Si0j0:=S(i0-1)j0,S(i0-1)j0:=0 空格上移；R3:if j0+13 then Si0j0:=Si0(j0+1),Si0(j0+1):=0 空格右移；R4:if i0+13 then Si0j0:=S(i0+1)j0,S(i0+1)j0:=0 空格下移。搜索算法应用实例-8数码问题 g(n):搜索树中节点 n 所在层的深度，每层为单位花费单位花费h(s)=w(s)=4 n h(n)=W(n)：相对于目标节点而言，节点 n 中“不在位”的将牌个数之和”(二者差异)启发式分量函数。f(n)=g(n)+h(n)：节点 n 的层次深度一定

24、，n 与目标节点之间的差异越小，即 h(n)越小，则 f(n)越小，优先扩展。搜索算法应用实例-8数码问题目标S(4)C(6)A(6)D(5)F(6)G(6)L(5)g(s)=d0=0g(A,B,C)=d1=1g(D,E,F)=d2=2g(G,H,I,J)=d3=3g(K)=d4=4g(L,M)=d5=5括号中为 f 值启发式最佳图搜索算法-A*算法 A*算法定义：算法定义：若将若将A算法中评价函数算法中评价函数 f(n)的启发式分量函数的启发式分量函数 h（n）的值）的值限制在限制在 h*（n）的下界范围内，亦即对所有节点）的下界范围内，亦即对所有节点 n，都满足，都满足h（n）h*（n），

25、则称此时的），则称此时的 A 算法为算法为 A*算法。算法。n A*算法作用：问题有解时，A*算法一定能够找到从初始节点 s 到目标节点 t 的最佳解径。n 信息度定理：有两个A*算法A1和A2,若A2比A1有较多的启发式信息（即对所有非目标节点均有：h1（n）h2（n）h*（n），则在具有一条从 s 到 t 的隐含状态图上，搜索结束时，由A2扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。启发式最佳图搜索算法-A*算法n A*算法应用验证:n 8数码问题A*算法搜索实例。A*算法应用实例-8数码问题状态描述：矩阵(Sij)，其中 1i,j3，Sij0,1,8 A*算

26、法应用实例-8数码问题 合法走步规则：合法走步规则：设i0,j0为空格所在行列数值，Si0j0=0R1:if j0-11 then Si0j0:=Si0(j0-1),Si0(j0-1):=0 空格左移；R2:if i0-11 then Si0j0:=S(i0-1)j0,S(i0-1)j0:=0 空格上移；R3:if j0+13 then Si0j0:=Si0(j0+1),Si0(j0+1):=0 空格右移；R4:if i0+13 then Si0j0:=S(i0+1)j0,S(i0+1)j0:=0 空格下移。A*算法应用实例-8数码问题 g(n):搜索树中节点n所在层的深度，每层为单位花费。单

27、位花费。n h(n)=P(n)：节点 n 中各将牌与目标节点中对应将牌相比归位的距离之和（不考虑夹在其间的将牌）。-启发式分量函数 f(n)=g(n)+h(n)：节点 n 的层次深度一定，节点 n 与目标节点之间对应将牌的距离之和越小，即 h(n)值越小，f(n)越小，优先扩展h(s)=P(s)=5A*算法应用实例-8数码问题 启发式函数比较启发式函数比较:h(n)=P(n):指出了本节点中各将牌归位的步数之和，但未指出了本节点中各将牌归位的步数之和，但未具体给出若考虑夹在其间的将牌，应如何移动将牌、搜索具体给出若考虑夹在其间的将牌，应如何移动将牌、搜索最小解径的指导信息，因此有最小解径的指导

28、信息，因此有 P(n)h(n)*。u 对于任一节点n，至少要移动 P(n)步才能达到目标。实际的走步数要经过一定程度的搜索。h(n)=W(n):指出了本节点与目标节点的差异,但未具体给出如何移动将牌、搜索最小解径的指导信息：W(n)h(n)*w 对于任一节点n，至少要移动 W(n)步才能达到目标。实际的走步数要经过一定程度的搜索。两算法均为A*算法 W(n)P(n)h*(n)A*算法应用实例-8数码问题g(s)=d0=0g(A,B,C)=d1=1g(D,E,F)=d2=2g(G,H,I,J)=d3=3g(K)=d4=4g(L,M)=d5=58数码问题搜索策略比较：宽度优先 A算法 A*算法小结n启发式搜索策略n g:n 考虑当前路径已经花费的费用，及时抛弃已经经过的花费太大且距目标仍远的路径;n h:n 估计当前路径上节点到目标节点还需要的费用，引导搜索向最有希望的路径前进。w A 算法：定义估计函数：f=g+h；u A*算法：定义估计函数：f=g+h；满足h（n）h*（n）。作业:1、设 h=0;f=g=边的标记值，程序求解 High-way map 问题，求出最短解径，给出求解过程（Open，Closed内容）。2、设g=搜索深度，h=W或h=P，程序实现8数码问题。打印搜索过程，即有向图生成过程；给出解径。