Fork me on GitHub

算法之美-回溯

N皇后的问题应该怎么解决?回溯法来帮忙!
此处输入图片的描述

什么是回溯?

回溯法思路的简单描述是:把问题的解空间转化成了图或者树的结构表示,然后使用深度优先搜索策略进行遍历,遍历的过程中记录和寻找所有可行解或者最优解。基本思想类同于图的深度优先搜索和二叉树的后序遍历。

回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树,当算法搜索至解空间树的某一节点时,先利用剪枝函数判断该节点是否可行(即能得到问题的解)。如果不可行,则跳过对该节点为根的子树的搜索,逐层向其祖先节点回溯;否则,进入该子树,继续按深度优先策略搜索。

回溯法的基本思想是按照输入数组的顺序,每一层递归处理一个元素,当处理到最后一层的时候,也就是把数组中的所有元素都处理完的时候,把当前结果加入到最后的返回结果中。值得注意的是,每次在递归到下一层之前,我们加入了某个要处理的元素X,在下一层递归返回之后,我们要把之前加入的元素X从当前结果中取出来。如果我们不把元素X取出来,那么在下一次循环中,我们还会加入新的元素Y。那么在这一层递归中就相当于处理了不止一个新元素。

经典题目实例

(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
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
private int rows;
private int cols;
public boolean hasPath(char[] array, int rows, int cols, char[] str) {
//异常情况判断
if(array.length == 0 || array.length != rows * cols){
return false;
}
if(str.length == 0){
return true;
}
char[][] matrix = new char[rows][cols];
boolean[][] mark = new boolean[rows][cols];

this.rows = rows;
this.cols = cols;
//把一维数组转化成二维矩阵
for (int r = 0, idx = 0; r < rows; r++) { //注意括号内的inx的定义方式
for (int c = 0; c < cols; c++) {
matrix[r][c] = array[idx++];
}
}
//遍历数组每个元素,依次与字符串比较
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (matrix[r][c] == str[0]) {
mark[r][c] = true;
if(helper(matrix, r, c, str,mark, 0)){
return true;
}
mark[r][c] = false;
}
}

}
return false;
}

//回溯算法的主体,依次迭代,直到最后的结论;
private boolean helper(char[][] matrix, int r, int c, char[] str,boolean[][] mark, int number) {

if(number == str.length-1){
return true;
}
number += 1;
if(r-1 >=0){
if(matrix[r-1][c] == str[number] && !mark[r-1][c]){
mark[r-1][c] = true;
if(helper(matrix, r-1, c, str, mark, number)){
return true;
}
}
}
if(r+1 < rows){
if(matrix[r+1][c] == str[number] && !mark[r+1][c]){
mark[r+1][c] = true;

if(helper(matrix, r+1, c, str, mark, number)){
return true;
}
}
}
if(c-1 >= 0){
if(matrix[r][c-1] == str[number] && !mark[r][c-1]){
mark[r][c-1] = true;
if(helper(matrix, r, c-1, str, mark, number)){
return true;
}
}
}
if(c+1 < cols){
if(matrix[r][c+1] == str[number] && !mark[r][c+1]){
mark[r][c+1] = true;
if(helper(matrix, r, c+1, str, mark, number)){
return true;
}
}
}
return false;
}

(2)机器人的运动范围

