回溯算法

发表于 | 分类于

回溯算法

回溯法实际是一种避免不必要搜索的穷举式搜索法。

用回溯法解题一般步骤：

  1. 确定问题解空间，判断是使用子集树还是使用排列树
  2. 以深度优先的方式搜索解空间树，在搜索过程中要判断要是用剪枝函数避免无效搜索。

回溯算法可分为递归回溯和迭代回溯

这篇文章使用递归回溯来进行解决，递归回溯更加简单直观，便于理解。

递归回溯算法步骤：

子集树实例：解决 0 1 背包问题

0 1 背包问题适合使用子集树来进行解决，对子集树的描述如下：

Package.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#pragma once
#include<string>
using namespace std;
class Package
{
public:
	int bestPrice = 0; // 最大价值
	Package();
	void getBest(int i);

private:
	const static int num = 3; // 物品数量
	int content = 30; // 背包容量
	int w[num] = { 20,15,15 }; // 物品重量
	int v[num] = { 40,25,25 }; // 物品价值

	int currentPrice = 0; // 当前价值
	int currentPath[3] = { 0 }; // 当前路径
	int bestPath[3] = { 0 }; // 最优路径
	int currentWeight = 0; // 当前背包中物品重量
};

Package.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include "Package.h"
#include<iostream>
#include<string>

void Package::getBest(int i) {
	// i 表示搜索树的第i层（根节点为0）
	if (i >= num) // 搜索到了树的最后一层
	{
		if (currentPrice > bestPrice) // 找到更好的结果
		{
			bestPrice = currentPrice; // 重新定义最大价值
			for (int i = 0; i < num; i++)  // 重新定义最优路径
			{
				bestPath[i] = currentPath[i];
			}
		}
		return;
	}
	else
	{
		for (int t = 0; t < 2; t++)
		{
			currentPath[i] = t; // 选择当前物品（t=0 表示不放入背包，t=1表示放入背包）
			if (currentWeight + t * w[i] <= content)
			{
				currentWeight += t * w[i];// 更新当前重量
				currentPrice += t * v[i];//更新当前价值
				getBest(i + 1);// 继续搜索下一层
				currentWeight -= t * w[i];//回溯
				currentPrice -= t * v[i];
			}
		}
	}
}

Package::Package() {
}

mian.cpp

1
2
3
4
5
6
7
8
9
#include<iostream>
#include "Package.h"

int main() {
	Package p;
	p.getBest(1);
	cout << p.bestPrice << endl;
	return 0;
}

仔细看看可以看到，0 1 背包的实际代码与上图中代码逻辑是一致的。（有时候，对算法的总结抽象很重要）

之前甚至目前我学习算法，觉得算法描述与实际代码之间相隔很远，就算给我算法描述我可能也无法写出代码。实际上，算法描述与代码之间确实有一定差距，而这差距就需要我们自己进行编程解决，比如 上图描述子集树的算法中output函数，算法描述很简单，但是需要我们按照我们的实际要求进行填充。

剪枝优化：

上面的的代码中其实已经进行了一步剪枝操作（所谓剪枝，就是提前将不符合条件的去掉），在

1
if (currentWeight + t * w[i] <= content)

处判断是否符合背包容量要求来进行剪枝避免无效搜索。

除此之外，当目前已经放入背包中的物品的价值 + 还没有考虑的物品总价值 仍然小于 目前得到的最大价值bestPrice时， 就没有继续搜索下去的必要了，就可以进行剪枝。

添加剪枝函数bound后的代码：

Package.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#pragma once
#include<string>
using namespace std;
class Package
{
public:
	int bestPrice = 0; // 最大价值
	Package();
	void getBest(int i);
	bool bound(int i); // 对于剩下的总物品的价值比当前所计算出物品总价值小的情况进行剪枝

private:
	const static int num = 3; // 物品数量
	int content = 30; // 背包容量
	int w[num] = { 20,15,15 }; // 物品重量
	int v[num] = { 40,25,25 }; // 物品价值

	int currentPrice = 0; // 当前价值
	int currentPath[3] = { 0 }; // 当前路径
	int bestPath[3] = { 0 }; // 最优路径
	int currentWeight = 0; // 当前背包中物品重量
};

Package.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include "Package.h"
#include<iostream>
#include<string>

