人工智能导论课件：第二章 产生式系统的搜索策略

1、上次课程回顾,产生式 IF THEN IF THEN 或者简写为： 组成三要素： 一个综合数据库存放信息 一组产生式规则（规则库）知识 一个控制系统（推理机）规则的解释或执行程序 （控制策略）（推理引擎） 产生式系统的推理方式 正向推理，反向推理，双向推理,第二章 产生式系统的搜索策略,引入,搜索? 当到学校的时候,找最方便的路线. 在餐厅就餐时,找喜欢的食品. 考学时,找合适的学校. 人的思维过程,可以看做一个搜索过程.,引例,传教士与野人问题： 3个传教士和3个野人在河边准备渡河,一条船,每次至多可供2人乘坐, 在每次渡河之后，都有多种方案供选择，究竟那种方案在满足题目所规定的约束条件下，

2、有利于顺利过河呢？ 搜索问题 假设通过搜索找到了问题的一个解,结束?,产生式系统的搜索策略,讨论的问题： 有哪些常用的搜索算法？能保证找到解么？ 总是可以终止的么？是否可能陷入无限循环 问题有解时能否找到解。 找到的解是最佳的吗？ 什么情况下可以找到最佳解？ 求解的效率如何。,本章的主要内容,状态空间的搜索问题 搜索方式： 盲目搜索 启发式搜索 关键问题： 如何利用知识，尽可能有效地找到问题的解（最佳解）,状态空间,状态空间: 一个状态空间可以表示为一个四元组【N, A, S, GD】,其中： N是图的结点或状态的集合。图的结点对应于问题求解过程中的各个状态 A是结点间弧（也就是连接）的集合。

3、对应于问题求解过程中的各个步骤 S是N的非空子集，表示问题的起始状态 GD是N的非空子集，表示问题的目标状态。,状态空间的搜索问题-引例,初始状态(3,3,1)-目标状态(0,0,0) 从初始状态到目标状态的转换中，有中间状态。 除了初始状态外，该序列中任何一个状态都可以通过一条规则由与它相临的前一个转态转换得到。 问题的解：合法的状态空间序列。 很多问题都可以转化为状态空间的搜索问题。,搜索问题示意图,S0,Sg,含义：如何在一个比较大的问题空间中，只通过搜索比较小的范围，就找到问题的解。,问题全状态空间,搜索空间,解路径,搜索方式,搜索策略主要任务：确定如何选取规则的方式。 盲目搜索方法：

4、不考虑给定问题所具有的特定知识，系统根据事先确定的某种固定排序，依次调用规则或随机调用规则。（无信息引导的搜索策略） 启发式搜索策略：考虑问题领域可应用的知识，动态地确定规则的排序，优先调用较合适的规则。（有信息引导的搜索策略） 使用不同的搜索策略，找到解的搜索范围是有区别的。,回溯策略,回溯策略(backtracking strategies)-盲目搜索的一种。 回溯策略：首先将规则给出固定的排序，在搜索时， 1）对当前状态依次检测每一条规则，在当前状态未使用的规则中找到第一条可应用的规则，应用于当前状态，得到的新的状态重新设置为当前状态，并重复以上搜索。 2） 如果当前状态无规则可用，或所

5、有规则都已经试探过，仍未找到问题的解，则将当前状态的前一个状态设置为当前状态。 3）重复以上搜索，直到找到问题的解，或者找不到问题的解。,回溯策略举例说明,例：皇后问题：,在一个4*4的国际象棋棋盘上，一次一个地摆布四枚皇后棋子，摆好后要满足 每行、每列和对角线上只允许出现一枚棋子，即棋子间不能相互俘获。,( ),( ),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) (2,3),(1,1) (2,4),Q,(1

6、,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) (2,4) (3.2),Q,(1,2),Q,

7、(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),方法是：一个个试探，按顺序找问题的解，一旦发现无法摆放，回溯,递归的思想,可以看出，这种求解过程呈现出递归的方法。,回溯算法示意图,当前状态n,目标

