DFS（深度優(yōu)先搜索）是一種常見的算法，我們平時(shí)遇到的大部分題目都可以用 DFS 解決，但是一般情況下，這都是騙分算法，很少會有爆搜為正解的題目。因?yàn)?DFS 的時(shí)間復(fù)雜度特別高。

一、定義

DFS（深度優(yōu)先搜索）定義上的深度優(yōu)先搜索的思路與樹的先序遍歷非常相似，是針對圖的搜索而提出的一種算法，下面是算法導(dǎo)論上的解釋：

在深度優(yōu)先搜索中，對于最新發(fā)現(xiàn)的頂點(diǎn)，如果它還有以此為頂點(diǎn)而未探測到的邊，就沿此邊繼續(xù)探測下去，當(dāng)頂點(diǎn)v的所有邊都已被探尋過后，搜索將回溯到發(fā)現(xiàn)頂點(diǎn)v有起始點(diǎn)的那些邊。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源頂點(diǎn)可達(dá)的所有頂點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的頂點(diǎn)，則選擇其中一個(gè)作為源頂點(diǎn)，并重復(fù)上述過程。整個(gè)過程反復(fù)進(jìn)行，直到所有的頂點(diǎn)都被發(fā)現(xiàn)時(shí)為止。

在實(shí)際的操作中，我們一般對深度優(yōu)先搜索問題進(jìn)行分類：

（1）定義的DFS：對圖的連通性進(jìn)行測試，典型的問題：迷宮連通性測試、圖的條件搜索等

（2）廣義的DFS–DFS思路的應(yīng)用：DFS搜索順序+規(guī)則問題、窮舉結(jié)果尋求最優(yōu)解/符合條件解等等，由于其窮舉答案的本質(zhì)，又被稱為爆搜

深度優(yōu)先搜索(下文統(tǒng)稱DFS)的精髓在于遞歸求解問題的思路以及回溯的處理。而針對搜索的過程，又有更為重要的剪枝、優(yōu)化，必要的剪枝優(yōu)化(通過對窮舉答案方式進(jìn)行改進(jìn))對DFS的順利執(zhí)行有著不可或缺的作用。本文章將針對DFS的原理、常見的題型、剪枝優(yōu)化的思路進(jìn)行分析。當(dāng)然，爆搜的題型千千萬，不可能一概而論，本文會通過具體的題目對幾類問題的求解思路進(jìn)行總結(jié)分析，構(gòu)建基本的思維模型。

二、原理分類與分析

（1）DFS連通性模型

在測試圖的連通性時(shí)，DFS與實(shí)際人們的思想一致，相對于起點(diǎn)選擇一條路走到底，發(fā)現(xiàn)不行就返回選擇的節(jié)點(diǎn)換一條路試，直到試出一條能到達(dá)終點(diǎn)的路。當(dāng)然，一直試不出來就表示該起點(diǎn)與某點(diǎn)(終點(diǎn))不連通。其他DFS連通性模型的思想與之類似。

1. 無需回溯：統(tǒng)計(jì)某點(diǎn)能到達(dá)的點(diǎn)的個(gè)數(shù)問題

在這類問題中，我們一般從某點(diǎn)出發(fā)進(jìn)行搜索，對于已經(jīng)被搜索過的點(diǎn)可以直接拋棄(標(biāo)記不可訪問)，對于當(dāng)前被搜索的點(diǎn)遞歸搜索周圍鄰接的點(diǎn)并進(jìn)行計(jì)數(shù)，直到無法搜索到合法的點(diǎn)返回。最終計(jì)數(shù)變量將記錄所有能到達(dá)的點(diǎn)。

2.需要回溯：迷宮類問題，測試兩點(diǎn)間連通性

在這類問題中，由于當(dāng)前選擇的路徑未必能夠到達(dá)目標(biāo)點(diǎn)，因此需要設(shè)置回溯，當(dāng)搜索到非法路徑返回時(shí)需要“恢復(fù)現(xiàn)場”，即：對于該路徑下各點(diǎn)的訪問狀態(tài)重置。

