人工智能搜索问题课件

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

从前有座山……18递归的思想从前有座山……从前有座山……递归的思想（续）当前状态目标状态g19递归的思想（续）当前状态目标状态g19一个递归的例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}NULLpLIST12320一个递归的例子intListLenght(LIST*pL回溯搜索算法 BACKTRACK（DATA）

DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。21回溯搜索算法 BACKTRACK（DATA）21回溯搜索算法递归过程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);4, LOOP:IFNULL(RULES)RETURNFAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R,DATA);8, PATH:=BACKTRACK(RDATA);9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);22回溯搜索算法递归过程BACKTRACK(DATA)22存在问题及解决办法解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态问题：深度问题死循环问题23存在问题及解决办法解决办法：当前状态问题：23回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：从初始到当前的状态表（逆向） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。24回溯搜索算法1BACKTRACK1（DATALIST）24回溯搜索算法11, DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);25回溯搜索算法11, DATA:=FIRST(DATALIS回溯搜索算法1（续）9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);26回溯搜索算法1（续）9, RULES:=TAIL(RULE一些深入的问题失败原因分析、多步回溯QQ27一些深入的问题失败原因分析、多步回溯QQ27一些深入问题（续）回溯搜索中知识的利用 基本思想(以皇后问题为例)： 尽可能选取划去对角线上位置数最少的。QQQQ322328一些深入问题（续）回溯搜索中知识的利用QQQQ31.2图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。

291.2图搜索策略问题的引出29一些基本概念节点深度： 根节点深度=0 其它节点深度=父节点深度+1012330一些基本概念节点深度：012330一些基本概念（续1）路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。31一些基本概念（续1）路径31一些基本概念（续1）扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。32一些基本概念（续1）扩展一个节点32一般的图搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);33一般的图搜索算法1,G=G0(G0=s),OPEN:=一般的图搜索算法（续）7,标记和修改指针： ADD(mj,OPEN),并标记mj到n的指针； 计算是否要修改mk、ml到n的指针； 计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；34一般的图搜索算法（续）7,标记和修改指针：34节点类型说明…...…...…...…...…...mjmkml35节点类型说明…...…...…...…...…...mjmk修改指针举例123456s36修改指针举例123456s36修改指针举例（续1）123456s37修改指针举例（续1）123456s37123456修改指针举例（续2）s38123456修改指针举例（续2）s38123456修改指针举例（续3）s39123456修改指针举例（续3）s391.3无信息图搜索过程深度优先搜索宽度优先搜索401.3无信息图搜索过程深度优先搜索40深度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目标在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GOLOOP;41深度优先搜索1,G:=G0(G0=s),OPEN:=(s231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标4223232832深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法43深度优先搜索的性质一般不能保证找到最优解43宽度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G:=ADD(mi,G);7,IF目标在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GOLOOP;44宽度优先搜索1,G:=G0(G0=s),OPEN:=(s23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标82341876544523232832宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法46宽度优先搜索的性质当问题有解时，一定能找到解46渐进式深度优先搜索方法目的解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。思想 首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所以分支为止。47渐进式深度优先搜索方法目的471.4启发式图搜索利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解481.4启发式图搜索利用知识来引导搜索，达到减少搜索范围，降希望：引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。49希望：49基本思想定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。50基本思想定义一个评价函数f，对当前的搜索状态进行评估，找出一1，启发式搜索算法A（A算法）评价函数的格式： f(n)=g(n)+h(n) f(n)：评价函数 h(n)：启发函数511，启发式搜索算法A（A算法）评价函数的格式：51符号的意义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)的估计值52符号的意义g*(n)：从s到n的最短路径的耗散值52A算法1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},

计算f(n,mi):=g(n,mi)+h(mi);

53A算法1,OPEN:=(s),f(s):=g(s)+h(A算法（续） ADD(mj,OPEN),标记mj到n的指针； IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),

标记mk到n的指针； IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml), 标记ml到n的指针, ADD(ml,OPEN);7,OPEN中的节点按f值从小到大排序；8,GOLOOP；54A算法（续） ADD(mj,OPEN),标记mj到n的指…...…...…...…...…...mjmkmlnab55…...…...…...…...…...mjmkmlnab5Closed表Open表56Closed表Open表56一个A算法的例子定义评价函数： f(n)=g(n)+h(n) g(n)为从初始节点到当前节点的耗散值 h(n)为当前节点“不在位”的将牌数

