搜索

搜索算法：枚举问题的所有可能答案，并逐一校验.

设集合 $A$ 满足以下性质：

• 若 $x\in A$，则 $2x$ 和 $3x-1$ 必属于 $A$.

已知 $3\in A$，问 $23$ 是否属于 $A$？

$A$ 的性质可抽象为下图：

$$\xymatrix@C=0em{ & x \ar[dl]\ar[dr] &\\ \margin 2x \margin & & 3x-1 }$$

以 $3$ 为树根，向下拓展树形图. 于是只需搜索 $23$ 是否在树中.

$$\xymatrix@C=0em{ &&&3\ar[dll]\ar[drr]\\ &6\ar[dl]\ar[dr]&&&&8\ar[dl]\ar[dr]\\ 12&&17&&16&&23 }$$

对于复杂的问题，可以先抽象出关系图，再搜索求解.

广度优先搜索（Breadth First Search，BFS）按层次搜索节点. 其原理如下：

1. 建立空队列.
2. 将根节点入队.
3. 取出队头，将其所有子节点入队.
4. 重复上一步直到队列为空.

BFS 搜索该图的步骤：

同一个节点不能被重复访问，否则将导致死循环.

bool vis[];  // vis[u]：节点 u 是否访问过

void bfs(int s) {
    queue<int> Q;
    Q.push(s);
    while(!Q.empty()) {
        int u = Q.top();
        Q.pop();
        for ( /* 枚举 u 的子节点 v */ ) {
            if (!vis[v]) {
                Q.push(v);
                vis[v] = true;
            }
        }
    }
}

深度优先搜索（Depth First Search，DFS）尽可能往更深处搜索节点. 其本质是递归.

DFS 搜索该图的步骤：

同一个节点不能被重复访问，否则将导致死循环.

bool vis[];  // vis[u]：节点 u 是否访问过

void dfs(int s) {
    vis[s] = true;
    for ( /* 枚举 u 的子节点 v */ ) {
        if (!vis[v]) {
            dfs(v);
        }
    }
}

搜索二维数组 $a[n,m]$ 时，$a[i,j]$ 抽象为节点 $(i,j)$. 其子节点为 $(i+1,j),(i-1,j),(i,j+1),(i,j-1)$，即与其相邻的四个节点.

$$\xymatrix @C=1em@R=1em { & 1 & 2 & 3 & \color{red}j & m\\ 1 & *+[o][F-]{\color{transparent}o}\ar@{-}[r]\ar@{-}[d] & *+[o][F-]{\color{transparent}o}\ar@{-}[r]\ar@{-}[d] & *+[o][F-]{\color{transparent}o}\ar@{-}[r]\ar@{-}[d] & *+[o][F-]{\color{transparent}o}\ar@{-}[r]\ar@{-}[d] & *+[o][F-]{\color{transparent}o}\ar@{-}[d]\\ 2 & *+[o][F-]{\color{transparent}o}\ar@{-}[r]\ar@{-}[d] & *+[o][F-]{\color{transparent}o}\ar@{-}[r]\ar@{-}[d] & *+[o][F-]{\color{transparent}o}\ar@{-}[r]\ar@{-}[d] & *+[o][F-]{\color{transparent}o}\ar@{-}[r]\ar@{<-}[d] & *+[o][F-]{\color{transparent}o}\ar@{-}[d]\\ \color{red}i & *+[o][F-]{\color{transparent}o}\ar@{-}[r]\ar@{-}[d] & *+[o][F-]{\color{transparent}o}\ar@{-}[r]\ar@{-}[d] & *+[o][F-]{\color{transparent}o}\ar@{<-}[r]\ar@{-}[d] & *+[o][F-]{\color{transparent}o}\ar@{->}[r]\ar@{->}[d] & *+[o][F-]{\color{transparent}o}\ar@{-}[d]\\ n & *+[o][F-]{\color{transparent}o}\ar@{-}[r] & *+[o][F-]{\color{transparent}o}\ar@{-}[r] & *+[o][F-]{\color{transparent}o}\ar@{-}[r] & *+[o][F-]{\color{transparent}o}\ar@{-}[r] & *+[o][F-]{\color{transparent}o} }$$

现在从某个节点开始搜索，枚举子节点的工作就显得繁琐. 以 DFS 为例：

bool vis[][];   // vis[x][y]: a[x][y] 是否访问过

void dfs(int x, int y) {
    vis[x][y] = true;
    if (x + 1 <= n && !vis[x + 1][y]) {
        dfs(x + 1, y);
    }
    if (x - 1 >= 1 && !vis[x - 1][y]) {
        dfs(x - 1, y);
    }
    if (y + 1 <= n && !vis[x][y + 1]) {
        dfs(x, y + 1);
    }
    if (y - 1 >= 1 && !vis[x][y - 1]) {
        dfs(x, y - 1);
    }
}

届时可以通过前驱节省工作量.

bool vis[][];

const int dx[] = {1, 0, -1, 0}; // 第一维度前驱
const int dy[] = {0, 1, 0, -1}; // 第二维度前驱

void dfs(int x, int y) {
    vis[x][y] = true;
    for (int i = 0; i < 4; i ++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny]) {
            dfs(nx, ny);
        }
    }
}