人工智能导论-第1章

第一章搜索问题内容： 状态空间的搜索问题。搜索方式：盲目搜索启发式搜索关键问题： 如何利用知识，尽可能有效地找到问题的解（最佳解）。1搜索问题（续1）S0Sg2搜索问题（续2）讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。31.1回溯策略例：皇后问题4()5()Q((1,1))6()QQ((1,1))((1,1)(2,3))7()Q((1,1))((1,1)(2,3))8()QQ((1,1))((1,1)(2,3))((1,1)(2,4))9()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))10()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))11()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))12()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))13()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))14()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))15()((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))16()((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))Q((1,2)(2,4)(3,1)(4,3))17回溯搜索算法

OPEN表CLOSED表

OPEN表用于存放刚生成的节点，CLOSED表用于存放将要扩展或者已经扩展的节点。状态节点父节点编号状态节点父节点18一般回溯搜索算法1. 把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G;2. 检查OPEN表是否为空，若为空则问题无解，退出;3. 把OPEN表的第一个节点取出放入CLOSED表，并记该节点为节点n;4.考察节点n是否为目标节点，若是，则求得了问题的解，退出;5. 扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记作集合M，并把这些子节点作为节点n的子节点加入G中;6. 针对M中子节点的不同情况，分别进行如下处理：19一般回溯搜索算法（续）6.1对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表。6.2对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针。6.3对于那些先前已经在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。7.按某种搜索策略对OPEN表中的节点进行排序。8.转第2步。20存在问题及解决办法解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态问题：深度问题死循环问题21一些深入的问题失败原因分析、多步回溯QQ22一些深入问题（续）回溯搜索中知识的利用 基本思想(以皇后问题为例)： 尽可能选取划去对角线上位置数最少的。QQQQ3223231.2图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。

24一些基本概念节点深度： 根节点深度=0

其它节点深度=父节点深度+1012325一些基本概念（续1）路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。26一些基本概念（续1）扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。27修改指针举例123456s28修改指针举例（续1）123456s29123456修改指针举例（续2）s30123456修改指针举例（续3）s311.3无信息图搜索过程深度优先搜索宽度优先搜索32深度优先搜索1,把初始节点S0放入OPEN表;2,如果OPEN表为空，则问题无解，退出;3,把OPEN表的第一个节点（记为节点n）取出放入CLOSED表;4,考察节点n是否为目标节点，若是，则求得了问题的解，退出;5,若节点n不可扩展，则转第2步;6,扩展节点n，将其子节点放入到OPEN表的首部，并为其配置指向父节点的指针，然后转第2步;33有界深度优先搜索1,把初始节点S0放入OPEN表中，置S0的深度d(S0)=0;2,如果OPEN表为空，则问题无解，退出;3,把OPEN表的第一个节点（记为节点n）取出放入CLOSED表;4,考察节点n是否为目标节点，若是，则求得了问题的解，退出;5,如果节点n的深度d(节点n)=dm，则转第2步；6,若节点n不可扩展，则转第2步;7,扩展节点n，将其子节点放入到OPEN表的首部，并为其配置指向父节点的指针，然后转第2步;34代价树（图）在上面的讨论中，都没有考虑搜索的代价问题，当时假设图中各边的代价都相同，且都为一个单位量。边上标有代价（或费用）的树（图）称为代价树（图）。在代价树中，若用g(x)表示从初始节点S0到节点x的代价，用c(x1,x2)表示从父节点x1到节点x2的代价，则有：g(x2)=g(x1)+c(x1,x2)35代价树的深度优先搜索1,把初始节点S0放入OPEN表;2,如果OPEN表为空，则问题无解，退出;3,把OPEN表的第一个节点（记为节点n）取出放入CLOSED表;4,考察节点n是否为目标节点，若是，则求得了问题的解，退出;5,若节点n不可扩展，则转第2步;6,扩展节点n，将其子节点按边代价从小到大的顺序放到OPEN表的首部，并为各子节点配置指向父节点的指针，然后转第2步;36重排九宫问题2831476

51238476

53728314765231847652831476528314765283164750542283164752831647528163754

283167542831675428163754

31深度优先搜索38283147652318476528314765283147652831647502318321476528371465231847652318476528314576281437652831647528316475832147652837146512384765234187652814376528314576

283641752831675412384765283167542816375483264175283641752831457628315746