283164751238476557一个A算法的例子定义评价函数：2831h计算举例 h(n)=42

831

64751234576

858h计算举例 h(n)=428312831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)目标1234565928328328322，最佳图搜索算法A*（A*算法）在A算法中，如果满足条件： h(n)≤h*(n) 则A算法称为A*算法。602，最佳图搜索算法A*（A*算法）在A算法中，如果满足条件：A*条件举例8数码问题h1(n)=“不在位”的将牌数h2(n)=将牌“不在位”的距离和2

831

64751234576

8将牌1：1将牌2：1将牌6：1将牌8：261A*条件举例8数码问题28312A*算法的性质A*算法的假设

设ni、nj是任意两个节点，有：C(ni,nj)>其中为大于0的常数几个等式f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始节点，t是目标节点，n是s到t的最佳路径上的节点。62A*算法的性质A*算法的假设几个等式62A*算法的性质（续1）定理1.1： 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。63A*算法的性质（续1）定理1.1：63A*算法的性质（续2）引理1.1： 对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)>f*(s)。64A*算法的性质（续2）引理1.1：64A*算法的性质（续3）引理1.2： A*结束前，OPEN表中必存在f(n)≤f*(s)。存在一个节点n，n在最佳路径上。f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)65A*算法的性质（续3）引理1.2：存在一个节点n，n在65A*算法的性质（续3）定理1.2： 对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。引理1.1：A*如果不结束，则OPEN中所有的n有f(n)>f*(s)引理1.2：在A*结束前，必存在节点n，使得f(n)≤f*(s)所以，如果A*不结束，将导致矛盾。66A*算法的性质（续3）定理1.2：引理1.1：A*如果不结束A*算法的性质（续4）推论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，均被扩展。得证。67A*算法的性质（续4）推论1.1：由定理1.2，知A*A*算法的性质（续5）定理1.3(可采纳性定理)： 若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。68A*算法的性质（续5）定理1.3(可采纳性定理)：68可采纳性的证明由定理1.1、1.2知A*一定找到一条路径结束设找到的路径s→t不是最佳的（t为目标）则：f(t)=g(t)>f*(s)由引理1.2知结束前OPEN中存在f(n)≤f*(s)的节点n，所以f(n)≤f*(s)<f(t)因此A*应选择n扩展，而不是t。与假设A*选择t结束矛盾。得证。注意：A*的结束条件69可采纳性的证明由定理1.1、1.2知A*一定找到一条路径结束A*算法的性质（续6）推论1.2： A*选作扩展的任一节点n，有f(n)≤f*(s)。由引理2.2知在A*结束前，OPEN中存在节点n’，f(n’)≤f*(s)设此时A*选择n扩展。如果n＝n’，则f(n)≤f*(s)，得证。如果n≠n’，由于A*选择n扩展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得证。70A*算法的性质（续6）推论1.2：由引理2.2知在A*结束前A*算法的性质（续7）定理1.4：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n)>h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。简写：如果h2(n)>h1(n)(目标节点除外)，则A1扩展的节点数≥A2扩展的节点数71A*算法的性质（续7）定理1.4：设对同一个问题定义了两个AA*算法的性质（续7）注意：

在定理1.4中，评价指标是“扩展的节点数”，也就是说，同一个节点无论被扩展多少次，都只计算一次。72A*算法的性质（续7）注意：72定理1.4的证明使用数学归纳法，对节点的深度进行归纳（1）当d(n)＝0时，即只有一个节点，显然定理成立。（2）设d(n)≤k时定理成立。（归纳假设）（3）当d(n)=k+1时，用反证法。设存在一个深度为k＋1的节点n，被A2扩展，但没有被A1扩展。而由假设，A1扩展了n的父节点，即n已经被生成了。因此当A1结束时，n将被保留在OPEN中。73定理1.4的证明使用数学归纳法，对节点的深度进行归纳73定理1.4的证明（续1）所以有：f1(n)≥f*(s)即：g1(n)+h1(n)≥f*(s)所以：h1(n)≥f*(s)-g1(n)另一方面，由于A2扩展了n，有f2(n)≤f*(s)即：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)，与定理条件矛盾。故定理得证。74定理1.4的证明（续1）所以有：f1(n)≥f*(s)对h的评价方法平均分叉树 设共扩展了d层节点，共搜索了N个节点，则:

其中，b*称为平均分叉树。b*越小，说明h效果越好。实验表明，b*是一个比较稳定的常数，同一问题基本不随问题规模变化。75对h的评价方法平均分叉树75对h的评价举例例：8数码问题，随机产生若干初始状态。使用h1： d=14,N=539, b*=1.44;d=20,N=7276， b*=1.47；使用h2： d=14,N=113, b*=1.23; d=20,N=676, b*=1.2776对h的评价举例例：8数码问题，随机产生若干初始状态。76A*的复杂性一般来说，A*的算法复杂性是指数型的，可以证明，当且仅当以下条件成立时： abs(h(n)-h*(n))≤O(log(h*(n))) A*的算法复杂性才是非指数型的，但是通常情况下，h与h*的差别至少是和离目标的距离成正比的。77A*的复杂性一般来说，A*的算法复杂性是指数型的，可以证明，3，A*算法的改进问题的提出： 因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。783，A*算法的改进问题的提出：78s(10)A(1)B(5)C(8)G目标631118一个例子：OPEN表CLOSED表s(10)s(10)A(7)B(8)C(9)A(7)s(10)B(8)C(9)G(14)A(5)C(9)G(14)C(9)G(12)B(7)G(12)A(4)G(12)G(11)B(8)s(10)A(5)B(8)s(10)C(9)A(5)s(10)B(7)C(9)s(10)A(4)B(7)C(9)s(10)79s(10)A(1)B(5)C(8)G目标631118一个例出现多次扩展节点的原因在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。s(10)A(1)B(5)C(8)G目标63111880出现多次扩展节点的原因在前面的扩展中，并没有找到从初始节点到解决的途径对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展。81解决的途径对h加以限制81改进的条件可采纳性不变不多扩展节点不增加算法的复杂性82改进的条件可采纳性不变82对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)83对h加以限制定义：一个启发函数h，如果对所有节点ni和nj，h单调的性质定理1.5： 若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。 即：当A*选n扩展时，有g(n)=g*(n)。84h单调的性质定理1.5：84定理1.5的证明设n是A*扩展的任一节点。当n＝s时，定理显然成立。下面考察n≠s的情况。设P＝(n0=s,n1,n2,…,nk=n)是s到n的最佳路径P中一定有节点在CLOSED中，设P中最后一个出现在CLOSED中的节点为nj，则nj+1在OPEN中。85定理1.5的证明设n是A*扩展的任一节点。当n＝s时，定理显定理1.5的证明（续1）由单调限制条件，对P中任意节点ni有：h(ni)≤C(ni,ni+1)+h(ni+1)

g*(ni)+h(ni)≤g*(ni)+C(ni,ni+1)+h(ni+1)由于ni、ni+1在最佳路径上，所以：g*(ni+1)=g*(ni)+C(ni,ni+1)带入上式有：g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)从i=j到i=k-1应用上不等式，有：g*(nj+1)+h(nj+1)≤g*(nk)+h(nk)即：f(nj+1)≤g*(n)+h(n)

注意：(nj在CLOSED中，nj+1在OPEN中)86定理1.5的证明（续1）由单调限制条件，对P中任意节点ni有定理1.5的证明（续2）重写上式：f(nj+1)≤g*(n)+h(n)另一方面，A*选n扩展，必有：

