搜索

[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*

剪枝

优化搜索顺序
例：小猫重量w[i],缆车最大承重W,问至少需要多少缆车。显然重量大的小猫安排较为“困难”，可以将小猫重量降序sort。
排除等效冗余组合问题不要写成排列
可行性剪枝
最优性剪枝
记忆化搜索（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*后实际搜索的状态数量很少。