程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2286 The Rotation Game 迭代搜索深度 + A* == IDA*

POJ 2286 The Rotation Game 迭代搜索深度 + A* == IDA*

編輯：C++入門知識

感覺這種算法還是比較局限的吧，重復搜索是一個不好的地方，而且需要高效的估值函數來進行強剪枝，這點比較困難。

迭代搜索深度是一個比較炫酷的搜索方式，不過有點拿時間換空間的感覺。

首先迭代深度比較搓的寫法是，首先設置一個閥值MaxH，初始為最小值。

當在搜索深度Depth <= MaxH時找到解則此時為最優解，否則MaxH++,繼續深搜。

另外一種比較吊的寫法是二分搜索深度，若搜到則減小閥值，否則增大閥值。

總之，迭代深度搜索就是通過改變深搜的深度來尋找最優解，這樣做的好處是省掉了BFS中狀態標記所有的空間花銷。

對於這種算法掌握的並不透徹，就不多說了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define _INF 0x3f3f3f3f
#define Mod 6000007

using namespace std;

int num[25];

int order[8][7] ={
{ 1, 3, 7,12,16,21,23},
{ 2, 4, 9,13,18,22,24},
{11,10, 9, 8, 7, 6, 5},
{20,19,18,17,16,15,14},
{24,22,18,13, 9, 4, 2},
{23,21,16,12, 7, 3, 1},
{14,15,16,17,18,19,20},
{ 5, 6, 7, 8, 9,10,11}
};

int MaxH;

int Cal(int *num)
{
    int mark[] = {0,0,0,0,0};

    for(int i = 7;i <= 9; ++i)
        mark[num[i]]++;
    for(int i = 12;i <= 13; ++i)
        mark[num[i]]++;
    for(int i = 16;i <= 18; ++i)
        mark[num[i]]++;
    return min(8-mark[1],min(8-mark[2],8-mark[3]));
}

int sta[1000];
int Top;
int anw;

bool dfs(int *num,int ans)
{
    int temp = Cal(num);

    if(temp == 0)
    {
        anw = num[8];
        return true;
    }

    if(temp + ans > MaxH)
        return false;

    int tn[25];

    int i,j;

    for(i = 0;i < 8; ++i)
    {
        sta[Top++] = i;
        for(j = 1;j <= 24; ++j)
            tn[j] = num[j];
        for(j = 0;j < 7; ++j)
            tn[order[i][j]] = num[order[i][(j+1)%7]];
        if(dfs(tn,ans+1))
            return true;
        Top--;
    }
    return false;
}

int main()
{
    int i;

    while(scanf("%d",&num[1]) && num[1])
    {
        for(i = 2;i <= 24; ++i)
            scanf("%d",&num[i]);

        if(Cal(num) == 0)
        {
            printf("No moves needed\n");
            printf("%d\n",num[7]);
            continue;
        }

        MaxH = 1;
        Top = 0;

        while(dfs(num,0) == false)
        {
            MaxH++;
        }
        for(i = 0;i < Top; ++i)
            printf("%c",sta[i]+'A');
        printf("\n%d\n",anw);
    }

    return 0;
}