人工智能第三章.ppt

第三章产生式系统的搜索策略  回溯策略 图搜索策略:无信息的图搜索 启发式的图搜索
8/18/2017
1
产生式系统的费用
信息(知识)
完备信息
0 无信息
计算费用
控制费用
规则应用费用
产生式系统费用
8/18/2017
2
回溯策略
8/18/2017
3
一、回溯算法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前
8/18/2017
4
BACKTRACK过程
Recursive Procedure BACKTRACK(DATA)
TERM(DATA),return NIL;
DEADEND(DATA),return FAIL;
←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).
8/18/2017
5
带来的问题及解决方案
⑴若DEADEND定义不好,则无限产生新的非终止的状态描述。
(既不成功又不失败的节点)
解决方案:设置门槛数,即搜索深度BOUND,当递归调用超过这个深度时return FAIL,引起回溯。
⑵程序中只有DATA和RDATA,回溯过程中将生成的状态都丢弃了,有可能陷入循环,重复地产生一系列非终止状态。
(实质属于情况(1))
解决方案:
在过程中保存一个状态描述表DATALIST:记录从初始状态到当前状态路径上的所有状态----递归变量变成DATALIST,取表头为DATA 。
加比较:当产生新状态RDATA时,比较是否为DATALIST中的一个状态(在这个表中),若是,则return FAIL,引起回溯,选择其它的Rule。
8/18/2017
6
四皇后问题:4枚皇后放在44的国际象棋棋盘上,如何放置使得它们不能相互俘获。
俘获:同行;同列;同对角线
二、回溯策略例……四皇后问题
其中a,b满足目标条件,
c,d,e为不可能构成满足目标条件的中间状态。
8/18/2017
7
综合数据库:以状态为节点的有向图
状态: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/18/2017
8



1
2
4
3
5
6
7
8
9


10
11
12



13
14
15
16
17
18
19
20
21
22
23



24



25
26
27




28
NIL
8/18/2017
9
四皇后问题
存在的问题:回溯的次数很多,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与以前相同
Rij排在Pik之前j<