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

第三章基本的问题求解方法问题求解的过程：1）知识表示；2）针对问题，分析特征，选择合适的方法来求解（包括搜索和推理）方法： 1）基于状态图方法-搜索； 2）基于谓词逻辑方法-推理； 3）基于结构化的知识表示方法来求解问题；本章介绍搜索技术第三章基本的问题求解方法问题求解的过程：1）知识表示；2）1搜索技术是人工智能的基本技术之一,在人工智能各应用领域中被广泛地使用。早期的人工智能程序与搜索技术联系就更为紧密，几乎所有的早期的人工智能程序都是以搜索为基础的。A.Newell和H·A·Simon-LT程序A·Newell和H·A·Simon-GPS(GeneralProblemSolver)R.Fikes和N.Nilsson-STRIPS(StanfordResearchInstituteProblemSolver)现在,搜索技术渗透在各种人工智能系统中,在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博奕都广泛使用。搜索技术是人工智能的基本技术之一,在人工智能各应用领域中被2搜索(search)路径状态序列搜索寻找从初始状态到目标状态的路径;S0Sg搜索(search)路径S0Sg3搜索的必要性AI为什么要研究search?问题没有直接的解法;解方程组;定理证明;需要探索地求解;搜索的必要性AI为什么要研究search?4搜索与检索的区别状态是否动态生成;检索:静态;在数据库中检索某人的纪录;搜索:动态生成;下棋搜索与检索的区别状态是否动态生成;5几个问题目标状态是否确定?确定:定理证明,eight-puzzle不确定:求积分,下棋;确定目标的性质;问题的解:路径(解路径)/目标状态;需要路径:下棋

不需要路径:电路设计

需要/不需要:诊病约束条件目标状态不确定时,用来约束目标状态的性质;X+Y=4:非整数解/整数解几个问题目标状态是否确定?6几个问题(续1)多解性;X+Y=4:整数解最优解评价标准/判断准则;min(x*y)北京->上海:时间最短/费用最少最优解是否唯一?下棋几个问题(续1)多解性;7搜索问题状态空间237

5148612384765搜索问题状态空间237

51486123847658搜索不是检索237

5148612384765搜索不是检索237

51486123847659难点237

5148612384765难点237

514861238476510启发式方法237

5148612384765启发式方法237

514861238476511搜索方法的评价标准

搜索问题是AI核心理论问题之一。一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。

搜索方法好的标准,一般认为有两个：

(1)搜索空间小;

(2)解最佳。搜索方法的评价标准

搜索问题是AI核心理论问题之一。一般一个12搜索分类搜索从问题性质上来看,可分为一般搜索和博奕搜索,从处理方法上来看,可分为盲目搜索和启发式搜索。还可以分得更细。到目前为止,AI领域中已提出许多具体的搜索方法,概括起来有：

(1)求任一解路的搜索策略

回溯法；爬山法(HillClimbing)；宽度优先法(Breadth-first)；深度优先法(Depth-first)

(2)求最佳解路的搜索策略

大英博物馆法(BritishMuseum)；最佳图搜索法(A*)

(3)求与或关系解图的搜索法

一般与或图搜索法(AO*)；极小极大法(Minimax)

剪枝法(Alpha-betaPruning)；启发式剪枝法(HeuristicPruning)搜索分类搜索从问题性质上来看,可分为一般搜索和博奕搜索,13人工智能第三章基本的问题求解方法14TOPICS回溯策略（Backtracking