8、状态t,r1,r2,ri-1,ri,m1,m2,mi-1,mi,定义一个递归过程，实现回溯搜索策略。 如果从当前状态DATA到目标状态有路径存在，则返回以规则序列表示的从DATA到目标状态的路径； 如果从当前状态DATA到目标状态没有路径存在，则返回FAIL。,有路径存在,无路径存在,回溯搜索算法,BACKTRACK（DATA） DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。,回溯搜索算法,递归过程BACKTRACK(DATA) 1, IF TERM(DATA)，RETURN NIL; 2, IF DEADEND(DATA)，RETURN FAI

9、L; 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); ，,（不合法状态回溯点）,全部规则应用均 失败，回溯,回溯点标记,表示：DATA满足结束条件,表DATA为非法状态,规则用完未找到目标,对新状态递归调用本过程,递归调用失败，则转移调用另一

10、规则进行测试,APPRULES计算DATA的可应用规则集，以某种原则排序后赋给RULES,递归过程BACKTRACK(DATA)图示,当前状态n,目标状态t,r1,r2,ri-1,ri,m1,m2,mi-1,mi,将循环与递归结合在一起.,探索n的子状态中,通过那个状态 可到达目标状态-通过循环实现.,探索n的某子状态, 是否可以达到 目标状态-通过递归实现.,举例-回溯算法,四皇后问题：在一个4*4的国际象棋棋盘上，一次一个地摆布四枚皇后棋子，摆好后要满足每行、每列和对角线上只允许出现一枚棋子，即棋子间不能相互俘获。 上图中状态分别记为（12 24 31 43）、（13 21 34 42）、

11、（11 21）、（11 22）、（11 23 31）。,当规则序列以R11、R12、R13、R14、R21、R44这种固定的排序方式调用BACKTRACK时，四皇后问题的搜索示意图如图所示。 共回溯22次，主过程结束时返回规则表（R12、R24、R31、R43）。,( ),Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,图3-4、四皇后问题的固定排序搜索树,存在问题及解决办法(1),回溯算法BACKTRACK中，设置了两个回溯点： 一个是当遇到非法状态时回溯； 一个是当试探了一个状态的所有子状态后，仍然找不到解回溯。 但可能会遇到这样的问题： 问题的某一个（或某些）分支具有无穷个状态，

12、算法可能会落入某个“深渊”，永远也回溯不回来； 在某一个分支上具有环路，搜索将在这个环路中一直进行下去，回溯不回来，找不到问题的解。,存在问题及解决办法（2）,解决办法： 对搜索深度加以限制 记录从初始状态到当前状态的路径,问题： 深度问题,死循环问题,存在问题及解决办法（3）,具体的，对原来的回溯算法上增加两个回溯点（算法BACKTRACK1（DATALIST）： 一个是用常量BOUND来限制算法所能够搜索的最大深度，当当前状态的深度达到了限制的深度时，算法将进行回溯，避免陷入“深渊”。 另一个是用一个表记录初始状态到当前状态（非当前状态），当新的状态产生时，查看是否已经在该表中出现过: 如

