当前位置:首页 >> 理学 >>

人工智能第三章


第三章 产生式系统的搜索策略
回溯策略 图搜索策略:无信息的图搜索 启发式的图搜索

1

7/4/2015

产生式系统的费用
计 算 费 用

产生式系统费用 控制费用

规则应用费用 0 无信息 信息(知识)
7/4/2015

完备信息

2

3.1 回溯策略

3

7/4/2015

一、回溯算法BACKTRACK
算法中用到的部分变量、常量、谓词、函数:
?

? ?

?

变量: DATA,RDATA:状态变量 RULES, PATH : 表变量 常量: NIL: 空表 ----LISP语言中的常量,也可用() 谓词: TERM(DATA): DATA满足结束条件时,为真 DEADEND(DATA):DATA不在解路上,为真(往下到达目标的可能性来定义这个谓词:若从 DATA当前状态往下走到达目标的可能性很小时,则放弃这个状态 ) NULL(X): 表X为空表时,为真 函数: APPRULES(DATA): 将DATA所有可用规则进行排序所得到的表 FIRST(X): 取表X的头 TAIL(X): 取表X的尾 CONS(E, X):将E加入表X前 7/4/2015

4

BACKTRACK过程
Recursive Procedure 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←R(DATA); 8. PATH←BACKTRACK(RDATA); 9. if PATH=FAIL,go LOOP; 10. return CONS(R,PATH).

5

7/4/2015

带来的问题及解决方案 ⑴若DEADEND定义不好,则无限产生新的非终止的状态描述。 (既不成功又不失败的节点) 解决方案:设置门槛数,即搜索深度BOUND,当递归调用超过 这个深度时return FAIL,引起回溯。 ⑵ 程序中只有DATA和RDATA,回溯过程中将生成的状态都丢弃了, 有可能陷入循环,重复地产生一系列非终止状态。 (实质属于情况(1)) 解决方案: 在过程中保存一个状态描述表DATALIST:记录从初始状态到当 前状态路径上的所有状态----递归变量变成DATALIST,取表头为 DATA 。 加比较:当产生新状态RDATA时,比较是否为DATALIST中的一 个状态(在这个表中),若是,则return FAIL,引起回溯,选择 其它的Rule。

6

7/4/2015

二、回溯策略例……四皇后问题
?

四皇后问题:4枚皇后放在4?4的国际象棋棋盘上,如何放置使得 它们不能相互俘获。 俘获:同行;同列;同对角线

其中a,b满足目标条件, c,d,e为不可能构成满足目标条件的中间状态。

7

7/4/2015

综合数据库:以状态为节点的有向图 状态:4?4矩阵 初始状态: 空矩阵 规则:Rij:if i=1时,矩阵中无皇后标志,或4 ? i >1时,矩阵的i-1行 有一个皇后标志,then在矩阵的第i行第j列放一个皇后标记 结束条件:TERM为真?矩阵中有4个皇后标志,且不能相互俘获 控制策略:回溯 DEADEND(DATA): DATA中存在1对皇后相互俘获,为真 APPRULES(RULES): Rij排在Rik之前?j<k

8

7/4/2015

?
1 ? 2 3 ? ? 5 11 6 7 8 9 ? 17 12 25 26 27 ? ? 18 4 ? 10

19

?

20
?

21

22

23

?
?

?

?

24 ? ?

?
?

9

13 7/4/2015 14 15

16
28

NIL

四皇后问题

Rij排在Pik之前?j<k

存在的问题:回溯的次数很多,22次回溯。 原因:没有关于问题的探索性信息指导规则排序。 解决方法之一:在规则排序过程中使用一些探索性信息, 减少回溯次数,提高算法效率. 例:使用函数 diag(i, j)来修改APPRULES(RULES) diag(i, j):通过单元(i,j)的最长对角线的长度. 修改后的 APPRULES(RULES): if diag(i,j)<diag(i,k),then Rij排在Rik前. if diag(i,j)= diag(i,k),then与以前相同

10

7/4/2015

?

请用回溯搜索策略 BACKTRACK 求解四皇后 问题,要求规则排序使用对角函数 diag(i, j)。 如果diag(i, j)<diag(i, k),则在排序中把Rij放 在Rik的前面;如果diag(i, j)=diag(i, k),j<k,则 把Rij放在Rik的前面。其中diag(i, j)定义为通过 单元(i, j)的最长对角线的长度.

11

7/4/2015