f(n)=g(n)+h(n)≤f(nj+1)比较两式，有：g(n)≤g*(n)但已知g*(n)是最佳路径的耗散值，所以只有：g(n)=g*(n)。得证。87定理1.5的证明（续2）重写上式：f(nj+1)≤g*(h单调的性质（续）定理1.6： 若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。即f(ni)≤f(nj)。

88h单调的性质（续）定理1.6：88定理1.6的证明由单调限制条件，有：h(ni)–h(nj)≤C(ni,nj)=f(ni)-g(ni)=f(nj)-g(nj)

f(ni)-g(ni)-f(nj)+g(nj)≤C(ni,nj)=g(ni)+C(ni,nj)

f(ni)-g(ni)-f(nj)+g(ni)+C(ni,nj)≤C(ni,nj)

f(ni)-f(nj)

≤0，得证。89定理1.6的证明由单调限制条件，有：=f(ni)-g(nih单调的例子8数码问题：h为“不在位”的将牌数1 h(ni)-h(nj)=0 (nj为ni的后继节点)-1 h(t)=0 c(ni,nj)=1满足单调的条件。 90h单调的例子8数码问题：90对算法加以改进一些结论：OPEN表上任以具有f(n)<f*(s)的节点定会被扩展。A*选作扩展的任一节点，定有f(n)≤f*(s)。91对算法加以改进一些结论：91改进的出发点OPEN=(…………)f*(s)f值小于f*(s)的节点f值大于等于f*(s)的节点fm：到目前为止已扩展节点的最大f值，用fm代替f*(s)92改进的出发点OPEN=(…………)f*(修正过程A1,OPEN:=(s),f(s)=g(s)+h(s),fm:=0;2,LOOP:IFOPEN=()THENEXIT(FAIL);3,NEST:={ni|f(ni)<fm} IFNEST≠()THENn:=NEST中g最小的节点 ELSEn:=FIRST(OPEN), fm:=f(n);4,…,8:同过程A。93修正过程A1,OPEN:=(s),f(s)=g(s)+hs(10)A(1)B(5)C(8)G目标631118前面的例子：OPEN表CLOSED表fms(0+10)s(0+10)10A(6+1)B(3+5)C(1+8)s(0+10)C(1+8)10A(6+1)B(2+5)s(0+10)C(1+8)B(2+5)10A(3+1)s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0)94s(10)A(1)B(5)C(8)G目标631118前面的h的单调化方法如果令： f(n)=max(f(n的父节点),g(n)+h(n)) 则容易证明，这样处理后的h是单调的。95h的单调化方法如果令：95IDA*算法(IterativeDeepeningA*)基本思想：回溯与A*的结合算法简介（非严格地） 1，设初始值f0； 2，集合S＝NULL； 3，用回溯法求解问题，如果节点n的f值大于f0，则将该节点放入集合S中，并回溯； 4，如果在3中找到了解，则结束； 5，如果3以失败结束，则f0＝S中节点的最小f值； 6，返回到2。96IDA*算法(IterativeDeepeningA*)知识的灵活应用例：如何转动，使得每个扇区数字和为12。13551441332523123122552342543433分析：阴影部分数字和：48直径部分数字和：24转45°改变阴影部分转90°改变直径部分但不改变阴影部分转180°改变扇区部分但不改变阴影部分也不改变直径部分97知识的灵活应用例：如何转动，使得每个扇区数字和为12。1354，其他的搜索算法爬山法（局部搜索算法）984，其他的搜索算法爬山法（局部搜索算法）98其他的搜索算法（续1）随机搜索算法动态规划算法 如果对于任何n，当h(n)=0时，A*算法就成为了动态规划算法。99其他的搜索算法（续1）随机搜索算法99动态规划st第一阶段第二阶段第三阶段第四阶段第五阶段100动态规划st第一阶段第二阶段第三阶段第四阶段第五阶段1005，搜索算法实用举例汉字识别后处理一个例子我钱线载哦栽哉裁劣绥 优仍们仿伦奶砧犯扔妨 要耍密穷安壁驻努窑垂 扳报叔嵌奴振技寂叙蔽 奋夯杏蚕香脊秀吞吝番 精猜指洁括治捐活冶桔 种神衬祥科钟拌样拎补

1015，搜索算法实用举例汉字识别后处理101汉字识别后处理二元语法时：为常量用识别信度代替问题变为求最大102汉字识别后处理二元语法时：为常量用识别信度代替问题变为求最大第一章搜索问题内容： 状态空间的搜索问题。搜索方式：盲目搜索启发式搜索关键问题： 如何利用知识，尽可能有效地找到问题的解（最佳解）。103第一章搜索问题内容：1搜索问题（续1）S0Sg104搜索问题（续1）S0Sg2搜索问题（续2）讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。105搜索问题（续2）讨论的问题：31.1回溯策略例：皇后问题1061.1回溯策略例：皇后问题4()107()5()Q((1,1))108()Q((1,1))6()QQ((1,1))((1,1)(2,3))109()QQ((1,1))((1,1)(2,3))7()Q((1,1))((1,1)(2,3))110()Q((1,1))((1,1)(2,3))8()QQ((1,1))((1,1)(2,3))((1,1)(2,4))111()QQ((1,1))((1,1)(2,3))((1,1()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))112()QQ((1,1))((1,1)(2,3))((1,1()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))113()QQ((1,1))((1,1)(2,3))((1,1()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))114()Q((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))115()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))116()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))117()((1,1))((1,1)(2,3))((1,1)()((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))118()((1,1))((1,1)(2,3))((1,1)()((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))119()((1,1))((1,1)(2,3))((1,1)递归的思想从前有座山……从前有座山……

从前有座山……120递归的思想从前有座山……从前有座山……递归的思想（续）当前状态目标状态g121递归的思想（续）当前状态目标状态g19一个递归的例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}NULLpLIST123122一个递归的例子intListLenght(LIST*pL回溯搜索算法 BACKTRACK（DATA）

DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。123回溯搜索算法 BACKTRACK（DATA）21回溯搜索算法递归过程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);4, LOOP:IFNULL(RULES)RETURNFAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R,DATA);8, PATH:=BACKTRACK(RDATA);9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);124回溯搜索算法递归过程BACKTRACK(DATA)22存在问题及解决办法解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态问题：深度问题死循环问题125存在问题及解决办法解决办法：当前状态问题：23回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：从初始到当前的状态表（逆向） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。126回溯搜索算法1BACKTRACK1（DATALIST）24回溯搜索算法11, DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);127回溯搜索算法11, DATA:=FIRST(DATALIS回溯搜索算法1（续）9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);128回溯搜索算法1（续）9, RULES:=TAIL(RULE一些深入的问题失败原因分析、多步回溯QQ129一些深入的问题失败原因分析、多步回溯QQ27一些深入问题（续）回溯搜索中知识的利用 基本思想(以皇后问题为例)： 尽可能选取划去对角线上位置数最少的。QQQQ3223130一些深入问题（续）回溯搜索中知识的利用QQQQ31.2图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。

1311.2图搜索策略问题的引出29一些基本概念节点深度： 根节点深度=0 其它节点深度=父节点深度+10123132一些基本概念节点深度：012330一些基本概念（续1）路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。133一些基本概念（续1）路径31一些基本概念（续1）扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。134一些基本概念（续1）扩展一个节点32一般的图搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);135一般的图搜索算法1,G=G0(G0=s),OPEN:=一般的图搜索算法（续）7,标记和修改指针： ADD(mj,OPEN),并标记mj到n的指针； 计算是否要修改mk、ml到n的指针； 计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；136一般的图搜索算法（续）7,标记和修改指针：34节点类型说明…...…...…...…...…...mjmkml137节点类型说明…...…...…...…...…...mjmk修改指针举例123456s138修改指针举例123456s36修改指针举例（续1）123456s139修改指针举例（续1）123456s37123456修改指针举例（续2）s140123456修改指针举例（续2）s38123456修改指针举例（续3）s141123456修改指针举例（续3）s391.3无信息图搜索过程深度优先搜索宽度优先搜索1421.3无信息图搜索过程深度优先搜索40深度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目标在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GOLOOP;143深度优先搜索1,G:=G0(G0=s),OPEN:=(s231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法145深度优先搜索的性质一般不能保证找到最优解43宽度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G:=ADD(mi,G);7,IF目标在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GOLOOP;146宽度优先搜索1,G:=G0(G0=s),OPEN:=(s23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标823418765414723232832宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法148宽度优先搜索的性质当问题有解时，一定能找到解46渐进式深度优先搜索方法目的解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。思想 首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所以分支为止。149渐进式深度优先搜索方法目的471.4启发式图搜索利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解1501.4启发式图搜索利用知识来引导搜索，达到减少搜索范围，降希望：引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。151希望：49基本思想定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。152基本思想定义一个评价函数f，对当前的搜索状态进行评估，找出一1，启发式搜索算法A（A算法）评价函数的格式： f(n)=g(n)+h(n) f(n)：评价函数 h(n)：启发函数1531，启发式搜索算法A（A算法）评价函数的格式：51符号的意义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)的估计值154符号的意义g*(n)：从s到n的最短路径的耗散值52A算法1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},