2814376524813765234187652341857612378465547698101211141316151817201922212325242726有界深度优先搜索39深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法40渐进式深度优先搜索方法目的解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。思想 首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所以分支为止。41宽度优先搜索1,把初始节点S0放入OPEN表;2,如果OPEN表为空，则问题无解，退出;3,把OPEN表的第一个节点（记为节点n）取出放入CLOSED表中;4,考察节点n是否为目标节点，若是，则求得了问题的解，退出;5,若节点n不可扩展，则转第2步;6,扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点都配置父节点的指针，然后转第2步。42代价树的宽度优先搜索1,把初始节点S0放入OPEN表，令g(S0)=0;2,如果OPEN表为空，则问题无解，退出;3,把OPEN表的第一个节点（记为节点n）取出放入CLOSED表中;4,考察节点n是否为目标节点，若是，则求得了问题的解，退出;5,若节点n不可扩展，则转第2步;6,扩展节点n，将其子节点放入OPEN表中，并为其配置父节点的指针；计算各子节点的代价，并按各节点的代价对OPEN表中的全部节点进行排序（按从小到大的顺序），然后转第2步。43目标283147652318476528314765283147652831647502148321476528371465231847652318476528314576281437652831647528316475832147652837146512384765234187652814376528314576

2836417528316754813247658321476528371465283746151238476535876910111220191817161514132322212424广度(宽度)优先搜索44宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法451.4启发式图搜索利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解46希望：引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。47基本思想定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。481，启发式搜索算法A（A算法）评价函数的格式：

f(n)=g(n)+h(n) f(n)：评价函数

