八数码问题之康拓展开求解

八数码问题之康拓展开求解

八数码问题描述：

在九宫格里放在1到8共8个数字还有一个是空格，与空格相邻的数字可以移动到空格的位置，问给定的状态最少需要几步能到达目标状态（用0表示空格）！

类似于华容道，只不过华容道的最终状态是：

123

456

780

解题思路：

这个问题正常想法是直接上BFS，但是难点就在于在bfs时，改用什么样的状态来保存当前状态以及搜索过的状态。最初的想法是用一个9！大小的数组或者set或者map存储，而数据类型用int或者int bool！ set和map的本质是：红黑树的平衡二叉树，所以插入效率是比较高的，查找运用二分查找，所以，也不是很复杂！但是呢，int这个东西就是只能用一维大小的数了，比如上面的最终状态就是 123456780 这个数。到这，很容易想到用全排列（dfs）来预处理一遍num数组（升序，记录从012345678~876543210），然后遍历的时候查找时第几个就直接在vis数组（大小为9！，是否搜索过）标记一下就可以了！

我们发现，上面可以有很多的时间优化。比如二分查找时候以及全排列的时候！话说，康拓展开就是专门用来解决全排列的一个很好的数学工具，对处理以上问题，说不定有质的飞跃！

唐拓展开描述：

（复制下百度百科了）康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

康托展开运算

其中,  为整数,并且 。

表示原数的第i位在当前未出现的元素中是排在第几个

康托展开的逆运算

既然康托展开是一个双射，那么一定可以通过康托展开值求出原排列，即可以求出n的全排列中第x大排列。

如n=5,x=96时：

首先用96-1得到95，说明x之前有95个排列.(将此数本身减去1)用95去除4! 得到3余23，说明有3个数比第1位小，所以第一位是4.用23去除3! 得到3余5，说明有3个数比第2位小，所以是4，但是4已出现过，因此是5.用5去除2!得到2余1，类似地，这一位是3.用1去除1!得到1余0，这一位是2.最后一位只能是1.所以这个数是45321。

按以上方法可以得出通用的算法。 

康托展开和逆康托展开

康托展开举例

再举个例子说明。

在   5个数的排列组合中，计算 34152的康托展开值。

首位是3，则小于3的数有两个，为1和2，

，则首位小于3的所有排列组合为

第二位是4，则小于4的数有两个，为1和2，注意这里3并不能算，因为3已经在第一位，所以其实计算的是在第二位之后小于4的个数。因此

第三位是1，则在其之后小于1的数有0个，所以

第四位是5，则在其之后小于5的数有1个，为2，所以

最后一位就不用计算啦，因为在它之后已经没有数了，所以

固定为0

根据公式：

所以比34152小的组合有61个，即34152是排第62。