）图搜索（GRAPHSEARCH）无信息搜索启发式搜索TOPICS回溯策略（Backtracking）15TOPIC1BacktrackingN1N0N2N3N4N5回溯策略TOPIC1BacktrackingN1N0N2N316例：四皇后问题例：四皇后问题17()()18()Q((1,1))()Q((1,1))19()QQ((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))20()Q((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))21()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,122()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,123()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,124()Q((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)25()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)26()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))()((1,1))((1,1)(2,3))((1,1)27()((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)28()((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))()((1,1))((1,1)(2,3))((1,1)29QQQQ()((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))QQQQ()((1,1))((1,1)(2,3))((130存在问题及解决办法问题和解决方法：深度问题对搜索深度加以限制死循环问题状态重复:A→B，B→C,C→A记录从初始状态到当前状态的路径存在问题及解决办法问题和解决方法：31TOPIC2GRAPHSEARCH图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。

N5N1N0N2

N3

N4TOPIC2GRAPHSEARCH图搜索策略N5N132一些基本概念图：一个节点的集合。节点由弧连接起来。

有向图：弧是一个节点指向另一个节点的图，称为有向图。

后继/父亲：如果有一条弧从ni指向nj，则nj称为ni的后继，ni称为nj的父辈（父亲）；

一些基本概念图：一个节点的集合。节点由弧连接起来。33一些基本概念(续1)路径：如果存在一个节点序列（ni0，ni1，……，nik），nij是nij-1是的后继，j=1，……，k，则称这个序列是从节点ni0到节点nik的一条路径，长度为k。祖先/后裔：如果存在一条从ni到nj的路径，则称nj是ni的后裔，ni称为nj的祖先。树：每个节点最多只有一个父辈。没有父辈的节点称为根节点。没有后继的节点称为叶节点。

一些基本概念(续1)路径：如果存在一个节点序列（ni0，ni34一些基本概念(续2)节点深度： 根节点深度=0 其它节点深度=父节点深度+10123一些基本概念(续2)节点深度：012335一些基本概念（续3）扩展一个节点生成出该节点的所有后继节点。弧的费用有一条弧连接ni和nj两个节点,用C(ni,nj)表示使用规则从ni到nj的费用(耗散值)。玉泉路---天安门路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。一些基本概念（续3）扩展一个节点36GRAPHSEARCH的思路OPEN表已经生成但未扩展节点CLOSED表已扩展节点扩展节点i生成节点j指针

调整指针GRAPHSEARCH的思路OPEN表37图搜索（GraphSearch）的一般过程

1、建立一个只有起始节点S的搜索图G，把S放入一个叫open的未扩展节点表；2、

建立已扩展节点表closed，初始为空；3、

LOOP；若open为空，则失败退出；4、

选open表中的第一个节点，设为n，移入closed表；5、若n为目标节点，则成功退出，该问题的解即是G中沿S指向n的路径；6、若不是目标节点，则扩展n，生成不是n的祖先的那些后继节点的集合m，把m的成员作为n的后继加入G中；7、对未曾在G中出现过的m成员，设一通向n的指针，把它们加入open表。对已在closed或open表上的m成员，确定是否要更改到n的指针方向，对已在closed上的m成员，确定是否要更改G中通向每个后裔节点的指针方向。8、按某一方式（深度优先、宽度优先、A*算法）重排open表9、GOLOOP图搜索（GraphSearch）的一般过程1、建立一个只38例子SOPENCLOSE{S}{}123{}{S}{1,2,3}{S}{2,1,3}{S}45{1,3}{S,2}{1,3,4,5}{S,2}{3,1,4,5}{S,2}{1,4,5}{S,2,3}6{1,4,5,6}{S,2,3}例子SOPENCLOSE{S}{}123{}{S}39例：右图中黑节点表示已扩展，白节点表示未扩展，问题：先扩展6号节点生成m1={4，7}，然后扩展节点1，生成m2={2}，按算法第七步重新修改原图。612453难点！！！算法中第七步7例：右图中黑节点表示已扩展，白节点表示未扩展，问题：先扩展640扩展节点6生成m1={4，7}的调整61245371235467×扩展节点6生成m1={4，7}的调整61245371235441再扩展节点1生成m2={2}的调整12354671235467××再扩展节点1生成m2={2}的调整123546712354642最终结果61245371235467最终结果6124537123546743图搜索与回溯算法的区别

扩展节点:回溯算法:生成一个儿子节点.

图搜索:扩展节点,生成所有儿子节点.

候选节点:回溯算法:一个.

图搜索:多个.

回溯:回溯算法:返回父亲节点.

图搜索:不一定返回父亲节点.图搜索与回溯算法的区别扩展节点:44TOPIC3无信息搜索如果在GRAPHSEARCH中，对节点的排序不使用与问题相关的信息，则称为无信息图搜索（盲目搜索）宽度优先和深度优先TOPIC3无信息搜索如果在GRAPHSEARCH中，对节451、breadth-firstsearch宽度优先搜索：如果搜索是以接近起始节点的程度依次扩展节点的。

搜索逐层进行；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。1、breadth-firstsearch宽度优先搜索：如46(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节4712345678910111213141516171819★21222324★26272829303112345678910111213141516171819★234567891011121314151617181912345678910123456789搜索演示★已扩展节点

正在扩展节点扩展的子节点

未扩展节点目标12345678910111213141516171819★48宽度优先法应用示例宽度优先法求九宫重排问题2318476512384765宽度优先法应用示例宽度优先法求九宫重排问题24923184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标82341876542323283250宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。一定能找到解找到的解一定是最佳解(在每个路径消耗是同样的意义上)搜索的空间大、慢。

分析宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的51深度优先搜索：首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。特点：扩展最深的节点,使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。算法：与宽度优先相似，不同在于：(5)把n的所有后继节点放到OPEN表的前端2、depth-firstsearch深度优先搜索：首先扩展最新产生的(即最深的)节点。深度相等的523456789101112131415161718192021★2324★26272829303112活结点表1121124224844816881616817881717884944918991818919919194425225105510209991010202010211010212110105115511★演示34567891011121314151617181920253例九宫重排问题83647■5初始状态1238■4765目标状态应用示例例九宫重排问题83初始状态1254231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abd12384765目标2323283255分析①不一定能找到解。②解不一定是最佳解。分析①不一定能找到解。563、其他方法含有深度界限的深度优先搜索算法：基于代价树的搜索算法：3、其他方法含有深度界限的深度优先搜索算法：57TOPIC4heuristicsearch盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发式方法的本质是部分地放弃算法"一般化,通用化"的概念,把所要解的问题的具体领域的知识加进算法中去,以提高算法的效率。

TOPIC4heuristicsearch盲目搜索效率低58启发式搜索：就是利用与问题有关的启发信息进行搜索启发信息：与具体问题有关的特性信息启发信息的强度强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解难点：获取；强度的确定；启发式搜索：就是利用与问题有关的启发信息进行搜索59启发信息的用途a、用于决定要扩展的下一节点（避免盲目扩展）b、在扩展过程中，用于决定生成哪一个或哪几个后继（以免太多无用节点）C、用于决定被抛弃or被修剪的节点（博羿中常用，其它不常见）。。。启发信息的用途a、用于决定要扩展的下一节点（避免盲目扩展）60基本思想启发式搜索过程中,要对OPEN表进行排序,这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度,我们总是希望能找到最有希望通向目标节点的待扩展节点优先扩展。希望的量度就是通过估价函数f（n）来描述的基本思想启发式搜索过程中,要对OPEN表进行排序,这就需61估价函数：定义为从初始节点经过n节点到达目的节点的路径的最小代价的估计值，XWZg(X)h(X)估价函数的形式为f(n)=g(n)+h(n)g（n）—是到目前为止,从s到n的最小路径

（实际值）h（n）—n节点到目标节点最佳路径的估计值，体现了启发信息通常f（n）由经验和直觉得到的，有很多种取法，关键在于h（n）。估价函数：定义为从初始节点经过n节点到达目的节点的路径的最小62e．g．八数码难题的估价函数 f（n）=g（n）+h（n） d（n）：节点n的深度 w（n）：不在位的数字个数 p（n）：不在位的数字离目标的距离之和例：右图（a）中2、8、1、6不在位，w（n）=4，p（n）=1+2+1+1=5；（b）6、8、2、1不在位，w（n）=4，p（n）=3+2+2+2=92831647568321475abc81263754e．g．八数码难题的估价函数2836863s（n）：沿着周围那些非中心方格上依顺时针方向检查n格局中每一将牌，如果其后紧跟的将牌正好是目标格局中该将牌的后续者，则该将牌得0分，否则得2分；在中中方格上有将牌得1分，无得0分；将所有将牌得分之和即为s（n）。图（c）中s（a）=6。2831647568321475abc81263754s（n）：沿着周围那些非中心方格上依顺时针方向检查n格局中每64例子:eight-puzzle评价函数f(n)=d(n)+W(n)d(n):节点n的深度;W(n):与目标相比,错位的数字数目，即不在位的数字个数;1238476528316475初始状态目标状态例子:eight-puzzle评价函数1238476528652831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)目标123456283283283266由前例看出,与深度优先搜索和宽度优先搜索相比较,启发式搜索大大减少了搜索范围,大大减少了扩展的节点,大大减少了生成的节点,从而达到降低问题复杂度,提高算法的效率的目的。由前例看出,与深度优先搜索和宽度优先搜索相比较,启发式搜67估价函数的进一步说明nSg*(n)h*(n)gf*(n)=g*(n)+h*(n)：从s经过n到g的最短路径g*(n)：从s到n的最短路径h*(n)：从n到g的最短路径f（n）=g（n）+h（n）：从s经过n到g的最短路径的估计值g(n)、h(n)分别是g*(n)、h*(n)的估计值估价函数的进一步说明nSg*(n)h*(n)gf*(n)=68g(n)一般取实际走过的路径的费用和.g(n)g*(n)随着算法的执行，由于指针的变动，g(n)会下降.

h0没有启发式信息;g(n)69启发式搜索算法A算法A*算法启发式搜索算法A算法70A算法在Graphsearch过程中，如果第8步的重排open表是依据f（n）=g（n）+h（n）进行的，则称该过程为A算法。g(n)取实际走过的路径的费用和;节点排序是按照f(n)从小到大排;如前例-九宫重排问题A算法在Graphsearch过程中，如果第8步的重排ope71算法A*在A算法中，如果满足条件： 0≤h(n)≤h*(n) 则A算法称为A*算法。称h（x）为h*（x）的下界，它表示某种偏于保守的估计。启发式搜索算法A*又称为最佳图搜索算法(OptimalSearch)。算法A*在A算法中，如果满足条件：725、经典例题（八数码难题）：设有八数码难题，起始状态如右图，要求找出九宫重排的最终解路径，并画框图。283164755、经典例题（八数码难题）：28373解法一：第一步：取估价函数为f（n）=d（n）+w（n），则显然按照定义1它是A算法；第二步：因为w（n）指的是不在位的个数，所以w（n）=4，即估计只需要走4步即可到达目标状态，而实际上要到达目标状态肯定要大于3步，即w（x）≤w*（x），满足定义，所以是A*算法；第三步：画图，并计算各个状态f（n）的值，取f（n）值最小的节点进行扩充。(图见前)解法一：74解法二：取估价函数为f（n）=d（n）+P（n），同理也是A*算法；如图解法二：取估价函数为f（n）=d（n）+P（n），同理也是A75人工智能第三章基本的问题求解方法76TipsA算法与A*算法区别区别在于在A*算法中，0≤h(n)≤h*(n)示例：八数码难题中h(n)的三种定义h(n)=w(n),h(n)=p(n)-A*算法h(n)=p(n)+3s(n)-A算法TipsA算法与A*算法区别区别在于在A*算法中，0≤h77A*算法具有可采纳性一般地说对任意一个图,当s到目标节点有一条路径存在时,如果搜索算法总是在找到一条从s到目标节点的最佳路径上结束,则称该搜索算法是可采纳的(Admissibility)。A*就具有可采纳性即当问题有解时,A*一定能找到一条到达目标节点的最佳路径。（why？）证明见参考资料-A*算法具有可采纳性考虑h(n)≡0的情况！！！！A*算法具有可采纳性一般地说对任意一个图,当s到目标节点78A*算法的理论意义A*算法的理论意义在于给出了求解最佳解的条件h(n)≤h*(n)

对给定的问题,函数h*(n)在问题有解的条件下客观上是存在的。但在问题求解过程中不可能都明确知道。因此,对实际问题,能不能使所定义的启发函数满足下界范围条件?这是个问题。如果困难很大,那未A*算法的实际应用就会受到限制。A*算法的理论意义A*算法的理论意义在于给出了求解最佳解的79以前面-八数码难题为例定义h(n)为任意节点与目标之间的差异若取=w(n)(将牌不在位个数),那未很容易看出,尽管我们对具体的h*(n)是多少很难确切知道,但根据“不在位”将牌个数这个估计,就能得出至少要移动W(n)步才能到达目标,显然有h(n)=W(n)≤h*(n)。进一步考虑任意节点与目标之间距离的信息,即取h(n)=p(n),p(n)定义为每一个将牌与其目标位置之间距离(不考虑夹在其间的将牌)的总和,那未同样能断定至少也要移动p(n)步才能达到目标，仍然有P(n)≤h*(n)。以前面-八数码难题为例80启发信息的强度的进一步分析强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解启发信息的强度的进一步分析强：降低搜索工作量，但可能导致找不81h(n)取不同函数时的八数码难题求解情况进行比较,比较h(n)=0、h(n)=W(n)和h(n)=p(n)三种情况的求解结果。

①h(n)=0:即启发函数启发信息为0,f(n)=h(n)+g(n)=g(n)＝d(n)(搜索深度),此实际上是宽度优先搜索。

②h(n)=W(n):即启发函数取将牌不在位的信息,f(n)=h(n)+g(n)=W(n)+d(n)(搜索深度)。

③h(n)=p(n):即启发函数取每一个将牌与其目标位置之间距离的总和的信息

h(n)取不同函数时的八数码难题求解情况进行比较,比较h(82实际上①中h(n)=0≤h*(n)，②和③均已证明W(n)≤h*(n)，P（n）≤h*(n)，即3种算法都是A*算法。比较搜索空间，分析启发信息强弱的效果：启发函数h(n)=0h(n)=W(n)h(n)=p(n)扩展节点数2665生成节点数461311实际上①中h(n)=0≤h*(n)，②和③均已证明W(83附：评价搜索算法的指标1、外显率（Penetrance）P=L/TL—从初始状态到目标状态的长度；T—从初始状态到目标状态所产生的所有状态的个数；显然P=1时，说明有效路径所经历的节点都有用附：评价搜索算法的指标1、外显率（Penetrance）842、有效分支数（EffectiveBranchingFactor）B—搜索过程中，平均每个节点产生的分支数目；因为每个节点产生的平均分支数为B，所以从初始到目标状态产生的总分支数T为：2、有效分支数（EffectiveBranchingFa85本章回顾教学内容：本章在上一章知识表示的基础上研究问题求解的方法，是人工智能研究的又一核心问题。本章主要介绍基本的搜索技术教学重点：图搜索策略、启发式搜索教学难点：启发式搜索教学方法：课堂教学为主，辅以恰当的实验。注意结合前面所学知识表示的基础内容，将其与问题求解方法融为一体。教学要求：重点掌握一般图搜索策略，掌握各种搜索方法，尤其是启发式搜索中的A*算法。

本章回顾教学内容：本章在上一章知识表示的基础上研究问题求解的86homework选做：利用A*算法求解九宫重排问题。要求：同前

----THEEND----homework选做：利用A*算法求解九宫重排问题。----87第三章基本的问题求解方法问题求解的过程：1）知识表示；2）针对问题，分析特征，选择合适的方法来求解（包括搜索和推理）方法： 1）基于状态图方法-搜索； 2）基于谓词逻辑方法-推理； 3）基于结构化的知识表示方法来求解问题；本章介绍搜索技术第三章基本的问题求解方法问题求解的过程：1）知识表示；2）88搜索技术是人工智能的基本技术之一,在人工智能各应用领域中被广泛地使用。早期的人工智能程序与搜索技术联系就更为紧密，几乎所有的早期的人工智能程序都是以搜索为基础的。A.Newell和H·A·Simon-LT程序A·Newell和H·A·Simon-GPS(GeneralProblemSolver)R.Fikes和N.Nilsson-STRIPS(StanfordResearchInstituteProblemSolver)现在,搜索技术渗透在各种人工智能系统中,在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博奕都广泛使用。搜索技术是人工智能的基本技术之一,在人工智能各应用领域中被89搜索(search)路径状态序列搜索寻找从初始状态到目标状态的路径;S0Sg搜索(search)路径S0Sg90搜索的必要性AI为什么要研究search?问题没有直接的解法;解方程组;定理证明;需要探索地求解;搜索的必要性AI为什么要研究search?91搜索与检索的区别状态是否动态生成;检索:静态;在数据库中检索某人的纪录;搜索:动态生成;下棋搜索与检索的区别状态是否动态生成;92几个问题目标状态是否确定?确定:定理证明,eight-puzzle不确定:求积分,下棋;确定目标的性质;问题的解:路径(解路径)/目标状态;需要路径:下棋

不需要路径:电路设计

需要/不需要:诊病约束条件目标状态不确定时,用来约束目标状态的性质;X+Y=4:非整数解/整数解几个问题目标状态是否确定?93几个问题(续1)多解性;X+Y=4:整数解最优解评价标准/判断准则;min(x*y)北京->上海:时间最短/费用最少最优解是否唯一?下棋几个问题(续1)多解性;94搜索问题状态空间237

5148612384765搜索问题状态空间237

514861238476595搜索不是检索237

5148612384765搜索不是检索237

514861238476596难点237

5148612384765难点237

514861238476597启发式方法237

5148612384765启发式方法237

514861238476598搜索方法的评价标准

搜索问题是AI核心理论问题之一。一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。

搜索方法好的标准,一般认为有两个：

(1)搜索空间小;

(2)解最佳。搜索方法的评价标准

搜索问题是AI核心理论问题之一。一般一个99搜索分类搜索从问题性质上来看,可分为一般搜索和博奕搜索,从处理方法上来看,可分为盲目搜索和启发式搜索。还可以分得更细。到目前为止,AI领域中已提出许多具体的搜索方法,概括起来有：

(1)求任一解路的搜索策略

回溯法；爬山法(HillClimbing)；宽度优先法(Breadth-first)；深度优先法(Depth-first)

(2)求最佳解路的搜索策略

大英博物馆法(BritishMuseum)；最佳图搜索法(A*)

(3)求与或关系解图的搜索法

一般与或图搜索法(AO*)；极小极大法(Minimax)

剪枝法(Alpha-betaPruning)；启发式剪枝法(HeuristicPruning)搜索分类搜索从问题性质上来看,可分为一般搜索和博奕搜索,100人工智能第三章基本的问题求解方法101TOPICS回溯策略（Backtracking

）图搜索（GRAPHSEARCH）无信息搜索启发式搜索TOPICS回溯策略（Backtracking）102TOPIC1BacktrackingN1N0N2N3N4N5回溯策略TOPIC1BacktrackingN1N0N2N3103例：四皇后问题例：四皇后问题104()()105()Q((1,1))()Q((1,1))106()QQ((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))107()Q((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))108()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,1109()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,1110()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,1111()Q((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)112()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)113()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))()((1,1))((1,1)(2,3))((1,1)114()((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)115()((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))()((1,1))((1,1)(2,3))((1,1)116QQQQ()((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))QQQQ()((1,1))((1,1)(2,3))((1117存在问题及解决办法问题和解决方法：深度问题对搜索深度加以限制死循环问题状态重复:A→B，B→C,C→A记录从初始状态到当前状态的路径存在问题及解决办法问题和解决方法：118TOPIC2GRAPHSEARCH图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。

N5N1N0N2

N3

N4TOPIC2GRAPHSEARCH图搜索策略N5N1119一些基本概念图：一个节点的集合。节点由弧连接起来。

有向图：弧是一个节点指向另一个节点的图，称为有向图。

后继/父亲：如果有一条弧从ni指向nj，则nj称为ni的后继，ni称为nj的父辈（父亲）；

一些基本概念图：一个节点的集合。节点由弧连接起来。120一些基本概念(续1)路径：如果存在一个节点序列（ni0，ni1，……，nik），nij是nij-1是的后继，j=1，……，k，则称这个序列是从节点ni0到节点nik的一条路径，长度为k。祖先/后裔：如果存在一条从ni到nj的路径，则称nj是ni的后裔，ni称为nj的祖先。树：每个节点最多只有一个父辈。没有父辈的节点称为根节点。没有后继的节点称为叶节点。

一些基本概念(续1)路径：如果存在一个节点序列（ni0，ni121一些基本概念(续2)节点深度： 根节点深度=0 其它节点深度=父节点深度+10123一些基本概念(续2)节点深度：0123122一些基本概念（续3）扩展一个节点生成出该节点的所有后继节点。弧的费用有一条弧连接ni和nj两个节点,用C(ni,nj)表示使用规则从ni到nj的费用(耗散值)。玉泉路---天安门路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。一些基本概念（续3）扩展一个节点123GRAPHSEARCH的思路OPEN表已经生成但未扩展节点CLOSED表已扩展节点扩展节点i生成节点j指针

调整指针GRAPHSEARCH的思路OPEN表124图搜索（GraphSearch）的一般过程

1、建立一个只有起始节点S的搜索图G，把S放入一个叫open的未扩展节点表；2、

建立已扩展节点表closed，初始为空；3、

LOOP；若open为空，则失败退出；4、

选open表中的第一个节点，设为n，移入closed表；5、若n为目标节点，则成功退出，该问题的解即是G中沿S指向n的路径；6、若不是目标节点，则扩展n，生成不是n的祖先的那些后继节点的集合m，把m的成员作为n的后继加入G中；7、对未曾在G中出现过的m成员，设一通向n的指针，把它们加入open表。对已在closed或open表上的m成员，确定是否要更改到n的指针方向，对已在closed上的m成员，确定是否要更改G中通向每个后裔节点的指针方向。8、按某一方式（深度优先、宽度优先、A*算法）重排open表9、GOLOOP图搜索（GraphSearch）的一般过程1、建立一个只125例子SOPENCLOSE{S}{}123{}{S}{1,2,3}{S}{2,1,3}{S}45{1,3}{S,2}{1,3,4,5}{S,2}{3,1,4,5}{S,2}{1,4,5}{S,2,3}6{1,4,5,6}{S,2,3}例子SOPENCLOSE{S}{}123{}{S}126例：右图中黑节点表示已扩展，白节点表示未扩展，问题：先扩展6号节点生成m1={4，7}，然后扩展节点1，生成m2={2}，按算法第七步重新修改原图。612453难点！！！算法中第七步7例：右图中黑节点表示已扩展，白节点表示未扩展，问题：先扩展6127扩展节点6生成m1={4，7}的调整61245371235467×扩展节点6生成m1={4，7}的调整612453712354128再扩展节点1生成m2={2}的调整12354671235467××再扩展节点1生成m2={2}的调整1235467123546129最终结果61245371235467最终结果61245371235467130图搜索与回溯算法的区别

扩展节点:回溯算法:生成一个儿子节点.

图搜索:扩展节点,生成所有儿子节点.

候选节点:回溯算法:一个.

图搜索:多个.

回溯:回溯算法:返回父亲节点.

图搜索:不一定返回父亲节点.图搜索与回溯算法的区别扩展节点:131TOPIC3无信息搜索如果在GRAPHSEARCH中，对节点的排序不使用与问题相关的信息，则称为无信息图搜索（盲目搜索）宽度优先和深度优先TOPIC3无信息搜索如果在GRAPHSEARCH中，对节1321、breadth-firstsearch宽度优先搜索：如果搜索是以接近起始节点的程度依次扩展节点的。

搜索逐层进行；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。1、breadth-firstsearch宽度优先搜索：如133(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节13412345678910111213141516171819★21222324★26272829303112345678910111213141516171819★234567891011121314151617181912345678910123456789搜索演示★已扩展节点

正在扩展节点扩展的子节点

未扩展节点目标12345678910111213141516171819★135宽度优先法应用示例宽度优先法求九宫重排问题2318476512384765宽度优先法应用示例宽度优先法求九宫重排问题213623184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标823418765423232832137宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。一定能找到解找到的解一定是最佳解(在每个路径消耗是同样的意义上)搜索的空间大、慢。

分析宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的138深度优先搜索：首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。特点：扩展最深的节点,使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。算法：与宽度优先相似，不同在于：(5)把n的所有后继节点放到OPEN表的前端2、depth-firstsearch深度优先搜索：首先扩展最新产生的(即最深的)节点。深度相等的1393456789101112131415161718192021★2324★26272829303112活结点表1121124224844816881616817881717884944918991818919919194425225105510209991010202010211010212110105115511★演示345678910111213141516171819202140例九宫重排问题83647■5初始状态1238■4765目标状态应用示例例九宫重排问题83初始状态12141231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abd12384765目标23232832142分析①不一定能找到解。②解不一定是最佳解。分析①不一定能找到解。1433、其他方法含有深度界限的深度优先搜索算法：基于代价树的搜索算法：3、其他方法含有深度界限的深度优先搜索算法：144TOPIC4heuristicsearch盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发式方法的本质是部分地放弃算法"一般化,通用化"的概念,把所要解的问题的具体领域的知识加进算法中去,以提高算法的效率。

TOPIC4heuristicsearch盲目搜索效率低145启发式搜索：就是利用与问题有关的启发信息进行搜索启发信息：与具体问题有关的特性信息启发信息的强度强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解难点：获取；强度的确定；启发式搜索：就是利用与问题有关的启发信息进行搜索146启发信息的用途a、用于决定要扩展的下一节点（避免盲目扩展）b、在扩展过程中，用于决定生成哪一个或哪几个后继（以免太多无用节点）C、用于决定被抛弃or被修剪的节点（博羿中常用，其它不常见）。。。启发信息的用途a、用于决定要扩展的下一节点（避免盲目扩展）147基本思想启发式搜索过程中,要对OPEN表进行排序,这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度,我们总是希望能找到最有希望通向目标节点的待扩展节点优先扩展。希望的量度就是通过估价函数f（n）来描述的基本思想启发式搜索过程中,要对OPEN表进行排序,这就需148估价函数：定义为从初始节点经过n节点到达目的节点的路径的最小代价的估计值，XWZg(X)h(X)估价函数的形式为f(n)=g(n)+h(n)g（n）—是到目前为止,从s到n的最小路径

（实际值）h（n）—n节点到目标节点最佳路径的估计值，体现了启发信息通常f（n）由经验和直觉得到的，有很多种取法，关键在于h（n）。估价函数：定义为从初始节点经过n节点到达目的节点的路径的最小149e．g．八数码难题的估价函数 f（n）=g（n）+h（n） d（n）：节点n的深度 w（n）：不在位的数字个数 p（n）：不在位的数字离目标的距离之和例：右图（a）中2、8、1、6不在位，w（n）=4，p（n）=1+2+1+1=5；（b）6、8、2、1不在位，w（n）=4，p（n）=3+2+2+2=92831647568321475abc81263754e．g．八数码难题的估价函数28368150s（n）：沿着周围那些非中心方格上依顺时针方向检查n格局中每一将牌，如果其后紧跟的将牌正好是目标格局中该将牌的后续者，则该将牌得0分，否则得2分；在中中方格上有将牌得1分，无得0分；将所有将牌得分之和即为s（n）。图（c）中s（a）=6。2831647568321475abc81263754s（n）：沿着周围那些非中心方格上依顺时针方向检查n格局中每151例子:eight-puzzle评价函数f(n)=d(n)+W(n)d(n):节点n的深度;W(n):与目标相比,错位的数字数目，即不在位的数字个数;1238476528316475初始状态目标状态例子:eight-puzzle评价函数12384765281522831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)目标1234562832832832153由前例看出,与深度优先搜索和宽度优先搜索相比较,启发式搜索大大减少了搜索范围,大大减少了扩展的节点,大大减少了生成的节点,从而达到降低问题复杂度,提高算法的效率的目的。由前例看出,与深度优先搜索和宽度优先搜索相比较,启发式搜154估价函数的进一步说明nSg*(n)h*(n)gf*(n)=g*(n)+h*(n)：从s经过n到g的最短路径g*(n)：从s到n的最短路径h*(n)：从n到g的最短路径f（n）=g（n）+h（n）：从s经过n到g的最短路径的估计值g(n)、h(n)分别是g*(n)、h*(n)的估计值估价函数的进一步说明nSg*(n)h*(n)gf*(n)=155g(n)一般取实际走过的路径的费用和.g(n)g*(n)随着算法的执行，由于指针的变动，g(n)会下降.

h0没有启发式信息;g(n)156启发式搜索算法A算法A*算法启发式搜索算