含有回溯的递归程序设计

目录

回溯

1.1 概念

• 递归是一种算法结构、技巧，而回溯是一种算法思想。
• 本质上是一种枚举思想，采用深度优先策略来枚举所有可能解，并且服从一定的择优条件。
• 遵循设定好的择优条件不断深入试探，最终达到目标，但是在试探过程中，若发现当前情况不是最优或者一定无法达到目标时，将返回到上一个状态，对上一个状态进行重新选择后，继续深入试探。

1.2 基本思路

从一条路往前走，能进则进，不能进则退回到最近的岔路，换一条路再试。

1.3 问题举例

1.3.1 N皇后问题

• 要求

在N × N的棋盘上放置N个皇后，这些皇后之间不能相互攻击。（合法位置）

• 思路（不考虑优化）
  • 递归：继续深入试探下一行的每一列。
  • 递归边界：N个皇后全部摆放完成。
  • 回溯条件：当前皇后已经不存在合法位置（越界）。
  • 具体思路：
    1. 如果能够将前面所有的皇后放置在合法位置，那么就继续试探下一个皇后，从第1个皇后开始依次类推。
    2. 如果第k个皇后已经不存在合法位置（越界），那么判断第k-1个皇后是否还存在其他合法位置，若存在，则移动到下一个合法位置，重新试探第k个皇后；若不存在，则重复步骤2。
    3. 第N个皇后同理，只是在第N个皇后放置在合法位置后，到达了递归边界，需要输出可行解，然后重复步骤2。
• 回溯过程图解

（图片转自博客园，目前未经过作者同意，如有侵权，将立即删除！）

• 核心代码

void Put_The_Queen_On_The_NOk_Row_And_The_NOj_column(int k, int n) {//需要摆放n个皇后，当前摆放到了第k行。
    int j;
    if(k > n)//发现可行解
        print(n); //输出可行解
    else {
         for(j = 1;j <= n;j++) {//试探这一行的每一列
            if(Find_The_Valid_Pos(k, j)) {//判断该位置是否合法
                q[k] = j;   //保存位置
                Put_The_Queen_On_The_NOk_Row_And_The_NOj_column(k + 1, n);  //继续试探下一行
            }
        }
    }
}

1.4 算法设计

1. 清楚递归边界（什么时候停止递归）
2. 清楚递归函数的功能（参数的功能、返回值的功能）
3. 回溯算法设计基本思路
   1. 只要当前层还存在合法选项，那么就在保证当前层合法的前提下，进入试探下一层。
   2. 如果当前层已经不存在合法选项，那么就回溯到上一层，并重复判断1./2.。
   3. 如果发现可行解，那么重复判断1./2.。

1.5 PTA编程题

1.5.1 整数分解为若干项之和

• 要求

将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的所有整数分解式子。

• 思路

  • 递归：
  • 递归边界：当前result（填入的所有数之和）与N（目标值）相等
  • 回溯条件：当前result（填入的所有数之和）与N（目标值）相等（在此之后不可能再出现可行解，继续试探没有意义）。
  • 具体思路：
    1. 每一个位置的值，均从1开始试探。
  1. 如果当前的result（已经填入的所有数之和）仍小于N（输入的目标值），那么就使 第n个数 从 上一个数的数值 往上 试探。
     1. 如果当前result与N相等，到达递归边界，输出可行解，并且回溯到上一个状态（此时只有n-2个数），继续使第n-1个数自加，并判断result与N的关系。
     2. 依次类推，直到遍历所有可行解。

• 核心代码

void Division(int x, int pos, int result){
    static int counter, array[32];
    if(result != N) {
        for (int i = x; result + i - 1 < N; i++) {
            array[pos] = i;
            Division(i, pos + 1, result + i);
        }
    }
    else{
        counter++;
        std::cout << N << '=';
        for (int i = 0; i < pos - 1; i++)
            std::cout << array[i] << '+';
        if (counter % 4 == 0 || array[pos - 1] == N)
            std::cout << array[pos - 1] << std::endl;
        else
            std::cout << array[pos - 1] << ';';
    }
}

1.5.2 输出全排列

• 要求

  • 输出前n个正整数的全排列（n<10）。
  • 排列的输出顺序为字典序，即序列a1,a2,⋯,an排在序列b1,b2,⋯,bn之前，如果存在k使得a1=b1,⋯,ak=bk 并且 ak+1<bk+1。

• 思路

  • 这题与N皇后问题更加类似，而且运行流程更加简单。因为回溯只会出现在发现可行解之后，即试探直到发现可行解的过程不会被回溯打断。
  • 递归：试探下一位的数字，并且判断拟填入的数字是否被用过
  • 递归边界：全排列数的长度与N（目标值）相等。
  • 回溯条件：拟填入的数字已经全部被使用过了。
  • 具体思路（“合法”即当前层待填入的数字还未被使用过 ）
    1. 只要当前层还存在合法选项，那么就在保证当前层合法的前提下，进入试探下一层。
    2. 如果当前层已经不存在合法选项，那么就回溯到上一层，并重复判断1./2.。
    3. 如果发现可行解，那么就重复判断1./2.。

• 注意

  输入的目标值与全排列数的位数始终是一致的。

• 核心代码

/*全局变量*/
int whole_array[32]; // 存储当前的全排列数
int sub[32]; //记录每一个数字是否被用过
int N; //目标值

/*递归函数*/
void Perm (int x){
    static int length = 0; //当前全排列的长度
    if(N <= x - 1){ //判断全排列树的长度是否等于目标值
        for(int i = 1;i <= N;i++) //输出
            printf("%d",whole_array[i]);    
        printf("\n");
    }
    else //只要全排列数的长度小于目标值
        for(int i = 1;i <= N;i++) //由于要输出字典序，每一个位置从1开始试探
            if(sub[i] == 0){ //判断这个数是否被用过
                whole_array[x] = i; //将这个数
                sub[i] = 1; //填入之后将这个数标记为1，即在该全排列数中已经出现
                Perm(x + 1); //到下一个位置继续试探
                sub[i] = 0; //如果发生回溯，那么需要重新将这个数字标记为没有出现过
            }
}

— （博客内容为原创，未经允许禁止转载！） —