重点：这是一份课件整理，出自杨乐大佬之手，就此声明。

首先，搜索是一种暴力，在数据范围小的情况下，枚举所有的可能性。我们来模拟处理问题的步骤。

搜索主要分两类：dfs（深度优先搜索）

　　　　　　　：bfs（广度优先搜索）

dfs的经典例题：

范式：

void dfs(_position_,_state_) if _success_ then _goal_ else     for every possible _move_//枚举每一种可能行动     if _acailable_ then//如果没有违法约束        _new_state_=(_state_,_move_)//计算新的状态        _new_possible_=nexr_position_ //计算下一个阶段        dfs(_new_position_,_new_state_)//进行下一步的搜索

 

1.数独问题

题目梗概：给出一个 9×9 的棋盘，上面已经填好了部分数字。要 求补充完整个棋盘，并且使得每行、每列、每个 3×3 小方阵内没 有重复的数字。

* 分析数独问题： 1 “划分游戏阶段”：从左到右从前到后，决定每一个空格的数字

　　　　　　　　 2“行动”：对于某一个特定的空格，枚举上面填什么数字

　　　　　　　　 3* “胜利”：全部填完了之后，判断这个填的方法是否符合条件

 

#include
     
      #include 
      
       #include 
       
        using namespace std;const int N = 9;const int Group[9][9] = {    0, 0, 0, 1, 1, 1, 2, 2, 2,    0, 0, 0, 1, 1, 1, 2, 2, 2,    0, 0, 0, 1, 1, 1, 2, 2, 2,    3, 3, 3, 4, 4, 4, 5, 5, 5,    3, 3, 3, 4, 4, 4, 5, 5, 5,    3, 3, 3, 4, 4, 4, 5, 5, 5,    6, 6, 6, 7, 7, 7, 8, 8, 8,    6, 6, 6, 7, 7, 7, 8, 8, 8,    6, 6, 6, 7, 7, 7, 8, 8, 8};int a[N][N];int row[N][N], col[N][N], gr[N][N];void print(){    printf("One Possible Solution:\n");    for(int i=0; i
        
         = 0) dfs3(next_x, next_y);//已经填好数了，那么我就跳过     else    {        for(int i=0; i
         
          = 0)                 {                    row[i][a[i][j]] = 1;                    col[j][a[i][j]] = 1;                    gr[Group[i][j]][a[i][j]] = 1;                }        /*把每一行每一列，每一小方块的已经给出的数全部标记为，        而这个group就是来判定这个位置是属于哪一个小方块的*//*        printf("row:\n");    for(int i=0; i
         
        
       
      
     

 

 

 

* 分析背包问题： 1 “划分游戏阶段”：从第一个物品开始，考虑它的选取情况

　　　　　　　　 2 “行动”：对于某一个特定的物品，考虑它选不选

　　　　　　　　 3* “约束”：选取完成后，还需要判断它是否能装得下

　　　　　　　　4* “最优方案”：如果可以装得下，我们需要选择一 个价值之和最大的

 

#include
     
      #include
      
       using namespace std;int w[1001],v[1001],n;int ans,t;void dfs(int x,int totw,int totv){    if(x>n)    {        if(totw>ans)            ans=totw;        return ;    }    else    {        dfs(x+1,totw,totv);        if(totv+v[x]<=t)        dfs(x+1,totw+w[x],totv+v[x]);    }}int main(){    scanf("%d%d",&n,&t);    for(int i=1;i<=n;i++)    scanf("%d%d",&w[i],&v[i]);    dfs(1,0,0);    printf("%d",ans);    return 0;}
      
     

 

对于这个问题我们来拓展一下：

1.如何记录拿了几件

//多定义一个a[1001] b[1001]void dfs(int x,int totw,int totv){    if(x>n)    {        if(totw>ans)            {                for(int i=1;i<=a[0];i++)                b[i]=a[i];                ans=totw;            }        return ;    }    else    {        dfs(x+1,totw,totv);        if(totv+v[x]<=t)        {            ++a[0],a[a[0]]=x;            dfs(x+1,totw+w[x],totv+v[x]);            a[a[0]]=0,--a[0];            //用a[0]来记录拿的个数 这个 也算一个技巧        }    }}

 

2.完全背包（取无数件）

void dfs(int x,int totw,int totv){    if(x>n)    {        if(totw>ans)            ans=totw;        return ;    }    else    {        dfs(x+1,totw,totv);        while(totv+v[x]*m<=t)        {        dfs(x+1,totw+w[x]*m,totv+v[x]*m);        m+=1;        }    }}

3.多重背包：给了规定件数可以取，求最大价值

void dfs(int x,int totw,int totv){    if(x>n)    {        if(totw>ans)            ans=totw;        return ;    }    else    {        dfs(x+1,totw,totv);        for(int i=1;i<=member[x];i++)        {            if(totv+v[x]*i

当然，我们这里都是最最基本的搜索，欢迎补充优化

 

* 分析哈密顿回路问题： 1 “划分游戏阶段”：走到了哪一个点

　　　　　　　　　　　 2 “行动”：下一步走哪一个点

　　　　　　　　　　　 3* “胜利”：把全部点都走遍了

　　　　　　　　　　　 4* “约束”：在过程中有没有走到重复的点

 

#include 
     
      #include 
      
       using namespace std;const int N = 25;int n, cnt;int a[N][N];int v[N], p[N];void print(){    printf("Route #%d: ", ++cnt);    for(int i=1; i<=p[0]; i++) printf("%d - ", p[i]);    printf("1\n");}void dfs(int x){    v[x] = 1, p[++p[0]] = x;//记录走的那几个点     if(p[0] == n)    {        if(a[p[0]][1]) print();//如果头和尾也相连，输出     }    else for(int i=1; i<=n; i++)             if(a[x][i] && !v[i])//有路径并且没有走过->搜索                 dfs(i);        v[x] = 0, p[p[0]] = 0, --p[0];//回溯 }int main(){//    freopen("hamilton.in", "r", stdin);//    freopen("hamilton.out", "w", stdout);    scanf("%d", &n);    for(int i=1; i<=n; i++)         for(int j=1; j<=n; j++)             scanf("%d", &a[i][j]);//用邻接矩阵来存储的哈密尔顿环     dfs(1);    return 0;}
      
     

 

*POJ 1979  红与黑：考虑 问题的各个步骤

　　1 阶段/ 搜索顺序：一步一步的走

　　2 状态：目前走到的位置

　　3 行动：向上下左右各走一步

　　4 胜利条件/ 结束条件：没有地方可以走了

　　5 约束：不能走出房间/ 不能走到红色瓷砖上

 

#include 
     
      using namespace std;const int N = 25;const int dx[4] = {
   1, 0, -1, 0};const int dy[4] = {
   0, 1, 0, -1};int n, m, sx, sy, cnt;int a[N][N], vs[N][N];void dfs(int x, int y){    ++cnt, vs[x][y] = 1;//计数加标记     for(int d=0; d<4; d++)    {        int i=x+dx[d], j=y+dy[d];//上下左右四个方向         if(i<1 || j<1 || i>n || j>m || a[i][j]=='#' || vs[i][j]) continue;        //不越界，不违法约束         dfs(i, j);    }}//当然，这道题用bfs也可以做，但都差不多 int gc(){    int c;    while(c=getchar(), c<=' ');    /*先输入数据，之后getchar()的返回值一个接一个赋给c,     然后比较c是不是不等于' '，如果不等于回车键就会执行循环。     如果等于就会结束*/      //相当于用输入字符矩阵     return c;}void work(){    for(int i=1; i<=n; i++)         for(int j=1; j<=m; j++)    {        a[i][j] = gc(), vs[i][j] = 0;        if(a[i][j]=='@') sx = i, sy = j;//标记所给位置     }    /*    ch=getchar();等待从键盘上输入一个字符    putchar(ch);输出此字符    他们包含在头文件　#include
      
       中．    */     cnt = 0;    dfs(sx, sy);//从所给位置开始搜索     printf("%d\n", cnt);}int main(){    freopen("rnb.in", "r", stdin);    freopen("rnb.out", "w", stdout);        while(scanf("%d%d", &m, &n), n*m) work();     //且m!=0||n!=0 ,当然它的数据是保证合法的     //用while循环输入，它的输入输出端是自动连在文件上的，    //所以用键盘输入是不会有结果的         return 0;}
      
     

 

