# 深度優先搜索
## 深度優先搜索
深度優先搜索是一種枚舉完所有完整路徑以遍歷所有情況的搜索方法。一般用遞歸實現，遞歸的分叉就是搜索的岔路，遞歸的邊界就是搜索的死胡同。
例如：有 n(n≤25) 件物品，每件種為 w[i]，價值為 c[i]，選出若干件放入限重為 W 的背包中，在不超重是前提下使得背包中的物品價值最大，求最大價值。
```C++
#include <cstdio>
const int maxn=30;
int n,v,maxv=0;
int w[maxn], c[maxn];
void DFS(int index,int sumw,int sumv){
if(index==n) return;
// 岔路：選不選 index+1
DFS(index+1,sumw,sumv);
if(sumw+w[index]<=v){
if(sumv+c[index]>maxv) maxv=sumv+c[index];
DFS(index+1,sumw+w[index],sumv+c[index]);
}
}
int main(){
// 輸入n,v c[i],w[i]
DFS(0,0,0);
// 輸出 maxv
return 0;
}
```
## 遞歸
遞歸求解的特征是分而治之，即將整個問題分割為與整個問題求解方法相同的子問題，反復劃分子問題并求解子問題，最后得到整個問題的解。
### 復雜遞歸
遞歸問題的參數構成了遞歸狀態。對于復雜問題，常采用試探方法。假設遞歸求解過程從狀態 s0 到狀態 sn，求解步驟如下：
* 假設當前狀態為 si，將 si 的環境設置為已處理過。
* 求出從 si 出發可以到達狀態 sj，若 sj=sn，輸出一個解；否則遞歸調用 sj，表示從 sj 開始處理。
* 若從 si 出發不能到達任何狀態，則回溯，將 si 狀態設置為未處理過。
以求解迷宮問題為例：
```C
struct{
int i;
int j;
}path[MaxSize];
void mgpath(int si, int sj, int ei, int ej, int d)
{
int i, j;
mg[si][sj] = -1; // 將當前環境設置為已處理過
di = -1;
// 判斷所有相鄰的方塊是否可以達到
while(di<4){
di++;
switch(di){
case 0: i = si; j = sj+1; break;
case 1: i = si+1; j = sj; break;
case 2: i = si; j = sj-1; break;
case 3: i = si-1; j = s.j; break;
}
// 若下一個狀態為最終要達到的狀態，則輸出一個解
if(i==ei && j==ej){
printf("Find a path that:\n");
path[d+1].i = i; path[d+1].j = j;
for(int k=0; k<=d+1;k++){
printf("(%d, %d)", path[k].i, path[k].j);
}
}
// 若存在下一個狀態，則開始處理下一個狀態，即遞歸調用
else if(mg[i][j]==0){
path[d+1].i = i; path[d+1].j = j;
mgpath(i, j, ei, ej, d+1);
}
}
// 不能達到任何狀態，則恢復當前環境，回溯
mg[i][j] = 0;
}
```
### 遞歸算法到非遞歸算法的轉換
遞歸算法時間效率通常較差，因此需要手工轉化為非遞歸算法。
#### 用循環消除單向遞歸
尾遞歸是指遞歸調用語句只有一個且處于算法的末尾，是單向遞歸的特例，例如階乘。
單向遞歸是指遞歸函數雖然有一處以上的遞歸調用語句，但各次遞歸調用語句的參數只和主調用函數有關，與相互之間的參數無關。例如，求 Fibonacci 數列$f(n)=f(n-1)+f(n-2)$ ，遞歸調用$f(n-1)$ 和$f(n-2)$ 只和主調用 $f(n)$ 有關，因此可用循環消除遞歸：
```C
int Fib(int n)
{
int f1 = 1;
int f2 = 2;
if(n==1)
return f1;
if(n==2)
return f2;
int f3;
for(int i=3; i<=n; i++){
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}
```
#### 利用棧消除非單向遞歸
主要注意兩點：
* 建立一個結構用于存放各狀態下產生的值和判斷是否執行操作（不再遞歸）的標識
* 注意復雜問題當前狀態不能繼續時需要恢復環境
以求解梵塔問題為例：
設 $hanoi(n,x,y,z)$ 表示將 n 個圓盤從 x 通過 y 移動到 z 上，則有：
* $hanoi(n,x,y,z): move(n,x,z)$ ，當 n=1 時
* $hanoi(n,x,y,z): hanoi(n-1,x,z,y); move(n,x,z);hanoi(n-1,y,x,z)$ ，其他情況
對應的遞歸算法是：
```C
void hanoi(int n, char x, char y, char z)
{
if(n==1)
printf("move the % plate from %c to %c", n, x, z);
else{
hanoi(n-1, x, z, y);
printf("move the % plate from %c to %c", n, x, z);
hanoi(n-1, y, x, z);
}
}
```
轉化為非遞歸算法：
```C
#include <stdio.h>
#define MaxSize 100
int main()
{
int n;
char x, y, z;
n = 3;
x = 'A'; y = 'B'; z = 'C';
struct stack{
// 保存狀態 n 下的值
int n;
char x, y, z;
// 標識可否執行操作，1 表示可執行
int tag;
}st[MaxSize];
int top = -1;
char a, b, c;
int m;
// 將狀態 n 入棧
top++;
st[top].n = n;
st[top].x = x; st[top].y = y; st[top].z = z;
st[top].tag = 0;
while(top>-1){
// 判斷可否執行操作（或者稱是否需要再遞歸）
if(st[top].tag==0){
// 判斷是否達到遞歸的終止條件
if(st[top].n==1){
st[top].tag = 1;
}
// 將遞歸的狀態入棧
else{
// 狀態 n 退棧
m = st[top].n;
a = st[top].x; b = st[top].y; c = st[top].z;
top--;
// 狀態 n-1 入棧，入棧的順序與遞歸相反
top++;
st[top].n = m-1;
st[top].x = b; st[top].y = a; st[top].z = c;
st[top].tag = 0;
top++;
st[top].n = m;
st[top].x = a; st[top].z = c;
st[top].tag = 1;
top++;
st[top].n = m-1;
st[top].x = a; st[top].y = c; st[top].z = b;
st[top].tag = 0;
}
}
else if(top>-1 && st[top].tag==1){
printf("move the %d plate from %c to %c\n", st[top].n, st[top].x, st[top].z);
top--;
}
}
return 0;
}
```
