人工智能 第三章 基本的问题求解方法

1、第三章第三章 基本的问题求解方法基本的问题求解方法问题求解的过程：问题求解的过程：1 1）知识表示；）知识表示；2 2）针对问）针对问题，分析特征，选择合适的方法来求解（包题，分析特征，选择合适的方法来求解（包括搜索和推理）括搜索和推理）方法：方法：1 1）基于状态图方法）基于状态图方法- -搜索；搜索；2 2）基于谓词逻辑方法）基于谓词逻辑方法- -推理；推理；3 3）基于结构化的知识表示方法来求解问题；）基于结构化的知识表示方法来求解问题；本章介绍本章介绍搜索技术搜索技术搜索技术是人工智能的基本技术之一, 在人工智能各应用领域中被广泛地使用。早期的人工智能程序与搜索技术联系就更为紧密，几乎

2、所有的早期的人工智能程序都是以搜索为基础的。uA.Newell和HASimon-LT程序uANewell和HASimon-GPS(General Problem Solver)uR.Fikes和N.Nilsson-STRIPS(Stanford Research Institute Problem Solver)现在, 搜索技术渗透在各种人工智能系统中, 在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博奕都广泛使用。 搜索(search)路径l状态序列搜索l寻找从初始状态到目标状态的路径;S0Sg搜索的必要性lAI为什么要研究search?l问题没有直接的解法;解方程组

3、;定理证明;l需要探索地求解;搜索与检索的区别l状态是否动态生成;l检索: 静态;在数据库中检索某人的纪录;l搜索: 动态生成;下棋几个问题l 目标状态是否确定?l确定: 定理证明, eight-puzzlel不确定: 求积分, 下棋;确定目标的性质;l 问题的解: 路径(解路径)/目标状态;需要路径:下棋 不需要路径:电路设计 需要/不需要: 诊病l 约束条件l目标状态不确定时, 用来约束目标状态的性质; lX+Y=4: 非整数解/整数解几个问题(续1)多解性;lX+Y=4:整数解最优解l评价标准/判断准则;lmin(x*y)l北京-上海: 时间最短/费用最少最优解是否唯一?l下棋搜索问题状

4、态空间2375148612384765搜索不是检索2375148612384765难点2375148612384765启发式方法2375148612384765搜索方法的评价标准 搜索问题是AI核心理论问题之一。一般一个问题可以用好几种搜索技术解决, 选择一种好的搜索技术对解决问题的效率很有关系, 甚至关系到求解问题有没有解。 搜索方法好的标准, 一般认为有两个： (1)搜索空间小; (2)解最佳。 搜索分类搜索从问题性质上来看, 可分为一般搜索和博奕搜索, 从处理方法上来看, 可分为盲目搜索和启发式搜索。还可以分得更细。到目前为止, AI领域中已提出许多具体的搜索方法, 概括起来有： (1)

5、求任一解路的搜索策略回溯法；爬山法(Hill Climbing)；宽度优先法(Breadth-first)；深度优先法(Depth-first) (2)求最佳解路的搜索策略大英博物馆法(British Museum)；最佳图搜索法(A*) (3)求与或关系解图的搜索法一般与或图搜索法(AO*)；极小极大法(Minimax)剪枝法(Alpha-beta Pruning)；启发式剪枝法(Heuristic Pruning) TOPICS回溯策略（ Backtracking ）图搜索（GRAPHSEARCH）无信息搜索启发式搜索TOPIC1 BacktrackingN1N0N2 N3 N4 N5 回

6、溯策略例：四皇后问题QQQQ()()Q(1,1)()QQ(1,1)(1,1)(2,3)()Q(1,1)(1,1)(2,3)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4)(3.2)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4

7、)(3.2)Q(1,2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)QQQQ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)(1,2)(1,2)(2,4)(1,2)(2,4)(3,1)(1,2)(2,4)(3,1)(4,3)存在问题及解决办法问题和解决方法：l深度问题对搜索深度加以限制l死循环问题状态重复: AB，BC, CA 记录从初始