三、BACKTRACK算法的修改与补充
Recursive Procedure BACKTRACK (DATA) s0 DATA←FIRST(DATALIST); if MEMBER(DATA,TAIL(DATALIST) s1. if TERM(DATA),returns0’ NIL ; return FAIL; s2.if DEADEND(DATA),return FAIL; if LENGTH(DATALIST)>BOUND, s3.RULES←APPRULES(DATAs2’ ); return FAIL; s4. LOOP:if NULL(RULES);return FAIL; s5. R←FIRST(RULES); s7’ RDATALIST←CONS(RDATA,DATALIST ); s6. RULES←TAIL(RULES ); s8 PATH←BACKTRACK1(RDATALIST) s7. RDATA←R(DATA) s8. PATH←BACKTRACK(RDATA); s9. if PATH=FAIL,go LOOP; s10. return CONS(R,PATH)
DATA 换成 DATALIST

12

7/4/2015

两层以上的回溯
× ×

×
× ×

13

7/4/2015

3.2 图搜索策略

14

7/4/2015

一、相关概念
?

有向图 :G=(P,A),P:点集 A:弧集 弧:两点间有方向的线。

如果有一条弧从节点ni出发指向nj;则节点nj称为节点 ni的子节点,节点ni称为节点nj的父亲节点. 对于产生式系统, 节点:用状态描述标记 弧:用规则标记 假定图中的每一个节点只有有限个子节点。

15

7/4/2015

?

路:节点序列(ni0, ni1,…,nik)称为从节点ni0到节点nik 的一条长度为k的路径,其中,对于j=1,…,k,每 一个nij都是nij-1的子节点。 如果存在一条从节点ni到节点nj的路径,则节点nj称 做是从节点ni出发可达到的,节点nj称做节点ni的后裔, 节点ni称做是节点nj的祖先。

?

解路径: 从初始节点到一个满足终止条件节点的 路径。 图搜索策略把寻找从初始状态描述到目标描述的 规则序列问题转化成寻找有向图的解路径问题.
7/4/2015

16

?

有向树:每一个节点最多只有一个父亲的有向图. 根节点:有向树中没有父节点的节点 叶节点:有向树中没有子节点的节点 有向树中节点的深度: 1) 根节点的深度是0, 2)其它节点的深度等于它父节点的深度加1。

17

7/4/2015

加权有向图(权图): 每条弧线上都有使用费用(正数)的图。 例:从节点ni到节点nj的有向孤的费用:C(ni, nj) 路径的费用:路径上所有弧费用的和. 两节点间具有最小费用的路径:是此两节点间 所有弧费用的费用总和最小的一条路。 最佳解路径:费用最小的解路径。
?

18

7/4/2015

? ? ?

隐含图:由部分节点和一组其它节点生成规则所确定 的图. 图搜索控制策略的目标:从隐含图出发生成一个部分 明确的图,使该明确图中含有目标节点. 图搜索非形式定义 假定:所有隐含图中有向弧的费用大于某一个小的正 数ε 问题:求隐含图中初始节点s到目标节点集{ti}中任意 成员的一条具有最小费用的解路径。
7/4/2015

19

二、一般的图搜索过程GRAPHSEARCH

? ? ?

OPEN表:未扩展的节点 CLOSED表:已扩展或正在扩展的节点 G:搜索图,动态变化,部分明确的图

20

7/4/2015

Procedure GRAPHSEARCH
1.G←{s}, OPEN ←(s). 2.CLOSED ←NIL. 3.LOOP:IF OPEN=NIL,THEN FAIL. 4. n ← FIRST(OPEN),OPEN ←TAIL(OPEN),CONS(n, CLOSED) . 5. IF TERM(n),THEN 成功结束 (解路径可通过追溯G中从n到s的指针获得)。 6. 扩展节点n, 令M={m︱ m是n的子节点,且m不是n的祖先} , G ←G ∪M 7. (设置指针,调整指针)对于m?M, (1)若m?CLOSED, m?OPEN, 建立m到n的指针,并CONS(m, OPEN). (2)(a)m?OPEN, 考虑是否修改m的指针. (b)m?CLOSED,考虑是否修改m及在G中后裔的指针。 8. 重排OPEN表中的节点(按某一任意确定的方式或者根据探索信息)。 9. GO LOOP
7/4/2015

21

?

?

?

Note1:算法结束时, OPEN:树的叶节点 CLOSED:1)非叶节点 2)被选来扩展但无后裔的叶节点 Note2:如果搜索的隐含图是一棵树, 步骤6和步骤7得以简化: step 6:扩展节点n, 令M={m︱ m是n的子节点} , G ←G ∪M step 7:建立m到n的指针,并CONS(m, OPEN). Note3:如果搜索的隐含图不是树,则需确定是否需要指针修改。
7/4/2015

22

3.3 无信息的图搜索过程
若在GRAPHSEARCH的步骤8中对OPEN表中 节点的排序不使用关于问题的探索性信息,则 必须任意规定一种排序方式,所得到的搜索过 程叫作无信息的。 一般有两种无信息的图搜索过程:深度优先搜 索与宽度优先搜索. 在人工智能中,一般说来人们对无信息的过程 不感兴趣.
23
7/4/2015