计算f(n,mi):=g(n,mi)+h(mi);

155A算法1,OPEN:=(s),f(s):=g(s)+h(A算法（续） ADD(mj,OPEN),标记mj到n的指针； IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),

标记mk到n的指针； IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml), 标记ml到n的指针, ADD(ml,OPEN);7,OPEN中的节点按f值从小到大排序；8,GOLOOP；156A算法（续） ADD(mj,OPEN),标记mj到n的指…...…...…...…...…...mjmkmlnab157…...…...…...…...…...mjmkmlnab5Closed表Open表158Closed表Open表56一个A算法的例子定义评价函数： f(n)=g(n)+h(n) g(n)为从初始节点到当前节点的耗散值 h(n)为当前节点“不在位”的将牌数

2831647512384765159一个A算法的例子定义评价函数：2831h计算举例 h(n)=42

831

64751234576

8160h计算举例 h(n)=428312831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)目标12345616128328328322，最佳图搜索算法A*（A*算法）在A算法中，如果满足条件： h(n)≤h*(n) 则A算法称为A*算法。1622，最佳图搜索算法A*（A*算法）在A算法中，如果满足条件：A*条件举例8数码问题h1(n)=“不在位”的将牌数h2(n)=将牌“不在位”的距离和2

831

64751234576