DFS小总结：* 问题的各个步骤:

　　　　　　1 阶段/ 搜索顺序　　　　

　　　　　　2 状态：全局状态记得回溯（有的不需要）　　　

　　　　　　3 行动：枚举所有可能的行动

　　　　　　4 胜利条件/ 结束条件

　　　　　　5 约束

下面我们来看BFS(前方高能预警)

 

* BFS 搜索的思想是十分简单的： - 给定一个起始状态(将其记作 S0)；

　　　　　　　　　　 - 记录从起始状态向外走一步能到达的状态(我们把它记作 S1)；

　　　　　　　　　　 - 记录从 S1 走一步能到达的状态(将它们记作 S2)；

　　　　　　　　　　　显然，这些 状态都能从起始状态走两步到达。

　　　　　　　　　　　* 最终，如果目标状态出现在 Sk 中，则显然它可以从起始状态 走k 步到达(所以最终答案是最小的 k)。

　　　　　　　　　　　* 我们称这种做法为逐步扩展。

 

八数码

题目太经典就不显示了，而且这道题目曾经搞的我一晚上也没睡好，所以我今天一定要把它办掉

八数码问题的状态即为棋盘上的八个数字

从每一个空格开始上下左右各一种可能

扩展出第一种状态，依次类推

补充一点，bfs 是用队列来实现的