无信息的图搜索过程
?

?

?

深度优先搜索:排列OPEN表中的节点时按它 们在搜索树中的深度递减排序 。深度最大的 节点放在表的前面,深度相等的节点以任意方 式排序。 宽度优先搜索:在排列OPEN表中节点时按它 们在搜索图中的深度递增顺序,深度最小的节 点放在表的前面 。 8-数码问题例子
7/4/2015

24

A B D E C F G D B

A C E F G D B

A C E F G

H I J KLM N O H I J KLM N O H I J KLM NO A B C E F G D
7/4/2015

A B E C F G D B

A C E F G

25

D

H I J KLM N O H I J KLM N OH I J KLM N O

一个简单二叉树的宽度优先搜索过程
A
B D C E F G D B

A
C E F G D B

A
C E F G D B

A C E F G

在每一个阶段,下一个要扩展的节点由箭头指示 出来。
26
7/4/2015

3.4 启发式图搜索过程
无信息的搜索方式需要产生大量的节点才能找 到解路径。这些节点都需要在内存中保存起来。 由此可见无信息搜索方式所需存储空间是相当 大的。而实际上计算机所能提供的存储总是有 限的,因此我们必须寻找效率更高的搜索方法。

27

7/4/2015

启发式搜索
?

?

启发式信息:用于帮助减少搜索量的与问题有 关的信息或知识。 启发式信息用在GRAPHSEARCH的步骤8中 对OPEN表中的节点进行排序,把最有希望的 节点排在最前面,使搜索图沿着有利于获得解 的方向扩展。 启发式搜索:使用启发信息指导的搜索过程叫 做启发式搜索。
7/4/2015

28

? 启发信息强,可以降低搜索的工作量,但可能导致找 不到最优解; ? 启发信息弱,一般会导致搜索的工作量加大,极端情 况下演变为盲目搜索,但有可能找到最优解。 我们希望,通过引入启发知识,在保证找到最佳解的 情况下,尽可能减少搜索范围,提高搜索效率。

29

7/4/2015

估价函数
使用启发信息的一种重要方法是采用估价函数。 ? 估价函数例:任意节点与目标节点的距离度量;棋盘上 对局势的度量;一个节点处在最佳路径上的概率等等。 ? 估价函数:定义在状态空间上的实值函数。 用f(n)表示节点n的估价函数: 1. f(n)表示从起点到目标,经由节点n最小费用路径上 费用的估计。 (在搜索图中,接近解路径的节点有较低的函数值) 2. 以估价函数f的递增次序排列OPEN表中的节点: 估价函数低的排在前; 具有相等函数值的节点以任意次序排序。 7/4/2015
?

30

例:八码难题
估价函数:f(n)=d(n)+W(n) 其中 d(n):节点n在搜索树中的深度 W(n):与n对应的状态描述中偏离目标的棋子的个数。 例:利用估价函数f(n)=d(n)+W(n)正向搜索八数码难题 初始状态 目标状态
?

2 8 3 1 6 4 7 5
7/4/2015

1 2 3

31

8 4 7 6 5

练习:
?

利用估价函数f(n)=d(n)+W(n)反向搜索上例八数码难 题。指出反向搜索和正向搜索在什么地方相遇。 (左优先、浅层的优先)

32

7/4/2015

估价函数的选择对搜索结果起着重要作用
如果估价函数没能识别出真正有希望的节点, 则可能延长搜索过程,扩展较多的节点。 ? 如果估价函数过高地估计了所有点的希望值, 则也同样导致扩展大量的节点. 例如在八数码问题题例中,如果让f(n)=d(n), 则得到宽度优先搜索。
?

33

7/4/2015

一些概念
K(ni, nj) :隐含图中节点ni到nj最小费用路径的实际费用。 若ni到nj无路,则函数K(ni, nj) 无定义。 ? h*(n):设{ti} 是目标节点集合,定义 h*(n)=mini{ K(n, ti) } 表示隐含图中从n到目标节点的最小费用路径的费用。 对不能到达目标节点的节点n,h*(n)无定义。 最佳解路径:从n到目标节点的任何费用为h*(n)的路径。 ? g*(n): g*(n)=K(s,n) 表示隐含图中从初始节点s到n的最佳解路径的费用。 ? f*(n):f*(n)=g*(n)+h*(n) 表示隐含图中,通过节点n,从s到目标节点的最佳解路径的费用。 当n是从初始节点到目标节点t的最佳解路径上的节点时, f*(n)= f*(s)=f*(t)=h*(s)。
?

34

7/4/2015

A算法和A*算法
?

