回溯搜索的浅析.doc

《回溯搜索的浅析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、冋溯搜索的浅析东莞市石龙第三屮学吴燕锋搜索算法经常被初学者认为是万能算法，半对某些题在缺乏解决问题的有效模型时，用搜索去解，确实可以得到一些分。搜索算法是人工智能屮的-•种基本方法，利用计算机的高性能来有H的、有方法地穷举一•个问题的部分或所有的可能情况，从血求出问题的解的一•种方法。但是搜索非常耗资源，这时可以考虑对搜索算法进行一些优化。这里我就简单介绍由搜索引伸出来的回溯搜索。回溯是搜索算法屮的一种控制策略。它的方法是，假设问题解的其屮--种可能情况向前搜索，在搜索过程屮，一旦发现原來的选择是错误的，就退

2、回一步重新选择，然后继续向前搜索，如此反复进行，直到得到解或证明无解为止。一、递归冋溯算法框架Proceduresearch(K:integer);BeginIf到H的地then输出解elsefori:=lto算法种数do讦满足条件thenbegin保存结果Search(k+1);〃这里还有另外一种方法，search(k+1,参数表)，信息的更改通过相关参数进行传递，不需要保存与恢复。恢复到保存结果之前的状态〃向前回溯一步end;end;回溯搜索过程中要注意的几个问题：1•用栈保存好前进屮的某些状态。2.制定

3、好约束条件二、应用实例这里我们引用经典的n皇后问题来说明，问题描述如下：在nXn的国际象棋棋盘上，放置n个皇后，使任何一个皇后都不能吃掉另一个，需满足的条件是：同一行、同一-列、同一-对角线上只能有一-个皇后。求所有满足要求的放置方案。【输入】queen.inn【输出】queen.out方案数【输入】nqueen.in8【输岀】nqueen.out92算法分析问题的关键在于如何判定某个皇后所在的行、列、对角线上是否有别的皇后，我们可以画一个矩阵，从矩阵的特点上找规律。这里我们以8皇后为例,如下图：•代表皇后如

4、果在同一行，则行号相同；如果在同一列，则列号相同；如果同在/对角线上，则行列值之和相同；如果同在对角线上，则行列值之差相同。因为每行有且仅有一个皇后，用一维数组a[1..8]表示皇后的放置：第i行皇后放在第j歹U，用a[i冃来表示，即下标是行数，内容是列数。如:a[3]=5就表示第3个皇后在第3行第5列。判断皇后是否安全，即检查同一列、同一对角线是否已经有皇后，开--标示数组b[1..8]控制同一列只能一•个皇后，如果两皇后在同一对角线上，则其行列坐标Z和或行列坐标Z差相等，所以我们可以用标志数组c[1..

5、.16],d[-7..7]控制同一对角线上只能有一个皇后。如果斜线不分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。在这种情况下，要表示两个皇后i和j不在同一列或斜线上的条件可以描述为:a[i]oa[j]andabs(i-j)oabs(a[i]-a[j])o参考程序Programqueenvara:array[L.maxn+1]ofinteger;b,c,d:airay卜1-manx.emanx+1]ofBoolean;Sum:integer;procedureprint;vari:ing

6、eger;beginwritelnCsum=sum);fori:=ltondowrite(a[i]);end;Proceduresearch(t:integer);varj:integer;beginift>nthenbegininc(sum);Ifsum<=5thenprintexit;end;forj:=ltondoIfb[j]andc[t+j]andd[t-j]thenbegina[t]:=j;b[j

7、:=false;cft+j]:=false;d[t-j]:=false;search(t+l);b[

8、j]:=true;c[t+j]:=true;〃冋溯到上•一步d[t-j]:=true;end;end;beginassign(input/queen.in');reset(input);assign(output/'queen.out");rewrite(output);fillchar(b,sizeof(b),true);fillchar(c,sizeof(c),true);fillchar(d,sizeof(d),true);readln(n);sum:=0;search(l);writeln(sum);

9、end.冋溯算法的公式三、回溯算法小结:回溯法是搜索算法屮的一种控制策略，它是从初始状态出发，运用题H给出的条件、规则，按照深度优先搜索的顺序扩展所有可能情况，从屮找出满足题意要求的解答。即：从问题的某一•种可能出发，搜索从这利嘴况出发所能达到的所有可能，如果有路可以走下去，就走到下一•个状态，继续按照这种规则搜索；当这一条路走到“尽头”而没达到H标状态的吋候，再倒回上一个出发点，从另一个可能出发，