文章目录

  之前的课老师给我们讲了回溯法,回溯法从本质上来说并不能减低问题规模的量级,只是通过一定的约束条件减少了问题规模的常数项系数。回溯法的基本做法是搜索,它是一种可以避免不必要搜索的穷举式搜索法。

  回溯法是采用深度优先的思想进行遍历,而分枝限界法采用的是广度优先遍历,两者从本质上来说没有太大的区别,剪枝函数的选取也大致相同,所以分支限界法不再进行相关的实例实现。

  回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分枝限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。

  回溯法适用于求解一些组合数较大的问题,典型的如m图着色问题、N后问题、01背包问题、符号三角形问题、TSP问题等。

  回溯法常见的两类解空间树大致有两种,子集树和排列树,子集树如01背包问题的解空间树,排列数树如TSP问题的解空间树。

  下面给出两者的基本demo:

  子集树:

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
package backtrackingAlgorithm;
/**
* 子集树演示
* @author jrhu05
*
*/
public class SubsetTreeTest {
static int N=3;//深度
static int[] x=new int[N+1];
static void Backtrace(int t)
{
if(t>N)
{
for(int i=1;i<=N;i++)
{
System.out.print(x[i]+" ");
}
System.out.println();
}
else
{
for(int i=0;i<=1;i++)
{
x[t]=i;
Backtrace(t+1);
}
}
}
public static void main(String[] args) {
Backtrace(1);
}
}

   排列树:

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
package backtrackingAlgorithm;
/**
* 排列树演示
* @author jrhu05
*
*/
public class PermutationTreeTest {
static int N=3;
static int[] x={0,1,2,3};
static void swap(int x1,int x2)
{
int temp=x[x1];
x[x1]=x[x2];
x[x2]=temp;
}
static void Backtrace(int t)
{
if(t>N)
{
for(int i=1;i<=N;i++)
{
System.out.print(x[i]+" ");
}
System.out.println();
}
else
{
for(int i=t;i<=N;i++)
{
swap(t,i); //意思是这个swap(x[t],x[i]);
Backtrace(t+1);
swap(t,i); //swap(x[t],x[i]);
}
}
}
public static void main(String[] args) {
Backtrace(1);
}
}

  下面给出一些常见的经典实例的实现,基本上就是对上述两个demo的灵活应用。

  01背包问题的回朔法求解:

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package backtrackingAlgorithm;
/**
* 01背包问题的回朔法求解
* 回溯法:01背包属于找最优解问题,用回溯法需要构造解的子集树。在搜索状态空间树时,
* 只要左子节点是可一个可行结点,搜索就进入其左子树。对于右子树时,先计算上界函数,以判断是否将其减去,剪枝
* 限界函数:当前价值cv+剩余容量可容纳的最大价值<=当前最优价值bestv,那么就进行剪枝,
* @author jrhu05
*
*/
public class OneZeroPackage {
static int c; //背包最大容量
static int n; //子集树的深度,即物品个数
static int []w; //物品重量w[i]
static int []v; //物品价值v[i]
static int cw; //当前物品总重(currentWeight)
static int cv; //当前物品总价值(currentValue)
static int bestv; //最优解

public static void main(String[] args) {
int[] wight={20,15,10};
int[] value={20,30,25};
int maxWight=25;
System.out.println(Knapsack(value, wight, maxWight));
}

public static int Knapsack(int []vv,int []ww,int cc)
{
//初始化
c=cc;
n=vv.length-1;
cw=0;
cv=0;
bestv=0;
v=vv;
w=ww;
//进行回溯操作
backtrack(0);
return bestv;
}

/**
* 递归式的回溯法实现
* @param i 递归出发点
*/
static void backtrack(int i)
{
//如果到达叶子节点,即表明找到一个可行解
//则将当前解返回
if(i>n)
{
bestv=cv;
return;
}
//如果可以放入第i个物品(即可以遍历左子树),
//则放入并且更新cw和cv
if(cw+w[i]<=c) //此即为约束函数类剪枝函数
{
cw+=w[i];
cv+=v[i];
//进行左子树遍历
backtrack(i+1);
//左子树遍历完成后进行回溯,回溯到当前节点
//即对cw和cv进行更新
cw-=w[i];
cv-=v[i];
}
//左子树遍历完成后,判断是否有可能产生比当前最优解还要大的解,如果可能则遍历右子树
if(bound(i+1)>bestv) //此即为限界函数类剪枝函数
backtrack(i+1);
}

/**
* 计算从节点i开始的上界函数(即当前价值cv+剩余容量可容纳的最大价值)
* @param i
* @return
*/
private static double bound(int i)
{
double cleft=c-cw; //背包剩余容量
double bound=cv; //如果i已经到了最后,那么没东西可以再放,即cv为上界
//一个个的加,直到无法再放了
//w[i]<=cleft是为了保证这个东西能完整的放进去
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
bound+=v[i];
i++;
}
return bound;
}

}

  图的M着色问题的回溯法求解:

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
65
package backtrackingAlgorithm;