根據(jù)數(shù)據(jù)結(jié)構(gòu)，又可以將兩個(gè)模型分別繼續(xù)細(xì)分，DFS可以基于鄰接矩陣、鄰接表、邊集數(shù)組實(shí)現(xiàn)，思路相同，只是路徑的遍歷方式、點(diǎn)的訪問有所改變。

?總結(jié)一下DFS的模板框架(簡單描述)

function dfs(當(dāng)前狀態(tài)){
	if(當(dāng)前狀態(tài) == 目的狀態(tài)){
        ···
    }
    for(···尋找新狀態(tài)){
        if(狀態(tài)合法){
            vis[訪問該點(diǎn)]；
            dfs(新狀態(tài));
            ?是否需要恢復(fù)現(xiàn)場->vis[恢復(fù)訪問]
        } 
    }
    if(找不到新狀態(tài)){
        ···
    }
}

（2）DFS思路應(yīng)用-窮舉求解問題

在無路可走時(shí)，我們往往會選擇搜索算法，因?yàn)槲覀兤谕糜?jì)算機(jī)的高性能來有目的的窮舉一個(gè)問題的部分甚至所有可能情況，從而在這些情況中尋找符合題目要求的答案。這也是“爆搜”之名的由來。

我們約定，對于問題的介入狀態(tài)，叫初始狀態(tài)，要求的狀態(tài)叫目標(biāo)狀態(tài)。

這里的搜索就是對實(shí)時(shí)產(chǎn)生的狀態(tài)進(jìn)行分析檢測，直到得到一個(gè)目標(biāo)狀態(tài)或符合要求的最佳狀態(tài)為止。對于實(shí)時(shí)產(chǎn)生新的狀態(tài)的過程叫擴(kuò)展（由一個(gè)狀態(tài)，應(yīng)用規(guī)則，產(chǎn)生新狀態(tài)的過程）

搜索的要點(diǎn)：

1. 選定初始狀態(tài)，在某些問題中可能是從多個(gè)合法狀態(tài)分別入手搜索；

2. 遍歷自初始狀態(tài)或當(dāng)前狀態(tài)所產(chǎn)生的合法狀態(tài)，產(chǎn)生新的狀態(tài)并進(jìn)入遞歸；

3. 檢查新狀態(tài)是否為目標(biāo)狀態(tài)，是則返回，否則繼續(xù)遍歷，重復(fù)2-3步驟。

對狀態(tài)的處理：DFS時(shí)，用一個(gè)數(shù)組存放產(chǎn)生的所有狀態(tài)。

1. 把初始狀態(tài)放入數(shù)組中，設(shè)為當(dāng)前狀態(tài)；

2. 擴(kuò)展當(dāng)前的狀態(tài)，從合法狀態(tài)中旬尋找一個(gè)新的狀態(tài)放入數(shù)組中，同時(shí)把新產(chǎn)生的狀態(tài)設(shè)為當(dāng)前狀態(tài)；

3. 判斷當(dāng)前狀態(tài)是否和前面的狀態(tài)重復(fù)，如果重復(fù)則回到上一個(gè)狀態(tài)，產(chǎn)生它的另一狀態(tài)；

4. 判斷當(dāng)前狀態(tài)是否為目標(biāo)狀態(tài)，如果是目標(biāo)目標(biāo)狀態(tài)，則找到一個(gè)解答，根據(jù)實(shí)際問題需求，選擇繼續(xù)尋找答案或是直接返回。

5. 如果數(shù)組為空，說明對于該問題無解。