但有一个很重要的问题就是 ：如何判重，以及哪些是重复的。

（好像这里有图的样子）

 

#include
     
      #include
      
       using namespace std;int main(){    printf("1 2 3\n");    printf("5   6\n");    printf("7 8 9\n");    cout<<"---->"    printf("         1 2 3\n");    printf("         5 6  \n");    printf("         7 8 9\n");    //那么把从这个空格开始向四个方向扩展，必定有一种情况是这样的    printf("1 2 3\n");    printf("5   6\n");    printf("7 8 9\n");    //这样就回到原来的状态了，即为重复    //而我们要克服的就是这些 }
      
     

 

接下来我们从程序入手

本来应该是三步优化，一步比一步快，但我想，我写的既然是一个总结帖，我为什么不直接把最优的展示出来能？（好像很有道理的样子）

---

其实是我懒

 

 下面我们看程序

struct _state{    int w[N][N];//当前这个棋盘的状态    int x, y;//该空格的位置    int step;//走了几步    int pre, dirc;//父亲和对应的操作

如何判重？

如果我们开一个九维数组的话，哪怕是开bool型的，有以下几个麻烦之处

1.写起来麻烦

2.存起来费空间

3.查找起来费时间

4.看着别扭

综上所述，我们聪明的前辈想到了一种很不错的存储办法，

------>用一个九位数来存

这样只需要int就足够了

像这样：

int calc()    {        int ret = 0;        for(int i=0; i

那么程序实现就是

int bfs(_state start, _state end){    head = tail = 1;    start.step = 0;    start.pre = -1;    queue[1] = start;        S.clear();    S.insert(start.calc());    for(; head<=tail; ++head)    {        _state cur = queue[head];        int x = cur.x, y = cur.y;        for(int i=0; i<4; i++)        {            int nx = x + dx[i], ny = y + dy[i];            if(nx<0 || ny<0 || nx>=N || ny>=N) continue;                        //枚举上下左右四个位置            _state now = cur;//新的状态            now.x = nx, now.y = ny;//新的空格位置            swap(now.w[x][y], now.w[nx][ny]);//交换位置            now.step++;//步数+1            now.pre = head;//记录父亲            now.dirc = i;//操作：空格移动的方向            int nst = now.calc();            if(S.find(nst) == S.end())//用set的一个判重，下面会讲：如果没有重复的数字                queue[++tail] = now,//加入队列                S.insert(nst);//并标记该状态            if (equal(now,end)) return tail;        }    }    return -1;}

补充一点：set是个神马东东

 

 set集合容器实现了红黑树（Red-Black Tree）的平衡二叉检索树的的数据结构，在插入元素时，它会自动调整二叉树的排列，把该元素放到适当的位置，以确保每个子树根节点的键值大于左子树所有节点的键值，而小于右子树所有节点的键值；另外，还得确保根节点的左子树的高度与右子树的高度相等，这样，二叉树的高度最小，从而检索速度最快。要注意的是，它不会重复插入相同键值的元素，而采取忽略处理。

        平衡二叉检索树的检索使用中序遍历算法，检索效率高于vector、deque、和list的容器。另外，采用中序遍历算法可将键值由小到大遍历出来，所以，可以理解为平衡二叉检索树在插入元素时，就会自动将元素按键值从小到大的顺序排列。

        构造set集合的主要目的是为了快速检索，使用set前，需要在程序头文件中包含声明“#include<set>”。

 

采用inset()方法把元素插入到集合中，插入规则在默认的比较规则下，是按元素值从小到大插入，如果自己指定了比较规则函数，则按自定义比较规则函数插入。使用前向迭代器对集合中序遍历，结果正好是元素排序后的结果。

下面我先放一波程序

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int N = 3;const int M = 1e6 + 5;const int dx[4] = {
   0, 0, 1, -1};const int dy[4] = {
   1, -1, 0, 0};//四个方向搜索的小技巧const char mov[4] = {
   'R', 'L', 'D', 'U'};struct _state{    int w[N][N];    int x, y;    int step;    int pre, dirc;    void read()//读入矩阵并存储空格位置    {        for(int i=0; i
        

S;int head, tail;int bfs(_state start, _state end)//开始状态，结束状态各有两个矩阵来表示{ head = tail = 1;//队列为空 start.step = 0;//初始步骤为零 start.pre = -1;//初始状态没有父亲 queue[1] = start;//初始状态入队 S.clear();//清空set S.insert(start.calc());//插入这个矩阵所转化为的九位数 for(; head<=tail; ++head)//如果队列不为空 { _state cur = queue[head];//取队首 int x = cur.x, y = cur.y;//复制空格位置 for(int i=0; i<4; i++) { int nx = x + dx[i], ny = y + dy[i]; if(nx<0 || ny<0 || nx>=N || ny>=N) continue; _state now = cur; now.x = nx, now.y = ny; swap(now.w[x][y], now.w[nx][ny]);//拓展空格位置 now.step++; now.pre = head;//记录是第几步 now.dirc = i;//从哪个方向拓展来的 int nst = now.calc(); if(S.find(nst) == S.end())//end()返回集合里最后一个元素的迭代器 　　　　　　　　　　　　　　　　　　　　　　//返回指向被查找元素的迭代器 　　　　//find()可以查找一个元素在集合里的迭代器，如果该元素未出现过，则返回end() queue[++tail] = now,//（注意是逗号）使该元素入队 S.insert(nst); if (equal(now,end)) return tail;//如果该矩阵已经和要求矩阵一样了 } } return -1;}int seq[N];void print(int no, int x){ printf("Step #%d\n", x); for(int i=0; i

=0; i=queue[i].pre) seq[++seq[0]] = i;//用s[0]来存储个数 for(int i=seq[0]; i>=1; i--) print(seq[i], seq[0]-i);//输出矩阵 printf("Moving Sequence: \n"); for(int i=seq[0]-1; i>=1; i--) printf("%c", mov[ queue[seq[i]].dirc ]);//输出该矩阵的操作 return 0;}