BFS-八数码问题与状态图搜索

　　在一个3*3的棋盘上放置编号为1~8的八个方块，每个占一格，另外还有一个空格。与空格相邻的数字方块可以移动到空格里。任务1：指定的初始棋局和目标棋局，计算出最少的移动步数；任务2：数出数码的移动序列。

　　把空格看成0，一共有九个数字。

　　输入样例：

　　1 2 3 0 8 4 7 6 5

　　1 0 3 8 2 3 7 6 5

　　输出样例：

　　2

　　1.把一个棋局看成一个状态图，总共有9！= 362880个状态。从初始棋局开始，每次移动转到下一个状态，达到目标棋局后停止。

　　2.康托展开

　　　　康托展开是一种特殊的哈希函数。其功能是在输入一个排列，计算出它在在全排列中从小到大排序的位次。

　　　　eg：判断 2143是{1，2，3，4}的全排列中的位次。

　　　　　　（1）首位小于2的所有排列。比2小的只有1，后面三个数的排列有3*2*1=3！个，写成1*3！=6

　　　　　　（2）首位为2，第二位小于1的所有排列。无，写成0*2！=0

　　　　　　（3）前两位为21，第三位小于4的所有排列。只有3一个数，写成1*1！=1

　　　　　　（3）前三位为214，第四位小于3的所有排列。无，写成0*0！=0

　　　　　　求和：1*3！+0*2！+1*1！+0*0！=7

　　　　所以位次的计算公式为X = a[n]*(n-1)! +a[n-1]*(n-2)! + … + a[1]*0!

 #include<bits/stdc++.h>

 #include<queue>

 using namespace std;

 const int len = ; //状态共9! = 362880种

 int visited[len] = {};//标记已有状态用来去重

 int start[];//起始状态

 int goal[];//目标状态

 int factory[] = {, , , , , , , , , };//0到9的阶乘

 int dir[][] = {{-, }, {, -}, {, }, {, }};

 struct node{

     int state[];//棋局状态按一维存放下来

     int dis;//记录从起始状态移动到当前状态的步数

 };

 bool cantor(int str[], int n){

     int result = ;

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

         int cnt = ;

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

             if(str[i] > str[j])

                 cnt ++;

         }

         result += cnt*factory[n-i-];

     }

     if(!visited[result]){

         visited[result] = ;

         return ;

     }

     return ;

 }

 int BFS(){

     node head, next;

     memcpy(head.state, start, sizeof(head.state));//复制起始状态并插入队列

     head.dis = ;

     cantor(head.state, );

     queue<node>q;

     q.push(head);

     while(!q.empty()){

         head = q.front();

         q.pop();

         int z;

         for(z=; z<; z++)

             if(head.state[z] == )//找到0

                 break;

         int x = z % ;//将0的一维位置转化为二维的横纵坐标

         int y = z / ;

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

             int newx = x + dir[i][];

             int newy = y + dir[i][];

             int newz = newx + *newy;//将0移动后重新转化为一维坐标

             if(newx>= && newx< && newy>= && newy<){//避免越界

                 memcpy(&next, &head, sizeof(struct node));

                 swap(next.state[z], next.state[newz]);//复制原先状态后，改变0的位置

                 next.dis ++;

                 if(memcmp(next.state, goal, sizeof(next.state)) == )

                     return next.dis;

                 if(cantor(next.state, ))//查重

                     q.push(next);

             }

         }

     }

     return -;

 }

 int main(){

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

         scanf("%d", start+i);

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

         scanf("%d", goal+i);

     int num = BFS();

     if(num != -)

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

     else

         printf("Impossible\n");

 }

　　（1）用于存放状态图的以及步数的结构体

　　（2）用于移动的数组

　　（3）用于去重的标记数组

　　（4）提前算好阶乘存放于数组中

　　（5）康拓函数判重

　　（6）BFS函数：queue<node>q；node head, next;

　　（7）状态图中某数字方块的一维坐标和二维坐标的相互转化

　　（8）检查坐标是否合法

八数码问题多种解法：https://www.cnblogs.com/zufezzt/p/5659276.html

巴特西

BFS-八数码问题与状态图搜索

最新文章

热门文章