演算法研討會-含有回溯的遞歸演算法設計探討
- 2019 年 10 月 7 日
- 筆記
含有回溯的遞歸程式設計
目錄
回溯
1.1 概念
- 遞歸是一種演算法結構、技巧，而回溯是一種演算法思想。
- 本質上是一種枚舉思想，採用深度優先策略來枚舉所有可能解，並且服從一定的擇優條件。
- 遵循設定好的擇優條件不斷深入試探，最終達到目標，但是在試探過程中，若發現當前情況不是最優或者一定無法達到目標時，將返回到上一個狀態，對上一個狀態進行重新選擇後，繼續深入試探。
1.2 基本思路
從一條路往前走，能進則進，不能進則退回到最近的岔路，換一條路再試。
1.3 問題舉例
1.3.1 N皇后問題
- 要求
在N × N的棋盤上放置N個皇后，這些皇后之間不能相互攻擊。（合法位置）
- 思路（不考慮優化）
- 遞歸：繼續深入試探下一行的每一列。
- 遞歸邊界：N個皇后全部擺放完成。
- 回溯條件：當前皇后已經不存在合法位置（越界）。
- 具體思路：
- 如果能夠將前面所有的皇后放置在合法位置，那麼就繼續試探下一個皇后，從第1個皇后開始依次類推。
- 如果第k個皇后已經不存在合法位置（越界），那麼判斷第k-1個皇后是否還存在其他合法位置，若存在，則移動到下一個合法位置，重新試探第k個皇后；若不存在，則重複步驟2。
- 第N個皇后同理，只是在第N個皇后放置在合法位置後，到達了遞歸邊界，需要輸出可行解，然後重複步驟2。
- 回溯過程圖解
（圖片轉自部落格園，目前未經過作者同意，如有侵權，將立即刪除！）
- 核心程式碼
void Put_The_Queen_On_The_NOk_Row_And_The_NOj_column(int k, int n) {//需要擺放n個皇后，當前擺放到了第k行。 int j; if(k > n)//發現可行解 print(n); //輸出可行解 else { for(j = 1;j <= n;j++) {//試探這一行的每一列 if(Find_The_Valid_Pos(k, j)) {//判斷該位置是否合法 q[k] = j; //保存位置 Put_The_Queen_On_The_NOk_Row_And_The_NOj_column(k + 1, n); //繼續試探下一行 } } } }1.4 演算法設計
- 清楚遞歸邊界（什麼時候停止遞歸）
- 清楚遞歸函數的功能（參數的功能、返回值的功能）
- 回溯演算法設計基本思路
- 只要當前層還存在合法選項，那麼就在保證當前層合法的前提下，進入試探下一層。
- 如果當前層已經不存在合法選項，那麼就回溯到上一層，並重複判斷1./2.。
- 如果發現可行解，那麼重複判斷1./2.。
1.5 PTA編程題
1.5.1 整數分解為若干項之和
- 要求
將一個正整數N分解成幾個正整數相加，可以有多種分解方法，例如7=6+1，7=5+2，7=5+1+1，…。編程求出正整數N的所有整數分解式子。
-
思路
- 遞歸：
- 遞歸邊界：當前result（填入的所有數之和）與N（目標值）相等
- 回溯條件：當前result（填入的所有數之和）與N（目標值）相等（在此之後不可能再出現可行解，繼續試探沒有意義）。
- 具體思路：
- 每一個位置的值，均從1開始試探。
- 如果當前的result（已經填入的所有數之和）仍小於N（輸入的目標值），那麼就使 第n個數 從 上一個數的數值 往上 試探。
- 如果當前result與N相等，到達遞歸邊界，輸出可行解，並且回溯到上一個狀態（此時只有n-2個數），繼續使第n-1個數自加，並判斷result與N的關係。
- 依次類推，直到遍歷所有可行解。
-
核心程式碼
void Division(int x, int pos, int result){ static int counter, array[32]; if(result != N) { for (int i = x; result + i - 1 < N; i++) { array[pos] = i; Division(i, pos + 1, result + i); } } else{ counter++; std::cout << N << '='; for (int i = 0; i < pos - 1; i++) std::cout << array[i] << '+'; if (counter % 4 == 0 || array[pos - 1] == N) std::cout << array[pos - 1] << std::endl; else std::cout << array[pos - 1] << ';'; } }1.5.2 輸出全排列
-
要求
- 輸出前n個正整數的全排列（n<10）。
- 排列的輸出順序為字典序，即序列a1,a2,⋯,an排在序列b1,b2,⋯,bn之前，如果存在k使得a1=b1,⋯,ak=bk 並且 ak+1<bk+1。
-
思路
- 這題與N皇后問題更加類似，而且運行流程更加簡單。因為回溯只會出現在發現可行解之後，即試探直到發現可行解的過程不會被回溯打斷。
- 遞歸：試探下一位的數字，並且判斷擬填入的數字是否被用過
- 遞歸邊界：全排列數的長度與N（目標值）相等。
- 回溯條件：擬填入的數字已經全部被使用過了。
- 具體思路（「合法」即當前層待填入的數字還未被使用過 ）
- 只要當前層還存在合法選項，那麼就在保證當前層合法的前提下，進入試探下一層。
- 如果當前層已經不存在合法選項，那麼就回溯到上一層，並重複判斷1./2.。
- 如果發現可行解，那麼就重複判斷1./2.。
-
注意
輸入的目標值與全排列數的位數始終是一致的。
-
核心程式碼
/*全局變數*/ int whole_array[32]; // 存儲當前的全排列數 int sub[32]; //記錄每一個數字是否被用過 int N; //目標值 /*遞歸函數*/ void Perm (int x){ static int length = 0; //當前全排列的長度 if(N <= x - 1){ //判斷全排列樹的長度是否等於目標值 for(int i = 1;i <= N;i++) //輸出 printf("%d",whole_array[i]); printf("n"); } else //只要全排列數的長度小於目標值 for(int i = 1;i <= N;i++) //由於要輸出字典序，每一個位置從1開始試探 if(sub[i] == 0){ //判斷這個數是否被用過 whole_array[x] = i; //將這個數 sub[i] = 1; //填入之後將這個數標記為1，即在該全排列數中已經出現 Perm(x + 1); //到下一個位置繼續試探 sub[i] = 0; //如果發生回溯，那麼需要重新將這個數字標記為沒有出現過 } }（部落格內容為原創，未經允許禁止轉載！）
