POJ 2286 The Rotation Game 搜索-IDA*+迭代加深

本題若用廣搜，空間需求量非常大，空間不足。深搜的話，深度很難控制，容易陷入死循環。在這個時候就要用到迭代加深的深搜方法。

所謂迭代加深，就是在深度無上限的情況下，先預估一個深度（盡量小）進行搜索，如果沒有找到解，再逐步放大深度搜索。這種方法雖然會導致重復的遍歷 某些結點，但是由於搜索的復雜度是呈指數級別增加的，所以對於下一層搜索，前面的工作可以忽略不計，因而不會導致時間上的虧空。

這種方法，可以算作是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 <iostream>   
#include <cstdio>   
#include <cstdlib>   
#include <cmath>   
#include <cstring>   
#include <string>   
#include <vector>   
#include <list>   
#include <deque>   
#include <queue>   
#include <iterator>   
#include <stack>   
#include <map>   
#include <set>   
#include <algorithm>   
#include <cctype>   
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)<depth&&dfs(k+1))//當前的步數加還需要的最少步數<depth   
            return true;  
        move(fan[i]);//移回來   
    }  
    return false;  
}  
  
int main()  
{  
    int i,j;  
    while(scanf("%d",&s[0])&&s[0])  
    {  
        for(i=1;i<24;i++)  
            scanf("%d",&s[i]);  
        depth=get(s);//差最少的步數   
        if(depth==0)  
        {  
            printf("No moves needed\n%d\n",s[mid[0]]);  
            continue;  
        }  
        while(!dfs(0))  
            depth++;//如果不行，最少步數+1   
        for(i=0;i<depth;i++)  
            printf("%c",op[path[i]]);  
        printf("\n%d\n",s[6]);//輸出中間位置的數字   
    }  
    return 0;  
}  

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
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)<depth&&dfs(k+1))//當前的步數加還需要的最少步數<depth
            return true;
        move(fan[i]);//移回來
    }
    return false;
}

int main()
{
    int i,j;
    while(scanf("%d",&s[0])&&s[0])
    {
        for(i=1;i<24;i++)
            scanf("%d",&s[i]);
        depth=get(s);//差最少的步數
        if(depth==0)
        {
            printf("No moves needed\n%d\n",s[mid[0]]);
            continue;
        }
        while(!dfs(0))
            depth++;//如果不行，最少步數+1
        for(i=0;i<depth;i++)
            printf("%c",op[path[i]]);
        printf("\n%d\n",s[6]);//輸出中間位置的數字
    }
    return 0;
}