搜索

搜索

[TOC]

双向BFS

基本形式

int bfs()
{
    if (A == B) return 0;
    queue<string> qa, qb;
    unordered_map<string, int> da, db;

    qa.push(A), qb.push(B);
    da[A] = db[B] = 0;//init

    int step = 0;
    while (qa.size() && qb.size())
    {
        int t;
        if (qa.size() < qb.size()) t = extend(qa, da, db, a, b);
        else t = extend(qb, db, da, b, a);

        if (t <= 10) return t;
        if ( ++ step == 10) return -1;
    }

    return -1;
}

int extend(queue<string>& q, unordered_map<string, int>&da, unordered_map<string, int>& db, 
    string a[N], string b[N]){
	...
}

A*

条件:边权非负,且保证有解(若无解则效率低于普通bfs)

适用范围:求最短路等,状态很多例如八数码问题。只能保证终点第一次出队时是最小值,不能保证其他点第一次出队是最小值。

估计距离的条件:设当前点到终点的估计距离为f(state),当前点到终点的真实子u段距离为g(state),要有f(state)<=g(state)

八数码:有解充要条件是逆序对数量为偶数,估计距离为现在这个状态每个点到目标位置的曼哈顿距离之和。

第k短路:先Dijkstra,得到每个点到终点的最短距离,以g(state)为f(state),再A*,当终点第k次出队,就是答案。

基本形式

priority_queue<int,vector<int>,greater<int> >q;
q里面存:起点到当前点的准确距离(不一定最短)+当前点到终点的估计距离
while(!q.empty()){
    t=q.top();
    终点第一次出队时是最小值。
    q.pop();
    for(t的所有邻边){
        如果能被更新就入队
    }
}

形式与Dijkstra相似,Dijkstra算法可看作把估计距离都取0的A*

剪枝

  1. 优化搜索顺序

    例:小猫重量w[i],缆车最大承重W,问至少需要多少缆车。显然重量大的小猫安排较为“困难”,可以将小猫重量降序sort。

  2. 排除等效冗余 组合问题不要写成排列

  3. 可行性剪枝

  4. 最优性剪枝

  5. 记忆化搜索(dp)

迭代加深

“找到最短的序列”类似问题 核心思想:

 while (!dfs(1, k))k++;

双向DFS

n个物品每个重量g[i],拿的总重不超过W,n<=46,W<=1«31,求最大能拿多重。 先降序排序,前一半dfs暴搜求所有可能的总重量,降重、排序,后一半也暴搜,对后一半可能的总和x,再前一半找y<=W-x的最大y值,更新x+y的最大值。复杂度从 $O(2^n)$ 降到$O(log(2^{n \over 2})*2^{n \over 2})$即$O(n2^{n \over 2} )$

IDA*

例题

给定n本书,编号为1∼n在初始状态下,书是任意排列的。 在每一次操作中,可以抽取其中连续的一段,再把这段插入到其他某个位置。 我们的目标状态是把书按照 1∼n的顺序依次排列。 求最少需要多少次操作。 若大于等于5次就直接输出"5 or more" 1<=n<=15

思路

先考虑每一步的决策数量: 当抽取长度为i的一段时,有n−i+1种抽法,对于每种抽法,有n−i种放法。另外,将某一段向前移动,等价于将跳过的那段向后移动,因此每种移动方式被算了两遍,所以每个状态总共的分支数量是:∑ni=1(n−i)∗(n−i+1)/2=(15∗14+14∗13+…+2∗1)/2=560

考虑在四步以内解决,最多有 560^4个状态,会超时。可以使用双向BFS或者IDA*来优化。我们用IDA*来解决此题。

估价函数:

需要满足:不大于实际步数 在最终状态下,每本书后面的书的编号应该比当前书多1。 每次移动最多会断开三个相连的位置,再重新加入三个相连的位置,因此最多会将3个错误的连接修正,所以如果当前有 tot个连接,那么最少需要 ⌈tot/3⌉次操作。因此当前状态 s的估价函数可以设计成 f(s)=⌈tot/3⌉如果当前层数加上 f(s)大于迭代加深的层数上限,则直接从当前分支回溯。

时间复杂度

理论上最多搜索 560^4个状态,使用IDA*后实际搜索的状态数量很少。