h(n)：启发函数49符号的意义g*(n)：从s到n的最短路径的耗散值h*(n)：从n到g的最短路径的耗散值f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值50局部择优搜索1,把初始节点S0放入OPEN表，计算f(S0);2,如果OPEN表为空，则问题无解，退出;3,把OPEN表的第一个节点（记为节点n）取出放入CLOSED表;4,考察节点n是否为目标节点，若是，则求得了问题的解，退出;5,若节点n不可扩展，则转第2步;6,扩展节点n，用估价函数f(x)计算每个子节点的估价值，并按估价值从小到大的顺序依次放到OPEN表的首部，为每个子节点配置指向父节点的指针，然后转第2步。51局部择优搜索与深度优先搜索的关系深度优先搜索、代价树的深度优先搜索以及局部择优搜索都是以子节点作为考察范围的。若令f(x)＝g(x)，则局部择优搜索就成为代价树的深度优先搜索；若令f(x)＝d(x)(这里d(x)表示节点x的深度），则局部择优搜索就成为深度优先搜索。所以深度优先搜索和代价树的深度优先搜索可看作局部择优搜索的两个特例。52全局择优搜索1,把初始节点S0放入OPEN表，计算f(S0);2,如果OPEN表为空，则问题无解，退出;3,把OPEN表的第一个节点（记为节点n）取出放入CLOSED表;4,考察节点n是否为目标节点，若是，则求得了问题的解，退出;5,若节点n不可扩展，则转第2步;6,扩展节点n，用估价函数f(x)计算每个子节点的估价值，并为每个子节点配置指向父节点的指针，把这些子节点都送入OPEN表中，然后对OPEN表中的全部节点按估价值从小到大的顺序进行排序7,转第2步。53全局择优搜索与广度优先搜索的关系在全局择优搜索中，若令f(x)＝g(x)，则全局择优搜索就成为代价树的广度优先搜索；若令f(x)＝d(x)(这里d(x)表示节点x的深度），则全局择优搜索就成为广度优先搜索。所以广度优先搜索和代价树的广度优先搜索可看作全局择优搜索的两个特例。54一个A算法的例子定义评价函数：

f(n)=g(n)+h(n) g(n)为从初始节点到当前节点的耗散值

h(n)为当前节点“不在位”的将牌数

283164751238476555h计算举例 h(n)=42

831

64751234576

8562831647528314765283164752831647523184765283147652831476528371465

83214765

2318476523184765123847651238476512378465s(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)目标123456572最佳图搜索算法A*（A*算法）如果使一般搜索过程满足如下条件，则它成为A*算法：1.把OPEN表中的节点按估价函数：f(x)=g(x)+h(x)

的值从小到大进行排序（一般搜索过程的第7步）2.g(x)是对g*(x)的估计，g(x)>0.3.h(x)是对h*(x)的下界，即对所有的x均有：

h(x)≤h*(x)

其中g*(x)是从初始节点S0到节点x的最小代价；h*(x)是从节点x到目标节点的最小代价，若有多个目标节点，则为其中的最小值。58A*条件举例8数码问题h1(n)=“不在位”的将牌数h2(n)=将牌“不在位”的距离和2

831

64751234576

8将牌1：1将牌2：1将牌6：1将牌8：259A*算法的性质A*算法的假设设ni、nj是任意两个节点，有：C(ni,nj)>，其中为大于0的常数。几个等式1.f*(s)=f*(t)=h*(s)=g*(t)=f*(n)

其中s是初始节点，t是目标节点，n是s到t的最佳路径上的节点。2.对于最佳路径（s,n1,n2,…,

ni,…,t）中的任一节点ni，均有 f(ni)=f*(s)。3.对于一条到达t的最佳路径（s,n1,n2,…,

ni,ni+1,…,t），则针对任一节点ni，路径（s,n1,n2,…,ni）也是从s到达ni的最佳路径，即：g*(ni)=g(ni).

证明：对任意节点ni，若（s,n1,n2,…,

ni）不是到达ni的最佳路径，即存在路径（s,n1,n2,…,

ni），使得从s到达ni更近，那么显然路径（s,n1,n2,…,ni,ni+1,…,t）也是从s到达t的最佳路径，这与（s,n1,n2,…,

ni,ni+1,…,t）是从s到达t的最佳路径矛盾。60A*算法的性质（续1）定理1.1： 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。61A*算法的性质（续2）引理1.1

： 对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)>f*(s)。证明：假设A*不终止。设e是图中各条边的最小代价，d*(xn)是从S0到节点xn的最短路径长度，则显然有：g*(xn)d*(xn)×e，又因为g(xn)g*(xn)，所以有g(xn)d*(xn)×e。因为h(xn)0,f(xn)g(xn)，故得到f(xn)d*(xn)×e。由于A*算法不终止，随着搜索的进行，d*(xn)会无限增大，从而使f(xn)也无限增大。最终使得f(n)>f*(s)。而f*(s)显然应该是一个有限值，矛盾。62A*算法的性质（续3）引理1.2：在A*终止前的每一步，总是有一个节点n，它在OPEN表中，且存在以下属性：n在最佳路径上。A*已经发现了到达n的一条最佳路径。f(n)≤f*(s)。证明：用归纳法。在搜索开始时，S在OPEN表中，它是到达目标的一条最佳路径，A*已经发现了这条路径，而且因为f(S)=h(S)h*(S)=f*(S).定理成立。假设在节点m(m0)

扩展时引理的结论是正确的，现在证明在节点(m+1)扩展时引理是正确的。63A*算法的性质（续4）设n是m个节点扩展后，A*发现的一个最佳路径上的假设节点，它在OPEN上。如果在第（m+1）步，n没有被选择扩展，n的属性和以前相同，因此证明了归纳步骤。如果n被选为扩展点，它的所有后继将被放在OPEN上，他们中至少有一个np，将会在到达目标的最优路径上（因为由于假定一个最优路径通过n，它必须通过它的一个后继）。故A*找到了到达np的一条最佳路径，因为如果有到达np的一条更好路径，那么这条路径也是到达目标的更好路径（这和我们的假设没有比通过n到达目标的路径更好的路径相矛盾）。这样，我们让np称为第m+1步新的n。现在证明f(np)f*(s).

因为对在一条最佳路径上的节点np，A*已经找到了到达np的一条最佳路径，我们有：f(np)=g(np)+h(np)=g*(np)+h(np)≤g*(np)+h*(np)=f*(np)=f*(s)。64A*算法的性质（续5）定理1.2： 对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。证明：由引理1.1，则OPEN中所有的n有f(n)>f*(s)。由引理1.2，在A*结束前OPEN表中必存在节点n，使得f(n)f*(s)。所以如果不结束，将导致矛盾。65A*算法的性质（续6）推论1.1：

OPEN表上任一具有f(n)<f*(s)的节点n，最终都将被A*选作扩展的节点。证明：由定理1.2知，A*一定结束，由A*的结束条件，OPEN表中f(t)最小时才结束。而f(t)f*(t)=f*(s)。所以，f(n)<f*(s)的n，均被扩展。66A*算法的性质（续7）定理1.3(可采纳性定理)： 若存在从初始节点s到目标节点t的路径，则A*必能找到最佳解结束。67可采纳性的证明（续8）证明：由定理1.1，1.2知，A*一定会找到一个目标节点结束。设找到一个目标节点t结束，而s到t不是一条最佳路径，即：f(t)=g(t)>f*(s).

而根据引理1.2知结束前OPEN表上一定存在有节点n，且处在最佳路径上，并有f(n)f*(s)，所以f(n)f*(s)<f(t)。这时算法A*应选n作为当前节点扩展，不可能选t，从而也不会去测试目标节点t，即这与假定A*选t结束矛盾，所以A*只能结束在最佳路径上。68A*算法的性质（续9）推论1.2：

A*选作扩展的任一节点n，有f(n)≤f*(s)。

证明：由引理1.2知，在A*结束前，OPEN中存在节点n，使得f(n)f*(s)。

设此时A*选择n扩展。如果n=n，则f(n)f*(s)，得证。如果nn，由于A*选择n扩展，而不是n，所以有f(n)f(n)f*(s)。得证。69A*算法的性质（续10）定理1.4：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n)>h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。简写：如果h2(n)>h1(n)(目标节点除外)，则A1扩展的节点数≥A2扩展的节点数70A*算法的性质（续11）注意：

