精华区文章阅读

发信人: GREnTOFEL (Crazy Plucking), 信区: Algorithm
标  题: 递归与回溯(转载)
发信站: 哈工大紫丁香 (2002年07月06日21:51:53 星期六), 站内信件

【以下文字转载自 Programming 讨论区】
【原文由 zjliu 所发表】
发信人: violinist (巷战狙击手), 信区: Algorithm
标  题: 递归与回溯
发信站: 日月光华 (Fri Jul  5 08:27:04 2002)

递归与回溯

[算法分析]
    为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它

的上一状态……这
种用自已来定义自己的方法，称为递归定义。例如：定义函数f(n)为：
        /n*f(n－1) (n>0)
f(n)= |
        \ 1(n=0)
    则当0时，须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……当n=0时，f(n)=1。

    由上例我们可看出，递归定义有两个要素：
    （1）递归边界条件。也就是所描述问题的最简单情况，它本身不再使用递归的定义。

         如上例，当n=0时，f(n)=1，不使用f(n-1)来定义。
    （2）递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。

         如上例：f(n)由f(n-1)定义，越来越靠近f(0),也即边界条件。最简单的情况是

f(0)=1。

    递归算法的效率往往很低, 费时和费内存空间. 但是递归也有其长处, 它能使一个蕴

含递归关系且结构
复杂的程序简介精炼, 增加可读性. 特别是在难于找到从边界到解的全过程的情况下, 如

果把问题推进一步
没其结果仍维持原问题的关系, 则采用递归算法编程比较合适.

    递归按其调用方式分为: 1. 直接递归, 递归过程P直接自己调用自己; 2. 间接递归,

即P包含另一过程
D, 而D又调用P.

    递归算法适用的一般场合为:
    1. 数据的定义形式按递归定义.
       如裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2.
       对应的递归程序为:
         Function fib(n : integer) : integer;
         Begin
            if n = 0 then fib := 1     { 递归边界 }
                     else if n = 1 then fib := 2
                                   else fib := fib(n-2) + fib(n-1)   { 递归 }

         End;
       这类递归问题可转化为递推算法, 递归边界作为递推的边界条件.
    2. 数据之间的关系(即数据结构)按递归定义. 如树的遍历, 图的搜索等.
    3. 问题解法按递归算法实现. 例如回溯法等.

    从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走

到" 尽头 "
的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断" 回溯 "寻找解的方法

, 称作
" 回溯法 ".

[参考程序]
    下面给出用回溯法求所有路径的算法框架. 注释已经写得非常清楚, 请读者仔细理解

.
Const maxdepth = ????;
Type statetype = ??????; { 状态类型定义 }
     operatertype = ??????; { 算符类型定义 }
     node = Record { 结点类型 }
               state : statetype; { 状态域 }
       operater :operatertype { 算符域 }
    End;
{ 注: 结点的数据类型可以根据试题需要简化 }
Var
   stack : Array [1..maxdepth] of node; { 存当前路径 }
   total : integer; { 路径数 }
Procedure make(l : integer);
Var i : integer;
Begin
   if stack[L-1]是目标结点 then
   Begin
      total := total+1; { 路径数+1 }
      打印当前路径[1..L-1];
      Exit
   End;
   for i := 1 to 解答树次数 do
   Begin
      生成 stack[l].operater;
      stack[l].operater 作用于 stack[l-1].state, 产生新状态 stack[l].state;
      if stack[l].state 满足约束条件 then make(k+1);
      { 若不满足约束条件, 则通过for循环换一个算符扩展 }
      { 递归返回该处时, 系统自动恢复调用前的栈指针和算符, 再通过for循环换一个算

符扩展 }
      { 注: 若在扩展stack[l].state时曾使用过全局变量, 则应插入若干语句, 恢复全

局变量在
                        stack[l-1].state时的值. }
   End;
   { 再无算符可用, 回溯 }
End;
Begin
   total := 0; { 路径数初始化为0 }
   初始化处理;
   make(l);
   打印路径数total
End.

[例子]    求N个数的全排列。
    ［分析］求N个数的全排列，可以看成把N个不同的球放入N个不同的盒子中，每个盒子

中只能有一
个球。解法与八皇后问题相似。
    ［参考过程］
       procedure try(I:integer);
       var j:integer;
        begin
             for j:=1 to n do
                  if a[j]=0 then
                 begin
                      x[I]:=j;
                      a[j]:=1;
                      if I<n then try(I+1)
                         else print;
                      a[j]=0;
                 end;
        end;

[习题] 用递归完成：
1、如下图，打印0－N的所有路径(0=〈N〈=9)：
   1―> 3―> 5―> 7―> 9
    ^    ^    ^    ^     ^
    |    |    |    |     |
   0―> 2―> 4―> 6―> 8
(说明：图中须加上0－>3，2－>5，4－>7，6－>9的连线)
2、快速排序。
3、打印杨辉三角。
最后, 给出一道经典的使用回溯算法解决的问题, 留给读者思考.
题目描述:
    对于任意一个m*n的矩阵, 求L形骨牌覆盖后所剩方格数最少的一个方案.

--

※ 来源:．日月光华 http://bbs.fudan.edu.cn [FROM: 10.11.12.201]

--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: 202.118.229.154]

Algorithm 版 (精华区)