人工智能搜索问题

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

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

DATA：当前状态。 返回值：从当前状态到目标状态路径 （以规则表形式表示） 或FAIL。21人工智能搜索问题第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人工智能搜索问题第22页存在问题及处理方法处理方法：对搜索深度加以限制统计从初始状态到当前状态路径当前状态问题：深度问题死循环问题23人工智能搜索问题第23页回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：从初始到当前状态表（逆向） 返回值：从当前状态到目标状态路径 （以规则表形式表示） 或FAIL。24人工智能搜索问题第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人工智能搜索问题第25页回溯搜索算法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人工智能搜索问题第26页一些深入问题失败原因分析、多步回溯QQ27人工智能搜索问题第27页一些深入问题（续）回溯搜索中知识利用 基本思想(以皇后问题为例)： 尽可能选取划去对角线上位置数最少。QQQQ322328人工智能搜索问题第28页1.2图搜索策略问题引出回溯搜索：只保留从初始状态到当前状态一条路径。图搜索：保留全部已经搜索过路径。

29人工智能搜索问题第29页一些基本概念节点深度： 根节点深度=0 其它节点深度=父节点深度+1012330人工智能搜索问题第30页一些基本概念（续1）路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1含有一个后继节点ni，则该序列称为从n0到nk路径。路径耗散值 一条路径耗散值等于连接这条路径各节点间全部耗散值总和。用C(ni,nj)表示从ni到nj路径耗散值。31人工智能搜索问题第31页一些基本概念（续1）扩展一个节点 生成出该节点全部后继节点，并给出它们之间耗散值。这一过程称为“扩展一个节点”。32人工智能搜索问题第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人工智能搜索问题第33页普通图搜索算法（续）7,标识和修改指针： ADD(mj,OPEN),并标识mj到n指针； 计算是否要修改mk、ml到n指针； 计算是否要修改ml到其后继节点指针；8,对OPEN中节点按某种标准重新排序；9,GOLOOP；34人工智能搜索问题第34页节点类型说明…...…...…...…...…...mjmkml35人工智能搜索问题第35页修改指针举例123456s36人工智能搜索问题第36页修改指针举例（续1）123456s37人工智能搜索问题第37页123456修改指针举例（续2）s38人工智能搜索问题第38页123456修改指针举例（续3）s39人工智能搜索问题第39页1.3无信息图搜索过程深度优先搜索宽度优先搜索40人工智能搜索问题第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人工智能搜索问题第41页231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标42人工智能搜索问题第42页深度优先搜索性质普通不能确保找到最优解当深度限制不合理时，可能找不到解，能够将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法差异：图搜索是一个通用与问题无关方法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人工智能搜索问题第44页23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标823418765445人工智能搜索问题第45页宽度优先搜索性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，含有通用性效率较低属于图搜索方法46人工智能搜索问题第46页渐进式深度优先搜索方法目标处理宽度优先方法空间问题和回溯方法不能找到最优解问题。思想 首先给回溯法一个比较小深度限制，然后逐步增加深度限制，直到找到解或找遍所以分支为止。47人工智能搜索问题第47页1.4启发式图搜索利用知识来引导搜索，到达降低搜索范围，降低问题复杂度目标。启发信息强度强：降低搜索工作量，但可能造成找不到最 优解弱：普通造成工作量加大，极限情况下变为 盲目搜索，但可能能够找到最优解48人工智能搜索问题第48页希望：引入启发知识，在确保找到最正确解情况下，尽可能降低搜索范围，提升搜索效率。49人工智能搜索问题第49页基本思想定义一个评价函数f，对当前搜索状态进行评定，找出一个最有希望节点来扩展。50人工智能搜索问题第50页1，启发式搜索算法A（A算法）评价函数格式： f(n)=g(n)+h(n) f(n)：评价函数 h(n)：启发函数51人工智能搜索问题第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人工智能搜索问题第52页A算法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);

53人工智能搜索问题第53页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；54人工智能搜索问题第54页…...…...…...…...…...mjmkmlnab55人工智能搜索问题第55页Closed表Open表56人工智能搜索问题第56页一个A算法例子定义评价函数： f(n)=g(n)+h(n) g(n)为从初始节点到当前节点耗散值 h(n)为当前节点“不在位”将牌数

283164751238476557人工智能搜索问题第57页h计算举例 h(n)=42