8、状态到当前状态的路径TOPIC2 GRAPH SEARCH图搜索策略问题的引出l回溯搜索：只保留从初始状态到当前状态的一条路径。l图搜索：保留所有已经搜索过的路径。N5 N1N0N2 N3 N4 一些基本概念图：一个节点的集合。节点由弧连接起来。 有向图：弧是一个节点指向另一个节点的图，称为有向图。 后继/父亲：如果有一条弧从ni指向nj，则nj称为n i的后继，ni称为nj的父辈（父亲）； 一些基本概念(续1)路径：如果存在一个节点序列（ni0，ni1，nik），nij是nij-1是的后继，j=1，k，则称这个序列是从节点ni0到节点nik的一条路径，长度为k。祖先/后裔：如果存在一条从ni

9、到nj的路径，则称nj是ni的后裔，ni称为nj的祖先。树：每个节点最多只有一个父辈。没有父辈的节点称为根节点。没有后继的节点称为叶节点。 一些基本概念(续2)节点深度：根节点深度=0其它节点深度=父节点深度+10123一些基本概念（续3）扩展一个节点l生成出该节点的所有后继节点。弧的费用l有一条弧连接ni和nj两个节点, 用C(ni, nj)表示使用规则从ni到nj的费用(耗散值)。 玉泉路-天安门路径的耗散值l一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni, nj)表示从ni到nj的路径的耗散值。GRAPHSEARCH的思路OPEN表l已经生成但未扩展节点CLOSED

10、表l已扩展节点扩展节点i生成节点j 指针 调整指针图搜索（图搜索（Graph Search）的一般过程的一般过程 1 1、建立一个只有起始节点、建立一个只有起始节点S S的搜索图的搜索图G G，把，把S S放入一个叫放入一个叫openopen的的未扩展节点表；未扩展节点表；2 2、 建立已扩展节点表建立已扩展节点表closedclosed，初始为空；初始为空；3 3、 LOOPLOOP；若；若openopen为空，则失败退出；为空，则失败退出；4 4、 选选openopen表中的第一个节点，设为表中的第一个节点，设为n n，移入移入closedclosed表；表；5 5、若、若n n为目标节点

11、，则成功退出，该问题的解即是为目标节点，则成功退出，该问题的解即是G G中沿中沿S S指向指向n n的路径；的路径；6 6、若不是目标节点，则扩展、若不是目标节点，则扩展n n，生成不是生成不是n n的祖先的那些后继的祖先的那些后继节点的集合节点的集合m m，把，把m m的成员作为的成员作为n n的后继加入的后继加入G G中；中；7 7、对未曾在、对未曾在G G中出现过的中出现过的m m成员，设一通向成员，设一通向n n的指针，把它们加的指针，把它们加入入openopen表。对已在表。对已在closedclosed或或openopen表上的表上的m m成员，确定是否要更成员，确定是否要更改到改

12、到n n的指针方向，对已在的指针方向，对已在closedclosed上的上的m m成员，确定是否要更改成员，确定是否要更改G G中通向每个后裔节点的指针方向。中通向每个后裔节点的指针方向。8 8、按某一方式（深度优先、宽度优先、按某一方式（深度优先、宽度优先、A A* *算法）重排算法）重排openopen表表9 9、GO LOOP GO LOOP 例子SOPENCLOSES 123 S 1,2,3 S 2,1,3 S 451,3 S,2 1,3,4,5 S,2 3,1,4,5 S,2 1,4,5 S,2,3 61,4,5,6 S,2,3 例：右图中黑节点表示例：右图中黑节点表示已扩展，白节点

13、表示未已扩展，白节点表示未扩展，问题：先扩展扩展，问题：先扩展6 6号号节点生成节点生成m1=4m1=4，77，然，然后扩展节点后扩展节点1 1，生成，生成m2=2m2=2，按算法第七步按算法第七步重新修改原图。重新修改原图。612453难点！算法中第七步7扩展节点6生成m1=4，7的调整61245371235467再扩展节点1生成m2=2的调整12354671235467最终结果61245371235467图搜索与回溯算法的区别 扩展节点:l回溯算法:生成一个儿子节点. l图搜索:扩展节点, 生成所有儿子节点. 候选节点:l回溯算法:一个. l图搜索:多个. 回溯:l回溯算法:返回父亲节点.

14、 l图搜索:不一定返回父亲节点.TOPIC3 无信息搜索如果在GRAPHSEARCH中，对节点的排序不使用与问题相关的信息，则称为无信息图搜索（盲目搜索）宽度优先和深度优先1 1、breadth-first searchbreadth-first searchp宽度优先搜索：如果搜索是以接近起始节点宽度优先搜索：如果搜索是以接近起始节点的程度依次扩展节点的的程度依次扩展节点的 。 p搜索逐层进行；在对下一层的任一节点进行搜索逐层进行；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。搜索之前，必须搜索完本层的所有节点。(1) (1) 把起始节点放到把起始节点放到OPENOPEN表中表

