设为首页 加入收藏

TOP

BFS(五):八数码难题 (POJ 1077)(二)
2019-07-10 12:10:29 】 浏览:216
Tags:BFS 八数码 难题 POJ 1077

       char space;    //  空格所在位置

};

      2)状态空间

      由于棋盘有9个格子,每种布局可以看成是数字1~9的一个排列,因此全部的布局数应为9!(362880)种。为了便于判断两种布局是否为同一种布局,可以编写一个函数int hash(const char *s)把数字1~9的排列映射为一个整数num(0<=num<=(9!-1))。例如,排列“123456789”映射为0、“213456789”映射为1、“132456789”映射为2、“231456789”映射为3、…、“987654312”映射为362878、“987654321”映射为362879。

      这样,每种状态就可以对应一个整数。反过来说,0~ (9!-1)之间的任一整数,也可以唯一对应一种状态。因此,判断两个状态结点cur和nst是否为同一种状态,只需判断 hash(cur.board)和hash(nst.board)是否相等即可,无需对两个格局数组的每个元素进行交互比较。

       为保存状态空间,定义三个全局数据:

      char visited[MAXN]; // visited[i]=1表示状态i被访问过;为0,表示未被访问

       int parent[MAXN];  // parent[i]=k 表示状态结点i是由结点k扩展来的

      char move[MAXN]; // move[i]=d 表示状态结点i是由结点k按照方式d扩展来的

      3)结点扩展规则

      棋子向空格移动实际上是空格向相反方向移动。设空格当前位置是cur.space ,则结点cur的扩展规则为:

      空格向上移动,cur.space=cur.space-3;空格向左移动,cur.space=cur.space-1;空格向右移动,cur.space=cur.space+1;空格向下移动,cur.space=cur.space+3。

设向上移动k=0、向左移动k=1、向右移动k=2、向下移动k=3,则上述规则可归纳为一条:空格移动后的位置为cur.space=cur.space-5+2*(k+1)。为此,定义一个数组

             const char md[4] = {'u', 'l', 'r', 'd'};

表示这四种移动方向。

      空格的位置cur.space<3,不能上移;空格的位置cur.space>5,不能下移;空格的位置cur.space是3的倍数,不能左移;空格的位置cur.space+1是3的倍数,不能右移。

      4)搜索策略

      将初始状态start放入队列中,求出start对应的hash值k = hash(start.board),并置   parent[k] = -1、visited[k] = 1。

      ① 从队列头取一个结点,按照向上、向左、向右和向下的顺序,检查移动空格后是否可以产生新的状态nst。

      ② 如果移动空格后有新状态产生,则检查新状态nst是否已在队列中出现过(visited[hash(nst.board)]== 1),是则放弃,返回①。

      ③ 如果新状态nst未在队列中出现过,就将它加入队列,再检查新状态是否目标状态(hash(nst.board)==0),如果是,则找到解,搜索结束;否则返回①。

      (2)源程序1。

#include<iostream>

#include<queue>

using namespace std;

struct node{   

       char board[9];  

       char space;  // 空格所在位置

};

const int MAXN = 362880;

int fact[]={ 1, 1,2,6,24,120,720,5040,40320};

//  对应  0!,1!,2!,3!,4!,5!,6!,7!,8!

int hash(const char *s)

// 把1..9的排列*s 映射为数字 0..(9!-1)

{   

       int i, j, temp, num;   

       num = 0;   

       for (i = 0; i < 9-1; i++)

       {     

           temp = 0; 

           for (j = i + 1; j < 9; j++)

          {

              if (s[j] < s[i])

                  temp++;       

          }

          num += fact[9-i-1] * temp;

       }

       return num;

}

char visited[MAXN];

int parent[MAXN];

char move[MAXN];

const char md[4] = {'u', 'l', 'r', 'd'};

void BFS(const node & start)

{

首页 上一页 1 2 3 4 5 6 下一页 尾页 2/6/6
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇洛古最简单50题解(41-50) 下一篇BFS(四):搜索状态判重

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目