A算法: 使用估价函数f(n)=g(n)+h(n) 排列OPEN表中节点顺序的
GRAPHSEARCH算法。 其中, g(n):对g*(n)的一个估计 是当前的搜索图G中s到n的最优路径费用 g(n)≥g*(n) h(n):对h*(n)的估计,称为启发函数。

Note:若h(n)=0,g(n)=d,则 f(n)=d,为宽度优先。
?

A*算法:对任何节点n都有h(n)≤h*(n)的A算法。
7/4/2015

35

3.5 A*算法的可采纳性

?

定义:如果一个搜索算法对于任何具
有解路径的图都能找到一条最佳路径, 则称此算法为可采纳的。 可以证明:A*算法是可采纳的(如果解 路径存在,A*一定由于找到最佳解路径 而结束)

36

7/4/2015

A*算法的可采纳性
定理1 GRAPHSEARCH对有限图必然终止。 证明:GRAPHSEARCH算法将在第3步将OPEN表中的 节点用光而结束;或在第5步,找到目标节点而结束。 在算法的每一次循环中,都要从OPEN表中删除一个 节点,若是目标节点,则再第5步算法结束,否则将 该节点的某些后继加到OPEN表中。 对有限图来说, OPEN表中节点个数是有限的,因 此,若算法不在第5步成功终止,则一定在第3步因 OPEN表中的所有节点全部取光而终止。

37

7/4/2015

A*算法的可采纳性
引理1 若A*不终止,OPEN表中节点的估价函数值可以 无限变大。 证明:设n是OPEN表中的任意节点,d*(n)是隐含图中从s 到n的最短路的长度,因为图中每条弧的费用都大于某一 个小的正数e, 于是有 g*(n)≥d*(n) ·e, 又g(n)≥g*(n)≥d*(n) ·e , f(n)= g(n)+h(n) ,且h(n) ≥0 因此 f(n)≥ g(n)≥ d*(n) ·e 若A*不终止,OPEN表中节点的d*值会不断增大,因此f 值也会不断增大。

38

7/4/2015

A*算法的可采纳性
定理2 若存在s到目标的解路径,则算法A*终止前的任何 时刻,OPEN表中总存在一个节点n’, n’在从s到 目标的最佳解路径上,且满足f(n’) ≤f*(s) 证明:设P:n0,n1,……,nk是一条最佳解路径,其中, nk是目标点,n0=s. 在A*结束之前,从左向右扫描序列P,令n’是P中第一 个在OPEN表中的节点。 (这样的n’是存在的:因为开始n0在OPEN表中,算法结束 前,若扩展ni,ni≠ nk,则ni+1在OPEN表中)。

39

7/4/2015

A*算法的可采纳性……定理2
因n’的所有祖先都在CLOSED表中,所以(n0,n1,……, n’)

是已被搜索出的从s到n’的最佳路,故 g(n’)= g*(n’)
又由A*算法定义知:h(n’)≤h*(n’), 故 f(n’)= g(n’)+ h(n’)≤g*(n’)+h*(n’)= f*(n’) 而对最佳路上任意一点n’,有:f*(n’)= f*(s) 因此,f(n’)≤f*(s) 证毕。

40

7/4/2015

A*算法的可采纳性
定理3 若存在解路径,则A*算法必终止。 证明:反证。若算法A*不终止, 由引理1知,OPEN表中任意节点的f值随着算法

A*的运行可以任意增大。
由定理2知,算法A*终止前的任何时刻,OPEN

表中总存在一个节点n’, 使得f(n’) ≤f*(s) 。
矛盾。
41
7/4/2015

A*算法的可采纳性
推论 OPEN表中的任一满足f(n)<f*(s)的 节点n,最终将被算法A*选作扩展节点。 证明: 若A*算法停在第3步,则OPEN表中的任一节点都被 扩展; 若A*算法停在第5步,即找到目标t而结束,下面用 反证法。假设存在OPEN表中满足f(n) < f*(n)的节点n, 而未选n为扩展点,因对目标t,有f(t) ≥ f*(s),而f(n) < f*(s),故f(n)< f(t),因此A*一定选n扩展而不选t,与A* 结束在点t矛盾。 证毕。

42

7/4/2015

A*算法的可采纳性
定理4 算法A*是可采纳的。 (若解路径存在,A*一定找到最佳解路径而终止). 证明:由定理3知,算法A*必终止。 由定理2知,算法A*终止前的任何时刻,OPEN 表中总存在一个节点n’, 使得f(n’) ≤f*(s),故算法 A*不会终止在第3步,因此必终止在第5步,因找到 一个目标节点而结束。 设t是算法A*找到的目标点, (下面用反证法证明t 在最佳解路上)
7/4/2015

43

A*算法的可采纳性……定理4