15、中( (如果该起始节点为如果该起始节点为一目标节点，则求得一个解答一目标节点，则求得一个解答) )。(2) (2) 如果如果OPENOPEN是个空表，则没有解，失败退出；是个空表，则没有解，失败退出；否则继续。否则继续。(3) (3) 把第一个节点把第一个节点( (节点节点n)n)从从OPENOPEN表移出，并把它表移出，并把它放入放入CLOSEDCLOSED的扩展节点表中。的扩展节点表中。(4) (4) 扩展节点扩展节点n n。如果没有后继节点，则转向上述。如果没有后继节点，则转向上述第第(2)(2)步。步。(5) (5) 把把n n的所有后继节点放到的所有后继节点放到OPENOPEN表的末

16、端，并提表的末端，并提供从这些后继节点回到供从这些后继节点回到n n的指针。的指针。(6) (6) 如果如果n n的任一个后继节点是个目标节点，则找的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第到一个解答，成功退出；否则转向第(2)(2)步。步。算法1234567891011121314151617 1819 2122 23 24 2627 282930311234567891011121314151617 1819 2 34 5 678 9 10 11 12 13 14 15 16 17 18 1912345678910123456789搜索演示已扩展节点正在扩展节点扩展

17、的子节点未扩展节点目标宽度优先法应用示例宽度优先法应用示例宽度优先法求九宫重排问题宽度优先法求九宫重排问题231847651238476523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标8234187654p宽度优先搜索是图搜索一般过程的特殊情宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第况，将图搜索一般过程中的第8 8步具体化为本步具体化为本算法中的第算法

18、中的第6 6步，这实际是将步，这实际是将OPENOPEN表作为表作为“先先进先出进先出”的队列进行操作。的队列进行操作。p一定能找到解一定能找到解p找到的解一定是最佳解找到的解一定是最佳解u(在每个路径消耗是同样的意义上在每个路径消耗是同样的意义上)p搜索的空间大、慢。搜索的空间大、慢。 分析分析p深度优先搜索：首先扩展最新产生的深度优先搜索：首先扩展最新产生的( (即最即最深的深的) )节点。深度相等的节点可以任意排列。节点。深度相等的节点可以任意排列。p特点：扩展最深的节点特点：扩展最深的节点, ,使得搜索沿着状态使得搜索沿着状态空间某条单一的路径从起始节点向下进行下空间某条单一的路径从起

19、始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。它才考虑另一条替代的路径。p算法：与宽度优先相似，不同在于：算法：与宽度优先相似，不同在于：(5) (5) 把把n n的所有后继节点放到的所有后继节点放到OPENOPEN表的前端表的前端2 2、depth-first searchdepth-first search34567891011121314151617 1819 20 21 23 24 2627 2829303112活结点表活结点表1 1211242248448168816168178817178 84944918

20、991818919919194 425225105510209 9 91010202010211010212110105115511演示例 九宫重排问题九宫重排问题28 3 16 427 5初始状态初始状态1 2 3 8 47 6 5目标状态目标状态应用示例应用示例2 32 31 8 41 8 47 6 57 6 5 2 32 31 8 41 8 47 6 57 6 52 8 32 8 31 41 47 6 57 6 52 32 31 8 41 8 47 6 57 6 52 8 32 8 31 41 47 6 57 6 52 8 32 8 31 6 41 6 47 57 52 8 32 8 3

21、 1 4 1 47 6 57 6 52 8 32 8 31 6 41 6 47 57 52 8 32 8 31 6 41 6 4 7 5 7 52 8 32 8 37 1 47 1 4 6 5 6 5 8 38 32 1 42 1 47 6 57 6 52 82 81 4 31 4 37 6 57 6 52 8 32 8 31 4 51 4 57 6 7 6 1 2 31 2 37 8 47 8 4 6 5 6 51 2 31 2 38 48 47 6 57 6 52 8 32 8 3 6 4 6 41 7 51 7 52 8 32 8 31 61 67 5 47 5 48 38 32 1 4

