窮竭搜索是將所有的可能性羅列出來(lái)，在其中尋找答案的方法。主要有深度優(yōu)先搜索和廣度優(yōu)先搜索這兩種方法
1.遞歸函數(shù)
在一個(gè)函數(shù)中再次調(diào)用該函數(shù)自身的行為叫做遞歸，這樣的函數(shù)被稱作遞歸函數(shù)。
階乘：
int fact(int n) {
if (n == 0) return 1;
return n * fact(n - 1);
}
斐波那契數(shù)列：
int memo[MAX_N + 1];
int fib(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
return memo[n] = fib(n - 1) + fib(n - 2);
}
2.棧
C++的標(biāo)準(zhǔn)庫(kù)中，stack::pop完成的僅僅是移除最頂端的數(shù)據(jù)。如果要訪問(wèn)最頂端的數(shù)據(jù)，需要使用stack::top函數(shù)（這個(gè)操作通常也被稱為peek）。
遞歸函數(shù)的遞歸過(guò)程也可以改用棧上的操作來(lái)實(shí)現(xiàn)?，F(xiàn)實(shí)中需要如此改寫的場(chǎng)合并不多，不過(guò)作為使用棧的練習(xí)試試看也是不錯(cuò)的。以下是使用stack的例子：
#include <stack>
#include <cstdio>
using namespace std;
int main() {
stack<int> s; // 聲明存儲(chǔ)int類型數(shù)據(jù)的棧
s.push(1); // {} → {1}
s.push(2); // {1} → {1,2}
s.push(3); // {1,2} → {1,2,3}
printf("%d\n", s.top()); // 3
s.pop(); // 從棧頂移除 {1,2,3}→{1,2}
printf("%d\n", s.top()); // 2
s.pop(); // {1,2} → {1}
printf("%d\n", s.top()); // 1
s.pop(); // {1} → {}
return 0;
}
3.隊(duì)列
在C++中queue::front是用來(lái)訪問(wèn)最底端數(shù)據(jù)的函數(shù)。以下是使用queue的例子：
#include <queue>
#include <cstdio>
using namespace std;
int main() {
queue<int> que; // 聲明存儲(chǔ)int類型數(shù)據(jù)的隊(duì)列
que.push(1); // {} → {1}
que.push(2); // {1} → {1,2}
que.push(3); // {1,2} → {1,2,3}
printf("%d\n", que.front()); // 1
que.pop(); // 從隊(duì)尾移除 {1,2,3}→{2,3}
printf("%d\n", que.front()); // 2
que.pop(); // {2,3} → {3}
printf("%d\n", que.front()); // 3
que.pop(); // {3} → {}
return 0;
}
4.深度優(yōu)先搜索
深度優(yōu)先搜索（DFS，Depth-First Search）是搜索的手段之一。它從某個(gè)狀態(tài)開始，不斷地轉(zhuǎn)移狀態(tài)直到無(wú)法轉(zhuǎn)移，然后回退到前一步的狀態(tài)，繼續(xù)轉(zhuǎn)移到其他狀態(tài)，如此不斷重復(fù)，直至找到最終的解。例如求解數(shù)獨(dú)，首先在某個(gè)格子內(nèi)填入適當(dāng)?shù)臄?shù)字，然后再繼續(xù)在下一個(gè)格子內(nèi)填入數(shù)字，如此繼續(xù)下去。如果發(fā)現(xiàn)某個(gè)格子無(wú)解了，就放棄前一個(gè)格子上選擇的數(shù)字，改用其他可行的數(shù)字。根據(jù)深度優(yōu)先搜索的特點(diǎn)，采用遞歸函數(shù)實(shí)現(xiàn)比較簡(jiǎn)單。
部分和問(wèn)題
給定整數(shù)a1、a2、…、an，判斷是否可以從中選出若干數(shù)，使它們的和恰好為k。
樣例1
n=4
a={1,2,4,7}
k=13
輸入
n=4
a={1,2,4,7}
k=13
輸出
Yes (13 = 2 + 4 + 7)
樣例2
輸入
n=4
a={1,2,4,7}
k=15
輸出
No
// 輸入
int a[MAX_N];
int n, k;
// 已經(jīng)從前i項(xiàng)得到了和sum，然后對(duì)于i項(xiàng)之后的進(jìn)行分支
bool dfs(int i, int sum) {
// 如果前n項(xiàng)都計(jì)算過(guò)了，則返回sum是否與k相等
if (i == n) return sum == k;
// 不加上a[i]的情況
if (dfs(i + 1, sum)) return true;
// 加上a[i]的情況
if (dfs(i + 1, sum + a[i])) return true;
// 無(wú)論是否加上a[i]都不能湊成k就返回false
return false;
}
void solve() {
if (dfs(0, 0)) printf("Yes\n");
else printf("No\n");
}
Lake Counting （POJ No.2386）
有一個(gè)大小為N×M的園子，雨后積起了水。八連通的積水被認(rèn)為是連接在一起的。請(qǐng)求出園子里總共有多少水洼？（八連通指的是下圖中相對(duì)W的*的部分）
輸入
N=10, M=12
園子如下圖（'W'表示積水，'.'表示沒(méi)有積水）
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
輸出
3
從任意的W開始，不停地把鄰接的部分用'.'代替。1次DFS后與初始的這個(gè)W連接的所有W就都被替換成了'.'，因此直到圖中不再存在W為止，總共進(jìn)行DFS的次數(shù)就是答案了。8個(gè)方向共對(duì)應(yīng)了8種狀態(tài)轉(zhuǎn)移，每個(gè)格子作為DFS的參數(shù)至多被調(diào)用一次，所以復(fù)雜度為O(8×N×M)=O(N×M)。
// 輸入
int N, M;
char field[MAX_N][MAX_M + 1]; // 園子
// 現(xiàn)在位置(x,y)
void dfs(int x, int y) {
// 將現(xiàn)在所在位置替換為.
field[x][y] = '.';
// 循環(huán)遍歷移動(dòng)的8個(gè)方向
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
// 向x方向移動(dòng)dx，向y方向移動(dòng)dy，移動(dòng)的結(jié)果為（nx,ny）
int nx = x + dx, ny = y + dy;
// 判斷(nx,ny)是不是在園子內(nèi)，以及是否有積水
if (0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W') dfs(nx, ny);
}
}
return ;
}
void solve() {
int res = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (field[i][j] == 'W') {
// 從有W的地方開始dfs
dfs(i, j);
res++;
}
}
}
printf("%d\n", res);
}
5.寬度優(yōu)先搜索
與深度優(yōu)先搜索的不同之處在于搜索的順序，寬度優(yōu)先搜索總是先搜索距離初始狀態(tài)近的狀態(tài)。也就是說(shuō)，它是按照開始狀態(tài)→只需1次轉(zhuǎn)移就可以到達(dá)的所有狀態(tài)→只需2次轉(zhuǎn)移就可以到達(dá)的所有狀態(tài)→……這樣的順序進(jìn)行搜索。對(duì)于同一個(gè)狀態(tài)，寬度優(yōu)先搜索只經(jīng)過(guò)一次，因此復(fù)雜度為O(狀態(tài)數(shù)×轉(zhuǎn)移的方式)。
深度優(yōu)先搜索（隱式地）利用了棧進(jìn)行計(jì)算，而寬度優(yōu)先搜索則利用了隊(duì)列。搜索時(shí)首先將初始狀態(tài)添加到隊(duì)列里，此后從隊(duì)列的最前端不斷取出狀態(tài)，把從該狀態(tài)可以轉(zhuǎn)移到的狀態(tài)中尚未訪問(wèn)過(guò)的部分加入隊(duì)列，如此往復(fù)，直至隊(duì)列被取空或找到了問(wèn)題的解。通過(guò)觀察這個(gè)隊(duì)列，我們可以就知道所有的狀態(tài)都是按照距初始狀態(tài)由近及遠(yuǎn)的順序被遍歷的。
迷宮的最短路徑
給定一個(gè)大小為N×M的迷宮。迷宮由通道和墻壁組成，每一步可以向鄰接的上下左右四格的通道移動(dòng)。請(qǐng)求出從起點(diǎn)到終點(diǎn)所需的最小步數(shù)。請(qǐng)注意，本題假定從起點(diǎn)一定可以移動(dòng)到終點(diǎn)。
輸入
N=10, M=10（迷宮如下圖所示。'#'，'.'，'S'，'G'分別表示墻壁、通道、起點(diǎn)和終點(diǎn)）
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
輸出
22
const int INF = 100000000;
// 使用pair表示狀態(tài)時(shí)，使用typedef會(huì)更加方便一些
typedef pair<int, int> P;
// 輸入
char maze[MAX_N][MAX_M + 1]; // 表示迷宮的字符串的數(shù)組
int N, M;
int sx, sy; // 起點(diǎn)坐標(biāo)
int gx, gy; // 終點(diǎn)坐標(biāo)
int d[MAX_N][MAX_M]; // 到各個(gè)位置的最短距離的數(shù)組
// 4個(gè)方向移動(dòng)的向量
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// 求從(sx, sy)到(gx, gy)的最短距離
// 如果無(wú)法到達(dá)，則是INF
int bfs() {
queue<P> que;
// 把所有的位置都初始化為INF
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) d[i][j] = INF;
// 將起點(diǎn)加入隊(duì)列，并把這一地點(diǎn)的距離設(shè)置為0
que.push(P(sx, sy));
d[sx][sy] = 0;
// 不斷循環(huán)直到隊(duì)列的長(zhǎng)度為0
while (que.size()) {
// 從隊(duì)列的最前端取出元素
P p = que.front(); que.pop();
// 如果取出的狀態(tài)已經(jīng)是終點(diǎn)，則結(jié)束搜索
if (p.first == gx && p.second == gy) break;
// 四個(gè)方向的循環(huán)
for (int i = 0; i < 4; i++) {
// 移動(dòng)之后的位置記為(nx, ny)
int nx = p.first + dx[i], ny = p.second + dy[i];
// 判斷是否可以移動(dòng)以及是否已經(jīng)訪問(wèn)過(guò)（d[nx][ny]!=INF即為已經(jīng)訪問(wèn)過(guò)）
if (0 <= nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != '#' &&
d[nx][ny] == INF) {
// 可以移動(dòng)的話，則加入到隊(duì)列，并且到該位置的距離確定為到p的距離+1
que.push(P(nx, ny));
d[nx][ny] = d[p.first][p.second] + 1;
}
}
}
return d[gx][gy];
}
void solve() {
int res = bfs();
printf("%d\n", res);
}
寬度優(yōu)先搜索與深度優(yōu)先搜索一樣，都會(huì)生成所有能夠遍歷到的狀態(tài)，因此需要對(duì)所有狀態(tài)進(jìn)行處理時(shí)使用寬度優(yōu)先搜索也是可以的。但是遞歸函數(shù)可以很簡(jiǎn)短地編寫，而且狀態(tài)的管理也更簡(jiǎn)單，所以大多數(shù)情況下還是用深度優(yōu)先搜索實(shí)現(xiàn)。反之，在求取最短路時(shí)深度優(yōu)先搜索需要反復(fù)經(jīng)過(guò)同樣的狀態(tài)，所以此時(shí)還是使用寬度優(yōu)先搜索為好。
寬度優(yōu)先搜索會(huì)把狀態(tài)逐個(gè)加入隊(duì)列，因此通常需要與狀態(tài)數(shù)成正比的內(nèi)存空間。反之，深度優(yōu)先搜索是與最大的遞歸深度成正比的。一般與狀態(tài)數(shù)相比，遞歸的深度并不會(huì)太大，所以可以認(rèn)為深度優(yōu)先搜索更加節(jié)省內(nèi)存。
此外，也有采用與寬度優(yōu)先搜索類似的狀態(tài)轉(zhuǎn)移順序，并且注重節(jié)約內(nèi)存占用的迭代加深深度優(yōu)先搜索（IDDFS，Iterative Deepening Depth-First Search）。IDDFS是一種在最開始將深度優(yōu)先搜索的遞歸次數(shù)限制在1次，在找到解之前不斷增加遞歸深度的方法
6.特殊狀態(tài)的枚舉
雖然生成可行解空間多數(shù)采用深度優(yōu)先搜索，但在狀態(tài)空間比較特殊時(shí)其實(shí)可以很簡(jiǎn)短地實(shí)現(xiàn)。比如，C++的標(biāo)準(zhǔn)庫(kù)中提供了next_permutation這一函數(shù)，可以把n個(gè)元素共n!種不同的排列生成出來(lái)。又或者，通過(guò)使用位運(yùn)算，可以枚舉從n個(gè)元素中取出k個(gè)的狀態(tài)或是某個(gè)集合中的全部子集等。
bool used[MAX_N];
int perm[MAX_N];
// 生成{0,1,2,3,4,...,n-1}的n!種排列
void permutation1(int pos, int n) {
if (pos == n) {
/*
* 這里編寫需要對(duì)perm進(jìn)行的操作
*/
return ;
}
// 針對(duì)perm的第pos個(gè)位置，究竟使用0~n-1中的哪一個(gè)進(jìn)行循環(huán)
for (int i = 0; i < n; i++) {
if (!used[i]) {
perm[pos] = i;
// i已經(jīng)被使用了，所以把標(biāo)志設(shè)置為true
used[i] = true;
permutation1(pos + 1, n);
// 返回之后把標(biāo)志復(fù)位
used[i] = false;
}
}
return ;
}
#include <algorithm>
// 即使有重復(fù)的元素也會(huì)生成所有的排列
// next_permutation是按照字典序來(lái)生成下一個(gè)排列的
int perm2[MAX_N];
void permutation2(int n) {
for (int i = 0; i < n; i++) {
perm2[i] = i;
}
do {
/*
* 這里編寫需要對(duì)perm2進(jìn)行的操作
*/
} while (next_permutation(perm2, perm2 + n));
// 所有的排列都生成后，next_permutation會(huì)返回false
return ;
}
7.剪枝
顧名思義，窮竭搜索會(huì)把所有可能的解都檢查一遍，當(dāng)解空間非常大時(shí)，復(fù)雜度也會(huì)相應(yīng)變大。
比如n個(gè)元素進(jìn)行排列時(shí)狀態(tài)數(shù)總共有n!個(gè)，復(fù)雜度也就成了O(n!)。這樣的話，即使n=15計(jì)算也很難較早終止。這里簡(jiǎn)單介紹一下此類情形要如何進(jìn)行優(yōu)化。
深度優(yōu)先搜索時(shí)，有時(shí)早已很明確地知道從當(dāng)前狀態(tài)無(wú)論如何轉(zhuǎn)移都不會(huì)存在解。這種情況下，不再繼續(xù)搜索而是直接跳過(guò)，這一方法被稱作剪枝。
我們回想一下深度優(yōu)先搜索的例題“部分和問(wèn)題”。這個(gè)問(wèn)題中的限制條件如果變?yōu)?≤ai≤108，那么在遞歸中只要sum超過(guò)k了，此后無(wú)論選擇哪些數(shù)都不可能讓sum等于k，所以此后沒(méi)有必要繼續(xù)搜索。
