递归2-回溯与递归

I. 回溯算法基础

• 回溯与递归的区别和联系

    很多人不理解回溯与递归到底是什么关系。其实很简单，回溯算法是一种算法思想，是我们解决问题的策略；而递归是一种算法结构。递归就是函数调用本身，一般回溯法多用递归来实现。

• 回溯法的基本思想

    在按某种搜索策略搜索的过程中，当到达某一状态时，继续向前搜索已经确定不会得到正确答案的情况下，可以返回上一搜索状态，沿着新的可能性继续搜索。其求解过程的实质是一个先序遍历一棵“状态树”的过程。

• 回溯法的特点

  1. 搜索策略:符合递归算法，问题解决可以化为子问题，算法类似，规模减小;
  2. 控制策略:当遇到失败的搜索状态，需要返回上一状态，沿另外的路径搜索;
  3. 数据结构:一般用数组保存搜索过程中的状态、路径。

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