22、2 1 47 6 57 6 52 8 32 8 37 1 47 1 46 56 52 82 81 4 31 4 37 6 57 6 52 8 32 8 31 4 51 4 57 67 612 23 34 45 56 67 78 89 9a ab bd d1 2 31 2 3 8 4 8 47 6 57 6 5目标目标分析不一定能找到解。解不一定是最佳解。 3 3、其他方法、其他方法p含有深度界限的深度优先搜索算法：含有深度界限的深度优先搜索算法：p基于代价树的搜索算法：基于代价树的搜索算法：TOPIC4 TOPIC4 heuristic searchp盲目搜索效率低，耗费过多的计算空间与时盲目

23、搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。间，这是组合爆炸的一种表现形式。 p利用知识来引导搜索，达到减少搜索范围，利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。降低问题复杂度的目的。p启发式方法启发式方法的本质是部分地放弃算法的本质是部分地放弃算法一般一般化化, 通用化通用化的概念的概念, 把所要解的问题的具体领把所要解的问题的具体领域域 的知识加进算法中去的知识加进算法中去, 以提高算法的效率。以提高算法的效率。 启发式搜索启发式搜索：就是利用与问题有关的启发信：就是利用与问题有关的启发信息进行搜索息进行搜索启发信息：与具体问题有关的特性信息启发信息：

24、与具体问题有关的特性信息启发信息的强度启发信息的强度强：降低搜索工作量，但可能导致找不到强：降低搜索工作量，但可能导致找不到最优解最优解弱：一般导致工作量加大，极限情况下变弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解为盲目搜索，但可能可以找到最优解难点：难点：获取；获取；强度的确定；强度的确定；启发信息的用途a a、用于决定要扩展的下一节点（避免盲目、用于决定要扩展的下一节点（避免盲目扩展）扩展）b b、在扩展过程中，用于决定生成哪一个或、在扩展过程中，用于决定生成哪一个或哪几个后继（以免太多无用节点）哪几个后继（以免太多无用节点）C C、用于决定被抛弃、用于决定被抛弃

25、oror被修剪的节点（博羿被修剪的节点（博羿中常用，其它不常见）中常用，其它不常见）。基本思想启发式搜索过程中, 要对OPEN表进行排序, 这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度, 我们总是希望能找到最有希望通向目标节点的待扩展节点优先扩展。 希望的量度就是通过估价函数f（n）来描述的p估价函数：定义为从初始节点经过估价函数：定义为从初始节点经过n n节点到达节点到达目的节点的路径的最小代价的估计值，目的节点的路径的最小代价的估计值，XWZg(X)h(X)估价函数的形式为估价函数的形式为f(n)=g(n)+h(n)g g（n n）是是到目前为止到目前为止, , 从从s

26、s到到n n的最小路径的最小路径 （实（实际值）际值）h h（n n） n n节点到目标节点到目标节点最佳路径的估计值，节点最佳路径的估计值，体现了启发信息体现了启发信息通常通常f f（n n）由经验和直）由经验和直觉得到的，有很多种取法，觉得到的，有很多种取法，关键在于关键在于h h（n n）。）。e eg g八数码难题的估价函数八数码难题的估价函数f f（n n）=g=g（n n）+h+h（n n）d d（n n）：）：节点节点n n的深度的深度w w（n n）：）：不在位的数字个数不在位的数字个数p p（n n）：）：不在位的数字离目标的距离之和不在位的数字离目标的距离之和例：右图（例：

27、右图（a a）中中2 2、8 8、1 1、6 6不在位，不在位，w w（n n）=4 =4 ，p p（n n）=1+2+1+1=5=1+2+1+1=5；（b b）6 6、8 8、2 2、1 1不不在位，在位，w w（n n）=4 =4 ，p p（n n）=3+2+2+2=9 =3+2+2+2=9 2831647568321475abc81263754s（n）：沿着周围那些非中心方格上依顺时针方向检查n格局中每一将牌，如果其后紧跟的将牌正好是目标格局中该将牌的后续者，则该将牌得0分，否则得2分；在中中方格上有将牌得1分，无得0分；将所有将牌得分之和即为s（n）。图（c）中s（a）=6。 2831

28、647568321475abc81263754例子: eight-puzzlen评价函数nf(n) = d(n) + W(n)nd(n): 节点n的深度;nW(n):与目标相比, 错位的数字数目，即不在位的数字个数;1238476528316475初始状态目标状态 2831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7

