人工智能搜索问题.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第一章 搜索问题,内容：,状态空间搜索问题。,搜索方式：,盲目搜索,启发式搜索,关键问题：,怎样利用知识，尽可能有效地找到问题解（最正确解）。,1,人工智能搜索问题,第1页,搜索问题（续1）,S,0,S,g,2,人工智能搜索问题,第2页,搜索问题（续2）,讨论问题：,有哪些惯用搜索算法。,问题有解时能否找到解。,找到解是最正确吗？,什么情况下能够找到最正确解？,求解效率怎样。,3,人工智能搜索问题,第3页,1.1 回溯策略,例：皇后问题,4,人工智能搜索问题,第4页,(),5,人工智能搜索问题,第5页,(),Q,(1,1),6,人工智能搜索问题,第6页,(),Q,Q,(1,1),(1,1)(2,3),7,人工智能搜索问题,第7页,(),Q,(1,1),(1,1)(2,3),8,人工智能搜索问题,第8页,(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),9,人工智能搜索问题,第9页,(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),Q,(1,1)(2,4)(3.2),10,人工智能搜索问题,第10页,(),Q,Q,(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页,递归思想（续）,当前状态,目标状态g,19,人工智能搜索问题,第19页,一个递归例子,int ListLenght(LIST*pList),if(pList=NULL)return 0;,else return ListLength(pList-next)+1;,NULL,pLIST,1,2,3,20,人工智能搜索问题,第20页,回溯搜索算法,BACKTRACK（DATA）,DATA：当前状态。,返回值：从当前状态到目标状态路径,（以规则表形式表示）,或FAIL。,21,人工智能搜索问题,第21页,回溯搜索算法,递归过程BACKTRACK(DATA),1,IF TERM(DATA)RETURN NIL;,2,IF DEADEND(DATA)RETURN FAIL;,3,RULES:=APPRULES(DATA);,4,LOOP:IF NULL(RULES)RETURN FAIL;,5,R:=FIRST(RULES);,6,RULES:=TAIL(RULES);,7,RDATA:=GEN(R,DATA);,8,PATH:=BACKTRACK(RDATA);,9,IF PATH=FAIL GO LOOP;,10,RETURN CONS(R,PATH);,22,人工智能搜索问题,第22页,存在问题及处理方法,处理方法：,对搜索深度加以限制,统计从初始状态到当前状态路径,当前状态,问题：,深度问题,死循环问题,23,人工智能搜索问题,第23页,回溯搜索算法1,BACKTRACK1（DATALIST）,DATALIST：从初始到当前状态表（逆向）,返回值：从当前状态到目标状态路径,（以规则表形式表示）,或FAIL。,24,人工智能搜索问题,第24页,回溯搜索算法1,1,DATA:=FIRST(DATALIST),2,IF MENBER(DATA,TAIL(DATALIST),RETURN FAIL;,3,IF TERM(DATA)RETURN NIL;,4,IF DEADEND(DATA)RETURN FAIL;,5,IF LENGTH(DATALIST)BOUND,RETURN FAIL;,6,RULES:=APPRULES(DATA);,7,LOOP:IF NULL(RULES)RETURN FAIL;,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,IF PATH=FAIL GO LOOP;,14,RETURN CONS(R,PATH);,26,人工智能搜索问题,第26页,一些深入问题,失败原因分析、多步回溯,Q,Q,27,人工智能搜索问题,第27页,一些深入问题（续）,回溯搜索中知识利用,基本思想(以皇后问题为例)：,尽可能选取划去对角线上位置数最少。,Q,Q,Q,Q,3 2 2 3,28,人工智能搜索问题,第28页,1.2 图搜索策略,问题引出,回溯搜索：只保留从初始状态到当前状态一条路径。,图搜索：保留全部已经搜索过路径。,29,人工智能搜索问题,第29页,一些基本概念,节点深度：,根节点深度=0,其它节点深度=父节点深度+1,0,1,2,3,30,人工智能搜索问题,第30页,一些基本概念（续1）,路径,设一节点序列为(n,0,n,1,n,k,)，对于i=1,k，若节点n,i-1,含有一个后继节点n,i,，则该序列称为从n,0,到n,k,路径。,路径耗散值,一条路径耗散值等于连接这条路径各节点间全部耗散值总和。用C(n,i,n,j,),表示从n,i,到n,j,路径耗散值。,31,人工智能搜索问题,第31页,一些基本概念（续1）,扩展一个节点,生成出该节点全部后继节点，并给出它们之间耗散值。这一过程称为“扩展一个节点”。,32,人工智能搜索问题,第32页,普通图搜索算法,1,G=G,0,(G,0,=s),OPEN:=(s);,2,CLOSED:=();,3,LOOP:IF OPEN=()THEN EXIT(FAIL);,4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);,5,IF GOAL(n)THEN EXIT(SUCCESS);,6,EXPAND(n)m,i,G:=ADD(m,i,G);,33,人工智能搜索问题,第33页,普通图搜索算法（续）,7,标识和修改指针：,ADD(m,j,OPEN),并标识m,j,到n指针；,计算是否要修改m,k,、m,l,到n指针；,计算是否要修改m,l,到其后继节点指针；,8,对OPEN中节点按,某种标准,重新排序；,9,GO LOOP；,34,人工智能搜索问题,第34页,节点类型说明,.,.,.,.,.,m,j,m,k,m,l,35,人工智能搜索问题,第35页,修改指针举例,1,2,3,4,5,6,s,36,人工智能搜索问题,第36页,修改指针举例（续1）,1,2,3,4,5,6,s,37,人工智能搜索问题,第37页,1,2,3,4,5,6,修改指针举例（续2）,s,38,人工智能搜索问题,第38页,1,2,3,4,5,6,修改指针举例（续3）,s,39,人工智能搜索问题,第39页,1.3 无信息图搜索过程,深度优先搜索,宽度优先搜索,40,人工智能搜索问题,第40页,深度优先搜索,1,G:=G,0,(G,0,=s),OPEN:=(s),CLOSED:=();,2,LOOP:IF OPEN=()THEN EXIT(FAIL);,3,n:=FIRST(OPEN);,4,IF GOAL(n)THEN EXIT(SUCCESS);,5,REMOVE(n,OPEN),ADD(n,CLOSED);,6,IF DEPTH(n)Dm GO LOOP;,7,EXPAND(n)m,i,G:=ADD(m,i,G);,8,IF 目标在m,i,中 THEN EXIT(SUCCESS);,9,ADD(m,j,OPEN),并标识m,j,到n指针;,10,GO LOOP;,41,人工智能搜索问题,第41页,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,2 8 3,6 4,1 7 5,2 8 3,1 6,7 5 4,8 3,2 1 4,7 6 5,2 8 3,7 1 4,6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1,2,3,4,5,6,7,8,9,a,b,c,d,1 2 3,8 4,7 6 5,目标,42,人工智能搜索问题,第42页,深度优先搜索性质,普通不能确保找到最优解,当深度限制不合理时，可能找不到解，能够将算法改为可变深度限制,最坏情况时，搜索空间等同于穷举,与回溯法差异：图搜索,是一个通用与问题无关方法,43,人工智能搜索问题,第43页,宽度优先搜索,1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();,2,LOOP:IF OPEN=()THEN EXIT(FAIL);,3,n:=FIRST(OPEN);,4,IF GOAL(n)THEN EXIT(SUCCESS);,5,REMOVE(n,OPEN),ADD(n,CLOSED);,6,EXPAND(n)m,i,G:=ADD(m,i,G);,7,IF 目标在m,i,中 THEN EXIT(SUCCESS);,8,ADD(OPEN,m,j,),并标识m,j,到n指针;,9,GO LOOP;,44,人工智能搜索问题,第44页,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,1,2,5,6,7,3,1 2 3,8 4,7 6 5,目标,8,2 3 4,1 8,7 6 5,4,45,人工智能搜索问题,第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:IF OPEN=()THEN EXIT(FAIL);,3,n:=FIRST(OPEN);,4,IF GOAL(n)THEN EXIT(SUCCESS);,5,REMOVE(n,OPEN),ADD(n,CLOSED);,6,EXPAND(n),m,i,计算f(n,m,i,):=g(n,m,i,)+h(m,i,);,53,人工智能搜索问题,第53页,A算法（续）,ADD(m,j,OPEN),标识m,j,到n指针；,IF f(n,m,k,)f(m,k,)THEN f(m,k,):=f(n,m,k,),标识m,k,到n指针；,IF f(n,m,l,),其中为大于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),由引理1.2知结束前OPEN中存在f(n)f*(s)节点n，所以,f(n)f*(s)h,1,(n)，则在含有一条从s到t路径隐含图上，搜索结束时，由A,2,所扩展每一个节点，也必定由A,1,所扩展，即A,1,扩展节点数最少和A,2,一样多。,简写：假如h,2,(n),h,1,(n)(目标节点除外)，则A,1,扩展节点数,A,2,扩展节点数,71,人工智能搜索问题,第71页,A*算法性质（续7）,注意：,在定理1.4中，评价指标是“扩展节点数”，也就是说，同一个节点不论被扩展多少次，都只计算一次。,72,人工智能搜索问题,第72页,定理1.4证实,使用数学归纳法，对节点深度进行归纳,（1）当d(n)0时，即只有一个节点，显然定理成立。,（2）设d(n)k时定理成立。（归纳假设）,（3）当d(n)=k+1时，用反证法。,设存在一个深度为k1节点n，被A,2,扩展，但没有被A,1,扩展。而由假设，A,1,扩展了n父节点，即n已经被生成了。所以当A,1,结束时，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数码问题，随机产生若干初始状态。,使用h,1,：,d=14,N=539,b*=1.44;,d=20,N=7276，b*=1.47；,使用h,2,：,d=14,N=113,b*=1.23;,d=20,N=676,b*=1.27,76,人工智能搜索问题,第76页,A*复杂性,普通来说，A*算法复杂性是指数型，能够证实，当且仅当以下条件成立时：,abs(h(n)-h*(n)O(log(h*(n),A*算法复杂性才是非指数型，不过通常情况下，h与h*差异最少是和离目标距离成正比。,77,人工智能搜索问题,第77页,3，A*算法改进,问题提出：,因A算法第6步对m,l,类节点可能要重新放回到OPEN表中，所以可能会造成屡次重复扩展同一个节点，造成搜索效率下降。,78,人工智能搜索问题,第78页,s(10),A(1),B(5),C(8),G 目标,6,3,1,1,1,8,一个例子：,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 目标,6,3,1,1,1,8,80,人工智能搜索问题,第80页,处理路径,对h加以限制,能否对h增加适当限制，使得第一次扩展一个节点时，就找到了从s到该节点最短路径。,对算法加以改进,能否对算法加以改进，防止或降低节点屡次扩展。,81,人工智能搜索问题,第81页,改进条件,可采纳性不变,不多扩展节点,不增加算法复杂性,82,人工智能搜索问题,第82页,对h加以限制,定义：一个启发函数h，假如对全部节点n,i,和n,j,，其中n,j,是n,i,子节点，满足,h(n,i,)-h(n,j,)c(n,i,n,j,),h(t)=0,或,h(n,i,)c(n,i,n,j,)+h(n,j,),h(t)=0,则称h是单调。,h(n,i,),n,i,n,j,h(n,j,),c(n,i,n,j,),83,人工智能搜索问题,第83页,h单调性质,定理1.5：,若h(n)是单调，则A*扩展了节点n之后，就已经找到了抵达节点n最正确路径。,即：当A*选n扩展时，有g(n)=g*(n)。,84,人工智能搜索问题,第84页,定理1.5证实,设n是A*扩展任一节点。当ns时，定理显然成立。下面考查n s情况。,设P(n,0,=s,n,1,n,2,n,k,=n)是s到n最正确路径,P中一定有节点在CLOSED中，设P中最终一个出现在CLOSED中节点为n,j,，则n,j+1,在OPEN中。,85,人工智能搜索问题,第85页,定理1.5证实（续1）,由单调限制条件，对P中任意节点n,i,有：,h(n,i,)C(n,i,n,i+1,)+h(n,i+1,),g*(n,i,),+h(n,i,),g*(n,i,),+C(n,i,n,i+1,)+h(n,i+1,),因为n,i,、n,i+1,在最正确路径上，所以：,g*(n,i+1,)=g*(n,i,)+C(n,i,n,i+1,),带入上式有：,g*(n,i,)+h(n,i,)g*(n,i+1,)+h(n,i+1,),从i=j到i=k-1应用上不等式，有：,g*(n,j+1,)+h(n,j+1,)g*(n,k,)+h(n,k,),即：,f(n,j+1,)g*(n)+h(n),注意：(n,j,在CLOSED中，n,j+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(n,i,)f(n,j,)。,88,人工智能搜索问题,第88页,定理1.6证实,由单调限制条件，有：,h(n,i,)h(n,j,)C(n,i,n,j,),=,f(n,i,)-g(n,i,),=,f(n,j,)-g(n,j,),f(n,i,)-g(n,i,)-f(n,j,)+g(n,j,)C(n,i,n,j,),=,g(n,i,)+C(n,i,n,j,),f(n,i,)-,g(n,i,),-f(n,j,)+,g(n,i,),+C(n,i,n,j,),C(n,i,n,j,),f(n,i,)-f(n,j,),0，得证。,89,人工智能搜索问题,第89页,h单调例子,8数码问题：,h为“不在位”将牌数,1,h(n,i,)-h(n,j,)=0(n,j,为n,i,后继节点),-1,h(t)=0,c(n,i,n,j,)=1,满足单调条件。,90,人工智能搜索问题,第90页,对算法加以改进,一些结论：,OPEN表上任以含有f(n)f*(s)节点定会被扩展。,A*选作扩展任一节点，定有f(n)f*(s)。,91,人工智能搜索问题,第91页,改进出发点,OPEN=(),f*(s),f值小于f*(s)节点,f值大于等于f*(s)节点,f,m,：,到当前为止已扩展节点最大f值，用f,m,代替f*(s),92,人工智能搜索问题,第92页,修正过程A,1,OPEN:=(s),f(s)=g(s)+h(s),f,m,:=0;,2,LOOP:IF OPEN=()THEN EXIT(FAIL);,3,NEST:=n,i,|f(n,i,)f,m,IF NEST ()THEN n:=NEST中g最小节点,ELSE n:=FIRST(OPEN),f,m,:=f(n);,4,8:,同过程A。,93,人工智能搜索问题,第93页,s(10),A(1),B(5),C(8),G 目标,6,3,1,1,1,8,前面例子：,OPEN表,CLOSED表,f,m,s(0+10),s(0+10),10,A(6+1)B(3+5)C(1+8),s(0+10)C(1+8),10,A(6+1)B(2+5),s(0+10)C(1+8)B(2+5),10,A(3+1),s(0+10)C(1+8)B(2+5)A(3+1),10,G(11+0),94,人工智能搜索问题,第94页,h单调化方法,假如令：,f(n)=max(f(n父节点),g(n)+h(n),则轻易证实，这么处理后h是单调。,95,人工智能搜索问题,第95页,IDA*算法(Iterative Deepening A*),基本思想：回溯与A*结合,算法介绍（非严格地）,1，设初始值f0；,2，集合SNULL；,3，用回溯法求解问题，假如节点nf值大于f0，则将该节点放入集合S中，并回溯；,4，假如在3中找到了解，则结束；,5，假如3以失败结束，则f0S中节点最小f值；,6，返回到2。,96,人工智能搜索问题,第96页,知识灵活应用,例：怎样转动，使得每个扇区数字和为12。,1,3,5,5,1,4,4,1,3,3,2,5,2,3,1,2,3,1,2,2,5,5,2,3,4,2,5,4,3,4,3,3,分析：,阴影部分数字和：48,直径部分数字和：24,转45改变阴影部分,转90改变直径部分,但不改变阴影部分,转180改变扇区部分,但不改变阴影部分,也不改变直径部分,97,人工智能搜索问题,第97页,4，其它搜索算法,爬山法（局部搜索算法）,98,人工智能搜索问题,第98页,其它搜索算法（续1）,随机搜索算法,动态规划算法,假如对于任何n，当h(n)=0时，A*算法就成为了动态规划算法。,99,人工智能搜索问题,第99页,动态规划,s,t,第一阶段,第二阶段,第三阶段,第四阶段,第五阶段,100,人工智能搜索问题,第100页,5，搜索算法实用举例,汉字识别后处理,一个例子,我钱线载哦栽哉裁劣绥,优仍们仿伦奶砧犯扔妨,要耍密穷安壁驻努窑垂,扳报叔嵌奴振技寂叙蔽,奋夯杏蚕香脊秀吞吝番,精猜指洁括治捐活冶桔,种神衬祥科钟拌样拎补,101,人工智能搜索问题,第101页,汉字识别后处理,二元语法时：,为常量,用识别信度代替,问题变为求,最大,102,人工智能搜索问题,第102页,