function dfs(當(dāng)前狀態(tài), 一系列其他的狀態(tài)量){
	if(當(dāng)前狀態(tài) == 目的狀態(tài)){
        ···
    }
    for(···尋找新狀態(tài)){
        if(狀態(tài)合法){
            vis[訪問該點(diǎn)]；
            dfs(新狀態(tài));
            ?是否需要恢復(fù)現(xiàn)場->vis[恢復(fù)訪問]
        } 
    }
    if(找不到新狀態(tài)){
        是否需要?jiǎng)?chuàng)建新規(guī)則？{
            創(chuàng)建并對當(dāng)前狀態(tài)進(jìn)行訪問vis;
            繼續(xù)搜索;
            恢復(fù)現(xiàn)場/恢復(fù)訪問vis;
        }
    }
}

?與圖的搜索類似，算法的框架基本不變，不同的是對于新狀態(tài)的尋找、控制遞歸終止的條件更為復(fù)雜。在實(shí)際的題目中，會有一些題目需要對合法的新狀態(tài)進(jìn)行干預(yù)：可能在首輪搜索無法應(yīng)用規(guī)則或所有條件均不滿足且需要人為創(chuàng)建新的規(guī)則以繼續(xù)搜索答案。這里也會設(shè)計(jì)到一系列剪枝與優(yōu)化的問題。

舉例說明：ACWing分成互質(zhì)組

題目描述：給定 n 個(gè)正整數(shù)，將它們分組，使得每組中任意兩個(gè)數(shù)互質(zhì)。至少要分成多少個(gè)組？

輸入格式：第一行是一個(gè)正整數(shù) n。

                第二行是 n 個(gè)不大于10000的正整數(shù)。

輸出格式：一個(gè)正整數(shù)，即最少需要的組數(shù)。

數(shù)據(jù)范圍：1≤n≤10

輸入樣例：

6
14 20 33 117 143 175

輸出樣例：

3

題目分析與算法設(shè)計(jì)：

給定n個(gè)數(shù)字分成互質(zhì)組，那么考慮最壞的情況，要分成n組(n個(gè)數(shù)均不互質(zhì))。因?yàn)轭}目的數(shù)據(jù)量并不大，可以采用DFS解決，具體思路如下：

預(yù)備工作：準(zhǔn)備一個(gè)數(shù)組存輸入數(shù)據(jù)，準(zhǔn)備一個(gè)容器，用于存不同的組，準(zhǔn)備一個(gè)檢索函數(shù)，可以檢索指定分組內(nèi)是否存在與目的數(shù)字重合的

**開始DFS：**首先是遞歸終止條件，判斷是否搜到末尾，搜到末尾則更新組數(shù)計(jì)數(shù)的值，返回；

**繼續(xù)：**每次在已有分組中從頭開始搜索，用檢索函數(shù)判斷當(dāng)前數(shù)字是否可以加入分組，若可以，加入后遞歸向下一個(gè)數(shù)字搜索

**新建分組：**考慮組數(shù)為0的情況、找不到可以加入組的情況，應(yīng)該設(shè)置創(chuàng)建新分組的情況，加入新分組后，同樣遞歸向后搜索。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 11;
int n, p[N], cnt, ans = N;
vector<int> num[N];	//這里使用STL中的Vector，其長度可變，更方便模擬分組的狀態(tài)

int gcd(int x, int y){
    return y ? gcd(y, x % y) : x;	//輾轉(zhuǎn)相除求最大公約數(shù)
}

//判斷兩數(shù)是否互質(zhì)
bool check(int x, int t){
    for (int i = 0; i < num[t].size(); i++){
        if (gcd(x, num[t][i]) > 1) return false;
    }
    return true;


void dfs(int now)
{
    if (now == n){
        ans = min(ans,  cnt);	//每次搜完取最小組數(shù)
        return;
    }
    for (int i = 0; i <  cnt; i++){
        if (check(p[now], i)){
            num[now].push_back(p[now]);
            dfs(now + 1);
            num[i].pop_back();
        }
    }
    //需要考慮首次搜索無組可加、當(dāng)前狀態(tài)無組可加
    num[cnt++].push_back(p[u]);
    dfs(now + 1);
    num[--cnt].pop_back(); 
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];
    dfs(0);
    cout << ans << endl;
    return 0;
}