若t 不在最佳解路径上,则 f(t) = g(t)+h(t)=g(t) >f*(s) 由定理2,A*算法终止前,OPEN表中总有一点n’, 使 f(n’)≤f*(s),因此 f(n’)<f(t);在OPEN表的排序 中,节点n’应排在节点t的前面。 因此,算法A*算法终止前应选n’去扩展,而不会选t, 与算法A*终止于t矛盾。 故原假设不对,s到t是最佳路。 44 证毕 7/4/2015

A*算法的可采纳性
定理5 算法A*选择的任意扩展点n都有f(n)≤f*(s)

证明:
若n是目标点,由定理4,f(n)=f*(s) 。 若n不是目标点,由定理2 ,A*算法终止前, OPEN表中总有点n’,使 f(n’)≤f*(s)。 若n=n’,则f(n)= f(n’)≤f*(s)。 否则,根据OPEN表按f值递增排序,此时, 算法A*选择n而没有选择n’,必有: f(n)≤ f(n’),故7/4/2015 f(n) ≤f*(s) 证毕。 45

3.6 A*算法的比较
定义 设A1和A2是两个 A*算法,分别使用如下两 个估价函数: f1(n)=g1(n)+h1(n) f2(n)=g2(n)+h2(n) 其中,h1(n)和h2(n)是h*(n)的两个下界.若对于 所有的非目标节点n,都有h2(n)>h1(n),则称算 法A2比算法A1有较多的信息.
46
7/4/2015

A*算法的比较
讨论:启发函数的启发能力在于它所具有的 启发性信息。 1. 当h(n)≡0时,反映了启发函数完全没有启 发信息,要扩展较多的节点. 2. 在具有可采纳性的前提下, 0≤h≤h*,h* 定出了h的上界,当h越接近h*时,它的启发 能力就越大.
47
7/4/2015

A*算法的比较
例 八码难题的A*算法的比较.

图3.7的估价函数:f1(n)=d(n),h1(n)≡0,采用宽度优
先搜索 ; 图3.8的估价函数:f2(n)=d(n)+w(n),h2(n)≡w(n).

对于所有非目标节点,有h2(n)>h1(n),因此,图3.7所
用算法不但比图3.8所用算法有较多的信息,而且扩展的节 点数要少。

48

7/4/2015

A*算法的比较 ……定理6
定理6 如果A1和A2是两个A*算法,算法A2比A1有 较多的信息,且它们搜索同一个隐含图。若该图存 在解路径,当这两个算法终止时,A2所扩展的每 一节点也必被A1所扩展,即: A2扩展的节点数≤A1扩展的节点数 证明:设n是A2所扩展的任一节点, 往证n也被A1扩展。 用d(n)记n在A2搜索树中的深度,对d(n)使用 49 数学归纳法。 7/4/2015

A*算法的比较……定理6
当d(n)=0时,则n=s。命题显然成立:若s不是目标节 点,这两个算法都必将扩展s ;若s是目标节点,这两个算 法都不必扩展s. 假设d(n) ≤k时成立,即A2搜索树中深度≤k的所有节点都 被算法A1扩展. 设d(n) =k+1,往证A2扩展的深度为k+1的节点也被A1 扩展。 因节点n被A2扩展,由于n的祖先点被A2扩展,根据归纳 假设,节点n的在A2搜索树中的所有祖先都被算法A1所扩 50 展. 7/4/2015

A*算法的比较 ……定理6
因此,节点n在A1的搜索树中,且在A1的搜索树 中存在一条从s到n的路。由于A2搜索树中点n之 前的树是A1搜索中点n之前的树的子树,因此有 g1(n) ≤ g2(n) 又因为h1(n) <h2(n),所以f1(n) <f2(n). 由于n被A2扩展,由定理5知: f2(n) ≤ f*(s) 故f1(n) <f2(n) ≤ f*(s) . 由推论知,点n必被A1选去扩展,归纳完成。
51
7/4/2015

3.7 单调限制
?

GRAPHSEARCH每当扩展一个节点n时,n的某些后 继可能已经在OPEN表中或CLOSED表中,因此算法 需要调整这些节点以及它们的后裔的指针。这种调整 涉及到通向一个节点的路径的费用的比较,增加了程 序的计算费用.测试一个节点是否以前曾经产生过的 计算费用更高.如果我们对启发函数增加某种限制, 使得算法A*选出一个节点扩展时,就已经发现了通向 这个节点的最佳路径,这样对节点是否已经产生过的 测试和指针的调整都不必进行了,这种限制当然是提 高算法A*效率的有效方法.

52

7/4/2015

3.7 单调限制
定义 如果启发函数h对任何节点ni和nj,只要nj
是ni的后继,都有

h(ni)-h(nj)≤c(ni, nj)
h(t)=0 (t是目标节点) 则称启发函数h满足单调限制.

53