8将牌1：1将牌2：1将牌6：1将牌8：2163A*条件举例8数码问题28312A*算法的性质A*算法的假设

设ni、nj是任意两个节点，有：C(ni,nj)>其中为大于0的常数几个等式f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始节点，t是目标节点，n是s到t的最佳路径上的节点。164A*算法的性质A*算法的假设几个等式62A*算法的性质（续1）定理1.1： 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。165A*算法的性质（续1）定理1.1：63A*算法的性质（续2）引理1.1： 对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)>f*(s)。166A*算法的性质（续2）引理1.1：64A*算法的性质（续3）引理1.2： A*结束前，OPEN表中必存在f(n)≤f*(s)。存在一个节点n，n在最佳路径上。f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)167A*算法的性质（续3）引理1.2：存在一个节点n，n在65A*算法的性质（续3）定理1.2： 对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。引理1.1：A*如果不结束，则OPEN中所有的n有f(n)>f*(s)引理1.2：在A*结束前，必存在节点n，使得f(n)≤f*(s)所以，如果A*不结束，将导致矛盾。168A*算法的性质（续3）定理1.2：引理1.1：A*如果不结束A*算法的性质（续4）推论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，均被扩展。得证。169A*算法的性质（续4）推论1.1：由定理1.2，知A*A*算法的性质（续5）定理1.3(可采纳性定理)： 若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。170A*算法的性质（续5）定理1.3(可采纳性定理)：68可采纳性的证明由定理1.1、1.2知A*一定找到一条路径结束设找到的路径s→t不是最佳的（t为目标）则：f(t)=g(t)>f*(s)由引理1.2知结束前OPEN中存在f(n)≤f*(s)的节点n，所以f(n)≤f*(s)<f(t)因此A*应选择n扩展，而不是t。与假设A*选择t结束矛盾。得证。注意：A*的结束条件171可采纳性的证明由定理1.1、1.2知A*一定找到一条路径结束A*算法的性质（续6）推论1.2： A*选作扩展的任一节点n，有f(n)≤f*(s)。由引理2.2知在A*结束前，OPEN中存在节点n’，f(n’)≤f*(s)设此时A*选择n扩展。如果n＝n’，则f(n)≤f*(s)，得证。如果n≠n’，由于A*选择n扩展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得证。172A*算法的性质（续6）推论1.2：由引理2.2知在A*结束前A*算法的性质（续7）定理1.4：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n)>h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。简写：如果h2(n)>h1(n)(目标节点除外)，则A1扩展的节点数≥A2扩展的节点数173A*算法的性质（续7）定理1.4：设对同一个问题定义了两个AA*算法的性质（续7）注意：

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