题目描述:地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动,每一次只能向左右上下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k 的格子。例如,当 k 为 18 时,机器人能够进入方格 (35,37),因为 3+5+3+7=18。但是,它不能进入方格 (35,38),因为 3+5+3+8=19。请问该机器人能够达到多少个格子?
题解:

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
private int rows;
private int cols;
private int result = 0;
private boolean[][] mark;
public int movingCount(int threshold, int rows, int cols){
this.rows = rows;
this.cols = cols;
this.mark = new boolean[rows][cols];
boolean[][] marktmp = new boolean[rows][cols];
//注意边界问题
if(!(threshold <= 0 || rows <=0 || cols <=0)){
helper(threshold,rows,cols,0,0,marktmp);
}


return result;
}
//回溯法核心
private void helper(int threshold, int rows, int cols, int r, int c, boolean[][] marktmp) {
if(judge(threshold,r,c) && !marktmp[r][c]){
System.out.println(Integer.toString(threshold)+" "+Integer.toString(r)+" "+Integer.toString(c));
marktmp[r][c] = true;
if(mark[r][c] == false){
mark[r][c] = true;
result++;
}
if(r+1 < rows){
helper(threshold,rows,cols,r+1,c,marktmp);
}
if(c+1<cols){
helper(threshold,rows,cols,r,c+1,marktmp);
}
if(r-1 >=0){
helper(threshold,rows,cols,r-1,c,marktmp);
}
if(c-1 >=0){
helper(threshold,rows,cols,r,c-1,marktmp);
}
}
}
//判断是否符合规则
private boolean judge(int threshold, int row, int col){
int tmp = 0;
while(row >0){
tmp += row%10;
row/=10;
}
while(col >0){
tmp += col%10;
col/=10;
}
return threshold >= tmp?true:false;
}

(3)N皇后问题

题目描述:要求在一个n×n的棋盘上放置n个皇后,使得它们彼此不受攻击。按照国际象棋的规则,一个皇后可以攻击与之同一行或同一列或同一斜线上的任何棋子。因此,n皇后问题等价于:要求在一个n×n的棋盘上放置n个皇后,使得任意两个皇后不在同一行或同一列或同一斜线上。
题解:

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
   private static int SIZE = 0;//皇后的个数
private static int count = 0;//记录摆放的方式数
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
System.out.println("请输入你要解决几个皇后的问题");
SIZE = input.nextInt();
input.close();
LinkedList<Location> list = new LinkedList<Location>();
NQueen(list, 0, 0); //从棋盘的第0行第0列开始
System.out.println(SIZE + "皇后共有 " + count + "种摆放方式");

}
static class Location{
int x;//对应棋盘的行
int y;//对应棋盘的列

Location(int x,int y){
this.x = x;
this.y = y;
}

public String toString() {
return "(" + x + "," + y + ")";
}
}

/**
* 主要函数,用回溯法。
*/
private static void NQueen(LinkedList<Location> list, int x, int y) {

if(list.size() == SIZE){ //当list元素个数为SIZE时,表示SIZE个皇后都摆放完毕,打印后即可退出函数。
printLocation(list); //打印皇后摆放方式
return ;
}

for(int i = x ; i < SIZE ; i++){
Location loc = new Location(i, y);
if(isLegalLoc(list, loc)){
list.offer(loc); //将第y行的皇后摆放好
NQueen(list, 0, y+1); //开始摆放y+1行的皇后,同样从第0列开始摆放
list.pollLast(); //每次摆放完一个皇后后,都要将其撤回,再试探其它的摆法。
}
}
}


/**
* 判断位置为loc的皇后是否合法
*/
private static boolean isLegalLoc(LinkedList<Location> list, Location loc) {
for(Location each : list){
if(loc.x == each.x || loc.y == each.y) //判断是否在同一行或同一列
return false;
else if (Math.abs(loc.x - each.x) == Math.abs(loc.y - each.y)) //判断是否在同斜线上
return false;
}
return true;
}

/**
* 打印皇后摆放方式
* @param list
*/
private static void printLocation(LinkedList<Location> list) {
String[][] show = new String[SIZE][SIZE];
for(int i = 0;i<SIZE;i++) {
for(int j = 0;j<SIZE;j++) {
show[i][j] = "0";
}
}
for(Location each : list){
System.out.print(each.toString() + "\t");
show[each.x][each.y] = "1";
}
System.out.println();

for(int i =0;i<SIZE;i++) {
for(int j=0;j<SIZE;j++) {
System.out.print(show[i][j] + " ");
}
System.out.println();
}
System.out.println();

count ++;
}

