⼋数码问题
编号为1-8的8个正⽅形滑块被摆成三⾏三列(有⼀个格⼦留空)，如图所⽰:
每次可以把与空格相邻的滑块移到空格中，⽽它原来的位置就成了新的空格。给定初始局⾯和⽬标局⾯，你的任务是计算出最少的移动步数，如果⽆法达到⽬标局⾯，输出-1。
264
137
58
815
736
42
样例输⼊：2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
样例输出：31
不难把⼋数码问题归结为图上的最短路问题。其中每个状态就是9个格⼦中的滑块编号（从上到下，从左到右地把它们放到⼀个包含9个元素的数组中）。具体程序如下：
#include <iostream>
#include <cstring>
using namespace std;
typedef int State[9];    /**定义状态类型*/
const int MAXSTATE=1000000;
State st[MAXSTATE],goal; /**状态数组，所有状态都保存在这⾥**/
int dist[MAXSTATE];      /**距离数组*/
int fa[MAXSTATE];        /**⽗亲编号数组，⽤于打印*/
int vis[36288],fact[9];
void init_lookup_table();
int try_to_insert(int s);
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
/**BFS返回⽬标状态在st数组下标**/
int bfs()
{
init_lookup_table();  /*初始化查表*/
int front=1,rear=2;
while (front < rear)
{cstring转为int
State& s =st[front];
if ( memcmp( goal, s,sizeof (s) )==0 ) return front;
int z;
for (z=0; z<9 ; z++)
if (!s[z]) break;
int x=z/3,y=z%3;
for (int d=0;d<4;d++)
{
int newx=x+dx[d];
int newy=y+dy[d];
int newz=newx*3+newy;
if (newx>=0 && newx<3 && newy>=0 && newy<3 )
{
State& t = st[rear];
memcpy(&t,&s,sizeof(s));
t[newz]=s[z];
t[z]=s[newz];
dist[rear] = dist[front]+1 ;
if (try_to_insert(rear)) rear++;
}
}
front++;
}
return 0;
}
注意，此处⽤到了 cstring 的 memcmp 和 memcpy 来完成整块内存的⽐较和复制，⽐⽤循环⽐较和循环赋值要快。主程序很容易实现：
int main()
{
for (int i=0;i<9;i++) cin>>st[1][i];  /*起始状态*/
for (int i=0;i<9;i++) cin>>goal[i];    /*⽬标状态*/
int ans=bfs();                          /*返回⽬标状态的下标*/
if (ans>0) cout<<dist[ans]<<endl;
else cout<<"-1"<<endl;
return 0;
}
注意，应该在调⽤bfs函数之前设置好st[1]和goal。上⾯的代码⼏乎是完整的，唯⼀没有涉及的是init_lookup_taible()和
try_to_insert(rear)的实现。为什么会有这个东西呢？还记得bfs中的vis数组吗？我们⽤它来进⾏bfs中的判重。这⾥的查表和它的功能类似，也是避免我们将同⼀个节点结构访问多次。树的bfs不需要判重，因为根本不会重复，但对于图来说，如果不判重，时间和空间都将产⽣极⼤的浪费。
如何判重呢？难道要声明⼀个9维数组vis，然后 if(vis[s[0]][s[1]][s[2]][s[3]]...[s[8]])  ? ⽆论程序好不好看，9维数组的每维都要包含9个元素，⼀共有9^9=387420489项，太多了，数组开不下。实际的节点数并没有这么多。(0-8的排列总共只有9!=362880个)，为什么9维数组开不下呢？原因在于，数组中有很多项都没有⽤到，但却占据了空间。
下⾯讨论3种常见的⽅法来解决这个问题，同时也将其⽤到⼋数码问题中。
第⼀种⽅法是：把排列变成整数，然后只开⼀个⼀维数组，也就是说，我们设计⼀套排列的编码和解码函数，把0-8的全排列和0-362879的整数⼀⼀对应起来。
int vis[36288],fact[9];
void init_lookup_table()
{
fact[0]=1;
for (int i=1;i<9;i++) fact[i]=fact[i-1] * i ;
}
int try_to_insert(int s)
{
int code =0; /*把st[s]映射到整数code*/
for (int i=0 ; i<9 ; i++)
{  int cnt=0;
for (int j=i+1;j<9;j++) if (st[s][j] < st[s][i]) cnt++;
code += fact[8-i] * cnt;
}
if (vis[code]) return 0;
return vis[code]=1;
}
尽管原理巧妙，时间效率也⾮常⾼，但编码解码法的适⽤范围并不⼤。如果隐式图的总节点数⾮常⼤，编码也将会很⼤，数组还是开不下。
第⼆种⽅法是适⽤哈希技术。简单地说，就是把节点变成整数，但不必⼀⼀对应，换句话说，只要设计⼀个所谓的哈希函数h(x)，然后将任意节点x映射到某个给定范围[0,M-1]的整数即可。其中M是程序员根据可⽤内存的⼤⼩⾃选的。在理想情况下，只需开⼀个⼤⼩为M 的数组就能完成判重，但此时往往有不同节点的哈希值相同，因此需要把哈希值相同的状态组织成链表，代码如下：
const int MAXHASHSIZE = 1000007;
int head[MAXHASHSIZE],next[MAXHASHSIZE];
void init_lookup_table() { memset(head,0,sizeof(head) ); }
int hash (State &s)
{
int v = 0;
for (int i = 0; i < 9; i++) v= v * 10 + s[i]; /**可以任意计算，例如，把九个数字组合成9位数*/
return v &MAXHASHSIZE;  /**确保hash函数值是不超过hash表的⼤⼩的⾮负整数*/
}
int try_to_insert(int s)
{
int h = hash(st[s]);
int u = head[h];
while(u)
{
if ( memcmp(st[u],st[s],sizeof (st[s]))==0 ) return 0; /**到了，插⼊失败**/
u=next[u];                                            /**那就顺着链表再下⼀个**/
}
next[s] = head[h];
head[h] = s;
return 1;
}
哈希表的执⾏效率很⾼，适⽤范围也很⼴。除了BFS中的结点判重外，你还可以把它⽤到其他需要快速
查的地⽅。不过需要注意的是：在哈希表中，对效率起到关键作⽤的是哈希函数。如果哈希函数选取得当，⼏乎不会有结点的哈希值相同，且此时链表查的速度也较快。但如果冲突严重，整个哈希表会退化成少数⼏条长长的链表，查速度将⾮常缓慢。有趣的是，前⾯的编码函数可以看做是⼀个完美的哈希函数，不需要解决冲突。不过，如果你事先并不知道它是完美的，也就不敢像前⾯⼀样只开⼀个vis数组。哈希技术还有很多值得探讨的地⽅。
第三种⽅法是使⽤STL中的集合。如果你⽤过STL的栈和队列，就可以理解下⾯的定义：set<State> vis 。它声明了⼀个类型为 state 的集合vis 。这样，只需⽤ unt(s)) 来判断 s 是否在集合vis中，并⽤vis.insert(s)加⼊集合，⽤ve(s)从集合中移除s。但问题在于，并不是所有类型的State都可以作为set中的元素类型。STL要求set的元素类型必须定义"<"运算符，如int,string，但C语⾔原⽣的数组(包括字符数组)却不⾏。下⾯是⼀种使⽤int的⽅法：
#include <set>
set<int> vis;
void init_lookup_table(){ vis.clear();}
int try_to_insert(int s)
{
int v=0;
for(int i = 0 ; i < 9 ; i++ ) v = v * 10 + st[s][i];
if (unt(v)) return 0;
vis.insert(v);
return 1;
}
但在很多其他场合中，数组是没有办法简单地转化成整数的。只能声明⼀个结构体，并重载"括号运算"来⽐较两个状态。这种实现⽅法，只能⽤两个整数读出两个状态在状态数组st中的下标，在⽐较时直接使⽤memcpy来⽐较整个内存块。
这种实现⽅法明显⽐刚才的要慢很多。因为调⽤memcmp直接⽐较两个整数要慢得多。事实上，在刚才的三种实现中，使⽤STL集合的代码最简单，但时间效率也最低。建议在做题时，仅仅把STL作为“跳板”——先写⼀个STL版的程序，确保主算法正确，然后把set替换成⾃⼰写的哈希表。
研读了这么多的⽅法，虽然脑⼦还有点乱，但是感觉越来越有趣了！⼀定要好好研究！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。