社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
递归
作为回溯算法的核心逻辑,是学习回溯法等其他算法的先遣知识
。本文从递归的概念开始,举例说明什么是递归。然后介绍回溯算法的概念和理解,最后介绍具体应用并给出Java版本的示例代码。
学习方法:遇到某一个不理解的点时需要暂时跳过
,理解算法时需要认真看代码和注释
(有些还需要一步步调试才能看懂)。先完成整体阅读,然后多读几遍相互启发。
一般能从传入的参数变量处得到结束条件
(我们在设计递归参数时要参照这一点)。递归结束条件
(用来结束递归)和递归方法体
(用来完成问题求解)。通过例子来感受下。public class Main {
public static void main(String[] args) {
System.out.println(recrusion(4));
}
//递归方法
private static int recrusion(int n) {
if (n == 1) return 1; //递归结束条件
int res = recrusion(n - 1) * n; //递归体
return res;
}
}
递归体必须不断逼近递归结束条件
(这是我们在设计递归体需要考虑的,否则就是无限递归)递归运行图解:
回溯算法是一种很重要也比较基础的算法,在面试或算法题中都有涉及。其适用于诸如迷宫问题、N皇后问题,背包问题等复杂问题的求解,有通用解法
的美称。回溯算法是类似于深度优先搜索的试探算法。在构造解的过程中,如果发现不满足条件的解时,就“回溯”(其实就是递归返回
)。博主个人理解是回溯算法其实就是一种穷举法,因为他会尝试遍历所有解(这是回溯法的最坏情况)
。
穷举法
来完成该问题。特定步骤有一般是可重复的
(可重入递归)。一步步构建的
,所以我们要思考选用一种合适的数据结构存储
中间得出来的不完全解。让递归函数可以根据前面的已经递归得到的信息(这些信息包括传进入的参数,构建中间的解和限制条件),选择继续递归或者回溯(就是递归返回)。解的评估算法
,及时排除不符合限制条件的解。启发:
- 回溯法一般是先把第一步的第一种情况遍历完了之后,在遍历第一步的第二种情况。请根据例子理解。
- 调用递归函数时
参数的变化趋势是要逼近结束条件的
。
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手 马克斯●贝瑟尔 于1848年提出。在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列或同-斜线上。问有多少种摆法(92)。
根据2.2 设计回溯算法一般方法进行分析设计算法。
穷举法
(参照上图)
(此时所有在[0,0]的解都已经找到,开始找[0,1]点出的解)
特定步骤
即为 每一层都从0开始放,放到7。重复8层即可遍历所有解。(满足重入递归)
选择合适的数据结构
观察在 【1】 中我们使用[0,0]来表示放置的一个点。但进一步我们发现第一个数仅表示第几层,所以可以使用一个一维数据来表示所有解,而用数组的下标来表示在第几层。如上图的解法可表示为array[3,6,2,7,1,4,0,5]
。解的评估算法
题目限制条件,不能在同一行、同一列、同一斜线。 //查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
/**
* @param n 表示第n个皇后
* @return
*/
private boolean judge(int n) {
judgeCount++;
for(int i = 0; i < n; i++) {
// 说明
//1. array[i] == array[n] 表示判断 第n个皇后是否和前面的n-1个皇后在同一列
//2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
// n = 1 放置第 2列 1 n = 1 array[1] = 1
// Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
//3. 判断是否在同一行, 没有必要,n 每次都在递增
if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
return false;
}
}
return true;
}
//编写一个方法,放置第n个皇后
private void check(int n) {
if(n == max) { // 递归终止条件 当n = 8 , 其实8个皇后就已经放好(从0开始的)
print(); //如果8个都放好了,则打印正确解(待完成)
return;
}
//依次放入皇后,并判断是否冲突
for(int i = 0; i < max; i++) {
//先把当前这个皇后 n , 放到该行的第1列
array[n] = i;
//判断当放置第n个皇后到i列时,是否冲突
if(judge(n)) { // 不冲突
//接着放n+1个皇后,即开始递归
check(n+1); // 递归参数要不断靠近终止条件, 这里n一直变大
}
//如果冲突,就下一步执行循环 array[n] = i+1; 即将第n个皇后,放置在本行的后一个位置,这里产生回溯。
//特别注意: check 是 每一次递归时,进入到check中都有 for(int i = 0; i < max; i++),因此会有回溯
}
}
package stack;
/**
* created by hbl on 2020/3/18.
*/
public class Queue8 {
//定义一个max表示共有多少个皇后
int max = 8;
//定义数组array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3}
int[] array = new int[max];
static int count = 0;
static int judgeCount = 0;
public static void main(String[] args) {
//测试一把 , 8皇后是否正确
Queue8 queue8 = new Queue8();
queue8.check(0);
System.out.printf("一共有%d解法", count);
System.out.printf("一共判断冲突的次数%d次", judgeCount); // 1.5w
}
//编写一个方法,放置第n个皇后
private void check(int n) {
if(n == max) { // 递归终止条件 当n = 8 , 其实8个皇后就已经放好(从0开始的)
print(); //如果8个都放好了,则打印正确解(待完成)
return;
}
//依次放入皇后,并判断是否冲突
for(int i = 0; i < max; i++) {
//先把当前这个皇后 n , 放到该行的第1列
array[n] = i;
//判断当放置第n个皇后到i列时,是否冲突
if(judge(n)) { // 不冲突
//接着放n+1个皇后,即开始递归
check(n+1); // 递归参数要不断靠近终止条件, 这里n一直变大
}
//如果冲突,就下一步执行循环 array[n] = i+1; 即将第n个皇后,放置在本行的后一个位置,这里产生回溯。
//特别注意: check 是 每一次递归时,进入到check中都有 for(int i = 0; i < max; i++),因此会有回溯
}
}
//查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
/**
*
* @param n 表示第n个皇后
* @return
*/
private boolean judge(int n) {
judgeCount++;
for(int i = 0; i < n; i++) {
// 说明
//1. array[i] == array[n] 表示判断 第n个皇后是否和前面的n-1个皇后在同一列
//2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
// n = 1 放置第 2列 1 n = 1 array[1] = 1
// Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
//3. 判断是否在同一行, 没有必要,n 每次都在递增
if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
return false;
}
}
return true;
}
//写一个方法,可以将皇后摆放的位置输出
private void print() {
count++;
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
以下给出三个应用回溯算法的典型应用题,要掌握回溯算法,还需要积累一定的使用经验。
if (leftNum == 0 && rightNum == 0)//结束
results.add(sbTemp.toString());
StringBuffer
进行存储(也可以使用String,因为当时想着可能会进行拼接,但后来发现每次都需要new ,这里涉及到引用类型的共享性问题,需要仔细体会)。(ps:用了一个ArrayList存放所有的解,一般我们都会把算好的所有正确结果存放到一个容器里
,便于传递和解耦。当学习算法时其实可以直接打印出来:如八皇后的print()
方法)并不是所有的算法都需要单独的评估算法
,这里进入的不同if进行递归,当所有递归返回时,算法就完成了,结合1。我们所有正确的解都是在第一次运行递归时
第二个if
里递归迭代出来的,因为最开始只能画一个左括号。有些题目if的顺序还有关系,但是这道题,两个if条件倒换一下,也能得出正确解。
if (rightNum > leftNum)//选择和条件。 就是我们每一步选择写一个括号的逻辑。
recrusion(new StringBuffer(sbTemp).append(')'), leftNum, rightNum - 1);
if (leftNum > 0) // 第一个if进入后,会进入第二个if,遍历所有可能的情况。因为增加括号时,不是增加"(" 就是增加")" 两者必居其一
recrusion(new StringBuffer(sbTemp).append('('), leftNum - 1, rightNum);
/**
* created by hbl on 2020/3/18.
*/
import java.util.ArrayList;
public class BackTracking {
static ArrayList<String> results = new ArrayList<String>();//用于存放解空间
public static void main(String[] args) {
int n = 3;
int leftNum = n, rightNum = n;//左括号和右括号都各有n个
recrusion(new StringBuffer(), leftNum, rightNum);
for (String s : results)
System.out.println(s);
}
/**回溯算法
* @param sbTemp 不完整解
* @param leftNum 剩余左括号数
* @param rightNum 剩余右括号数
*/
public static void recrusion(StringBuffer sbTemp, int leftNum, int rightNum) {
if (leftNum == 0 && rightNum == 0)//结束
results.add(sbTemp.toString());
if (rightNum > leftNum)//选择和条件。 就是我们每一步选择写一个括号的逻辑。
recrusion(new StringBuffer(sbTemp).append(')'), leftNum, rightNum - 1);
if (leftNum > 0) // 第一个if进入后,会进入第二个if,遍历所有可能的情况。因为增加括号时,不是增加"(" 就是增加")" 两者必居其一
recrusion(new StringBuffer(sbTemp).append('('), leftNum - 1, rightNum);
}
}
/**
* Question:给出一个不重复大于0数字的数组和一个目标,求数组中数的组合的和得到该目标(数字不同组合顺序当做一个解)。
* example: arrays [2,3,7,6] target: 9
* solutions:
* 2 7
* 7 2
* 3 6
* 6 3
*/
public class BackTracking {
static int[] num = new int[]{2, 3, 7, 6};
static int target = 9;
public static void main(String[] args) {
find(num, "");
}
public static void find(int[] num, String temp) {
if (evaluate(temp, target)) {
System.out.println(temp);
return;
}
for (int i = 0; i < num.length; i++) {
if (num[i] != -1) {//如果取过这个数字了,就置为-1
int k = num[i];
num[i] = -1;
find(num, temp + k);
num[i] = k;
}
}
}
public static boolean evaluate(String temp, int target) {
int count = 0;
for (int i = 0; i < temp.length(); i++) {
count = count + temp.charAt(i) - 48; // char类型 '0' 的ascII 为48
}
return target == count;
}
}
如果有什么错误或不足,欢迎交流 !
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!