29、)目标123456由前例看出, 与深度优先搜索和宽度优先搜索相比较, 启发式搜索大大减少了搜索范围, 大大减少了扩展的节点, 大大减少了生成的节点, 从而达到降低问题复杂度, 提高算法的效率的目的。 估价函数的进一步说明nSg*(n)h*(n) gf*(n)=g*(n)+h*(n)：从s经过n到g的最短路径lg*(n)：从s到n的最短路径lh*(n)：从n到g的最短路径f（n）=g（n）+h（n）：从s经过n到g的最短路径的估计值lg(n)、h(n) 分别是g*(n)、h*(n) 的估计值g(n)l一般取实际走过的路径的费用和.lg(n) g*(n)l随着算法的执行，由于指针的变动，g(n)会

30、下降. h0l没有启发式信息;启发式搜索算法A算法A*算法A算法在Graphsearch过程中，如果第8步的重排open表是依据f（n）=g（n）+h（n）进行的，则称该过程为A算法。lg(n)取实际走过的路径的费用和;l节点排序是按照f(n)从小到大排;l如前例-九宫重排问题算法A*在A算法中，如果满足条件： 0h(n)h*(n)则A算法称为A*算法。l称h（x）为h*（x）的下界，它表示某种偏于保守的估计。启发式搜索算法A*又称为最佳图搜索算法(Optimal Search)。 5 5、经典例题（八数码难题）：、经典例题（八数码难题）：设有八数码难题，起始状态如右图，设有八数码难题，起始状

31、态如右图，要求找出九宫重排的最终解路径，要求找出九宫重排的最终解路径，并画框图。并画框图。28316475解法一：解法一：第一步：取估价函数为第一步：取估价函数为f f（n n）=d=d（n n）+w+w（n n），），则显然按照定义则显然按照定义1 1它是它是A A算法；算法；第二步：因为第二步：因为w w（n n）指的是不在位的个数，所以指的是不在位的个数，所以w w（n n）=4=4，即估计只需要走，即估计只需要走4 4步即可到达目标状步即可到达目标状态，而实际上要到达目标状态肯定要大于态，而实际上要到达目标状态肯定要大于3 3步，步，即即w w（x x）w w* *（x x），），满足

32、定义，所以是满足定义，所以是A A* *算法；算法；第三步：画图，并计算各个状态第三步：画图，并计算各个状态f f（n n）的值，取的值，取f f（n n）值最小的节点进行扩充。值最小的节点进行扩充。( (图见前图见前) )解法二：取估价函数为f（n）=d（n）+P（n），同理也是A*算法；如图Tips A算法与A*算法区别区别在于在A*算法中， 0h(n)h*(n)示例：八数码难题中h(n)的三种定义h(n)=w(n), h(n)=p(n)-A*算法h(n)=p(n)+3s(n)-A算法A*算法具有可采纳性 一般地说对任意一个图, 当s到目标节点有一条路径存在时, 如果搜索算法总是在找到一条

33、从s到目标节点的最佳路径上结束, 则称该搜索算法是可采纳的(Admissibility)。lA*就具有可采纳性即当问题有解时, A*一定能找到一条到达目标节点的最佳路径。（why？）证明见参考资料-A*算法具有可采纳性考虑h(n)0的情况！A*算法的理论意义 A*算法的理论意义在于给出了求解最佳解的条件h(n) h*(n) 对给定的问题,函数h*(n)在问题有解的条件下客观上是存在的。但在问题求解过程中不可能都明确知道。因此, 对实际问题, 能不能使所定义的启发函数满足下界范围条件? 这是个问题。如果困难很大, 那未A*算法的实际应用就会受到限制。 以前面-八数码难题为例定义h(n)为任意节点与目标之间的差异若取= w(n)(将牌不在位个数), 那未很容易看出, 尽管我们对具体的h*(n)是多少很难确切知道, 但根据“不在位”将牌个数这个估计, 就能得出至少要移动W(n)步才能到达目标, 显然有h(n) = W(n) h*(n)。进一步考虑任意节点与目标之间距离的信息, 即取h(n) = p(n), p(n)定义为每一个将牌与其目标位置之间距离(不考虑夹在其间的将牌)的总和,那未同样能断定至少也要移动p(n)步才能达到目