搜索与回溯算法模板及其应用
搜索与回溯算法模板及其应用
本文介绍了搜索与回溯算法模板及其应用，主要包括：
【1】 搜索与回溯算法基本思想 【2】模板算法1及其应用（素数环问题） 【3】模板算法2及其应用（数字拆分问题） 【4】搜索与回溯算法在排列组合中的应用（A(n, r)、C(n, r) 问题）
【1】搜索与回溯算法基本思想
为了求得问题的解，先选择某一种可能情况向前探索，在探索的过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
【2】模板算法1及其应用（素数环问题）
2.1 模板算法1：
int search(int k) {
for (i = 1; i <= 算符种数; i++) {
if (满足条件) {
保存结果;
if (到目的地) {
输出解;
} else {
search(k+1);
}
恢复: 保存结果之前的状态 { 回溯一步 }
}
}
}2.2 模板算法1应用举例（素数环）：
题目描述：
素数环：从 1 到 4 这 4 个数摆成一个环，要求相邻的两个数的和是一个素数。
解题思路：
非常明显，这是一道回溯的题目。从 1 开始，每个空位有 4 种可能（算符种数），只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第 4 个数还要判断和第 1 个数的和是否素数。
C++ 实现：
#include<iostream>
#include<cmath>
using namespace std;
int search(int t); // 回溯过程，t表示回溯深度
void print(); // 打印结果
bool pd(int x, int y); // 判断两个数的和是否是素数，起始时要计算1+0，故将1也算为质数
int a[5] = {0}; // 保存每个位置填进去的数字，也是问题的答案
int b[5] = {0}; // 标记每个位置是否被填入，如果填入，修改为 1
int total = 0; // 总方案数
int main() {
search(1); // 从第一层开始
cout << total << endl; // 输出总方案数
}
int search(int t) {
for (int i = 1; i <= 4; i++) {
if (pd(i, a[t-1]) && !b[i]) { // 如果数字i与左边的数之和是素数且数字i没有使用过
a[t] = i; // 把数字i填进去
b[i] = 1; // 标记数字i使用过
if (t == 4) { // 到目的地
if (pd(a[4], a[1])) {
print();
}
} else {
search(t+1);
}
b[i] = 0; // 恢复，回溯一步
}
}
}
void print() {
total++;
cout << "<" << total << "> ";
for (int i = 1; i <= 4; i++) {
cout << a[i] << " ";
}
cout << endl;
}
bool pd(int x, int y) { // 起始时要计算1+0，故将1也算为质数
int tar = x + y;
int i = 2;
while (i <= sqrt(tar) && tar%i != 0) {
i++;
}
if (i > sqrt(tar)) {
return true;
} else {
return false;
}
}最后的输出结果为：
<1> 1 2 3 4
<2> 1 4 3 2
<3> 2 1 4 3
<4> 2 3 4 1
<5> 3 2 1 4
<6> 3 4 1 2
6【3】模板算法2及其应用（数字拆分问题）
3.1 模板算法2：
int search(int k) {
if (到目的地) {
输出解;
} else {
for (i = 1; i <= 算符种数; i++) {
if (满足条件) {
保存结果;
search(k+1);
恢复: 保存结果之前的状态 { 回溯一步; }
}
}
}
}3.2 模板算法2应用举例（数字拆分）：
题目描述：
数字拆分：将任何一个大于 1 的自然数 n 拆分成若干个小于 n 的自然数之和。如数字 3 有两种拆分方法：3 = 1+1+1、3 = 1+2。
解题思路：
这道题和 Leetcode 找硬币类似，可以把小于 n 的自然数看成硬币的种类数。如果只是求组合数，可以使用找硬币的动态规划求解 【518】找硬币问题，求不同的组合数，与顺序无关。但是如果还要输出不同的拆分方法，就要使用以下搜索与回溯算法。
C++ 实现：
#include<iostream>
using namespace std;
int search(int s, int k); // 回溯过程，s表示目标，k表示组合的数字个数（深度）
void print(int k); // 打印结果，k表示组合的数字个数（深度）
int a[10001] = {1}; // 保存结果，从数字1开始
int total = 0; // 总结果数
int n; // 输入
int main() {
cin >> n;
search(n, 1);
cout << total << endl;
}
int search(int s, int k) {
if (s == 0) { // 如果结果减小到0，即到目的地
print(k-1); // 上一层是结果
} else {
for (int i = a[k-1]; i <= s; i++) { // 当前数i要大于等于前一个数a[k-1]
if (i < n) { // 当前数要小于n
a[k] = i;
s -= i; // 目标减去当前数
search(s, k+1); // 下一层
s += i; // 恢复：回溯一步
}
}
}
}
void print(int k) {
total++;
cout << "<" << total << "> ";
for (int i = 1; i <= k; i++) {
cout << a[i] << " ";
}
cout << endl;
}最后的输出结果为（假设输入的 n 为 4）：
<1> 1 1 1 1
<2> 1 1 2
<3> 1 3
<4> 2 2
4【4】搜索与回溯算法在排列组合中的应用
4.1 排列问题：
问题描述：
设有 n 个整数的集合 {1, 2, ..., n}，从中任意取出 r 个数进行排列 (r < n)，试列出所有的排列。
C++ 实现：
#include<iostream>
using namespace std;
int search(int k); // 回溯过程，k表示深度
void print(); // 打印结果
int a[10001] = {0}; // 保存结果，记录排列的各个数字
int b[10001] = {0}; // 标记数字i是否使用过，如果使用过标记为1
int n, r; // 求 A(n, r)
int total; // 总共的排列数
int main() {
cout << "input: n, r: ";
cin >> n >> r;
search(1);
cout << total << endl;
}
int search(int k) {
for (int i = 1; i <= n; i++) { // 有n种算符
if (!b[i]) {
a[k] = i;
b[i] = 1;
if (k == r) { // 如果从n个数中选择了r个数，即到达目的地
print();
} else {
search(k+1);
}
b[i] = 0; // 恢复，回溯一步
}
}
}
void print() {
total++;
cout << "<" << total << "> ";
for (int i = 1; i <= r; i++) {
cout << a[i] << " ";
}
cout << endl;
}注意：如果想求全排列，只需要把 r 改成 n 即可。
4.2 组合问题：
问题描述：
设有 n 个整数的集合 {1, 2, ..., n}，从中任意取出 r 个数进行组合 (r < n)，试列出所有的组合。
解题思路：
组合问题和排列问题求解过程几乎一模一样，只不过在组合问题中，出现了如 (1 2 3)，就不能出现其他 5 种情况 (1 3 2) 、(1 3 2)、 (2 1 3)、 (2 3 1)、 (3 1 2)、 (3 2 1)。因此，我们只需要将排列问题 int search(int k) 中的 if (!b[i]) 改写成 if (!b[i] && i > a[k-1])**，即保证当前数 i 比前一个数 ak-1 大，就能够避免出现后面重复的情况。**
C++ 实现：
#include<iostream>
using namespace std;
int search(int k); // 回溯过程，k表示深度
void print(); // 打印结果
int a[10001] = {0}; // 保存结果，记录组合的各个数字
int b[10001] = {0}; // 标记数字i是否使用过，如果使用过标记为1
int n, r; // 求 C(n, r)
int total; // 总共的组合数
int main() {
cout << "input: n, r: ";
cin >> n >> r;
search(1);
cout << total << endl;
}
int search(int k) {
for (int i = 1; i <= n; i++) { // 有n种算符
if (!b[i] && i > a[k-1]) { // 因为是求组合数，所以还要保证当前数i比前一个数a[k-1]大
a[k] = i;
b[i] = 1;
if (k == r) { // 如果从n个数中选择了r个数，即到达目的地
print();
} else {
search(k+1);
}
b[i] = 0; // 恢复，回溯一步
}
}
}
void print() {
total++;
cout << "<" << total << "> ";
for (int i = 1; i <= r; i++) {
cout << a[i] << " ";
}
cout << endl;
}