import java.util.Arrays;

/**
* 图的M着色问题的回溯法求解
* 图用邻接矩阵来表示
* @author jrhu05
*
*/
public class theIssueOfColoringUpPictures {
static int[][] map={{0,1,1,0,0},
{1,0,1,1,1},
{1,1,0,0,1},
{0,1,0,0,1},
{0,1,1,1,0}};

static int[] color={0,0,0,0,0};
static int n=color.length;
public static void main(String[] args) {
String[] colorSet={"red","green","blue"};
CUPicBackAlgo(0,0);
for (int i = 0; i < color.length; i++) {
System.out.print(colorSet[color[i]]+" ");
}
System.out.println();
}

private static int CUPicBackAlgo(int deep,int flag) {
// TODO 自动生成的方法存根
if (deep>=n) {
//找到一组可行解
return 0;
}
else {
for(int i=flag;i<3;i++){//有三种颜色
color[deep]=i;
if (check(deep)) {
System.out.println(Arrays.toString(color));
if (CUPicBackAlgo(deep+1,0)==0) {
//一旦找到可行解就断开for循环
break;
}
}else if (i==2) {//如果该节点所有的解都不满足条件那么进行回溯
System.out.println(Arrays.toString(color));
System.out.println("back track");
CUPicBackAlgo(deep-1,color[deep-1]+1);
}

}
}
return 0;
}

private static boolean check(int deep) {
// TODO 自动生成的方法存根
//检查颜色是否满足要求
for (int i = 0; i < deep; i++) {
if (map[deep][i]==1&&color[i]==color[deep]) {
return false;
}
}
return true;
}
}

  旅行商问题的回溯法求解:

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package backtrackingAlgorithm;

import java.util.Arrays;

/**
* 旅行商问题的回溯法求解
* Travel Salesman Problem
* 图用邻接矩阵来表示
* 解空间是序列树
* @author jrhu05
*
*/
public class TSP {
static int NUM=4;
//static int MAX=Integer.MAX_VALUE;
static int MAX=Integer.MAX_VALUE;
//图G的邻接矩阵
static int[][] map={{0,0,0,0,0},
{0,MAX,30,6,4},
{0,30,MAX,5,10},
{0,6,5,MAX,20},
{0,4,10,20,MAX}};
static int[] currentx={1,1,2,3,4}; //当前解
static int[] bestx={0,0,0,0,0,1}; //最优解,顺序输出即可
static int cc=0; //当前费用
//static int NoEdge=-1; //无边标记
static int bestc=-1; //最优费用


static void BackTrack(int t) //t从2开始
{
//到达第n个节点
if(t>NUM)
{
if(cc+map[currentx[NUM-1]][currentx[NUM]]+map[currentx[NUM]][1]<bestc)
{
for(int i=1;i<=NUM;i++)
{
bestx[i]=currentx[i];
}
bestc=cc+map[currentx[NUM-1]][currentx[NUM]]+map[currentx[NUM]][1];
System.out.print(Arrays.toString(bestx)+"--->");
System.out.println(countPrice());
}
}
else
{
for(int i=t;i<=NUM;i++)
{
//如果上一个节点和它此后的节点有边,并且费用不高于现有的最优费用(bestc==-1表示第一次)
if(cc+map[currentx[t-1]][currentx[i]]<bestc ||bestc==-1)
{
swap(t,i);
cc+=map[currentx[t-1]][currentx[t]];
BackTrack(t+1);
cc-=map[currentx[t-1]][currentx[t]];
swap(t,i);
}
}
}

}//注,此时默认currentx[1]==1,即从第一个节点出发

static void swap(int x1, int x2) {
// TODO 自动生成的方法存根
int temp=currentx[x1];
currentx[x1]=currentx[x2];
currentx[x2]=temp;
}

private static int countPrice() {
// TODO 自动生成的方法存根
int best=0;
for (int i = 1; i < bestx.length-1; i++) {
best+=map[bestx[i]][bestx[i+1]];
}
return best;
}

public static void main(String[] args) {
BackTrack(1);
System.out.print(Arrays.toString(bestx)+"--->");
System.out.print(countPrice());
}
}

  八皇后问题的回朔法求解:

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package backtrackingAlgorithm;

