百度一下 藏锋者 就能快速找到本站! 每日资讯归档 下载藏锋者到桌面一键访问

当前位置:主页 > 人工智能 > 回溯策略

回溯策略

所在栏目:人工智能 时间:10-11 21:03 分享:

回溯过程是控制策略的一种方法。选择一条规则,如果不能得出一个解,那么忘掉参与的各步,并选择另一条规则代之。从形式上看不管有多少知识对选择规则有用,都可采用回溯的策略。如果没有有用的知识,那么规则可根据任意的方法选取,最后控制将退回,以便去选择合适的规则。

一个简单的递归过程抓住了回溯控制下的产生式系统的运行本质,这个递归过程叫做BACKTRACK,它取单个自变量DATA,最初设置为产生式系统的综合数据库。在过程结束时,返回一张规则表。这张表如果依次应用于初始数据库,则产生一个满足结束条件的数据。如果过程找不到规则表就返回FAIL(失败)。BACKTRACK过程定义如下:算法3.4 递归回溯算法。

RecursiveprocedureBACKTRACK(DATA)(1)If TERM(DATA),returnNIL;/TERM是一个谓词,对满足产生式系统结束条件变量来说取值为真。在成功结束时,返回空表NIL。/(2)IfDEADEND(DATA),returnFAIL;/DEADEND是一个谓词,对已经知道不在一条解路上的自变量来说取值为真。在这种情况下,过程返回符号FAIL。/(3)RULES←APPRULUES(DATA);/APPRULUES是一个函数,它计算可应用于其自变量的规则并排列这些规则(任意排列或者按照启发式准则排列)。/(4)LOOP:IfNULL(RULES),returnFAIL;/ 如果不再有可应用的规则,那么过程失败。/(5)R←FIRST(RULES);/ 选出最好的一条可应用规则。/(6)RULES←TAIL(RULES);/ 删去刚才选用的一条规则,缩小可应用的规则表。/(7)RDATA←R(DATA);/ 应用规则R产生一个新的数据库。/(8)PATH←BACKTRACK(RDATA);/在新数据库上递归调用BACK-TRACK。/(9)IfPATH=FAIL,goLOOP;/若递归调用失败,则试另一条规则。/(10)returnCONS(R,PATH);/ 否则,通过把R加到表的前面,向上走一遍成功的规则表。/现在我们对这个过程作几点解释。首先,只有在过程产生一个满足结束条件的数据库时,才能在第(1)步成功结束。用于产生这个数据库的规则表在第(10)步建成。不成功的结束出现在第(2)步、第(4)步。在递归调用期间出现失败而退出时,过程会回溯到较高的一层。第(2)步执行的测试是根据问题的数据库检验一下是否正好可能有一个解。在第(4)步如果所有可应用的规则都已经试完,那么过程失败。

过程BACKTRACK可能永远结束不了,因为可能无限地生成出新的非终结的数据库,或者可能循环不止。这两个情况可以通过把深度范围加在递归的方法上,适当地加以避免。当深度超出这个范围时,任何的递归调用均失败。避免循环则更简单,办法是保留迄今为止产生的数据库表,并不断检验新的数据库,看一看和表上的任一数据库是否吻合。

回溯策略 免费邮件订阅: 邮件订阅

图片推荐

热点排行榜

CopyRight? 2013 www.cangfengzhe.com All rights reserved