三、剪枝優(yōu)化、題型歸納總結(jié)

在通過搜索解決實(shí)際問題的過程中，我們是通過窮舉每種情況來尋找合法解，然而在一些情況比較復(fù)雜的題目、數(shù)據(jù)量較強(qiáng)的題目中，由于算法的時(shí)間復(fù)雜度較高、數(shù)據(jù)規(guī)模過大，從而會導(dǎo)致運(yùn)行超時(shí)甚至程序卡死，因此在對復(fù)雜問題的答案進(jìn)行搜索時(shí)，我們應(yīng)該靈活的針對每種題型設(shè)計(jì)對應(yīng)的搜索規(guī)則并進(jìn)行優(yōu)化，通常通過設(shè)置剪枝、排除無效情況、對問題進(jìn)行適當(dāng)?shù)霓D(zhuǎn)化等手法對搜索算法進(jìn)行優(yōu)化，使算法高效的執(zhí)行并得出我們想要的結(jié)果。

對算法的剪枝與優(yōu)化堪稱是爆搜算法的精髓，如何合理的設(shè)置剪枝優(yōu)化直接關(guān)系能否得到結(jié)果，這對我們的解題思維是一個(gè)很大的挑戰(zhàn)，本板塊將對常見的剪枝優(yōu)化思路、對細(xì)節(jié)的處理進(jìn)行歸納總結(jié)。

（一）剪枝與優(yōu)化

（1）剪枝與優(yōu)化的原則

1. 正確性：剪枝優(yōu)化的過程是使算法逼近最優(yōu)解的過程，而不是使算法遠(yuǎn)離最優(yōu)解甚至跳過最優(yōu)解的過程。剪枝的前提是保證對最優(yōu)解不丟不漏。

2. 準(zhǔn)確性：在保證正確性的前提下，我們采取必要的手段使算法跳過一定不含有目標(biāo)狀態(tài)/最優(yōu)解的分支，從而保證算法高效地進(jìn)行并更迅速的找出

3. 高效性：設(shè)計(jì)優(yōu)化程序的根本目的,是要減少搜索的次數(shù),使程序運(yùn)行的時(shí)間減少. 但為了使搜索次數(shù)盡可能的減少,我們又必須花工夫設(shè)計(jì)出一個(gè)準(zhǔn)確性較高的優(yōu)化算法,而當(dāng)算法的準(zhǔn)確性升高,其判斷的次數(shù)必定增多,從而又導(dǎo)致耗時(shí)的增多,這便引出了矛盾. 因此,如何在優(yōu)化與效率之間尋找一個(gè)平衡點(diǎn),使得程序的時(shí)間復(fù)雜度盡可能降低,同樣是非常重要的。

（2）枝與優(yōu)化的一般入手點(diǎn)

1. 優(yōu)化搜索順序：在一些題目中，可以通過對子問題分支進(jìn)行分析，先解決相對簡單的子問題從而使尚未解決的子問題得到簡化，通過對搜索順序的優(yōu)化可以實(shí)現(xiàn)這一點(diǎn)。

2. 排除冗余信息：對限制條件進(jìn)行分析，不要額外添加沒有意義的搜索規(guī)則

3. 可行性剪枝：對于顯然不包含目標(biāo)狀態(tài)的搜索方向及時(shí)停止搜索，轉(zhuǎn)而向可能包含目標(biāo)狀態(tài)的分支進(jìn)行搜索

4. 最優(yōu)性剪枝：每次搜索完成后更新當(dāng)前得到的最優(yōu)狀態(tài)/最優(yōu)解，在每次搜索開始前判斷當(dāng)前解是否已經(jīng)比上次得出的狀態(tài)/解更劣？如果是則停止本次搜索，轉(zhuǎn)向其他搜索分支

