基础穷竭搜索：DFS&BFS

1 预备基础

1.1 递归函数 Recursion

Fibonacci的递归实现以指数级别展开，由于调用过程中大量出现重复计算，考虑通过记忆化搜索/动态规划进行优化。

1.2 栈 Stack : Last In Fiset Out

push ：在Stack的顶端放入一组数据
pop：从顶端取出一组数据

(C++)
stack::pop 移除最顶端数据
stack::top 访问最顶端的数据（peek）

#include <stack>
#include <iostream>
int main(){
    std::stack<int> s;
    s.push(1);//push 1 to the top element
    s.push(321);
    std::cout<<s.top();//print 321
    s.pop();// remove the top element
    return 0;
}

1.3 队列 Queue : First In First Out

push ：在Queue的队尾放入一组数据
pop：从顶端取出一组数据

（C++）
queue::push
queue::pop
queue::front

#include <queue>
#include <iostream>
int main(){
    std::queue<int> s;
    s.push(1);
    s.push(321);//push 1 to the last element
    //{1,321}
    std::cout<<s.front();//print 1
    s.pop();// remove the top element
    //{321}
    return 0;
}

2 算法具体

2.1 Depth-First Search (DFS)

基于栈，从某个状态开始，不断转移状态直到无法继续转移，然后回退到前一状态继续转移到其它状态。

//(Template)Problem：部分和问题
//给定整数a1， a2， a3， ...， an ；判断是否可以从中选出若干数，使它们之和为k
#include <iostream>
int a[100];
int n, k;
bool dfs(int i, int sum);
int main()
{
    std::cin >> n; //input the length of array
    for (int i = 1; i <= n; i++)
        std::cin >> a[i];
    std::cin >> k; //input goals
    if(dfs(0,0))
        std::cout<<"Yes";
    else
        std::cout<<"No";
    return 0;
}
//已经得到前i项和sum，处理i项之后的分支
bool dfs(int i, int sum)
{
    if(i==n) //截止条件：如果在这一层就到底了
        return sum==k;//若前n项都计算完成（再没法计算，已为最大），返回sum是否等于目标值k
    if(dfs(i+1,sum)) //状态A：不将第i项包括在内
        return true;
    if(dfs(i+1,sum+a[i+1]))//状态B：将第i项包括在内
        return true;
    return false; //返回条件or判否条件
}

// Problem: Lake Counting (POJ2386)
// Description:
// 由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。
// 我们用一个NxM(1<=N<=100;1<=M<=100)网格图表示。每个网格中有水('W') 或是旱地('.')。
// 一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。
// 给出约翰田地的示意图，确定当中有多少水坑。
// Sample Input:
// 10 12
// W........WW.
// .WWW.....WWW
// ....WW...WW.
// .........WW.
// .........W..
// ..W......W..
// .W.W.....WW.
// W.W.W.....W.
// .W.W......W.
// ..W.......W.
#include <iostream>
int field[101][101] = {{0}};
int move[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int N, M;
int nx, ny;
void dfs(int x, int y);
int main()
{
    //input
    char tmp;
    std::cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
        {
            std::cin >> tmp;
            if (tmp == 'W')
                field[i][j]++;
        }
    int res = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            if (field[i][j])
            {
                dfs(i, j);
                res++;
            }
    std::cout << res;
    return 0;
}
void dfs(int x, int y)
{
    //此时有field[x][y]==1
    field[x][y]--;//归0
    for (int i = 0; i < 8; i++)
    {
        nx = x + move[i][0];
        ny = y + move[i][1];
        if (nx > 0 && nx <= N && ny > 0 && ny <= M)
            if (field[nx][ny])
                dfs(nx, ny);
    }
    return;
}

2.2 Breadth-First Search (BFS)

利用队列，从某个状态出发，搜索距离初始状态近的状态。复杂度O(状态数*转移方式)
首先将初始状态加入到队列，从队列最前端不断取出状态，把从该状态可以转移到的状态中尚未访问过的部分加入队列，直到队列被取空or找到了问题的解。常用于求最短路径、最少操作等问题。
状态简单时，可以构造成pair或编码成int来表达状态。复杂时考虑封装类来表示状态。
通过标记来管理访问过的状态，做到由近及远的搜索。如对于求解最短距离的问题，不妨用d[N][M]把最短距离保存起来，同时用足够大常数初始化。

// (template)Problem: 迷宫最短路径
// 给定N*M迷宫，迷宫由通道和墙壁组成，每一步可以向临接的上下左右四格的通道移动。求出从起点到终点所需的最小步数。
// 假设从起点一定可以移动到终点。N,M<=100.
#include <iostream>
#include <queue>
const int INF = 1000000000;
typedef std::pair<int, int> P;
int maze[101][101] = {{0}};                          // map:0-wall(default);1-way
int dis[101][101] = {{INF}};                         // distance
int N, M;                                            // edge of the map
int s[2], g[2];                                      // start pos& goal pos
int move[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // change the status
int bfs()
{
    std::queue<P> que;
    // initialization
    que.push(P(s[0], s[1]));
    dis[s[0]][s[1]] = 0;
    while (que.size())
    {
        //取出que最前端元素
        P p = que.front();
        que.pop();
        // arrived at the goal pos -> jump out from the scope
        if (p.first == g[0] && p.second == g[1])
            break;
        for (int i = 0; i < 4; i++)
        {
            // current pos:
            int currentPos[2] = {p.first + move[i][1], p.second + move[i][2]};
            // not beyond the edge:
            if (currentPos[0] > 0 && currentPos[1] > 0 && currentPos[0] <= N && currentPos[1] <= M)
                // is way && have not accessing
                if (maze[currentPos[0]][currentPos[1]] && dis[currentPos[0]][currentPos[1]]) 
                {
                    que.push(P(currentPos[0], currentPos[1]));
                    dis[currentPos[0]][currentPos[1]] = dis[p.first][p.second] + 1;
                }
        }
    }
    return dis[g[0]][g[1]];
}
int main()
{
    // input
    char tmp;
    std::cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
        {
            std::cin >> tmp;
            if (tmp == '#')
                continue;
            if (tmp == 'S')
            {
                s[1] = i;
                s[2] = j;
            }
            else if (tmp == 'G')
            {
                g[1] = i;
                g[2] = j;
            }
            maze[i][j]++;
        }
    // solve
    std::cout << bfs();
}

拓展：Iterative Deepening Depth-First Search （IDDFS）迭代加深深度优先搜索

2.3 特殊状态枚举

生成可行解空间多数采用深度优先搜索，但在状态空间相对特殊时可以简短实现。
C++标准库提供函数nextperutation，可以将个元素共种不同的排列生成出来。或使用位运算枚举从个元素中取出个的共种状态或某集合中的全部子集。