迭代加深搜索

一、算法简介

　　迭代加深搜索是在速度上接近广度优先搜索，空间上和深度优先搜索相当的搜索方式。由于在使用过程中引入了深度优先搜索，所以也可以当作深度优先搜索的优化方案。

　　迭代加深搜索适用于当搜索深度没有明确上限的情况。

　　例如上图的一棵搜索树，在进行深度优先搜索前先规定好这次搜索的最大深度dep，当搜索到达dep却还没搜索到结果时回溯。

　　之后不断加大搜索深度，重新搜索，直到找到结果为止。虽然这样搜索次数会累计很多次，但每一次搜索的范围和下一次搜索的范围相比微不足道，所以整体搜索速度不会受太大影响。

　　由于深度是从小到大逐渐增大的，所以当搜索到结果时可以保证搜索深度是最小的。这也是迭代加深搜索在一部分情况下可以代替广度优先搜索的原因（还比广搜省空间）。

二、算法图示

　　　假设G是需要搜索到的结果。

　　当 dep = 1 时搜索深度为1，搜索到节点Ａ，未搜索到结果，dep++ 并进行下一次深搜。

　　当 dep = 2 时搜索深度为２，搜索到节点 A,B,C,D 未搜索到结果，dep++ 并进行下一次深搜。

　　当 dep = 3 时搜索深度为3，搜索到节点 A,B,C,D,E,G 搜索到结果G，停止全部搜索并记录记录结果。

三、[codevs 1004四子连棋]

　　在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。

●	○	●
○	●	○	●
●	○	●	○
○	●	○

　　一般这样找最小搜索深度的题都用广度优先搜索写，但是由于广搜空间占用多，于是我们可以用迭代加深搜索作替代品。

　　本题迭搜思路就是逐渐增加每一次下棋的最大移动步数，当棋盘状态满足题目所给条件时退出并记录步数。

　　下面贴AC程序

 #include <stdio.h>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 int board[][];

 int movex[]={,-,,,},movey[]={,,,,-};

 int Ox1,Oy1,Ox2,Oy2,dep,f;

 int avalible(int a,int b,int k){

     if(board[a][b]!=k&&a>=&&a<=&&b>=&&b<=) return ;

     else return ;

 }

 int jdg(){

     for(int i=;i<=;i++){

         if(board[i][]==board[i][]&&board[i][]==board[i][]&&board[i][]==board[i][]) return ;

         if(board[][i]==board[][i]&&board[][i]==board[][i]&&board[][i]==board[][i]) return ;

     }

     if(board[][]==board[][]&&board[][]==board[][]&&board[][]==board[][]) return ;

     if(board[][]==board[][]&&board[][]==board[][]&&board[][]==board[][]) return ;

     return ;

 }

 void dfs(int x,int y,int p,int q,int pre,int step){

     if(jdg()){

         f=;

         return ;

     }

     else if(step>dep) return ;

     for(int i=;i<=;i++){

         int nx=x+movex[i];

         int ny=y+movey[i];

         int np=p+movex[i];

         int nq=q+movey[i];

         if(avalible(nx,ny,pre)){

             swap(board[x][y],board[nx][ny]);

             dfs(nx,ny,p,q,board[x][y],step+);

             swap(board[x][y],board[nx][ny]);

         }

         if(avalible(np,nq,pre)){

             swap(board[p][q],board[np][nq]);

             dfs(x,y,np,nq,board[p][q],step+);

             swap(board[p][q],board[np][nq]);

         }

     }

 }

 int main(){

     for(int i=;i<=;i++)

         for(int j=;j<=;j++){

             char ch;

             cin>>ch;

             if(ch=='B') board[i][j]=;

             else if(ch=='W') board[i][j]=;

             else board[i][j]=;

             if(board[i][j]==&&!Ox1) Ox1=i,Oy1=j;

             else if(board[i][j]==) Ox2=i,Oy2=j;

         }

     for(dep=;;dep++){

         dfs(Ox1,Oy1,Ox2,Oy2,,);

         dfs(Ox1,Oy1,Ox2,Oy2,,);

         if(f){

             printf("%d",dep);

             return ;

         }

     }

     return ;

 }

巴特西

迭代加深搜索[codevs1004 四子连棋]

迭代加深搜索

一、算法简介

二、算法图示

三、[codevs 1004四子连棋]

最新文章

热门文章