搜索算法

Concepts

Uninformed (Blind) Search: 对要搜索的节点一无所知。

Informed (Heuristic) Search: 对要搜索的节点有一些启发性的知识，可以用来加速搜索。

BFS

def bfs(s0):
    q = [s0]
    vis = set()

    while not q.empty():
        s = q[0]; q = q[1:]
        if is_goal(s):
            return s
        vis.add(s)
        for n in s.neighbors(): # direct neighbors (distance = 1)
            if not n in vis:
                q.append(n)

    return None

bfs(s0)

*Space *: \(O(|V|)\) for the queue of all nodes in a certain depth.

Time: \(O(|V|)\)

BFS需要设计vis的状态，并且只适用于vis是全局的问题（抵达一个状态后，之后就不能通过其他路径再抵达这个状态，因为第二次抵达是次优的）。

DFS

vis = set()
def dfs(s):
    if is_goal(s): return s
    for n in s.neighbors(): # direct neighbors (distance = 1)
        if not n in vis:
            vis.add(n)
            res = dfs(n)
            if res is not None:
                return res
    return None

dfs(s0)

*Space *: \(O(|V|)\) if for a graph (the vis list), but \(O(D)\) for a tree (no need for vis list).

Time: \(O(|V|)\)

DFS与BFS的区别

搜索满足条件的节点：都可以，时间复杂度都是\(O(|V|)\).

搜索最优路径：BFS时间效率更高，但需要存储队列。DFS空间效率更高，但时间更长。

搜索全部路径、路径是否存在：通常允许路径重叠，此时只能用DFS！（DFS可以包含结构vis[i]=1; dfs(i); vis[i]=0，此时时间复杂度为指数级，且无法有效地用BFS的vis状态实现。）

“解是否存在”的问题通常需要剪枝。

在字母矩阵中检索单词

此问题允许单词搜索路径重叠，从而只能用DFS。例如如下实例：

[['a', 'b'],
 ['b', 'a']]
 "abab"

class Solution {
public:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool exist(vector<vector<char>>& board, string word) {
        int N = board.size(), M = board[0].size(), L = word.size();

        vector<vector<int>> vis(N, vector<int>(M, 0));
        bool flag = false;

        function<void(int, int, int)> dfs = [&](int i, int j, int l) {
            if (l == L) {
                flag = true;
                return;
            }
            for (int d = 0; d < 4; d++) {
                int ni = i + dx[d], nj = j + dy[d];
                if (ni >= 0 && nj >= 0 && ni < N && nj < M && vis[ni][nj] == 0 && board[ni][nj] == word[l]) {
                    vis[ni][nj] = 1;
                    dfs(ni, nj, l+1);
                    if (flag) return; // necessary pruning! else TLE.
                    vis[ni][nj] = 0;
                }
            }
        };

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == word[0]) {
                    vis = vector<vector<int>>(N, vector<int>(M, 0)); // set 0
                    vis[i][j] = 1;
                    dfs(i, j, 1);
                    if (flag) return true;
                }
            }
        }
        return false;
    }
};

时间复杂度为\(O(3^LMN)\)，最坏需要遍历所有长度L的路径，每步有三个方向（不能回头），最多有\(MN\)个起点。

IDS

DFS在特定数据下具有优势，但也有一个重大缺陷，即树的深度有可能是无限的。

此时可以结合BFS与DFS，限制每次DFS的最大搜索深度。

每次增大搜索深度上限都会导致DFS的重新调用，但在完全多叉树的情况下，新的节点总是远多于重复搜索的结点的。

Best-FS

对节点的已知信息可以用两个函数来表示：

\(g(s)\): cost function that measures the cost from \(s_0\) to \(s\). (e.g. the current steps)

\(h(s)\): heuristic function that estimates the cost from \(s\) to \(s_g\)

def bfs(s0):
    q = [s0]
    vis = set()

    while not q.empty():
        s = q[0]; q = q[1:]
        if is_goal(s):
            return s
        vis.add(s)
        for n in s.neighbors(): # neighbors increasingly ordered by function x(s)
            if not n in vis:
                q.append(n)

    return None

bfs(s0)

\(x(s)= g(s)\): this reduces to BFS.

\(x(s) = h(s)\): Greedy Search.

\(x(s) = g(s) + h(s)\): Heuristic Seaerch.

A*

\(h(s)\) is admissible if \(h(s) \le C(s, s_g)\).

A* is a heuristic search algorithm that uses admissible \(h(s)\).

A* is complete and optimal.

但是这样的\(h(s)\)不一定好找。

IDA*

A* use BFS as the backbone.

To reduce the Space Complexity of BFS, we can use IDS to replace BFS.

This is called IDA*.

alpha-beta pruning

对于双方、零和、确定性的游戏（TicTacToe，五子棋，围棋），其搜索树的搜索目标每层都会反转，即MIN层-MAX层结构。

进一步假设双方都是绝对理性的情况下，可以使用AB剪枝搜索。

alpha: 我方（MAX）能获得的最大利润。

beta: 对方（MIN）给我们的最小利润。

def minimax(node, depth, a=-inf, b=+inf):
    if node is a terminal node or depth == 0:
        return the heuristic value of node
    if node is min node:
        foreach child of node:
            b = min(b, minimax(child, depth-1, a, b))
            if b <= a:
                  return b
        return b
    else:
        foreach child of node:
            a = max(a, minimax(child, depth-1, a, b))
            if b <= a:
                   return a
        return a

对手发现可以给我们一个比我们当前可获得最大收益值更小的值时，触发剪枝。

我们发现可以获得一个比我们当前获得最小收益值更大的值时，触发剪枝。