/**
* 八皇后问题的回朔法求解
* @author jrhu05
*
*/
public class NQueensWithBacAlo {
// 皇后的个数
private static int queensNum = 8;

// column[i] = j 表示第 i 列的第 j 行放置一个皇后
private static int[] queens = new int[queensNum + 1];

// rowExists[i] = true 表示第 i 行有皇后
private boolean[] rowExists = new boolean[queensNum + 1];

// a[i] = true 表示右高左低的第 i 条斜线有皇后
private boolean[] a = new boolean[queensNum * 2];

// b[i] = true 表示左高右低的第 i 条斜线有皇后
private boolean[] b = new boolean[queensNum * 2];

// 初始化变量
private void init() {
for (int i = 0; i < queensNum + 1; i++) {
rowExists[i] = false;
}

for(int i = 0; i < queensNum * 2; i++) {
a[i] = b[i] = false;
}
}

// 判断该位置是否已经存在一个皇后,存在则返回 true
private boolean isExists(int row, int col) {
return (rowExists[row] || a[row + col - 1] || b[queensNum + col - row]);
}

// 主方法:测试放置皇后
public void testing(int column) {

// 遍历每一行
for (int row = 1; row < queensNum + 1; row++) {
// 如果第 row 行第 column 列可以放置皇后
if (!isExists(row, column)) {
// 设置第 row 行第 column 列有皇后
queens[column] = row;
// 设置以第 row 行第 column 列为交叉点的斜线不可放置皇后
rowExists[row] = a[row + column - 1] = b[queensNum + column - row] = true;

// 全部尝试过,打印
if(column == queensNum) {
for(int col = 1; col <= queensNum; col++) {
System.out.print("("+col + "," + queens[col] + ") ");
}
System.out.println();

int[][] map=new int[queensNum][queensNum];
for (int[] is : map) {
for (int i : is) {
i=0;
}
}
for(int col = 1; col <= queensNum; col++) {
map[col-1][queens[col]-1]=1;
//System.out.print("("+col + "," + queens[col] + ") ");
}
System.out.println();
for (int[] is : map) {
for (int i : is) {
System.out.print(i+" ");
}
System.out.println();
}
return;
}else {
// 放置下一列的皇后
testing(column + 1);
}
// 撤销上一步所放置的皇后,即回溯
rowExists[row] = a[row + column - 1] = b[queensNum + column - row] = false;
}
}
}

// 测试
public static void main(String[] args) {
NQueensWithBacAlo queen = new NQueensWithBacAlo();
queen.init();
// 从第 1 列开始求解
queen.testing(1);

}
}

  其中八皇后问题的解法参考了:http://haolloyin.blog.51cto.com/1177454/353105/

  该处有详细的解释。


如果觉得文章很有趣或对你带来了帮助,欢迎请我喝杯咖啡哦~

文章目录