void Package::getBest(int i) {
	// i 表示搜索树的第i层（根节点为0）
	if (i >= num) // 搜索到了树的最后一层
	{
		if (currentPrice > bestPrice) // 找到更好的结果
		{
			bestPrice = currentPrice; // 重新定义最大价值
			for (int i = 0; i < num; i++)  // 重新定义最优路径
			{
				bestPath[i] = currentPath[i];
			}
		}
		return;
	}
	else
	{
		for (int t = 0; t <= 1; t++)
		{
			currentPath[i] = t; // 选择当前物品（0 表示不放入背包，1表示放入背包）
			if (currentWeight + t * w[i] <= content && bound(i))
			{
				currentWeight += t * w[i];// 更新当前重量
				currentPrice += t * v[i];//更新当前价值
				getBest(i + 1);// 继续搜索下一层
				currentWeight -= t * w[i];
				currentPrice -= t * v[i];
			}
		}
	}

}

// 当剩下的所有物品全都放入背包仍不能超过当前所找到的最大价值时，进行剪枝
bool Package::bound(int i) {
	int flag = false;
	int tempPrice = currentPrice;
	for (int t = i; t <= num; t++)
	{
		tempPrice += v[t];
		if (tempPrice > bestPrice)
		{
			flag = true;
		}
	}
	return flag;
}

Package::Package() {
}

子集树实例：n皇后问题

直接看代码：

NQueen.h

1
2
3
4
5
6
7
8
9
10
#pragma once
class NQueen
{
public:
	static const int row_length = 4;
	int chessboard[row_length][row_length] = { 0 };// 棋盘
	void place(int chessboard[][row_length], int row); // 放置棋子
	void printChessboard(int chessboard[row_length][row_length]); // 打印棋盘
	bool isVaild(int chessboard[][row_length], int row, int index); // 提前检查放置在(row,index)的棋子是否合法
};

NQueen.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cmath>
#include "NQueen.h"
using namespace std;

void NQueen::place(int chessboard[][row_length], int row) {
	if (row > row_length - 1) // 递归终止条件
	{
		printChessboard(chessboard);
		return;
	}
	for (int i = 0; i < row_length; i++) // 对row行的每一列进行判断
	{
		if (isVaild(chessboard, row, i)) // 如果合法
		{
			chessboard[row][i] = 1;
			place(chessboard, row + 1); // 进入下一行
			chessboard[row][i] = 0;
		}
	}
}

bool NQueen::isVaild(int chessboard[][row_length], int row, int index) {
	// 查找竖向是否有棋子
	for (int i = 0; i < row_length; i++)
	{
		if (chessboard[i][index] == 1)
		{
			return false;
		}
	}
	// 查找横向是否有棋子
	for (int i = 0; i < row_length; i++)
	{
		if (chessboard[row][i] == 1)
		{
			return false;
		}
	}
	// 查找 斜率为正的方向是否有棋子
	for (int i = 0; i < row_length; i++)
	{
		for (int j = 0; j < row_length; j++)
		{
			if ((index != j && row != i ) && abs((index - j) / (row - i)) == 1 && chessboard[i][j] == 1)
			{
				return false;
			}
		}
	}
	return true;
}

void NQueen::printChessboard(int chessboard[][row_length]) {
	for (int i = 0; i < row_length; i++)
	{
		for (int j = 0; j < row_length; j++) {
			cout << chessboard[i][j] << " ";
		}
		cout << endl;
	}
}

代码注释解释的很详细了。这里要说明的是这里和普通的子集树又不一样，平常的子集树的一维的，但是这里等于是二维的。但是回溯的思想是一样的。

子集树实例：最大团问题

一个无向图 G=(V，E)，V 是点集，E 是边集。取 V 的一个子集 U，若对于 U 中任意两个点 u 和 v，有边 (u,v)∈E，那么称 U 是 G 的一个完全子图。 U 是一个团当且仅当 U 不被包含在一个更大的完全子图中。

G的最大团指的是定点数最多的一个团。

直接看代码就可以：

MaxClique.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#pragma once
class MaxClique
{
public:
	static const int point_num = 5;
	int bestPath[point_num] = { 0 }; // 选择过程中产生的相对优的路径
	int currentPointNum = 0; // 当前团中节点的数量
	int bestPointNum = 0; // 
	void getMaxClique(int t);
	bool isClique(int currentPath[point_num], int point);// 判断point是否与currentPath中的所有节点都有边相连

private:
	char point[point_num] = { 1,2,3,4,5 };
	int graph[point_num][point_num] = { {0,1,0,1,1},
										{1,0,1,0,1},
										{0,1,0,0,1},
										{1,0,0,0,1},
										{1,1,1,1,0}
	};
	