代码：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;
static const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};   // 阶乘
vector<int> m;
int cantor(int *a, int n)
{int x = 0;for (int i = 1; i <= n; ++i) {int smaller = 0;  // 在当前位之后小于其的个数for (int j = i + 1; j <= n; ++j) {if (a[j] < a[i])smaller++;}x += FAC[n - i] * smaller; // 康托展开累加}return x;  // 康托展开值
}  
//康托展开逆运算
void decantor(int x, int n,int a[10] )
{vector<int> v;  // 存放当前可选数for(int i=1;i<=n;i++)v.push_back(i);int k=1;for(int i=n;i>=1;i--){int r = x % FAC[i-1];int t = x / FAC[i-1];x = r;sort(v.begin(),v.end());// 从小到大排序a[k++]=v[t]-1;     // 剩余数里第t+1个数为当前位v.erase(v.begin()+t);   // 移除选做当前位的数}}int main(int argc, char const *argv[])
{int a[10]={0,2, 8, 3, 1, 0, 4, 7, 6, 5};int b[10];cout<<"the "<<cantor(a,9)<<"-th num is:"<<endl;int t=cantor(a,9);decantor(t, 9,b);for(int i=1;i<=9;i++)cout<<b[i];cout<<endl;//cout<<cantor(b,9)<<endl;return 0;
}

有了以上的康拓展开的算法，时间复杂度上就减少了很多！

so，问题解决了，记录下我自己写的代码：

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>using namespace std;
static const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};   // 阶乘
bool v[362880+5];
int m[10];//存储初始形态
int em[10];//目标形态
int tem[]={1,2,3,4,5,6,7,8};
int dir[4][2]={0,1,-1,0,0,-1,1,0};//方向
struct node
{int x,y,step,state;//0的坐标（x，y），步数，状态int last;//上一步下标char last_go;//从上一步到这一步的方法node(){x=0;y=0;step=0;state=0;last=0;last_go='n';}
};
//vector是从0开始的数组
vector<node> htg;//记录到达最终状态的步骤，udlr 分别为 上下左右
queue<node>q;void can_go(int x,int y,int n,int m[10])//可以走的话该怎么走（交换值）
{switch(n){case 1:swap(m[(x-1)*3+y],m[(x-1)*3+y+1]);break;case 2:swap(m[(x-1)*3+y],m[(x-1)*3+y-3]);break;case 3:swap(m[(x-1)*3+y],m[(x-1)*3+y-1]);break;case 4:swap(m[(x-1)*3+y],m[(x-1)*3+y+3]);break;}
}char how_go(int n)//怎么走
{switch(n){case 1:return 'r';case 2:return 'u';case 3:return 'l';case 4:return 'd';}return 'n';
}int cantor(int *a, int n)
{int x = 0;for (int i = 1; i <= n; ++i) {int smaller = 0;  // 在当前位之后小于其的个数for (int j = i + 1; j <= n; ++j) {if (a[j] < a[i])smaller++;}x += FAC[n - i] * smaller; // 康托展开累加}return x;  // 康托展开值
}void decantor(int x, int n,int a[10])
{vector<int> v;  // 存放当前可选数// 所求排列组合for(int i=1;i<=n;i++)v.push_back(i);int k=1;for(int i=n;i>=1;i--){int r = x % FAC[i-1];int t = x / FAC[i-1];x = r;sort(v.begin(),v.end());// 从小到大排序a[k++]=v[t]-1;     // 剩余数里第t+1个数为当前位v.erase(v.begin()+t);   // 移除选做当前位的数}//for(int i=1;i<=5;i++)//    cout<<a[i];}void init()
{/* map<int ,bool> iterator::it;for(it=v.begin();it!&#d();it++){v.erase(it);}*/while(!q.empty()) q.pop();memset(v,false,sizeof(v));htg.clear();}//搜索，传入空格坐标（x，y）
bool bfs(int x,int y,int state,int endtate)
{int k=0;node tn;tn.x=x,tn.y=y,tn.step=0,tn.state=state,tn.last=k;q.push(tn);v[state]=true;while(!q.empty()){tn=q.front();htg.push_back(tn);k++;if(tn.state==endtate)return true;q.pop();int a[10];decantor(tn.state, 9,a);/*for(int i=1;i<=9;i++)cout<<a[i];cout<<endl;int next;cin>>next;*/for(int i=0;i<4;i++){int tx=tn.x+dir[i][0];int ty=tn.y+dir[i][1];if(tx<=3&&tx>0&&ty<=3&&ty>0){node tnn;int ta[10];for(int j=1;j<=9;j++)ta[j]=a[j];can_go(tn.x,tn.y,i+1,ta);int ts=cantor(ta, 9);if(v[ts]==false){tnn.x=tx,tnn.y=ty;tnn.step=tn.step+1;tnn.last=k;tnn.last_go=how_go(i+1);v[ts]=true;tnn.state=ts;q.push(tnn); }}}}return false;}int n,cnt;
int sequeue[10];
int temp[10];
int p;void mergeSort(int l = 0, int r = cnt )
{if (r - l == 1) return;int mid = (l + r) / 2;mergeSort(l, mid);mergeSort(mid, r);int i = l;int j = mid;int k = l;while (i < mid || j < r){if ( j >= r || (i < mid && (sequeue[i] <= sequeue[j]))){temp[k++] = sequeue[i++];}else{temp[k++] = sequeue[j++];p += mid - i;}}for (int i = l; i < r; i++){sequeue[i] = temp[i];}
}int is_can(int *s1)//能否到达最终状态
{//strcpy(sequeue,s1)p=0;mergeSort(0, cnt);int t1=p;for(int i=0;i<=7;i++)sequeue[i] = s1[i];p=0;mergeSort(0, cnt );int t2=p;if(t1%2==t2%2)return 1;return 0;
}int main()
{int x,y;int z[10]={0,1,1,1,2,2,2,3,3,3};int zz[10]={0,1,2,3,1,2,3,1,2,3};char t[10];while(~scanf("%s",t+1)){init();//gets(t);//输入初始cnt=0;for(int i=1;i<=9;i++){sequeue[cnt] = t[i]-'0';if (sequeue[cnt]) cnt++;m[i]=t[i]-'0';  if(m[i]==0){x=z[i];y=zz[i];}}//输入最终状态scanf("%s",t+1);cnt=0;for(int i=1;i<=9;i++){em[i]=t[i]-'0';tem[cnt] = t[i]-'0';if (tem[cnt]) cnt++;}   if(is_can(tem)){bfs( x,y,cantor(m, 9),cantor(em, 9) );if(q.front().step==0)cout<<"no move"<<endl;else{vector<char> htgt;cout<<q.front().step<<endl;for(int i=htg.size()-1;i!=0;i=htg[i].last-1)htgt.push_back(htg[i].last_go);for(int i=htgt.size()-1;i>=0;i--)cout<<htgt[i];cout<<endl;}}elsecout<<"-1"<<endl;/*if(!bfs( x,y,cantor(m, 9),cantor(em, 9) )){cout<<"-1"<<endl;}*/}
}

上面代码用了归并排序的方法判断了是否能到达最终状态，大大提高了搜索的时间！

判断八数码能否到达最终状态：初始状态和最终状态除0以外的所有数字的逆数个数之和是否为相同的奇偶性，证明大家可以网上搜搜就能了解了。

结语：

看其他大佬的博客，处理这种问题还有很多的算法，比如双向bfs，A*搜索，可以让时间更高效，特别是A*特别神奇。类似于人类的直观，很有意思，有时间就去研究一下，现在也只能了解到那么多，所以，就到这了，88！