5. 記憶化搜索：記憶化搜索是一種搜索的形式，對搜索的結(jié)果用數(shù)組或其他數(shù)據(jù)結(jié)構(gòu)記錄下來。

（二）問題的轉(zhuǎn)化、數(shù)據(jù)的預(yù)處理與壓縮

在解決實(shí)際問題時(shí)，我們可以巧妙地對題目給出的數(shù)據(jù)進(jìn)行適當(dāng)?shù)霓D(zhuǎn)化，從而構(gòu)造出DFS的模型進(jìn)行求解。

這與數(shù)學(xué)上的構(gòu)造函數(shù)思想類似，在掌握題目數(shù)據(jù)的基礎(chǔ)上對數(shù)據(jù)進(jìn)行預(yù)處理從而構(gòu)造可以按照某規(guī)則進(jìn)行檢索的新數(shù)據(jù)，通過對新數(shù)據(jù)進(jìn)行搜索從而得出原數(shù)據(jù)符合要求的解。

舉例說明：

單詞接龍是一個(gè)與我們經(jīng)常玩的成語接龍相類似的游戲。

現(xiàn)在我們已知一組單詞，且給定一個(gè)開頭的字母，要求出以這個(gè)字母開頭的最長的“龍”，每個(gè)單詞最多被使用兩次。

在兩個(gè)單詞相連時(shí)，其重合部分合為一部分，例如 beast 和 astonish ，如果接成一條龍則變?yōu)?beastonish。

我們可以任意選擇重合部分的長度，但其長度必須大于等于1，且嚴(yán)格小于兩個(gè)串的長度，例如 at 和 atide 間不能相連。

輸入格式：輸入的第一行為一個(gè)單獨(dú)的整數(shù) n 表示單詞數(shù)，以下 n 行每行有一個(gè)單詞（只含有大寫或小寫字母，長度不超過20），輸入的最后一行為一個(gè)單個(gè)字符，表示“龍”開頭的字母。

你可以假定以此字母開頭的“龍”一定存在。

輸出格式：只需輸出以此字母開頭的最長的“龍”的長度。

輸入樣例：

5
at
touch
cheat
choose
tact
a

輸出樣例：

23

代碼如下：

#include <bits/stdc++.h>
#define N 26
using namespace std;

vector<int> ver[N],edge[N];//匹配的單詞編號和匹配長度
string word[N];
int n, res;
int st[N];

void dfs(string u, int k)
{
    st[k] ++;
    res = max(res, (int)u.size());

    for(int i = 0;i < ver[k].size(); i++)
    {
        int point = ver[k][i],d = edge[k][i];
        if(st[point]<2)
            dfs(u + word[point].substr(d), point);
    }
    st[k]--;
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> word[i];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            string a = word[i] , b = word[j];
            int len = min(a.size(),b.size());
            for(int k=1;k<len;k++)
            {
                if(a.substr(a.size()-k)==b.substr(0,k))
                {
                    ver[i].push_back(j);
                    edge[i].push_back(k);
                    break;
                }
            }
        }

    string head;
    cin >> head;
    for(int i = 1; i <= n; i++)
        if(head[0] == word[i][0]) dfs(word[i], i);
    cout << res << endl;
    return 0;
}

對于數(shù)據(jù)的預(yù)處理和規(guī)模壓縮，舉一個(gè)非常巧妙地例子：數(shù)獨(dú)

題目描述：數(shù)獨(dú)是一種傳統(tǒng)益智游戲，你需要把一個(gè)9 × 9的數(shù)獨(dú)補(bǔ)充完整，使得圖中每行、每列、每個(gè)3 × 3的九宮格內(nèi)數(shù)字1~9均恰好出現(xiàn)一次。

請編寫一個(gè)程序填寫數(shù)獨(dú)。

輸入格式

輸入包含多組測試用例。

每個(gè)測試用例占一行，包含81個(gè)字符，代表數(shù)獨(dú)的81個(gè)格內(nèi)數(shù)據(jù)（順序總體由上到下，同行由左到右）。