	int currentPath[point_num] = { 0 };
};

MaxClique.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include "MaxClique.h"
using namespace std;
/*
最大团使用子集树的算法进行解决
对本问题中使用的currentPath进行说明：例如节点标号{1,2,3},currentPath[3] = { 1,0,1}, 即表示节点 1,3 构成最大团
*/
void MaxClique::getMaxClique(int t) {
	if (t > point_num - 1) // 递归终止条件
	{
		if (currentPointNum > bestPointNum)
		{
			bestPointNum = currentPointNum;
			for (int i = 0; i < point_num; i++)
			{
				bestPath[i] = currentPath[i];
			}
		}
		return;
	}

	if (isClique(currentPath, t)) // 如果与团中每个节点都有边相连
	{
		currentPath[t] = 1; // 将该节点加入到团中
		currentPointNum++; //团中节点数+1
		getMaxClique(t + 1);
		currentPointNum--;//回溯
		currentPath[t] = 0;
	}
	else
	{
		currentPath[t] = 0;
		getMaxClique(t + 1);
	}

}

bool MaxClique::isClique(int currentPath[point_num], int n)
// n 表示的是节点的索引值，从0开始
{
	if (n == 0)
	{
		return true;
	}
	for (int i = 0; i < point_num; i++)
	{
		if (currentPath[i] == 1 && graph[point[i] - 1][n] == 0) // 节点n与当前团中的节点存在不相连的情况
		{
			return false;
		}
	}
	return true;
}

Main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
#include"MaxClique.h"
using namespace std;

int main() {
	MaxClique clique;
	clique.getMaxClique(0);
	for (int i = 0; i < clique.point_num; i++)
	{
		cout << clique.bestPath[i] << " ";
	}
	return 0;
}

从上面的代码中可以看到，还以使用子集树一样的套路，不过这里要注意的是需要根据不同的题来进行不同的具体使用。

例如这个题，再像处理0 1 背包那样（如下图的操作）

就不行了，这里要通过if else 来代替for 循环，这样可以更好的判断向已有的团中加入一个节点是否满足团的条件。

根据具体情况进行具体分析的能力和思想很重要。算法只能提供给我们一种思想，但是我们不能把这种思想僵化为一种固定模式，算法是动态随机应变的。

排列树实例：全排列问题

比如：集合{ 1,2,3}的全排列为：

{ 1 2 3}

{ 1 3 2 }

{ 2 1 3 }

{ 2 3 1 }

{ 3 2 1 }

{ 3 1 2 }

通过全排列问题可以找到排列树的实质原理，因为排列树就是对一个序列进行全排列。

直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
using namespace std;

void getResult(int a[], int start);
void printArray(int a[], int length);
const int length = 3;
int array[length] = { 1,2,3 };
int main() {
	int start = 0; //起始位置
	int a[length] = { 1,2,3 };
	getResult(a, start);
	return 0;
}

void getResult(int a[], int start) {
	if (start > length - 1) // 递归终止条件
	{
		printArray(a, length);
		return;
	}
	for (int i = start; i < length; i++) {
		swap(a[start], a[i]); // 这个交换操作是重点，目的就是通过递归交换两个元素的位置，达到全排列的目的
		getResult(a, start + 1);
		swap(a[start], a[i]);
	}
}