7/4/2015

单调限制的性质……定理7
定理7 如果A*算法的启发函数h满足单调限制, 则当算法A*选择节点n扩展时,就已经发现了通 向节点n的最佳路径,即g(n)=g*(n). 证明:设n是算法A*选出扩展的任一节点。 ?若n=s,则g(n)=g*(n)=0,算法A*已发现通向s 的最佳路径. ?若n≠s,设序列P=(s=n0,n1,…,nk=n)是隐含 图中从s到n的一条最佳路径(不知道是否在A*的搜 7/4/2015 索树中)。

54

单调限制的性质……定理7
若P在当前树中,则得证。 否则,当算法A*选择n进行扩展时: 设P中从n0开始,串n0,…,nj都在 CLOSED表中,即nj是P中从左向右CLOSED表 中的最后一个节点,且 nj ≠n. 此时,nj的后继节 点nj+1在OPEN表中.
55

7/4/2015

单调限制的性质……定理7
由已知h(n)满足单调限制,对任意i=0,…,k-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)

56

7/4/2015

单调限制的性质……定理7
因为j≤k-1,所以j<k 利用传递性,我们得到 g*(nj+1)+h(nj+1) ≤ g*(nj+2)+h(nj+2) ≤ ... ≤ g*(nk)+h(nk) 由P是从s到nk的最佳路, (n0,n1,…,nj+1)是 最佳路,且已被搜索出,所以:g(nj+1)= g*(nj+1) 所以 f(nj+1) ≤g*(nk)+h(nk)= g*(n)+h(n)
57
7/4/2015

单调限制的性质……定理7
即,f(nj+1) ≤g*(n)+h(n) 因A*算法选择n扩展时,OPEN表中有nj+1, 故f(n) ≤ f(nj+1) 。 因此, g (n)+h(n)=f(n) ≤ g*(n)+h(n) 所以:g(n) ≤ g*(n). 再由g*(n) ≤ g(n) ,知g(n) = g*(n) 。 证毕。
58
7/4/2015

单调限制的性质……定理8
定理8 如果A*算法启发式函数h满足单调限制, 则A*所扩展的节点序列的估价函数值是非递减的.

证明:设ni和ni+1是A*扩展的节点序列中任意二相邻 节点, ni在前 。 若扩展ni时, ni+1在OPEN表中,显然: f(ni) ≤ f(ni+1)
59
7/4/2015

单调限制的性质……定理8
若扩展ni时, ni+1不在OPEN表中,而A*扩展完 ni后,立刻扩展ni+1 ,故一定是ni+1为ni的后继, 继而加到OPEN表中。于是,扩展ni+1时有: f(ni+1)=g(ni+1)+h(ni+1) = g*(ni+1)+ h(ni+1) (由定理7) =g*(ni)+c(ni,ni+1)+h(ni+1) =g(ni)+c(ni,ni+1)+h(ni+1) (由定理7) 由单调性, c(ni,ni+1)+h(ni+1) ≥ h(ni) 所以 f(ni+1) ≥ g(ni)+h(ni) = f(ni) 证毕。
60
7/4/2015

A*算法的小结
1. A*算法搜索隐含图时,有解必停,且必停在最 佳解路上;

2. 在满足h (n) ≤h*(n)的前提下,启发函数越大,
其所包含的启发信息越多,所扩展的节点越少;

3. 若启发函数满足单调限制,则每走一步都在最
佳解路上,且估价函数不减,简化了算法的第7 步(调整指针).
61
7/4/2015

3.8 算法A的启发能力

定义 设A1和A2是两个启发式算法,它们分别使 用估价函数f1和f2,如果在寻找解路径的过程

中,A1所用的计算费用比A2少,则称A1比A2
有较强的启发能力,也可以称估价函数f1比f2 有较强的启发能力.
62

7/4/2015

算法A的启发能力
影响算法A启发能力的三个重要因素:

(1)算法A所找到的解路径的费用。
(2)算法A在寻找这条解路径的过程中所需要

扩展的节点数。
(3)计算启发函数所需要的计算量。

63

7/4/2015

算法A的启发能力
h(n) ≤ h*(n) 保证了A*的可采纳性,可采纳性 可能意味着算法需要扩展更多的节点,使总 的费用提高。 Note1:若能保证高效(增强算法的启发能力), 则牺牲可采纳性是可取的。 例:八码难题 (a) h(n)=W(n):不在位数码的个数 问题:每个数码离开目标的距离不一致, 说明不了复位困难程度。
64
7/4/2015

(b) h(n)=P(n):每个数码离“家”距离的和。 问题:不能说明离“家”近,但离空格远的数码 复 位的难易。

1 2 4 8 3 7 6 5
初始状态
7/4/2015

1 2 3 8 4 7 6 5
目标状态

