《人工智能 第一章课件.ppt》由会员分享，可在线阅读，更多相关《人工智能 第一章课件.ppt（117页珍藏版）》请在三一办公上搜索。
1、第1章、搜索问题,有许多智力问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)许多实际问题（如最优路径规划、人力排班、装箱问题、机器人行动规划等） 都可以归结为在某一状态空间中搜索目标或路径的问题。,2,3,4,5,问题 ： 如何解决这类问题？,这类问题不能用简单的数学公式/数学方程来描述，属于非结构化问题。难以获得求解所需的全部信息；更没有现成的算法可供求解使用属于组合爆炸问题，稍大规模的问题就超出了人类的认知负荷解决方法：利用计算机的超人计算能力，通过不断试探搜索找到问题的（最优）解。优点建模简单,7,具体方法： 状态空间法,状态：是指问题状态的的向量表示（x,y,z,.)。问题有
2、初始状态，有目标状态有些状态可能是非法的，问题不可能发展到那种状态问题表示为向量，向量就是在Euclidean空间，因此问题的初始状态和目标状态都是此空间中的点。此类问题的特征是找出从初始状态到目标状态的路径，方法是通过一个状态向另一个状态的转换实现的。,8,问题状态的表示方法（一）,9,问题状态的表示方法（二）,10,问题状态的变迁,11,问题状态的表示方法,12,问题状态的变迁,搜索问题-主要内容,内容：状态空间的搜索问题。搜索方式：盲目搜索启发式搜索关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解），寻找过程就是搜索。,14,状态空间法1. 状态空间表示方法,状态(State)：
3、求解过程中每一步问题状况的表示Sk=Sk0, Sk1 )当对每一个分量都给以确定的值时，就得到了一个具体的状态。操作(Operator): 也称为算符，它是把问题从一种状态变换为另一种状态的手段。操作可以是一个机械步骤，一个运算，一条规则或一个过程。状态空间(State space): 用来描述一个问题的全部状态以及这些状态之间的相互关系。常用表示为(S, F, G)其中，S为问题的所有初始状态的集合；F为操作的集合；G为目标状态的集合。 状态空间也可用一个赋值的有向图来表示，称为状态空间图,其中节点表示问题的状态，有向边表示操作。,15,状态空间法求解问题的基本过程：首先为问题选择适当的“状
4、态”及“操作”的形式化描述方法；然后从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止； 此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解。,状态空间法2. 状态空间问题求解,16,修道士(Missionaries)和野人(Cannibals)问题(简称M-C问题)。 设在河的一岸有三个野人、三个修道士和一条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：修道士和野人都会划船，但每次船上至多可载两个人；在河的任一岸，如果野人数目超过修道士数，修道士会被野人吃掉。 如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没
5、有修道士被野人吃掉的安全过河计划。,状态空间法3. 状态空间的例子,17,解：首先选取描述问题状态的方法。在这个问题中，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸。从而可用一个三元组来表示状态 S=(m, c, b)其中，m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸的船数。 右岸的状态可由下式确定： 右岸修道士数 m=3-m 右岸野人数 c=3-c 右岸船数 b=1-b 在这种表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有442=32种状态。,状态空间法3. 状态空间的例子,18,这32种状态并非全有意义，除去不合法状态和修道士被野人
6、吃掉的状态，有意义的状态只有16种： S0=(3, 3, 1) S1=(3, 2, 1) S2=(3, 1, 1) S3=(2, 2, 1) S4=(1, 1, 1) S5=(0, 3, 1) S6=(0, 2, 1) S7=(0, 1, 1) S8=(3, 2, 0) S9=(3, 1, 0) S10=(3, 0, 0) S11=(2, 2, 0) S12=(1, 1,0) S13=(0, 2, 0) S14=(0, 1, 0) S15=(0, 0, 0)有了这些状态，还需要考虑可进行的操作。 操作是指用船把修道士或野人从河的左岸运到右岸，或从河的右岸运到左岸。 每个操作都应当满足如下条件：
7、 一是船至少有一个人（m或c）操作，离开岸边的m和c的减少数目应该等于到达岸边的m和c的增加数目； 二是每次操作船上人数不得超过2个； 三是操作应保证不产生非法状态。 因此，操作应由条件部分和动作部分： 条件：只有当其条件具备时才能使用 动作：刻划了应用此操作所产生的结果。,19,操作的表示： 用符号Pij表示从左岸到右岸的运人操作 用符号Qij表示从右岸到左岸的操作其中： i表示船上的修道士人数 j表示船上的野人数操作集 本问题有10种操作可供选择： F=P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20 下面以P01和Q01为例来说明这些操作的条
8、件和动作。 操作符号 条件 动作 P01 b=1, m=0或m=3， c1 b=0, c=c-1 Q01 b=0, m=0或m=3，c2 b=1, c=c+1,搜索问题,S0,Sg,如何实现搜索？,讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。,1.1 回溯策略,例：皇后问题,( ),( ),Q,(1,1),( ),Q,Q,(1,1),(1,1) (2,3),( ),Q,(1,1),(1,1) (2,3),( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),( ),Q,Q,(1,1),(1,1) (
9、2,3),(1,1) (2,4),Q,(1,1) (2,4) (3.2),( ),Q,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) (2,4),(1,1) (2,4) (3.2),( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),( ),(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) (2,4),(1,1) (
10、2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),( ),(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) (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),递归的思想（续）,当前状态,目标状态g,一个递归的例子,int ListLenght(LIST *pLis
11、t)if (pList = NULL) return 0;else return ListLength(pList-next)+1;,回溯搜索算法,BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。,回溯搜索算法,递归过程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);
12、6,RULES:=TAIL(RULES);7,RDATA:=GEN(R, DATA);8,PATH:=BACKTRACK(RDATA);9,IF PATH=FAIL GO LOOP;10,RETURN CONS(R, PATH);,存在问题及解决办法,解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径,问题：深度问题,死循环问题,回溯搜索算法1,BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。,回溯搜索算法1,1, DATA:=FIRST(DATALIST)2, IF MENBER
13、(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);,回溯搜索算法1（续）,9,RULES:=TAIL(RULES);10,RDATA:=GEN(R, DATA);11,RDATALIST:=CONS(RDATA, DATAL
14、IST);12,PATH:=BACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R, PATH);,一些深入的问题,失败原因分析、多步回溯,一些深入问题（续）,回溯搜索中知识的利用基本思想(以皇后问题为例)：尽可能选取划去对角线上位置数最少的。,1.2 图搜索策略,问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。,一些基本概念,节点深度：根节点深度=0其它节点深度=父节点深度+1,0,1,2,3,一些基本概念（续1）,路径设一节点序列为(n0, n1,nk)，对于i=1,k，若节点ni
15、-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni, nj)表示从ni到nj的路径的耗散值。,一些基本概念（续1）,扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。,一般的图搜索算法,1, G=G0 (G0=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)
16、 THEN EXIT(SUCCESS);6, EXPAND(n)mi, G:=ADD(mi, G);,一般的图搜索算法（续）,7, 标记和修改指针：ADD(mj, OPEN), 并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算是否要修改ml到其后继节点的指针；8, 对OPEN中的节点按某种原则重新排序；9, GO LOOP；,节点类型说明,.,.,.,.,.,mj,mk,ml,修改指针举例,1,2,3,4,5,6,s,修改指针举例（续1）,1,2,3,4,5,6,s,1,2,3,4,5,6,修改指针举例（续2）,s,1,2,3,4,5,6,修改指针举例（续3）,s,1.3 无信息
17、图搜索过程,深度优先搜索宽度优先搜索,深度优先搜索,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, IF DEPTH(n)Dm GO LOOP;7, EXPAND(n) mi, G:=ADD(mi, G);8, IF 目标在mi中 THEN EXIT(SUCCESS);9, ADD(mj, OPEN), 并标记m
18、j到n的指针;10, GO LOOP;,1 2 38 47 6 5,2 31 8 47 6 5,2 31 8 47 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,目标,深度优先搜索的性质,一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举图搜索是一个通用的与问题无关的方法,宽度优先搜索,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
19、 (SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, G:=ADD(mi, G);7, IF 目标在mi中 THEN EXIT(SUCCESS);8, ADD(OPEN, mj), 并标记mj到n的指针;9, GO LOOP;,2 31 8 47 6 5,1,2,5,6,7,3,目标,8,4,宽度优先搜索的性质,当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法,1.4 启发式图搜索,利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信
20、息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解,*,希望：,引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。,*,基本思想,定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。,*,1，启发式搜索算法A（A算法）,评价函数的格式：f(n) = g(n) + h(n)f(n)：评价函数h(n)：启发函数,*,符号的意义,g*(n)：从s到n的最短路径的耗散值h*(n)：从n到g的最短路径的耗散值f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值g(n)、
21、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值,*,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) mi, 计算f(n, mi):=g(n, mi)+h(mi);,A算法（续）,ADD(mj, OPEN), 标记mj到n的指针；IF f(n, mk)f(mk) THEN f(mk):=f
22、(n, mk), 标记mk到n的指针；IF f(n, ml)f(ml,) THEN f(ml):=f(n, ml),标记ml到n的指针, ADD(ml, OPEN);7, OPEN中的节点按f值从小到大排序；8, GO LOOP；,.,.,.,.,.,mj,mk,ml,n,a,b,Closed表,Open表,一个A算法的例子,定义评价函数：f(n) = g(n) + h(n)g(n)为从初始节点到当前节点的耗散值h(n)为当前节点“不在位”的将牌数,2 8 31 6 47 5,1 2 38 47 6 5,*,h计算举例,h(n) =4,2 8 31 6 47 5,1 2 3,45,7 6,8,
23、*,2 8 31 6 47 5,s(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),目标,1,2,3,4,5,6,爬山法（局部搜索算法）,f(n)=h(n),分支界限法,如果对于任何n，f(n)=g(n), h(n)=0,动态规划算法,如果对于任何n，当h(n)=0时，求s-t的最短路径,对某一中间结点I, 只要考虑s 到I的最短路径分支,其余路径不考虑, A算法就成为了动态规划算法。,2，最佳图搜索算法A*（A*算法）,在A算法中，如果满足条件：h(n)h*(n)则A算法称为A*算法。,*,A*条件举例,
24、8数码问题h1(n) = “不在位”的将牌数h2(n) = 将牌“不在位”的距离和,*,A*算法的性质,A*算法的假设 设ni、nj是任意两个节点，有： C(ni, nj) 其中为大于0的常数,几个等式 f*(s) = f*(t) = h*(s) = g*(t) = f*(n) 其中s是初始节点，t是目标节点，n是s到t的最佳路径上的节点。,*,A*算法的性质（续1）,定理1.1：对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。,*,A*算法的性质（续2）,引理1.1 ：对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增
25、到任意大，或有f(n)f*(s)。,*,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),*,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*不结束，将导致矛盾。,*,A*算法的性质（续4）,推论1.1
26、：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，均被扩展。得证。,*,A*算法的性质（续5）,定理1.3 (可采纳性定理)：若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。,*,可采纳性的证明,由定理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*
27、(s) f(t)因此A*应选择n扩展，而不是t。与假设A*选择t结束矛盾。得证。,*,A*算法的性质（续6）,推论1.2：A*选作扩展的任一节点n，有f(n)f*(s)。,由引理2.2知在A*结束前，OPEN中存在节点n， f(n)f*(s)设此时A*选择n扩展。如果nn，则f(n)f*(s)，得证。如果n n，由于A*选择n扩展，而不是n，所以有f(n) f(n)f*(s)。得证。,*,A*算法的性质（续7）,定理1.4：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n) h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A
28、2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。简写：如果h2(n) h1(n) (目标节点除外)，则A1扩展的节点数A2扩展的节点数,*,A*算法的性质（续7）,注意： 在定理1.4中，评价指标是“扩展的节点数”，也就是说，同一个节点无论被扩展多少次，都只计算一次。,*,定理1.4的证明,使用数学归纳法，对节点的深度进行归纳（1）当d(n)0时，即只有一个节点，显然定理成立。（2）设d(n)k时定理成立。（归纳假设）（3）当d(n)=k+1时，用反证法。设存在一个深度为k1的节点n，被A2扩展，但没有被A1扩展。而由假设，A1扩展了n的父节点，即n已经被生成了。
29、因此当A1结束时，n将被保留在OPEN中。,定理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) (引理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) ，与定理条件矛盾。故定理得证。,对h的评价方法,平均分叉树设共扩展了d
30、层节点，共搜索了N个节点，则:其中，b*称为平均分叉树。b*越小，说明h效果越好。实验表明，b*是一个比较稳定的常数，同一问题基本不随问题规模变化。,对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.27,A*的复杂性,一般来说，A*的算法复杂性是指数型的，可以证明，当且仅当以下条件成立时：abs(h(n)-h*(n) O(log(h*(n)A*的算法复杂性才是非指数型的，但是通常情况下， h与h*的差别至少是
31、和离目标的距离成正比的。,*,3，A*算法的改进,问题的提出：因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。,*,一个例子：,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),*,出现多次扩展节点的原因,在
32、前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。,*,解决的途径,对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展。,*,改进的条件,可采纳性不变不多扩展节点不增加算法的复杂性,*,对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),ni,nj,h(nj),c(ni,nj),*
33、,h单调的性质,定理1.5：若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。即：当A*选n扩展时，有g(n)=g*(n)。,*,定理1.5的证明,设n是A*扩展的任一节点。当ns时，定理显然成立。下面考察n s的情况。设P(n0=s, n1, n2, , nk=n)是s到n的最佳路径P中一定有节点在CLOSED中，设P中最后一个出现在CLOSED中的节点为nj，则nj+1在OPEN中。,定理1.5的证明（续1）,由单调限制条件，对P中任意节点ni有： h(ni) C(ni, ni+1)+h(ni+1) g*(ni)+h(ni) g*(ni)+C(ni, ni+1)
34、+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中),定理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)是最佳路径的
35、耗散值，所以只有：g(n) = g*(n)。得证。,h单调的性质（续）,定理1.6：若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。即f(ni) f(nj)。,*,定理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，得证。,*,h单调的例子,8数码问题：h为“不在
36、位”的将牌数 1h(ni) - h(nj) = 0(nj为ni的后继节点) -1 h(t) = 0c(ni, nj) = 1 满足单调的条件。,*,对算法加以改进,一些结论：OPEN表上任以具有f(n) f*(s)的节点定会被扩展。A*选作扩展的任一节点，定有f(n)f*(s)。,*,改进的出发点,OPEN = ( ),f*(s),f值小于f*(s)的节点,f值大于等于f*(s)的节点,fm：到目前为止已扩展节点的最大f值，用fm代替f*(s)h(n)=0 for nodes in NEST,*,修正过程A,1, OPEN:=(s), f(s)=g(s)+h(s), fm:=0;2, LOOP
37、: IF OPEN=( ) THEN EXIT(FAIL);3, NEST:=ni|f(ni)fmIF NEST ( ) THEN n:=NEST中g最小的节点 ELSE n:=FIRST(OPEN), fm:=f(n);4, , 8: 同过程A。,*,前面的例子：,OPEN表,CLOSED表,fm,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),*,h的单调化方法,如果令：f(n) = max(f(n的父节点), g(n)+h(n)则容易证明，这样处理后的h是单调的。,*,搜索算法的讨论,1.弱方法盲目搜索算法产生组合爆炸启发搜索算法属于弱方法,不能保证找到解2. 算法分析数学分析统计分析程序分析分析指标: 时间和空间,*,作业,1.2,8数码问题. Figure 1.17h1(n) = “不在位”的将牌数Draw out the searching tree using A,*,
