I. 回溯算法基础
-
回溯与递归的区别和联系
很多人不理解回溯与递归到底是什么关系。其实很简单，回溯算法是一种算法思想，是我们解决问题的策略；而递归是一种算法结构。递归就是函数调用本身，一般回溯法多用递归来实现。 -
回溯法的基本思想
在按某种搜索策略搜索的过程中，当到达某一状态时，继续向前搜索已经确定不会得到正确答案的情况下，可以返回上一搜索状态，沿着新的可能性继续搜索。其求解过程的实质是一个先序遍历一棵“状态树”的过程。 -
回溯法的特点
- 搜索策略:符合递归算法，问题解决可以化为子问题，算法类似，规模减小;
- 控制策略:当遇到失败的搜索状态，需要返回上一状态，沿另外的路径搜索;
- 数据结构:一般用数组保存搜索过程中的状态、路径。
II. 回溯法的经典例子
-
爬楼梯问题
对于一个与 n 级台阶组成的楼梯，爬楼梯时一次可以上 1 级台阶或 2 级台阶。共有多少种不同的走法。
1. 问题分析
由题可知，在任何一级台阶我们往上爬的时候都有两种选择:爬 1 级台阶或者爬2 级台阶。那就会产生回溯，当我们爬 2 级台阶会超出楼梯时，我们再返回来爬 1 级台阶;其次，n 级台阶可能是由第 n-1 级台阶爬上来的，也可能是从第 n-2 级台 阶爬上来的。所以，对于 n 级台阶的问题又可以分解成为两个相似的字问题。符合递归的条件。
2. Java代码实现
/**
* @Author: 落脚丶
* @Date: 2017/10/15
* @Time: 上午11:24
* @ClassName: ClimbStairs
* @Description: 爬楼梯方法的回溯解法
*/
public class ClimbStairs {
static int s = 1;
public static int[] steps = new int[10];
public static void main(String[] args){
System.out.println("请输入台阶数：");
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
tryStep(n);
}
static void tryStep(int n){ // 爬n级楼梯
for (int i = 1; i <= 2; i++){
// 对于每次爬有两次尝试，一次爬1级或者一次爬2级
if (n < i)
break;
steps[s++] = i; // 一步走了i级台阶
n -= i; //缩小问题的规模
if (n == 0) {
for (int j = 1; j < s; j++){
System.out.print("第"+ j + "步走了" + steps[j]
+ "级台阶 ");
}
System.out.println();
} else {
tryStep(n);
}
n += i;
steps[s--] = 0;
}
}
}
/**
* 以4级台阶为例的输出：
*
* 请输入台阶数：
* 4
* 第1步走了1级台阶 第2步走了1级台阶 第3步走了1级台阶 第4步走了1级台阶
* 第1步走了1级台阶 第2步走了1级台阶 第3步走了2级台阶
* 第1步走了1级台阶 第2步走了2级台阶 第3步走了1级台阶
* 第1步走了2级台阶 第2步走了1级台阶 第3步走了1级台阶
* 第1步走了2级台阶 第2步走了2级台阶
*/
-
八皇后问题
在国际象棋棋盘8 × 8上放置八个皇后，使得任意两个皇后之间不能在同一行，同一列，也不能位于同于对角线上。问共有多少种不同的方法，并且指出各种不同的放法。
1. 算法思路:
我们知道，假如不考虑题中的限制，每行放置皇后都有 8 种放法，我们可以用一个完全八叉树来描述整个过程。而实际问题中我们需要根据条件来对树进行枝。
我们可以定义一个数组 position[8]，其中 position[i] = j 代表第 i 行 j 列。于是，约束条件可以如下表示:
a. 不在同一列:position[i] != position[j];
b. 不在对角线上:|i − j| != |position[i] − position[j]|.从第一行确定第 1 个皇后的位置，然后在第二行搜索第 2 个皇后的位置，... ， 每前进一步检查是否满足约束条件，不满足约束条件的时候回溯到上一个皇后的位置，尝试该行其他列是否满足条件，直到找到问题解。
2. 算法的Java实现:
/**
* @Author: 落脚丶
* @Date: 2017/10/18
* @Time: 下午4:55
* @ClassName: EightQueen
* @Description: 8皇后问题回溯解法
*/
public class EightQueen {
private static int num = 1; // 方案的总数
private static final int MAX_QUEEN = 8;
private static int[] position = new int[MAX_QUEEN];
public static void main(String[] args) {
trail(0);
}
/**
* @Date: 2017/10/18
* @Time: 下午5:00
* @Method: isValid
* @Return: 位置是否满足条件
* @Description: 判断位置是否满足条件
*/
static boolean isValid(int row) {
for (int i = 0; i < row; i++) {
/**
* 如果前面放好的位置不在同一行、同一列、同一对角线
* 则返回true
* 否则返回false
*/
if (position[i] == position[row] ||
Math.abs(position[i] - position[row]) ==
Math.abs(i - row) ) {
return false;
}
}
return true;
}
/**
* @Date: 2017/10/18
* @Time: 下午5:29
* @Method: print
* @Description: 打印皇后摆放位置的结果
*/
static void print() {
System.out.println("第" + num++ +"种摆法：");
for (int i = 0; i < MAX_QUEEN; i++) {
for (int j = 0; j < MAX_QUEEN; j++) {
if(position[i] == j)
System.out.print("+ ");
else
System.out.print("0 ");
}
System.out.println();
}
System.out.println();
}
static void trail(int row) {
// 如果摆完MAX_QUEEN行，则输出结果
if (row == MAX_QUEEN) {
print();
return;
}
for (int column = 0; column < MAX_QUEEN; column++) {
position[row] = column; // 放在第row行第column列
// 如果满足条件，则进行下一行
if (isValid(row))
trail(row + 1);
}
}
}
部分输出结果（合成图片）：
结果展示.jpg
网友评论