13、出现过，表明有环路存在，算法将回溯，从而解决环路问题。,回溯搜索算法1,BACKTRACK1（DATALIST） DATALIST：从初始到当前的状态表（逆向） 初始状态排在表的最后，当前状态排在最前 返回值：从当前状态到目标状态的路径 （以规则表的形式表示）或FAIL。,回溯搜索算法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(DATALIS

14、T)BOUND RETURN FAIL; 6, RULES:=APPRULES(DATA); 7, LOOP: IF NULL(RULES) RETURN FAIL; 8,R:=FIRST(RULES);,设置DATA为当前状态,若DATA在TAIL（DATALIST）中存在，表示有回路，必须回溯。,取尾操作，表示取表DATALIST中除了第一个元素外的所有元素。,回溯搜索算法1（续）,9,RULES:=TAIL(RULES); 10,RDATA:=GEN(R, DATA); 11,RDATALIST:=CONS(RDATA, DATALIST); 12,PATH:=BACKTRCK1(RDA

15、TALIST) 13,IF PATH=FAIL， GO LOOP; 14,RETURN CONS(R, PATH);,将新状态加入到表DATALIST中,递归调用本过程,递归调用失败，则转移调用另一规则进行测试,一些深入的问题（1）,失败原因分析、多步回溯 上面的算法只描述了回溯一层的情况，即第n层递归调用失败，则控制退回到第n-1层。但实际上，往往早成深层搜索失败在于浅层原因，因此可以利用启发信息，分析失败原因，再回溯到合适的层次上，这就是多层回溯策略的思想。,一些深入问题（续）,回溯搜索中知识的利用(以皇后问题为例)： 基本思想: 所影响的棋盘位置越少，给以后放皇后留的余地越大，找到解的可

16、能性越大。 不论在任何位置,行列的影响数相同,尽可能选取最长对角线上影响数最少的。,( ),( 12 ),( 12, 21 ),Q,Q,( 12, 24 ),( 12, 24, 31 ),( 12, 24, 31, 42 ),( 12, 24, 31, 43 ),Q,Q,Q,Q,顺序: R12、R13、R11、R14 R21、R24、R22、R23 R31、R34、R32、R33 R42、R43、R41、R44,还有没有其他的方法？考虑： 规则的排序,练习,课本P55, 第一题.,第4次课 2013年09月12日,上次课程回顾,产生式系统的搜索策略 回溯算法 BACKTRACK（DATA） 深

17、度问题,死循环问题 BACKTRACK1（DATALIST） 利用启发信息,2.2 图搜索策略,问题的引出 回溯搜索：只保留从初始状态到当前状态的一条路径。 好处：节省存储空间 不足：被回溯掉的已经搜索过的部分，不能 被以后利用。 图搜索：保留所有已经搜索过的路径。,一些基本概念,节点深度： 根节点深度=0 其它节点深度=父节点深度+1,0,1,2,3,一些基本概念（续1）,路径 设一节点序列为(n0, n1,nk)，对于i=1,k，若任一节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。 路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni, n

18、j)表示从ni到nj的路径的耗散值。,一些基本概念（续2）,路径的耗散值的计算 C（ni，t）=C（ni，nj）+C（nj，t） 其中C（nj，t）为 njt这条路径的耗散值 扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。,一般的图搜索算法,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) THEN EX

19、IT(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,实心结点在CLOSE表中（已扩展过的结点），空心结点在OPEN表中（待扩展点）,修改指针举例（续1）,1,2,3,4,5,6,s,1,2,3,4,5,6,修改指针举例（

20、续2）,s,1,2,3,4,5,6,修改指针举例（续3）,s,2.3 无信息图搜索过程,无信息图搜索 深度优先搜索 宽度优先搜索,深度优先搜索,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

21、, IF 目标在mi中 THEN EXIT(SUCCESS); 9, ADD(mj, OPEN), 并标记mj到n的指针; 10, GO LOOP;,哪一步体现了深度优先？,表示节点mj是通过n得到的。,举例说明-深度优先搜索,八数码问题：在3*3九宫格棋牌上，摆有8个将牌都刻有1-8数码中的某一个数码。棋牌中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。 问：如何移动将牌，实现从初始状态到目标状态的转变。问题的解答就是给出一个合法的走步序列。,1 2 3 8 4 7 6 5,2 3 1 8 4 7 6 5,1 2 3 8 4 7 6 5,初始状态,

22、目标状态,2 3 1 8 4 7 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 (SUCCESS); 5, REMOVE(n, O

23、PEN), 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 3 1 8 4 7 6 5,1,2,5,6,7,3,目标,8,4,宽度优先搜索的性质,当问题有解时，一定能找到解 当问题为单位耗散值，且问题有解时，一定能找到最优解 方法与问题无关，具有通用性 效率较低 属于图搜索方法,渐进式深度优先搜索方法,目的 解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。 思想 首先给算法一个比较小的

24、深度限制，然后逐渐增加深度限制，直到找到解或找遍所以分支为止。,第5次课 2013年09月16日,上次课程回顾,一般图搜索算法 无信息图搜索 深度优先搜索 宽度优先搜索,2.4 启发式图搜索,利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。 启发信息的强度 强：降低搜索工作量，但可能导致找不到最 优解 弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解,基本思想,定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。,希望：,引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。,1，启发式搜索算法A（A算法）,评价函数

25、的格式： f(n) = g(n) + h(n) f(n)：评价函数 h(n)：启发函数,基本思想：定义一个评价函数f,对当前的搜索状态进行评估，找出一个最有希望的结点来扩展,符号的意义,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)的估计值,A算法,1, OPEN:=(s), f(s):=g(s)+h(s); 2, LOOP: IF OPEN=( ) THEN EXIT(FAIL); 3, n:=FIRST(OPEN); 4

