POJ 2286 The Rotation Game 搜索-IDA*+迭代加深 - c++编程基础

本题若用广搜，空间需求量非常大，空间不足。深搜的话，深度很难控制，容易陷入死循环。在这个时候就要用到迭代加深的深搜方法。

所谓迭代加深，就是在深度无上限的情况下，先预估一个深度（尽量小）进行搜索，如果没有找到解，再逐步放大深度搜索。这种方法虽然会导致重复的遍历某些结点，但是由于搜索的复杂度是呈指数级别增加的，所以对于下一层搜索，前面的工作可以忽略不计，因而不会导致时间上的亏空。

这种方法，可以算作是DFS和BFS的结合。适合大树而可行解不是很深的题目。

IDA*对于最优解层数小，每次扩展状态多的时候是一个杀手锏啊。IDA*就是一个加了层数限制depth的DFS，超过了限制就不在搜索下去，如果在当前层数没有搜到目标状态，就加大层数限制depth，这里还只是一个IDA算法，并不是A*的。当然我们可以用A*的估计函数去剪枝，如果当前深度d+h()>depth的时候就可以不再搜索下去了，这样就是IDA*了。

　　对于这道题，我们把状态用一维数组存储，然后对每个元素设定相应的编号：

　　　　　　 0 1
　　　　　　 2 3
　　　　　　4 5 6 7 8 9 10
　　　　　　 11 12
　　　　　　13 14 15 16 17 18 19
　　　　　　 20 21
　　　　　　 22 23　　并且把每个操作的相应编号用数组存起来就好处理了：

AC代码：

#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
using namespace std;  
  
typedef long long LL;  
const int N=2222222;  
const LL II=1000000007;  
  
int n,m,depth;  
int vis[2222222],s[24];  
int path[N];  
int t[4][2]={-1,0,0,1,1,0,0,-1};  
char op[]="ABCDEFGH";  
int mid[8]={6,7,8,11,12,15,16,17};//中间位置   
int fan[8]={5,4,7,6,1,0,3,2};//反方向移动，回归   
int xh[8][7]=//8种操作，每次移动7位   
{  
    0,2,6,11,15,20,22,  
    1,3,8,12,17,21,23,  
    10,9,8,7,6,5,4,  
    19,18,17,16,15,14,13,  
    23,21,17,12,8,3,1,  
    22,20,15,11,6,2,0,  
    13,14,15,16,17,18,19,  
    4,5,6,7,8,9,10  
};  
  
int max3(int a,int b,int c)  
{  
    return (a>b a:b)>c (a>b a:b):c;  
}  
  
int get(int a[])  
{  
    int i,cnt[4]={0,0,0,0};  
    for(i=0;i<8;i++)  
        cnt[s[mid[i]]]++;  
    return 8-max3(cnt[1],cnt[2],cnt[3]);// 8-返回中间最多的那个数 的数量   
}  
  
void move(int k)  
{  
    int i,t=s[xh[k][0]];  
    for(i=1;i<7;i++)  
        s[xh[k][i-1]]=s[xh[k][i]];  
    s[xh[k][6]]=t;  
}  
  
bool dfs(int k)  
{  
    if(k>=depth)  
        return false;  
    int i,h;  
    for(i=0;i<8;i++)  
    {  
        move(i);  
        path[k]=i;  
        h=get(s);  
        if(h==0)  
            return true;  
        if((k+h)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
const int N=2222222;
const LL II=1000000007;

int n,m,depth;
int vis[2222222],s[24];
int path[N];
int t[4][2]={-1,0,0,1,1,0,0,-1};
char op[]="ABCDEFGH";
int mid[8]={6,7,8,11,12,15,16,17};//中间位置
int fan[8]={5,4,7,6,1,0,3,2};//反方向移动，回归
int xh[8][7]=//8种操作，每次移动7位
{
    0,2,6,11,15,20,22,
    1,3,8,12,17,21,23,
    10,9,8,7,6,5,4,
    19,18,17,16,15,14,13,
    23,21,17,12,8,3,1,
    22,20,15,11,6,2,0,
    13,14,15,16,17,18,19,
    4,5,6,7,8,9,10
};

int max3(int a,int b,int c)
{
    return (a>b a:b)>c (a>b a:b):c;
}

int get(int a[])
{
    int i,cnt[4]={0,0,0,0};
    for(i=0;i<8;i++)
        cnt[s[mid[i]]]++;
    return 8-max3(cnt[1],cnt[2],cnt[3]);// 8-返回中间最多的那个数 的数量
}

void move(int k)
{
    int i,t=s[xh[k][0]];
    for(i=1;i<7;i++)
        s[xh[k][i-1]]=s[xh[k][i]];
    s[xh[k][6]]=t;
}

bool dfs(int k)
{
    if(k>=depth)
        return false;
    int i,h;
    for(i=0;i<8;i++)
    {
        move(i);
        path[k]=i;
        h=get(s);
        if(h==0)
            return true;
        if((k+h)