(4)迷宫问题

题目描述:以一个M×N的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
(1) 根据二维数组,输出迷宫的图形。
(2) 探索迷宫的四个方向:RIGHT为向右,DOWN向下,LEFT向左,UP向上,输出从入口到出口的行走路径。
题解:

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
class Position{
public Position(){

}

public Position(int row, int col){
this.col = col;
this.row = row;
}

public String toString(){
return "(" + row + " ," + col + ")";
}

int row;
int col;
}

class Maze{
public Maze(){
maze = new int[15][15];
stack = new Stack<Position>();
p = new boolean[15][15];
}

/*
* 构造迷宫
*/
public void init(){
Scanner scanner = new Scanner(System.in);
System.out.println("请输入迷宫的行数");
row = scanner.nextInt();
System.out.println("请输入迷宫的列数");
col = scanner.nextInt();
System.out.println("请输入" + row + "行" + col + "列的迷宫");
int temp = 0;
for(int i = 0; i < row; ++i) {
for(int j = 0; j < col; ++j) {
temp = scanner.nextInt();
maze[i][j] = temp;
p[i][j] = false;
}
}
}

/*
* 回溯迷宫,查看是否有出路
*/
public void findPath(){
// 给原始迷宫的周围家一圈围墙
int temp[][] = new int[row + 2][col + 2];
for(int i = 0; i < row + 2; ++i) {
for(int j = 0; j < col + 2; ++j) {
temp[0][j] = 1;
temp[row + 1][j] = 1;
temp[i][0] = temp[i][col + 1] = 1;
}
}
// 将原始迷宫复制到新的迷宫中
for(int i = 0; i < row; ++i) {
for(int j = 0; j < col; ++j) {
temp[i + 1][j + 1] = maze[i][j];
}
}
// 从左上角开始按照顺时针开始查询

int i = 1;
int j = 1;
p[i][j] = true;
stack.push(new Position(i, j));
while (!stack.empty() && (!(i == (row) && (j == col)))) {

if ((temp[i][j + 1] == 0) && (p[i][j + 1] == false)) {
p[i][j + 1] = true;
stack.push(new Position(i, j + 1));
j++;
} else if ((temp[i + 1][j] == 0) && (p[i + 1][j] == false)) {
p[i + 1][j] = true;
stack.push(new Position(i + 1, j));
i++;
} else if ((temp[i][j - 1] == 0) && (p[i][j - 1] == false)) {
p[i][j - 1] = true;
stack.push(new Position(i, j - 1));
j--;
} else if ((temp[i - 1][j] == 0) && (p[i - 1][j] == false)) {
p[i - 1][j] = true;
stack.push(new Position(i - 1, j));
i--;
} else {
stack.pop();
if(stack.empty()){
break;
}
i = stack.peek().row;
j = stack.peek().col;
}

}

Stack<Position> newPos = new Stack<Position>();
if (stack.empty()) {
System.out.println("没有路径");
} else {
System.out.println("有路径");
System.out.println("路径如下:");
while (!stack.empty()) {
Position pos = new Position();
pos = stack.pop();
newPos.push(pos);
}
}

/*
* 图形化输出路径
* */

String resault[][]=new String[row+1][col+1];
for(int k=0;k<row;++k){
for(int t=0;t<col;++t){
resault[k][t]=(maze[k][t])+"";
}
}
while (!newPos.empty()) {
Position p1=newPos.pop();
resault[p1.row-1][p1.col-1]="#";

}

for(int k=0;k<row;++k){
for(int t=0;t<col;++t){
System.out.print(resault[k][t]+"\t");
}
System.out.println();
}


}

int maze[][];
private int row = 9;
private int col = 8;
Stack<Position> stack;
boolean p[][] = null;
}

class hello{
public static void main(String[] args){
Maze demo = new Maze();
demo.init();
demo.findPath();
}
}

-------------本文结束感谢阅读-------------