26、, 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(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；,A算法

27、（续）,A算法由一般的图搜索算法改变而成，在算法的第7步，按照f值从小到大对OPEN表中的结点进行排序。 g(n)按照已搜索的结果，按照从初始结点s到结点n的路径，计算耗散值。而h(n)依赖于启发信息，与问题有关。 h(n)通常称为启发函数，是对未来扩展的方向作出估计。 算法A按照f(n)递增的顺序排列OPEN表的结点，体现了好的优先搜索的策略。,简单说明A算法,.,.,.,.,.,mj,mk,ml,n,a,b,一个A算法的例子,定义评价函数： f(n) = g(n) + h(n) g(n)为从初始节点到当前节点的耗散值 h(n)为当前节点“不在位”的将牌数 这样 f(n)可估计出通向目标结点

28、的希望程度。,2 8 3 1 6 4 7 5,1 2 3 8 4 7 6 5,h计算举例,h(n) =4,2 8 3 1 6 4 7 5,1 2 3,4 5,7 6,8,2 8 3 1 6 4 7 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,搜索过程的OPEN表和CLOSED表,OPEN表,CLOSED表,初始化 (s(4),第1循环结束 (B(4) A(6) C(6),第2循环结束 (D(5 ) E(5) A(6) C(6) F(6),第3循环结束(E(5) A(

29、6) C(6) F(6) G(6) H(7),第4循环结束(I(5) A(6) C(6) F(6) G(6) H(7) J(7),第5循环结束 (K(5) A(6) C(6) F(6) G(6) H(7) J(7),第6循环结束 (L(5) A(6) C(6) F(6) G(6) H(7) J(7) M(7),第7循环结束 第4步成功退出,(s(4) B(4) D(5) E(5) I(5) K(5),(s(4) B(4) D(5) E(5) I(5),(s(4) B(4) D(5) E(5),(s(4) B(4) D(5),(s(4) B(4),(s(4),( ),引入-最佳图搜索算法A*,h

30、(n)为当前节点“不在位”的将牌数 h(n) =4,2 8 3 1 6 4 7 5,1 2 3 8 4 7 6 5,最佳图搜索算法A*（A*算法）,在A算法中，如果满足条件： h(n)h*(n) 则A算法称为A*算法。,表示从结点n到目标结点g的最短路径的耗散值,A*条件举例,八数码问题 h1(n) = “不在位”的将牌数 h2(n) = 将牌“不在位”的距离和,尽管对具体的h*(n)是多少很难确切知道，但根据“不在位” 将牌个数的计算，就能得出至少需要移动h1(n)步才能达到目标，显然有h1(n) h*(n) 。,每一个将牌与其目标位置之间距离,2 8 3 1 6 4 7 5,S（5）,2

31、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 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 3 1 8 4 7 6 5,1 2 3 8 4 7 6 5,1 2 3 8 4 7 6 5,1 2 3 7 8 4 6 5,A（7）,B（5）,C（7）,D（7）,E（5）,F（7）,G（5）,H（7）,I（5）,J（5）,K（7）,目标,1 2 3 8 4 7 6 5,A*算法的性质,A*算法的假设 设ni、nj是任意两个节点，有： C(ni, nj) 其中为大于0的常数

32、,几个等式 f*(s) = f*(t) = h*(s) = g*(t) = f*(n) 其中s是初始节点，t是目标节点，n是s到t的最佳路径上的节点。,第6次课 2013年09月19日,中秋节,第7次课 2013年09月23日,2.4 启发式图搜索,利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。 启发信息的强度: 强, 弱 希望:引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。,上次课程回顾,A算法: f(n) = g(n) + h(n) A*算法: 在A算法中，满足条件 h(n)h*(n) A*算法的性质 设ni、nj是任意两个节点，有： C(ni,

33、nj) , 其中为大于0的常数 f*(s) = f*(t) = h*(s) = g*(t) = 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

34、, mk)f(mk) THEN f(mk):=f(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；,A*算法的性质（续1）,定理1： 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。 1）假设A搜索失败，第2步结束，open表为空 2）有路径存在，有解。niclosed ni+1closed. 3） niclosed, 结束前被扩展，ni+1加入closed或者成功。,证明：设A搜索失

35、败，算法在第2步结束open表空，closed表中的结点结束前被扩展过。 由于图有解, (n0=s,n1,n2,nk=t)表一解路径，检查该序列找closed表中结点ni，niclosed，ni+1closed，则ni+1被加到open中，则open空前，ni+1被处理过。 若 ni+1是目标结点，则搜索成功，否则它被加入到closed中，这都与假设相矛盾。,A*算法的性质（续2）,引理2.1 ： 对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)f*(s)。 证明：d*(n): s到任一节点n最短路径； e=minC（n

36、i，ni+1），g(n) g*(n) d*(n)e 故f(n) = g(n) + h(n) g(n) d*(n)e 若A不结束，d*(n)趋于无穷大，f值将增大到任意大。 参考p32,A*算法的性质（续3）,引理2.2：A*结束前，OPEN表中必存在f(n)f*(s) (n在最佳路径上的结点）。,存在一个节点n，n在 最佳路径上。 f(n) = g(n) + h(n) = g*(n)+h(n) g*(n)+h*(n) = f*(n) = f*(s),A*算法的性质（续3）,定理2： 对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。,引理2.1：A*如果不结束，则OPEN中所

37、有的n有f(n) f*(s) 与下面的 引理2.2：在A*结束前，必存在节点n，使得 f(n) f*(s) 矛盾 所以，如果A*不结束，将导致矛盾。,A*算法的性质（续4）,推论2.1： OPEN表上任一具有f(n)f*(s)的节点n，最终都将被A*选作扩展的节点。,由定理2，知A*一定结束，由A*的结束条件，OPEN表中f(t)最小时才结束。而 f(t) f*(t) f*(s) 所以f(n)f*(s)的n，均被扩展。得证。,A*算法的性质（续5）,定理3 (可采纳性定理)： 若存在初始节点s到目标节点t的路径，则A*必能找到最佳解结束。,可采纳性的证明,由定理1、2知A*一定找到一条路径结束

38、 设找到的路径s t不是最佳的（t为目标） 则：f(t) = g(t) f*(s) 由引理2.2知结束前OPEN中存在f(n)f*(s)的节点n，所以 f(n) f*(s) f(t) 因此A*应选择n扩展，而不是t。与假设A*选择t结束矛盾。得证。 注意：A*的结束条件,A*算法的性质（续6）,推论3.1： 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*算法的性质（续

39、7）,定理4： 设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n) h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。 简写：如果h2(n) h1(n) (目标节点除外)，则A1扩展的节点数A2扩展的节点数,A*算法的性质（续7）,注意： 在定理4中，评价指标是“扩展的节点数”，也就是说，同一个节点无论被扩展多少次，都只计算一次。,定理4的证明,使用数学归纳法，对节点的深度进行归纳 （1）当d(n)0时，即只有一个节点，显然定理成立。 （2）设d(

40、n)k时定理成立。（归纳假设） （3）当d(n)=k+1时，用反证法。 设存在一个深度为k1的节点n，被A2扩展，但没有被A1扩展。而由假设，A1扩展了n的父节点，即n已经被生成了。因此当A1结束时，n将被保留在OPEN中。,定理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*

41、(s) - g1(n) f*(s) g2(n) (B) 比较A、B两式，有 h1(n) h2(n) ，与定理条件矛盾。故定理得证。,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(

42、7) C(9) s(10),A(4) B(7) C(9) s(10),出现多次扩展节点的原因,在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。,解决的途径,对h加以限制 能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。 对算法加以改进 能否对算法加以改进，避免或减少节点的多次扩展。,对算法改进的条件,可采纳性不变 不多扩展节点 不增加算法的复杂性,第8次课 2013年09月26日,上次课程回顾,A*算法的性质 对有限图，如果从初始节点s到目标节点t 有路径存在，则算法A一定成功结束。 定理2：对无限图，若从初始节点s到目标节点t有路径存在，

43、则A*一定成功结束。 对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)f*(s)。 引理2.2：A*结束前，OPEN表中必存在f(n)f*(s) (n在最佳路径上的结点）,上次课程回顾 (续),定理3 (可采纳性定理)：若存在初始节点s到目标节点t的路径， 则A*必能找到最佳解结束。 定理4：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n) h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数

44、至少和A2一样多。 多次扩展节点的原因: 在前面的扩展中，并没有找到从初始节点到当前节点的最短路径. 解决的途径:,解决的途径,对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是单调的。

45、,h(ni),ni,nj,h(nj),c(ni,nj),h单调的性质,定理5： 若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。 即：当A*选n扩展时，在单调条件下有g(n)=g*(n)。,定理5的证明,设n是A*扩展的任一节点。当ns时，定理显然成立。下面考察ns的情况。 设P(n0=s, n1, n2, , nk=n)是s到n的最佳路径,假设从OPEN表中取非初始节点n扩展时，没有找到路径P,这时P中一定有节点在CLOSED中，设P中最后一个出现在CLOSED中的节点为nj，则nj+1在OPEN中。,定理5的证明（续1）,由单调限制条件，对P中任意节点ni有：

46、 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中),定理5的证明（续2）,重写上式：f(nj+1) g*(n)+h(n) 另一方面，A*选n扩展，

47、必有： f(n) = g(n)+h(n) f(nj+1) 比较两式，有： g(n) g*(n) 但已知g*(n)是最佳路径的耗散值，所以只有：g(n) = g*(n)。得证。,h单调的性质（续）,定理6： 若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。即f(ni) f(nj)。 (ni是nj的父节点),定理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

48、)+ g(ni)+C(ni, nj) C(ni, nj) f(ni) - f(nj) 0，得证。,h单调的例子,八数码问题： h(n)=“不在位”的将牌数,满足单调条件: 目标的h值显然等于0，即h(t)=0 八数码问题一次移动一个将牌，移动后有三种情况 1 （从在位移到了不在位，h值增1） h(ni) - h(nj) = 0 （从不在位移到了不在位，h值不变） -1 （从不在位移到了在位，h值减1） 又八数码问题每走一步的耗散值为1，即c(ni, nj) = 1。 所以， h(ni) - h(nj) c(ni, nj)。 所以h(n)满足单调的条件。,目标结点都在位,对算法加以改进,一些结论

49、（推论）： OPEN表上任一具有f(n) f*(s)的节点n定会被A*扩展。 A*选作扩展的任一节点，定有f(n)f*(s)。 上面两个推论是改进A*算法的理论基础。,改进的出发点（1）,A*算法，按照结点的f值从小到大排序OPEN表中的结点。 以f*(s)界将OPEN表划分为两个部分： 1) f值小于f*(s)的节点（称为NEST) 2) f值大于等于f*(s)的节点,改进的出发点（2）,OPEN = ( ),f*(s),f值小于f*(s)的节点,f值大于等于f*(s)的节点,推论：A*选作扩展的任一节点，定有f(n)f*(s)。 fm：到目前为止已扩展节点的最大f值，用fm代替f*(s),

50、一个例子：,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),改进的出发点（3）,由前面的推论： OPEN表上任一具有f(n) f*(s)的节点n定会被A*扩展。（NEST部分） 因此，NEST中的节点，不论是先扩展还是后扩展，在A*结束前总归要被扩展。因此，如果改变NE

51、ST中结点的次序，不会影响到算法扩展结点的个数。 对NEST中的节点，按照f(n)=g(n)（即令h0，是单调的）次序扩展，既可避免重复扩展结点，又不会增加扩展结点的个数。,修正过程A,1, OPEN:=(s), f(s)=g(s)+h(s), fm:=0; 2, LOOP: IF OPEN=( ) THEN EXIT(FAIL); 3, NEST:=ni|f(ni)fm IF NEST ( ) THEN n:=NEST中g最小 的节点 ELSE n:=FIRST(OPEN), fm:=f(n); 4, , 8: 同过程A。,前面的例子：,OPEN表,CLOSED表,fm,s(0+10),s(

52、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),评价函数的启发能力（p46）,A算法的启发能力和选择启发函数h(n)的关系？,评价函数的启发能力（1）,一般来讲，启发能力越强，搜索效率越高。有时，如果选用不满足A*算法的h函数，虽然会牺牲找到最佳解的可能，但可使启发能力得到改善。有利于求解一些较难的问题。 以八数码问题为例。,初始状态,目标状态,评价函数的启发能力（2）,选用启发函数

53、h(n)=p(n)时，仍不能估计出交换两个将牌位置难易程度的影响。 引入S(n)分量，反映状态n时的将牌排列次序的计分值 S(n)的计分值的计算： 1）对于非中心格中的数码，如果其后（顺时针）紧跟的数码和目标状态相应将牌的顺序相比不一致，则令Si(n)=2，否则Si(n)=0。 2）若中心格无将牌，则令Si(n)=0，否则令Si(n)=1。 3）S(n)为全部Si(n)之和，即S(n)= Si(n)。,为每一个将牌与其目标位置之间的距离和,评价函数的启发能力（2）,2 1 6 4 8 7 5 3,2 1 6 4 8 7 5 3,g(n)=1, h(n)=p(n)+3S(n),1 2 3,4 5

54、,8 7,7 6,评价函数的启发能力（2）,2 1 6 4 8 7 5 3,2 6 4 1 8 7 5 3,g(n)=1, h(n)=p(n)+ 3S(n),1 2 3,4 5,8 7,7 6,定义新的启发函数(1),定义启发函数h(n)= p(n)+ 3S(n)，则f(n)= g(n)+ p(n)+ 3S(n). f(n)值小的节点，确能反映该节点越有希望处于到达目标节点的最佳路径上。 使用新定义的f(n)函数搜索过程如下图，图中圆圈中的数字是f函数值，不带圈的数字表示扩展顺序。,h(n)=p(n)+3S(n)的搜索树,h(n)=p(n)+3S(n)的搜索树,注释：S(n)计算：顺一个方向检查，某一将牌的 后继与目标状态顺序比较，例如2后面应为3，如果是其他， 则为不一致,定义新的启发函数(2),该例子定义了一个不满足A*条件的h函数，但刚