在定理1.4中，评价指标是“扩展的节点数”，也就是说，同一个节点无论被扩展多少次，都只计算一次。71定理1.4的证明（续12）使用数学归纳法，对节点的深度进行归纳（1）当d(n)＝0时，即只有一个节点，显然定理成立。（2）设d(n)≤k时定理成立。（归纳假设）（3）当d(n)=k+1时，用反证法。设存在一个深度为k＋1的节点n，被A2扩展，但没有被A1扩展。而由假设，A1扩展了n的父节点，即n已经被生成了。因此当A1结束时，n将被保留在OPEN中。72定理1.4的证明（续1）因为A1没有扩展n，所以有：f1(n)≥f*(s)(推论1.1)

即：g1(n)+h1(n)≥f*(s)所以：h1(n)≥f*(s)-g1(n)由于A2扩展了n，有f2(n)≤f*(s)（推论1.2）即：h2(n)≤f*(s)–g2(n)

(A)另一方面，由于d(n)=k时，A2扩展的节点A1一定扩展，有

g1(n)≤g2(n)(因为A2的路A1均走到了)所以：h1(n)≥f*(s)-g1(n)≥f*(s)–g2(n)(B)比较A、B两式，有h1(n)≥h2(n)，与定理条件矛盾。故定理得证。73对h加以限制定义：一个启发函数h，如果对所有节点ni和nj，其中nj是ni的子节点，满足

h(ni)-h(nj)≤c(ni,nj) h(t)=0

或

h(ni)≤c(ni,nj)+h(nj) h(t)=0

则称h服从一致性条件。h(ni)ninjh(nj)c(ni,nj)74h单调的性质一致性条件的性质：设ni和nj是由A*在搜索树上产生的两个节点，nj是ni的后继。如果满足一致性条件，就有f(nj)f(ni)。证明：因为h(nj)h(ni)-c(ni,nj)，所以h(nj)+g(nj)h(ni)+g(nj)-c(ni,nj)。但是g(nj)=g(ni)+c(ni,nj)（我们可能会担心g(nj)会比这个值小，因为我们可能会顺着其它的比通过ni点代价更低的路径到达nj。但这样一来，在搜索树上nj就不是ni的后继了）。因此，f(nj)f(ni)。因为这个原因，一致性条件（对h）也常称为单调条件（对f）。75定理1.5： 若h(n)是满足一致性条件，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。 即：当A*选n扩展时，有g(n)=g*(n)。76定理1.5的证明证明：假设A*在隐式图G中正在搜索从开始节点n0到目标节点的一条最佳路径，它准备扩展一个打开的节点n。设＝(n0,n1,…,nm,nm+1,…,n=nk)是图G中从n0到n的一条最佳路径的节点序列，nm是被A*扩展的最后一个节点（注意中一定存在这样的节点，至少n0就是在中）。因为nm是上最后一个没打开的节点，因此nm+1在OPEN上是一个扩展候选者