例题

骑士精神

Description

　　在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。

　　给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：

　　

　　为了体现出骑士精神，他们必须以最少的步数完成任务。

Input

　　第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。

Output

　　对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。

Sample Input

2

10110

01*11

10111

01001

00000

01011

110*1

01110

01010

00100

Sample Output

7

-1

样例中第二个数据的初始情况对应该图：

做法

这题的状态共有3^25，遍历完所有状态的时间则是8^15。

考虑用IDA*（貌似有其它做法）

举个简单的例子（不是指这题）：

如果用DFS，搜得过深却容易找不到解。所以应用BFS或IDDFS（迭代加深搜索）。

但是BFS有一个缺点，就是空间大。

因此，结合DFS和BFS，就有了IDDFS。

就是先搜深度为0的节点，再搜深度为1的节点、2的节点……直到搜出解。

为什么不用二分？因为节点的数量是指数级增长的，这样可能搜出很多无意义的情况。

IDDFS的缺点：搜过的点会再搜。

然而这样时间还会爆掉。我们可以用启发式搜索中的IDA*，设h（估价函数）为当前这个状态，没回到应该回到位置上的点的个数-1。为什么要-1？对于这题，若走k次，则最多更新k+1个点（原因显然，自己思考）；反过来就是说，若想要更新k个节点，则最少走k-1次。所以，h要-1。这样就保证了h(i)<=h*(i)（估计距离<=实际距离），保证了答案的正确性。只需利用h进行剪枝即可。

代码实现（C++）

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

char map[7][7];//地图

char tar[7][7]={{},{0,'1','1','1','1','1'},{0,'0','1','1','1','1'},{0,'0','0','*','1','1'},{0,'0','0','0','0','1'},{0,'0','0','0','0','0'}};//目标状态

int fx[9]={0,-1,-1, 1, 1,-2,-2, 2, 2};

int fy[9]={0,-2, 2,-2, 2,-1, 1,-1, 1};

bool IDA_star(int,int,int,int,int);

int main()

{

    int T;

    scanf("%d",&T);

    getchar();//使用getchar()的原因只是方便读入

    int i,j,h,x,y;

    while (T--)

    {

        for (i=1;i<=5;++i)

        {

            for (j=1;j<=5;++j)

                if ((map[i][j]=getchar())=='*')

                {

                    x=i;

                    y=j;

                }

            getchar();

        }

        h=0;

        for (i=1;i<=5;++i)

            for (j=1;j<=5;++j)

                h+=(map[i][j]!=tar[i][j]);//统计不在位置上的点

        for (i=0;i<=15;++i)

            if (IDA_star(0,h-1,i,x,y))//迭代加深（h-1的原因见上面）

            {

                printf("%d\n",i);

                break;

            }

        if (i>15)

            printf("-1\n");

    }

}

bool IDA_star(int g,int h,int lim,int x,int y)//g为现在的步数，h为估价函数，lim为限制深度，(x,y)为'*'的坐标（x行y列）

{

    if (g+h>lim)//剪枝，若无论如何不能在限制时间内达到

        return 0;

    if (g==lim)

        return 1;

    int i,tx,ty;

    char tmp;

    for (i=1;i<=8;++i)

    {

        tx=x+fx[i];

        ty=y+fy[i];

        if (1<=tx && tx<=5 && 1<=ty && ty<=5)

        {

            tmp=0;

            tmp-=(map[x][y]!=tar[x][y])+(map[tx][ty]!=tar[tx][ty]);//将两个点对估价函数的影响减去

            swap(map[x][y],map[tx][ty]);//交换

            tmp+=(map[x][y]!=tar[x][y])+(map[tx][ty]!=tar[tx][ty]);//将两个交换后的点对估价函数的影响加上

            if (IDA_star(g+1,h+tmp,lim,tx,ty))

                return 1;

            swap(map[x][y],map[tx][ty]);

        }

    }

    return 0;

}

巴特西

IDA*算法——骑士精神

例题

做法

代码实现（C++）

最新文章

热门文章