搜索基础

深度优先搜索（DFS）

以遍历单条路径上的所有节点为优先，搜索所有可能的路径。

• 沿一条状态路径转移，直到没有下一个状态
• 再退回访问前一状态的其他可能路径。

实现

• 用栈管理候选状态
• 递归栈

代码示例

递归栈实现

void dfs(int u){
    // 递归出口（即上一个节点为叶子节点）
    if(!u) return;
    // 访问当前节点
    cout << node[u].val << " ";
    // 递归访问子节点
    for(int v: node[u].next) dfs(v);
}

栈实现

void stack_dfs(int root){
    // 栈中存储待访问的节点，初始时只有根节点
    stack<int> st;
    st.push(root);
    // 还有待访问节点，继续访问
    while(!st.empty()){
        // 取栈顶为当前节点，并弹出
        int u = st.top();
        st.pop();
        // 访问当前节点
        cout << node[u].val << " ";
        // 将子节点压入栈（后进先出，倒序保证访问顺序与递归一致）
        for(int v: node[u].next) if(v) st.push(v);
    }
}

广度优先搜索（BFS）

以遍历单个节点上的所有路径为优先，搜索所有可能的路径。

• 先访问某状态的所有可能路径
• 再依次路径上的下一个状态。

实现

• 队列管理候选状态
• 优先对列（有特殊要求时）

代码示例

void bfs(int root){
    // 队列中存储待访问的节点，初始时只有根节点
    queue<int> q;
    q.push(root);
    // 还有待访问节点，继续访问
    while(!q.empty()){
        // 取队首为当前节点，并弹出
        int u = q.front();
        q.pop();
        // 访问当前节点
        cout << node[u].val << " ";
        // 将子节点压入队列（先进先出）
        for(int v: node[u].next) if(v) q.push(v);
    }
}

回溯法（Backtracking）

系统地搜索解空间，用于寻找满足特定条件的解（或所有解）

• 选择可能路径
• 继续搜索
• 回退（撤销选择）
• 继续搜索下一个选择

实现

• 深度优先搜索搭配递归栈

代码示例

int maxlen = 3; // 目标解的长度
int selection = 5; // 选项的范围
void backtrack(vector<int> &path){
    // 满足条件，处理当前解
    if(path.size() == maxlen){
        for(int num : path) cout << num << ' ';
        cout << endl;
        return;
    }
    // 遍历所有选项
    for(int i = 1; i <= selection; i++){
        // 做选择
        path.push_back(i);
        // 继续搜索
        backtrack(path);
        //* 回退（撤销选择）
        path.pop_back();
    }
}

剪枝法（Pruning）

在搜索中，通过剪枝操作来减少搜索树的大小，以提高搜索效率。

实现

• 可行性剪枝：当前状态已不可能达到目标
• 最优性剪枝：当前状态已不可能比之前找到的解更优
• 去重剪枝（记忆化）：已经搜索过的状态不再搜索
• 顺序剪枝：以某种顺序搜索，使其他剪枝效果最大化
• 其他：估价函数、贪心初始解等

代码示例

洛谷P1433

double ans = -1;
int n;
vector<bool> vis;// 标记已访问的节点
vector<double> minDis;
// 贪心初始解，用于最优性剪枝（省略）
void greedy(){}
// DFS + 剪枝
void dfs(int pos, int num, double d){
    // 可行性剪枝：递归正常结束
    if(num == n) {
        ans = (ans > 0) ? min(ans, d) : d;
        return;
    }
    // 最优性剪枝：当前距离已经不可能比ans更优
    if(d >= ans && ans > 0) return;
    double minD = 0;
    // 最优性剪枝：即使接下来选最短路，距离也不可能比ans更优
    for(int i = 1;i <= n;i++){
        if(vis[i]) continue;
        if(i == pos) continue;
        minD += minDis[i];
    }
    if(minD + d >= ans && ans > 0) return;
    // 顺序剪枝：优先搜索距离较近的节点，使最优性剪枝剪掉更多分支
    vector<pair<double, int>> order;
    for(int i = 1;i <= n;i++) 
        if(!vis[i]) order.push_back({cut[pos][i], i});
    sort(order.begin(), order.end());
    // dfs主体
    for(auto [_, i]: order){
        // 去重剪枝：已经搜索过的节点不再搜索
        if(vis[i]) continue;
        if(i == pos) continue;
        // 回溯
        vis[i] = 1;
        dfs(i, num + 1, d + cut[pos][i]);
        vis[i] = 0;
    }
}
int main(){
    // 输入（省略）
    // 先用贪心算法得到初始解
    greedy();
    // DFS + 剪枝搜索最优解
    fill(vis.begin(), vis.end(), 0);
    dfs(0, 0, 0);
    cout << ans;
    return 0;
}