void printArray(int a[], int length) {
	for (int i = 0; i < length; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}

排列树实例：解决TSP问题：

TSP问题解决可以使用排列树，排列树的算法描述为：

TSP.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class TSP
{
public:
	static const int city_num = 5; // 城市数量
	int bestPath[city_num+1] = { 0 };// 最优路径经过的城市编号
	int bestLength = 200; // 每次搜索中得到的最优路径长度,初始设置一个大值
	int start_city = 0; // 开始城市在数组中的索引
	int city[city_num] = { 1,2,3,4,5 }; // 城市编号，为方便使用数字
	TSP();
	void getTSP(int i,int city);
	bool isInPath(int city); // 判断当前城市是否已经别选中了
	bool isHasRoute(int city1 , int city2 ); //判断另个城市之间是否有通道
private:
	
	
	
	int length[city_num][city_num] = { {-1, 10, -1, 4, 12},
										{10, -1, 15, 8, 5 },
										{-1, 15, -1, 7, 30 },
										{4, 8, 7, -1, 6 },
										{12, 5, 30, 6, -1} }; // 城市之间的距离，-1表示城市之间没有通路
	
	int currentPath[city_num] = { 0 }; //在寻找最优路径过程中搜索的路径中城市编号
	int currentLength = 0; //在寻找最优路径过程中搜索的路径长度
};

TSP.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
对于TSP问题，需要通过排列树进行搜索
*/
#include<iostream>
#include "TSP.h"
using namespace std;
TSP::TSP() {
	currentPath[0] = city[start_city]; // 提前设置起始点
	bestPath[city_num] = city[start_city];  // 提前设置终止点（与起始点相同） 
}
void TSP::getTSP(int i, int n) {
	// i 表示搜索树的第几层；n表示对第i层的编号为n的进行操作
	if (i == city_num - 1) // 到达了搜索树最后一层
	{
		if (isHasRoute(city[start_city], currentPath[city_num - 1]))
		{
			if (currentLength + length[start_city][currentPath[city_num - 1] - 1] < bestLength) // 当找到更好的路径
			{
				bestLength = currentLength + length[start_city][currentPath[city_num - 1] - 1];
				for (int t = 0; t < city_num; t++)
				{
					bestPath[t] = currentPath[t];
				}
			}
		}

		return;
	}
	for (int t = 0; t < city_num; t++)
	{
		if (isHasRoute(n, city[t]) && !isInPath(city[t])) // 寻找到和当前城市n有直接相连的城市，并且该城市还没有被选择
		{
			currentPath[i + 1] = city[t]; //将当前城市纳入考虑范围
			currentLength += length[n - 1][city[t] - 1]; // 将当前路径纳入考虑范围。注意由于我是将城市按数字进行编号，因此通过n-1就可以得到城市在数组中的索引
			getTSP(i + 1, city[t]); // 这里解释一下，之所以传递第二个参数是因为在下次递归中需要知道新选择节点编号（这样才能找到与新城市相邻的城市）
			currentPath[i + 1] = 0; // 回溯
			currentLength -= length[n - 1][city[t] - 1];
		}
	}
}

// 判断城市（编号）是否已经在已选择路径中了
bool TSP::isInPath(int city) {
	for (int i = 0; i < city_num; i++) {
		if (city == currentPath[i])
		{
			return true;
		}
	}
	return false;
}

// 判断两个城市（编号）之间是否直接相连
bool TSP::isHasRoute(int city1, int city2) {
	// 由于这里我使用的是数字来表示城市的，所以对于判断城市之间是否直接相连比较方便，城市编号-1就可以作为索引。但是实际情况要复杂
	if (length[city1 - 1][city2 - 1] != -1)
	{
		return true;
	}
	else
	{
		return false;
	}
}

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include "TSP.h"
using namespace std;

int main() {
	TSP tsp;
	tsp.getTSP(0, tsp.city[tsp.start_city]);
	for (int i = 0; i < tsp.city_num + 1; i++)
	{
		cout << tsp.bestPath[i] << endl;
	}
	cout << "最优:" << tsp.bestLength << endl;
	return 0;
}

上面代码是我自己写的，因为我把排列树的基本忘了，我就按着自己的理解写了。虽然最后结果是正确的，但是很显然代码质量很差，我在编码的过程中感觉自己想的有些复杂，但是又不能写出更好的。硬着头皮写完后参考了网上的资料。其实按着求全排列那样写就可以。

回溯算法其他问题：

子集树解决装载问题 :

leetcode Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

经过这个题可以发现，对于回溯问题，并不是所有的要使用子集树或排列树，比如当寻找[a,b,c] 和 [d,e,f]的搭配时(ad,ae..) ，子集树和排列树好像都不那么合适，这时候就需要具体问题具体分析了：

回溯法时间复杂度

一般用回溯法都是一些NP问题。

回溯法的最坏复杂度就是无解的时候。因为想证明无解就得否定所有的解，也就是说会考虑所有的可能成为解的情况。

例如用排列树皇后问题，复杂度是O(n!),因为等价于找到1～n的其中一个排列。

又例如01背包，当然在容量以及物品的体积在一个比较小的范围可以动态规划。然而在一般情形，只能搜索2^n种情况。所以就是O(2^n).

基本上回溯法就是两种复杂度，指数或者阶乘。