遞歸2-回溯與遞歸

I. 回溯算法基礎(chǔ)
  • 回溯與遞歸的區(qū)別和聯(lián)系
    ? 很多人不理解回溯與遞歸到底是什么關(guān)系。其實(shí)很簡(jiǎn)單，回溯算法是一種算法思想，是我們解決問(wèn)題的策略；而遞歸是一種算法結(jié)構(gòu)。遞歸就是函數(shù)調(diào)用本身，一般回溯法多用遞歸來(lái)實(shí)現(xiàn)。
  • 回溯法的基本思想
    ? 在按某種搜索策略搜索的過(guò)程中，當(dāng)?shù)竭_(dá)某一狀態(tài)時(shí)，繼續(xù)向前搜索已經(jīng)確定不會(huì)得到正確答案的情況下，可以返回上一搜索狀態(tài)，沿著新的可能性繼續(xù)搜索。其求解過(guò)程的實(shí)質(zhì)是一個(gè)先序遍歷一棵“狀態(tài)樹(shù)”的過(guò)程。
  • 回溯法的特點(diǎn)
    1. 搜索策略:符合遞歸算法，問(wèn)題解決可以化為子問(wèn)題，算法類(lèi)似，規(guī)模減小;
    2. 控制策略:當(dāng)遇到失敗的搜索狀態(tài)，需要返回上一狀態(tài)，沿另外的路徑搜索;
    3. 數(shù)據(jù)結(jié)構(gòu):一般用數(shù)組保存搜索過(guò)程中的狀態(tài)、路徑。
II. 回溯法的經(jīng)典例子
  • 爬樓梯問(wèn)題

? 對(duì)于一個(gè)與 n 級(jí)臺(tái)階組成的樓梯，爬樓梯時(shí)一次可以上 1 級(jí)臺(tái)階或 2 級(jí)臺(tái)階。共有多少種不同的走法。
1. 問(wèn)題分析
?由題可知，在任何一級(jí)臺(tái)階我們往上爬的時(shí)候都有兩種選擇:爬 1 級(jí)臺(tái)階或者爬2 級(jí)臺(tái)階。那就會(huì)產(chǎn)生回溯，當(dāng)我們爬 2 級(jí)臺(tái)階會(huì)超出樓梯時(shí)，我們?cè)俜祷貋?lái)爬 1 級(jí)臺(tái)階;其次，n 級(jí)臺(tái)階可能是由第 n-1 級(jí)臺(tái)階爬上來(lái)的，也可能是從第 n-2 級(jí)臺(tái) 階爬上來(lái)的。所以，對(duì)于 n 級(jí)臺(tái)階的問(wèn)題又可以分解成為兩個(gè)相似的字問(wèn)題。符合遞歸的條件。
2. Java代碼實(shí)現(xiàn)