65

2 8 3 1 6 4 7 5
初始状态

1 2 3 8 4 7 6 5
目标状态

下面给出该八数码问题取不同启发函数,应用A*算法求 得最佳解时所扩展和生成的节点数。

66

7/4/2015

67

7/4/2015

(c) h(n)=P(n)+3S(n) P(n):每个数码离“家”距离的和。 S(n):记分函数:

68

7/4/2015

? ?

对于中心方格,若有数码,记1分,否则记0分。 对非中心的外围上的数码,沿顺时针方向依次检查每个数码:若 此数码与其后面的数码与目标中顺序不同(若此数码后面的数码 不是它在目标状态的后继),则记2分,否则记0分。

1 2 3 8 4 7 6 5 7 5 3 八数码难题的初始状态与目标状态 2 1 6 4 8
P(n)=1+l+ 2+l+1+3+0+2= 11 S(n)=2+2+2+2+2+2+2+l=15 所以:h(n)= P(n)+ 3S(n)=11 +3×15=56 7/4/2015

69

70

7/4/2015

?该例子给了一个不满足A*条件的h函数。从图上可以看出,启发效果 非常的好,对于需要18步才能完成的8数码问题,几乎没有扩展什么 多余的节点,就找到了解路径。

?这里所用的方法一是组合两个不同的启发函数;二是采取加权的方 法(这里对S(n)加权为3),来加大S(n)的作用。
?这样得到的启发函数由于不满足A*条件,因此不能保证找到问题的 最佳解,但往往可以提高搜索效率,加快找到解的速度。由于这样的 启发函数还是反映了被评估节点到目标节点路径耗散值的多少,算法 虽然不能一定找到最优解,但一般来说,找到的也是一个可以被接受 的满意解。很多情况下,满意解就足够了,最优解并没有什么特殊的 意义,二者可能相差很少,但却使得问题简单了很多。值得指出的是, 该例子所得到的解,刚好是一个最优解。
7/4/2015

71

算法A的启发能力
Note2:可控制g和h在搜索中所起的作用:

有时,把估价函数写成:f=g+wh(w 为正数)的形式
w很小时,强调宽度优先 w很大时,强调启发分量 经验表明,让w的值与搜索树中节点的深度成相反方向 变化时,搜索效率往往会有所提高.在深度较小时,搜 索主要依靠启发部分,随着深度的增加,宽度优先部分 的作用逐渐增大,以保证最终能找到一条解路径.一般w

72

与深度成反比。

7/4/2015

3.9 有关算法
正向搜索:从初始节点到目标的搜索

反向搜索:从目标节点到初始节点的搜索
双向搜索:正向和反向搜索的结合

搜索需要产生的节点数
宽度优先搜索,使用双向搜索要优越许多 对于启发式搜索,评价单向搜索和双向搜索的优劣 很复杂,双向搜索使用不当可能是单向搜索量的二倍.
73
7/4/2015

3.9 有关算法
分阶段搜索:为了完成搜索过程,可对搜索图

进行修剪,释放出一部分存储空间。
把OPEN表具有最小f值的一些节点打上标记,

记住这些节点和通向这些点的最佳路径,删去
搜索图其余部分。 然后恢复节点和路径,重新开始搜索。 分阶段搜索并不能保证找到一条解路径。
74
7/4/2015

3.10 启发能力的度量
? ? ?

搜索方法的启发能力主要依赖于给定问题的具体 因素。 判断启发能力的强弱主要是凭经验而不是凭计算。 某些实现上的度量是可计算的。这些度量不能完 全决定一个算法的启发能力,在比较各种搜索算 法的优劣时是很有用的。

75

7/4/2015

启发能力的度量……渗透度
渗透度是对一个搜索算法的搜索性能的度量,表 示搜索集中指向某个目标的程度,而不是在无关 的方向上徘徊。 定义为: P=L/T 其中,L是算法发现的解路径的长度, T是算法在寻找这条解路径期间所产生的节点 数(不包括初始节点,包括目标节点)
76
7/4/2015

启发能力的度量……渗透度
例 图3.9的八数码问题,L=18,T=43, 渗透度:P = L / T = 18 / 43 = 0.42 若一个算法每次选取的节点都在解路径上,则 L= T ,P=1; 一般搜索的渗透度P<1 ; 无信息的搜索P<<1; 渗透度大,所产生的搜索树向纵深发展; 渗透度小,所产生的搜索树沿水平方向发展。
7/4/2015

77

启发能力的度量……渗透度
搜索算法的渗透度取决于问题的难度和算法的效率。 当最佳解路短时,可能有较高的渗透度; 当最佳解路长时,算法产生节点的数目将以更快的 速度增加,可能有较低的渗透度。 渗透度有时并不能很好地反映搜索向目标方向发展 的集中程度。
78
7/4/2015

