Skip to main content

5 Searching

DFS​

Backtracking

The basic idea is that suppose we have a partial solution (x1,...,xi)(x_1, ... , x_i ) where each xk∈Skx_k\in S_k for 1≤k≤i<n1\leq k\leq i<n.

First we add xi+1∈Si+1x_{i+1} \in S_{i+1} and check if (x1,...,xi,xi+1)(x_1, ... , x_i,x_{i+1})satisfies the constrains. If the answer is “yes” we continue to add the next x, else we delete xi+1x_{i+1} and backtrack to the previous partial solution (x1,...,xi)(x_1, ... , x_i ).

void dfs(){
    if (递归出口) {
        记录答案;
        return;
    }
    for (所有的拆解可能性) {
        修改所有的参数
        dfs(参数列表);
        还原所有被修改过的参数
    }
    return 
}

搜索的顺序

Permutations​

if (递归出口) {
    记录答案;
    return;
}
for (所有的拆解可能性) {
    swap(x[i], x[j]);
    dfs(参数列表);
    swap(x[i],x[j])
}
return

Combinations​

Input two numbers n, r, and the algorithm outputs all combinations of r numbers in [1..n]

//First number observe
void combination(int n, int r, int start, vector<int>& track){
    if(track.size() == r){
        sol.push_back(track);
        return;
    }
    for(int i = start;i <= n; ++i){
        track.push_back(i);
        combination(n, r, i + 1, track);
        track.pop_back();
    }
}
//Last number observe
void combination(int n, int r, vector<int>& track){
    if(r == 0){
        sol.push_back(track);
        return;
    }
    for(int i = r; i <= n; ++i){
        track[r] = i;
        combination(i - 1, r - 1, track);
    }
}

剪枝与状态更新

状态更新:若变量与栈的回退有关，可将其加入形参而不是全局变量

sum += i;

剪枝:可行性和最优性剪枝

BFS​

基本结构

void bfs(){
    起点入列，已访问;
    while(!非空){
        取队首;
        队首出队;
        队首孩子结点入队,已访问;
    }
}

Summary

  • 拓扑排序
  • 连通块
  • 简单图最短路径