831

64751234576

858人工智能搜索问题第58页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)目标12345659人工智能搜索问题第59页2，最正确图搜索算法A*（A*算法）在A算法中，假如满足条件： h(n)≤h*(n) 则A算法称为A*算法。60人工智能搜索问题第60页A*条件举例8数码问题h1(n)=“不在位”将牌数h2(n)=将牌“不在位”距离和2

831

64751234576

8将牌1：1将牌2：1将牌6：1将牌8：261人工智能搜索问题第61页A*算法性质A*算法假设

设ni、nj是任意两个节点，有：C(ni,nj)>

其中为大于0常数几个等式f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始节点，t是目标节点，n是s到t最正确路径上节点。62人工智能搜索问题第62页A*算法性质（续1）定理1.1： 对有限图，假如从初始节点s到目标节点t有路径存在，则算法A一定成功结束。63人工智能搜索问题第63页A*算法性质（续2）引理1.1： 对无限图，若有从初始节点s到目标节点t路径，则A*不结束时，在OPEN表中即使最小一个f值也将增到任意大，或有f(n)>f*(s)。64人工智能搜索问题第64页A*算法性质（续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)65人工智能搜索问题第65页A*算法性质（续3）定理1.2： 对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。引理1.1：A*假如不结束，则OPEN中全部n有f(n)>f*(s)引理1.2：在A*结束前，必存在节点n，使得f(n)≤f*(s)所以，假如A*不结束，将造成矛盾。66人工智能搜索问题第66页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，均被扩展。得证。67人工智能搜索问题第67页A*算法性质（续5）定理1.3(可采纳性定理)： 若存在从初始节点s到目标节点t有路径，则A*必能找到最正确解结束。68人工智能搜索问题第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人工智能搜索问题第69页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)。得证。70人工智能搜索问题第70页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扩展节点数71人工智能搜索问题第71页A*算法性质（续7）注意：

在定理1.4中，评价指标是“扩展节点数”，也就是说，同一个节点不论被扩展多少次，都只计算一次。72人工智能搜索问题第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人工智能搜索问题第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人工智能搜索问题第74页对h评价方法平均分叉树 设共扩展了d层节点，共搜索了N个节点，则:

其中，b*称为平均分叉树。b*越小，说明h效果越好。试验表明，b*是一个比较稳定常数，同一问题基本不随问题规模改变。75人工智能搜索问题第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人工智能搜索问题第76页A*复杂性普通来说，A*算法复杂性是指数型，能够证实，当且仅当以下条件成立时： abs(h(n)-h*(n))≤O(log(h*(n))) A*算法复杂性才是非指数型，不过通常情况下，h与h*差异最少是和离目标距离成正比。77人工智能搜索问题第77页3，A*算法改进问题提出： 因A算法第6步对ml类节点可能要重新放回到OPEN表中，所以可能会造成屡次重复扩展同一个节点，造成搜索效率下降。78人工智能搜索问题第78页s(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)79人工智能搜索问题第79页出现屡次扩展节点原因在前面扩展中，并没有找到从初始节点到当前节点最短路径，如节点A。s(10)A(1)B(5)C(8)G目标63111880人工智能搜索问题第80页处理路径对h加以限制能否对h增加适当限制，使得第一次扩展一个节点时，就找到了从s到该节点最短路径。对算法加以改进能否对算法加以改进，防止或降低节点屡次扩展。81人工智能搜索问题第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人工智能搜索问题第83页h单调性质定理1.5： 若h(n)是单调，则A*扩展了节点n之后，就已经找到了抵达节点n最正确路径。 即：当A*选n扩展时，有g(n)=g*(n)。84人工智能搜索问题第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人工智能搜索问题第85页定理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人工智能搜索问题第86页定理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人工智能搜索问题第87页h单调性质（续）定理1.6： 若h(n)是单调，则由A*所扩展节点序列其f值是非递减。即f(ni)≤f(nj)。

88人工智能搜索问题第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人工智能搜索问题第89页h单调例子8数码问题：h为“不在位”将牌数1 h(ni)-h(nj)=0 (nj为ni后继节点)-1 h(t)=0 c(ni,nj)=1满足单调条件。 90人工智能搜索问题第90页对算法加以改进一些结论：OPEN表上任以含有f(n)<f*(s)节点定会被扩展。A*选作