第八篇博客——搜索

宽度搜索 BFS

BFS的核心的数据结构是队列，访问完当前的数据(myqueue.front())后将其子状态压入队列中，每次访问都是访问队列头部的数据。下面是模版。

bool visit[MAXN];

struct status{
    int n,k;
    status(int n,int k):n(n),k(k){}
};

int BFS(int n,int k){
    queue<int> myq;
    myq.push(status(n,0));
    visit[n]=true;
    while(!myq.empty()){
        status cur=myq.front();
        myq.pop();
        if(cur.n==k)
            return cur.k;
        for(int i=0;i<3;i++){
            status next(cur.n,cur.k+1);
            if(i==0)
                next.n+=1;
            else if(i==1)
                next.n-=1;
            else
                next.n*=2;
            myq.push(next);
            visit[next.n]=true;
        }
    }
}

总结：

状态。确定所需的状态。通过状态的扩展，遍历所有的状态，从中寻找需要的答案。
状态扩展方式。在BFS中，需要尽可能地扩展状态，并对先拓展得到的状态进行下一次状态拓展。
有效状态。对有些状态，不需要再次扩展，直接舍弃即可（剪枝）
队列。新队列压入栈尾，每次取队头元素扩展。
标记。为了判断什么状态是有效的，什么是无效的。
有效状态数。时间复杂度和有效状态数是同一个数量级的，所以在搜索之前必须估算是否能够在接受范围内。
最优。一旦问题中出现最少、最短、最优等关键字的时候就需要考虑宽度优先搜索可否解决。

练习：玛雅人的密码

#include <iostream>
#include<cstdio>
#include<string>
#include<queue>
#include<set>

using namespace std;

struct node{
    string str;
    int step;
    node(string s,int st):str(s),step(st){}
};

set<string> inq;

void BFS(string origin){
    queue<node> q;
    q.push(node(origin,0));
    inq.insert(origin);
    while(!q.empty()){
        node current=q.front();
        q.pop();
        if(current.str.find("2012")!=string::npos){
            //查找成功就可以输出
            cout<<current.step<<endl;
            return;
        }
        for(int i=0;i<current.str.size()-1;i++){
            string temp=current.str;
            temp[i]=current.str[i+1];
            temp[i+1]=current.str[i];
            if(inq.find(temp)==inq.end()){
                q.push(node(temp,current.step+1));
                inq.insert(temp);
            }
        }
    }
    cout<<"-1"<<endl;
}
int main(){
    int N;
    string str;
    while(cin>>N>>str){
        if(N<4)
            cout<<"-1"<<endl;
        else
            BFS(str);
    }
    return 0;
}

深度优先搜索

深度优先搜索强调问题是否得到解。在问题中如果不是强调要得到问题的最优解，则可以使用深度优先搜索来解决这个问题。

习题1:神奇的口袋

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。

#include<iostream>
using namespace std;
int a[21];
int res=0;
int n;


void dfs(int now,int j){
    for(int i=j;j<n;j++){

        if(a[j]+now>40)
            dfs(now,j+1);
        if(a[j]+now<40){
            dfs(now+a[j],j+1);
        }
        //不用更新形式参数，因为now+a[j]自动变成形式参数
        if(now+a[j]==40){
            res++;
        }
    }
}
int main(){
    while(cin>>n){
        res=0;
        //方式数目=0
        for(int i=0;i<n;i++){
            cin>>a[i];

        }
        dfs(0,0);
        cout<<res<<endl;
    }
    return 0;
}

习题2:八皇后

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

/* DFS
 * 行从0到7逐层增加，不会存在重复放到同一行的情况
 * 列需要用bool col[8]记录某行是否已经放置
 * 对角线则需要用一个bool matrix[8][8](代码里用到矩阵名是djx)，并放到Judge(int x,int y)中判断
 * 然后思路就比较简单了，按照DFS对可扩展的状态进行递归
 * 每层的可扩展状态满足：
 *    （1）列上没有其它棋子
 *    （2）对角线上没有棋子
 * 好像把DFS中的now换成row更容易理解？
 */
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 8;
bool djx[maxN][maxN] = {false};
bool col[maxN] = {false};

vector<int> vi;        //可以用string

bool Judge(int x,int y){    
    //用于判断当前条件下（djx数组目前的状态下）对角线上是否已经有棋子了
    int y2 = y;
    for(int i=x;i>=0;i--){
        if(y>=0 && djx[i][y--]==true)
            return false;
        if(y2<8 && djx[i][y2++]==true)
            return false;
    }
    return true;
}
void DFS(int now,int ans){
    if(now==8){
        vi.push_back(ans);
        return ;
    }
    for(int j=0;j<8;j++){        //完全的DFS思路
        if(!col[j] && Judge(now,j)){
            col[j] = true;
            djx[now][j] = true;           //注意：题目里的所有数字都是从1开始计数，所以使用j+1记录answer
            DFS(now+1,ans*10+j+1);        //可以用string，由于最长8为十进制数，所以用int了
            col[j] = false;
            djx[now][j] = false;
        }
    }
}
int main(){
    DFS(0,0);
    sort(vi.begin(),vi.end());      //对answer进行排序
    int index;
    while(cin>>index){
        cout<<vi[index-1]<<endl;    //注意题目中所有数字均为从1计数
    }
    return 0;
}