极速赛车

您现在的位置:极速赛车教育教学网>> 文章中心>> 学科学习>> 微机>>正文内容
微机

趣谈数据结构(六)

作者:大榕树 来源:http://www.mydrs.org 发布时间:2009年05月06日 点击数: 【字体: 收藏 查看评论
本讲,我们来谈谈搜索与回溯。

  搜索与回溯是计算机解题中常用的算法,有很多问题无法根据某种确定的计算法则来求解,此时可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是:为了求得问题的解,先选择某一种可能情况向前探索,在探索过程中,一旦发现原来的选择是错误的,就退回一步重新选择,继续向前探索,如此反复进行,直至得到解或证明无解。

  如迷宫问题:进入迷宫后,先随意选择一个前进方向,一步步向前试探前进,如果碰到死胡同,说明前进方向已无路可走,这时,首先看其它方向是否还有路可走,如果有路可走,则沿该方向再向前试探;如果已无路可走,则返回一步,再看其它方向是否还有路可走;如果有路可走,则沿该方向再向前试探。按此原则不断搜索回溯再搜索,直到找到新的出路或从原路返回入口处无解为止。

  例1  在8×8的国际象棋盘上,放置八个皇后,使任何一个皇后都不能吃掉另一个。

  分析:要使任何一个皇后都不能吃掉另一个,需满足的条件是:同一行、同一列、同一对角线上只能有一个皇后。

  考虑每行有且仅有一个皇后,设一维数组A[1..8]表示皇后的放置:第i行皇后放在第j列,用A[i]=j来表示,即下标是行数,内容是列数。

  放置第i个皇后的算法为:
  procedure try(i);
   begin
    选择第i个皇后的位置;
     if 安全 then
      begin
       放置第i个皇后;
       if i=8 then 输出
        else try(i+1);{放置第i+1个皇后}
        放置不成功,回溯一步,当前皇后退出,尝试下一个位置是否可行
      end;
   end;

  判断皇后是否安全,即检查同一列、同一对角线是否已有皇后,建立标志数组b[1..8]控制同一列只能有一个皇后,若两皇后在同一对角线上,则其行列坐标之和或行列坐标之差相等,故亦可建立标志数组c[1..16]、d[-7..7]控制同一对角线上只能有一个皇后。

  从分析中,我们不难看出,搜索前进过程实际上是不断递归调用的过程,当递归返回时即为回溯的过程。

源程序如下:
program ex1;
var
 a:array[1..8] of byte;
 b:array[1..8] of boolean;
 c:array[1..16] of boolean;
 d:array[-7..7] of boolean;
 sum:byte;
procedure pr;
 var j:byte;
 begin
  for j:=1 to 8 do write(a[j]:4);
  inc(sum);writeln(' sum=',sum);
 end;
procedure try(t:byte);
 var i:byte;
 begin
  for i:=1 to 8 do
   if b[i] and c[t+i] and d[t-i] then {寻找放置皇后的位置}
    begin {放置皇后,建立相应标志值}
     a[t]:=i;
     b[i]:=false;
     c[t+i]:=false;
     d[t-i]:=false;
     if t=8 then pr;{8个皇后都放置好,输出}
     else try(t+1);{继续递归放置下一个皇后}
     b[i]:=true; {递归返回即为回溯一步,当前皇后退出}
     c[t+i]:=true;
     d[t-i]:=true;
    end;
 end;
begin
 fillchar(b,sizeof(b),#1);
 fillchar(c,sizeof(c),#1);
 fillchar(d,sizeof(d),#1);
 sum:=0;
 try(1);
end.

相关信息
没有相关内容
观后心情
感动 同情 无聊 愤怒 搞笑 难过 高兴 路过