启发能力的度量……有效分枝系数
有效分枝系数就是一棵搜索树的平均分枝数. 设搜索树的深度是L,算法所产生的总节点数为T, 有效分枝系数是B,则有 B+B2十…+BL=T 或 B(BL-1)/(B-1)=T
79
7/4/2015

启发能力的度量……有效分枝系数
图3.12给出了不同L值B与T的关系
当L=18,T=43时,

搜索树的有效分枝系数B大约为:
1.08.

80

7/4/2015

启发能力的度量……有效分枝系数
有效分枝系数与路径的长度无关,可以利用这一 事实预测不同深度的搜索所需产生的节点个数。

例 若用估价函数f=g+p+3s去解决一个复杂的八数 码问题.
设解路径长度L=30, 有效分枝系数 B=1.08. 则由图3.12知,所需产生节点的个数大约为l20
81
7/4/2015

启发能力的度量……有效分枝系数

图 3.13 给出了在不同的 B 值下渗透度随路径长 度的变化曲线. 由图中可以看出,同样的有效分枝系数,渗透 度随路径的深度下降.

82

7/4/2015

本章小结

? ? ? ?

回溯算法BACKTRACK 图搜索算法GRAPHSEARCH 启发式图搜索过程 A*算法的可采纳性

83

7/4/2015

小结
? ? ? ?

A*算法的比较 单调限制及性质 算法A的启发能力 启发能力的度量

84

7/4/2015

度量问题求解的性能
完备性:当问题有解时,这个算法是否能保证 找到一个解? 最优性:该搜索策略是否能找到最优解?

时间复杂度:找到一个解需要花费多少长时间?

空间复杂度:执行搜索的过程中需要多少内存?
85
7/4/2015


相关文章:
人工智能课后答案 第三章.doc
人工智能课后答案 第三章 - 1.基于谓词逻辑的机器推理方法:自然演绎推理,归结
人工智能第三章(3).pdf
人工智能第三章(3) - 2013-10-24 规则演绎系统 消解反演方法的特点
人工智能第三章_图文.ppt
人工智能第三章_计算机软件及应用_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档人工智能第三章_计算机软件及应用_IT/计算机_专业资料。第三章 产生式...
人工智能,第三章2_图文.ppt
人工智能,第三章2 - 大学计算机类进阶课人工智能第三章ppt课件... 《人工
人工智能第三章_图文.ppt
人工智能第三章 - 3.4 归结演绎推理 归结演绎推理是一种基于Robinson
北京交通大学人工智能第三章_图文.ppt
北京交通大学人工智能第三章_计算机软件及应用_IT/计算机_专业资料。北京交通大
人工智能第三章._图文.ppt
人工智能第三章. - 第三章 产生式系统的搜索策略 回溯策略 图搜索策略:无信息
人工智能第三章 知识与知识表示_图文.ppt
人工智能第三章 知识与知识表示 - 第3章 知识与知识表示 人类的智能活动过程主
人工智能 第三章确定性推理方法_图文.ppt
人工智能 第三章确定性推理方法 - 人工智能原理与应用 第三章 确定性推理 按照
人工智能第三章ppt_图文.ppt
人工智能第三章ppt_计算机软件及应用_IT/计算机_专业资料。第2章回顾 知识
人工智能第三章_图文.ppt
人工智能第三章 - 第三章 产生式系统的搜索策略 回溯策略 图搜索策略:无信息的
人工智能第三章.ppt
人工智能第三章 - 第三章 确定性推理 按照推理过程所用知识的确定性,推理可分为
人工智能第三章_图文.ppt
人工智能第三章 - 第三章 知识表示 知识表示是研究用什么形式将有关问题的 知识
人工智能 第三章3_图文.ppt
人工智能 第三章3 - 3.4 Herbrand定理 ? 问题: 一阶逻辑公式的
人工智能PDF第三章(1)_图文.pdf
人工智能PDF第三章(1) - 第三章 搜索推理技术 ? 主要内容 ? ? ?
人工智能 AI 第三章1_图文.ppt
人工智能 AI 第三章1 - 第3章 谓词逻辑与归结原理 概述 ? 命题逻辑 ?
人工智能第三章.doc
人工智能第三章 - 第三章 高级知识推理 教学内容: 客观事物 教学内容:现实世
人工智能第三章_图文.ppt
人工智能第三章 - 人工智能原理 1 12/23/2011 3.5 A*算法的可
人工智能(第三章)_图文.pdf
人工智能(第三章) - 第三章 搜索技术 1 吉林大学地面机械仿生技术教育部重点
人工智能第三章 确定性推理.doc
人工智能第三章 确定性推理 文档格式的课件文档格式的课件隐藏>> 第
更多相关标签: