回溯过程是控制策略的一种方法。选择一条规则，如果不能得出一个解，那么忘掉参与的各步，并选择另一条规则代之。从形式上看，不管有多少知识对选择规则有用，都可采用回溯的策略。如果没有有用的知识，那么规则可根据任意的方法选取，最后控制将退回，以便选择合适的规则。
一个简单的递归过程抓住了回溯控制下的产生式系统的运行本质。这个递归过程叫作BACKTRACK，它取单个自变量DATA，最初设置为产生式系统的综合数据库。在过程结束时，返回一张规则表。这张表如果依次应用于初始数据库，则产生一个满足结束条件的数据；如果过程找不到规则表就返回FAIL（失败）。BACKTRACK过程定义如下：
算法5.4 递归回溯算法
Recursive Procedure BACKTRACK（DATA）
（1）if TERM（DATA），returnNIL；/*TERM是一个谓词，对满足产生式系统结束条件的变量来说其取值为真。在成功结束时，返回空表NIL。＊/
（2）证DEADEND（DATA），return FAIL；/*DEADEND是一个谓词，对已经知道不在一条解路上的自变量来说其取值为真。在这种情况下，过程返回符号FAIL。＊/
（3）RULES·APPRULUES（DATA）；/*APPRULUES是一个函数，它计算可应用于其自变量的规则并排列这些规则（任意排列或者按照启发式准则排列）。＊/
（4）LOOP：ifNl几L（RULES），returnFAIL；/＊如果不再有可应用的规则，那么过程失败。＊/
（5）R·FIRST（RULES）；/＊选出最好的一条可应用规则。＊/(www.xing528.com)
（6）RULES·TAIL（RULES）；/＊删去刚才选用的一条规则，缩小可应用的规则表。＊/
（7）RDATA·R（DATA）；/＊应用规则R产生一个新的数据库。＊/
（8）PATH·BACKTRACK（RDATA）；/＊在新数据库上递归调用BACKTRACK。＊/
（9）还PATH=FAIL，goLOOP；/＊若递归调用失败，则试另一条规则。＊/
（10）returnCONS（R，PATH）；/＊否则，通过把R加到表的前面，向上走一遍成功的规则表。＊/
现在对这个过程作几点解释。首先，只有在过程产生一个满足结束条件的数据库时，才能在第（1）步成功结束。用于产生这个数据库的规则表在第（10）步建成。不成功的结束出现在第（2）步和第（4）步。在递归调用期间出现失败而退出时，过程会回溯到较高的一层。
第（2）步执行的测试是根据问题的数据库检验一下是否正好可能有一个解。在第（4）步如果所有可应用的规则都已经试完，那么过程失败。
过程BACKTRACK可能永远结束不了，这是因为可能无限地生成出新的非终结的数据库，或者可能循环不止。这两种情况可以通过把深度范围加在递归的方法上，适当地加以避免。当深度超出这个范围时，任何的递归调用均失败。避免循环则更简单，办法是保留迄今为止产生的数据库表，并不断检验新的数据库，看是否和表上的任一数据库相吻合。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