每個(gè)字符都是一個(gè)數(shù)字（1-9）或一個(gè)”.”（表示尚未填充）。

您可以假設(shè)輸入中的每個(gè)謎題都只有一個(gè)解決方案。

文件結(jié)尾處為包含單詞“end”的單行，表示輸入結(jié)束。

輸出格式

每個(gè)測試用例，輸出一行數(shù)據(jù)，代表填充完全后的數(shù)獨(dú)。

輸入樣例：

4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

輸出樣例：

417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

題目分析：

本題目數(shù)據(jù)量較大，用爆搜解決超時(shí)是個(gè)問題，因此如何優(yōu)化剪枝便成了重點(diǎn)，下面是需要進(jìn)行的準(zhǔn)備工作，這些預(yù)處理極其關(guān)鍵！

1. 開始時(shí)判斷是否搜索成功，若成功則返回；

2. ！優(yōu)化：找出備選方案數(shù)最少的空格，先填它，從而實(shí)現(xiàn)整體的優(yōu)化；

3. 找出能填的數(shù)字懟上去試試，能行繼續(xù)搜，搜到底return上來true，搜不到返回false，那么恢復(fù)現(xiàn)場，繼續(xù)找數(shù)搜。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 9;
int map[1 << N], ones[1 << N];
int row[N], col[N], cell[3][3];
char sudoku[100];

inline int lowbit(int x){
    return x & (-x);
}

inline int get(int x, int y){
    return row[x] & col[y] & cell[x / 3][y / 3];
}

void makeg(){
    for(int i = 0; i < N; i++) map[1 << i] = i;
    for(int i = 0, k = 0; i < (1 << N); i++, k = 0){
        for(int j = i; j; j -= lowbit(j)) k++;
        ones[i] = k;
    }
}

void init(){
    for (int i = 0; i < N; i++) row[i] = col[i] = (1 << N) - 1;
    for(int i = 0; i < 3 ; i++)
        for(int j = 0; j < 3; j++) cell[i][j] = (1 << N) - 1;
}

bool dfs(int cnt){
    //搜索成功結(jié)束
    if(!cnt) return true;
    //找出備選數(shù)字?jǐn)?shù)目最少的空格
    int minn = 10;
    int x, y;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(sudoku[i * 9 + j] == '.'){
                int tmp = ones[get(x, y)];
                if(tmp < minn) minn = tmp, x = i, y = j;
            }
        }
    }
    for(int i = get(x, y); i; i -= lowbit(i)){
        int tmp = map[lowbit(i)];
        row[x] -= 1 << tmp;
        col[y] -= 1 << tmp;
        cell[x / 3][y  /3] -= 1 << tmp;
        sudoku[x * 9 + y] = '1' + tmp;
        if(dfs(cnt - 1)) return true;
        row[x] += 1 << tmp;
        col[y] += 1 << tmp;
        cell[x / 3][y / 3] += 1 << tmp;
        sudoku[x * 9 + y] = '.';
    }
    return false;
}

int main(){
    makeg();
    while(cin >> sudoku,  sudoku[0] != 'e'){
        init();
        int cnt = 0;
        for(int i = 0, k = 0; i < N; i++){
            for(int j = 0; j < N; j++, k++){
                if(sudoku[k] != '.'){
                    int tmp = sudoku[k] - '1';
                    row[i] -= 1 << tmp;
                    col[j] -= 1 << tmp;
                    cell[i / 3][j / 3] -= 1 << tmp;
                }
                else cnt++;
            }
        }
        dfs(cnt);
        cout << sudoku << endl;
    }
    return 0;
}

從本題中可以看出，通過合理利用位運(yùn)算使運(yùn)算和數(shù)據(jù)的規(guī)模極大的得到了縮小，因此，合理利用巧解法可以優(yōu)化搜索算法。但這類思路通常難以想到，需要大量的刷題經(jīng)驗(yàn)積累。