技術文章 » 遞迴與回溯法

遞迴與回溯法

2023-03-18 21:00:40

遞迴

 

引入

　　什麼是遞迴？先看大家都熟悉的一個民間故事：從前有座山，山上有座廟，廟裡有一個老和尚在給小和尚講故事，故事裡說，從前有座山，山上有座廟，廟裡有一個老和尚在給小和尚講故事，故事裡說……。象這樣，一個物件部分地由它自己組成，或者是按它自己定義，我們稱之為遞迴。
　　一個函數、過程、概念或數學結構，如果在其定義或說明內部又直接或間接地出現有其本身的參照，則稱它們是遞迴的或者是遞迴定義的。在程式設計中，過程或函數直接或者間接呼叫自己，就被稱為遞迴呼叫。

遞迴的概念

  • 遞迴過程是藉助於一個遞迴工作棧來實現的
  • 問題向一極推進，這一過程叫做遞推；
  • 問題逐一解決，最後回到原問題，這一過程叫做迴歸。
  • 遞迴的過程正是由遞推和迴歸兩個過程組成。

　　用遞迴方法編寫的問題解決程式具有結構清晰，可讀性強等優點，且遞迴演演算法的設計比非遞迴演演算法的設計往往要容易一些，所以當問題本身是遞迴定義的，或者問題所涉及到的資料結構是遞迴定義的，或者是問題的解決方法是遞迴形式的時候，往往採用遞迴演演算法來解決。

遞迴的應用及實現

　　遞迴演演算法在可計算性理論中佔有重要地位，它是演演算法設計的有力工具，對於拓展程式設計思路非常有用。就遞迴演演算法而言並不涉及高深數學知識，只不過初學者要建立起遞迴概念不十分容易。

　　我們先從一個最簡單的例子匯入。

　　求斐波那契數列的第n位（C++程式碼）：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int fibonacci(int n) {
 5     if (n <= 1) {
 6         return n;
 7     } else {
 8         return fibonacci(n-1) + fibonacci(n-2);
 9     }
10 }
11 
12 int main() {
13     int n ;
14     cin >> n ;
15     printf("斐波那契數列前 %d 項為：\n", n);
16     for (int i = 1; i <= n; i++) {
17         printf("%d ", fibonacci(i));
18     }
19     printf("\n");
20     return 0;
21 }

回溯法

 

回溯法的概念與模板

　　回溯法是一種常用的演演算法，它主要用於解決一些組合優化問題，例如八皇后問題、0/1揹包問題等。回溯法的基本思想是：從問題的某一種狀態開始，搜尋所有可能的情況，直到找到符合要求的解為止。

　　回溯法的實現過程通常採用遞迴的方式，每次遞迴都會嘗試一種可能的情況，如果這種情況不符合要求，就回溯到上一層遞迴，嘗試其它的情況。在回溯的過程中，需要記錄已經嘗試過的情況，以避免重複計算。

　　回溯法的時間複雜度通常比較高，因為它需要搜尋所有可能的情況。但是，在一些特殊的情況下，回溯法可以通過剪枝等優化技巧來提高效率。

　　回溯法是一種常用的演演算法思想，可以用於解決很多問題，比如八皇后問題、0/1揹包問題等。下面是一個用C語言實現回溯法的模板： 
 1 #include <bits/stdc++.h>
 2 
 3 #define MAX_N 100 // 最大的問題規模
 4 
 5 int n; // 問題規模
 6 int a[MAX_N]; // 儲存解的陣列
 7 
 8 // 檢查當前解是否合法
 9 int check(int cur) {
10     // TODO: 根據具體問題實現
11 }
12 
13 // 回溯函數
14 void backtrack(int cur) {
15     if (cur == n) { // 找到一個解
16         // TODO: 處理解的程式碼
17         return;
18     }
19     for (int i = 0; i < n; i++) { // 列舉當前位置的所有可能取值
20         a[cur] = i; // 嘗試將當前位置設為i
21         if (check(cur)) { // 如果當前解合法
22             backtrack(cur + 1); // 繼續搜尋下一個位置
23         }
24     }
25 }
26 
27 int main() {
28     // TODO: 讀入問題規模n和其它必要的輸入
29     backtrack(0); // 從第0個位置開始搜尋
30     return 0;
31 }

在實際使用中，需要根據具體問題實現check函數和處理解的程式碼。

八皇后問題

　　下面是一個八皇后問題的回溯法實現：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int N = 8;
 5 int queen[N]; // 存放每一行皇后所在的列號
 6 
 7 bool check(int row, int col) // 判斷當前位置是否可以放置皇后
 8 {
 9     for (int i = 0; i < row; i++)
10     {
11         if (queen[i] == col || abs(row - i) == abs(col - queen[i]))
12             return false;
13     }
14     return true;
15 }
16 
17 void backtrack(int row) // 回溯函數
18 {
19     if (row == N) // 找到一組解
20     {
21         for (int i = 0; i < N; i++)
22             cout << queen[i] << " ";
23         cout << endl;
24         return;
25     }
26 
27     for (int col = 0; col < N; col++) // 列舉當前行所有可能的列
28     {
29         if (check(row, col)) // 如果當前位置可以放置皇后
30         {
31             queen[row] = col; // 記錄當前皇后所在的列號
32             backtrack(row + 1); // 繼續搜尋下一行
33         }
34     }
35 }
36 
37 int main()
38 {
39     backtrack(0);
40     return 0;
41 }

　　在上面的程式碼中，check函數用於判斷當前位置是否可以放置皇后，backtrack函數用於搜尋所有可能的情況。在搜尋過程中，queen陣列用於記錄每一行皇后所在的列號。

　　回溯法是一種非常實用的演演算法，它可以解決很多組合優化問題。但是，由於回溯法的時間複雜度較高，因此在實際應用中需要注意優化。

 

                                                                        碼字不易，點個讚唄§(*￣▽￣*)§