1、 第三章 产生式系统的搜索策略回溯策略 图搜索策略：无信息的图搜索启发式的图搜索*1产生式系统的费用信息（知识）完备信息0 无信息计算费用 控制费用规则应用费用产生式系统费用Date23.1 回溯策略Date3一、回溯算法 BACKTRACK 算法中用到的部分变量、常量、谓词、函数： 变量：DATA， RDATA：状态变量RULES, PATH ： 表变量 常量：NIL: 空表 -LISP语言中的常量，也可用（） 谓词：TERM(DATA): DATA满足结束条件时，为真DEADEND(DATA):DATA不在解路上，为真（往下到达目标的可能性来定义这个谓词：若从 DATA当前状态往下走到达目
2、标的可能性很小时，则放弃这个状态 ）NULL(X): 表 X为空表时，为真 函数：APPRULES(DATA): 将 DATA所有可用规则进行排序所得到的表FIRST(X): 取表的头TAIL(X): 取表的尾CONS(E, X):将加入表前Date4BACKTRACK过程Recursive Procedure BACKTRACK（ DATA）1 if TERM（ DATA）， return NIL；2 if DEADEND（ DATA）， return FAIL；3 RULESAPPRULES （ DATA）；4 LOOP： if NULL（ RULES）， return FAIL；5 RF
3、IRST （ RULES）； 6 RULESTAIL （ RULES）；7 RDATAR （ DATA）； 8 PATHBACKTRACK （ RDATA）；9 if PATH FAIL， go LOOP；10. return CONS（ R， PATH） .Date5带来的问题及解决方案 若 DEADEND定义不好，则无限产生新的非终止的状态描述。（既不成功又不失败的节点）解决方案： 设置门槛数，即搜索深度 BOUND，当递归调用超过这个深度时 return FAIL，引起回溯。 程序中只有 DATA和 RDATA，回溯过程中将生成的状态都丢弃了，有可能陷入循环，重复地产生一系列非终止状态。
4、（实质属于情况 (1)）解决方案：在过程中保存一个状态描述表 DATALIST：记录从初始状态到当前状态路径上的所有状态 -递归变量变成 DATALIST，取表头为 DATA 。加比较：当产生新状态 RDATA时，比较是否为 DATALIST中的一个状态（在这个表中），若是，则 return FAIL，引起回溯，选择其它的 Rule。Date6 四皇后问题： 4枚皇后放在 44的国际象棋棋盘上，如何放置使得它们不能相互俘获。俘获：同行；同列；同对角线二、回溯策略例 四皇后问题其中 a， b满足目标条件，c， d， e为不可能构成满足目标条件的中间状态。Date7综合数据库：以状态为节点的有向图
5、状态： 44矩阵初始状态： 空 矩阵规则： Rij:if i=1时，矩阵中无皇后标志，或 4 i 1时，矩阵的 i-1行有一个皇后标志， then在矩阵的第 i行第 j列放一个皇后标记 结束条件： TERM为真 矩阵中有 4个皇后标志，且不能相互俘获控制策略：回溯DEADEND(DATA): DATA中存在 1对皇后相互俘获，为真APPRULES(RULES): Rij排在 Rik之前 jkDate8124356 7 8 910111213 14 15 1617 181920 21 22 232425 26 2728 NILDate9四皇后问题存在的问题：回溯的次数很多， 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之前 jkDate10