/**
* @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("請(qǐng)輸入臺(tái)階數(shù)：");
     Scanner scanner = new Scanner(System.in);
     int n = scanner.nextInt();
     tryStep(n);
 }
 static void tryStep(int n){ // 爬n級(jí)樓梯
     for (int i = 1; i <= 2; i++){
         // 對(duì)于每次爬有兩次嘗試，一次爬1級(jí)或者一次爬2級(jí)
         if (n < i)
             break;
         steps[s++] = i; // 一步走了i級(jí)臺(tái)階
         n -= i; //縮小問(wèn)題的規(guī)模
         if (n == 0) {
             for (int j = 1; j < s; j++){
                 System.out.print("第"+ j + "步走了" + steps[j] 
                 + "級(jí)臺(tái)階 ");
             }
             System.out.println();
         } else {
             tryStep(n);
         }
         n += i;
         steps[s--] = 0;
     }
 }
}
/**
* 以4級(jí)臺(tái)階為例的輸出：
*
* 請(qǐng)輸入臺(tái)階數(shù)：
* 4
* 第1步走了1級(jí)臺(tái)階 第2步走了1級(jí)臺(tái)階 第3步走了1級(jí)臺(tái)階 第4步走了1級(jí)臺(tái)階
* 第1步走了1級(jí)臺(tái)階 第2步走了1級(jí)臺(tái)階 第3步走了2級(jí)臺(tái)階
* 第1步走了1級(jí)臺(tái)階 第2步走了2級(jí)臺(tái)階 第3步走了1級(jí)臺(tái)階
* 第1步走了2級(jí)臺(tái)階 第2步走了1級(jí)臺(tái)階 第3步走了1級(jí)臺(tái)階
* 第1步走了2級(jí)臺(tái)階 第2步走了2級(jí)臺(tái)階 
*/
  • 八皇后問(wèn)題

    ? 在國(guó)際象棋棋盤(pán)8 × 8上放置八個(gè)皇后，使得任意兩個(gè)皇后之間不能在同一行，同一列，也不能位于同于對(duì)角線上。問(wèn)共有多少種不同的方法，并且指出各種不同的放法。
    1. 算法思路:
    ? 我們知道，假如不考慮題中的限制，每行放置皇后都有 8 種放法，我們可以用一個(gè)完全八叉樹(shù)來(lái)描述整個(gè)過(guò)程。而實(shí)際問(wèn)題中我們需要根據(jù)條件來(lái)對(duì)樹(shù)進(jìn)行枝。
    ? 我們可以定義一個(gè)數(shù)組 position[8]，其中 position[i] = j 代表第 i 行 j 列。于是，約束條件可以如下表示:
    a. 不在同一列:position[i] != position[j];
    b. 不在對(duì)角線上:|i ? j| != |position[i] ? position[j]|.

    ? 從第一行確定第 1 個(gè)皇后的位置，然后在第二行搜索第 2 個(gè)皇后的位置，... ， 每前進(jìn)一步檢查是否滿足約束條件，不滿足約束條件的時(shí)候回溯到上一個(gè)皇后的位置，嘗試該行其他列是否滿足條件，直到找到問(wèn)題解。
    2. 算法的Java實(shí)現(xiàn):

/**
 * @Author: 落腳丶
 * @Date: 2017/10/18
 * @Time: 下午4:55
 * @ClassName: EightQueen
 * @Description: 8皇后問(wèn)題回溯解法
 */
public class EightQueen {
    private static int num = 1; // 方案的總數(shù)
    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++) {
            /**
             * 如果前面放好的位置不在同一行、同一列、同一對(duì)角線
             * 則返回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: 打印皇后擺放位置的結(jié)果
    */
    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行，則輸出結(jié)果
        if (row == MAX_QUEEN) {
            print();
            return;
        }
        for (int column = 0; column < MAX_QUEEN; column++) {
            position[row] = column; // 放在第row行第column列
            // 如果滿足條件，則進(jìn)行下一行
            if (isValid(row))
                trail(row + 1);
        }
    }
}

部分輸出結(jié)果（合成圖片）：


結(jié)果展示.jpg
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 回溯算法 回溯法：也稱(chēng)為試探法，它并不考慮問(wèn)題規(guī)模的大小，而是從問(wèn)題的最明顯的最小規(guī)模開(kāi)始逐步求解出可能的答案，并...
    fredal閱讀 14,015評(píng)論 0贊 89
  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問(wèn)題, 分享了一些自己做題目的經(jīng)驗(yàn)。 張土汪：刷leetcod...
    土汪閱讀 12,928評(píng)論 0贊 33
  • LeetCode 刷題隨手記 - 第一部分 前 256 題（非會(huì)員），僅算法題，的吐槽 https://leetc...
    蕾娜漢默閱讀 18,395評(píng)論 2贊 36
  • 貪心算法 貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上...
    fredal閱讀 9,424評(píng)論 3贊 52
  • 昨天在公交車(chē)上狠狠地哭了一通，像斷線的珠子一大滴一大滴的。 坐隔壁的隔壁的中年男人用復(fù)雜的眼神看著我，但我又有什么...
    巫女不WU閱讀 493評(píng)論 0贊 1

友情鏈接更多精彩內(nèi)容