八数码问题(八重境界)
参考
1.http://www.cnblogs.com/goodness/archive/2010/05/04/1727141.html 八数码的八境界
2.https://www.cnblogs.com/zufezzt/p/5659276.html HDU 1043 八数码（八境界）
以下仅为个人理解,不能保证正确
境界1:暴力广搜+STL(HDU1043 G++ 爆内存 C++ 1248ms 32568kb AC)
说实话这个能过真的是太秀了鬼鬼,差200kb就爆炸
由于八数码的状态总共也就9!=362880,所以完全可以采用set判重,string存储状态,map存储到终态需要的步数
int dy[4]={-1,1,0,0};
int dx[4]={0,0,-1,1};
string dir="durl";
set<string> f;
map<string,string> m;从最终状态开始”12345678x”,倒着记录
m["12345678x"]="";
f.insert("12345678x");然后就是bfs咯
代码如下:
#includeelsecout<return 0;
}
这个差点爆炸,不过挑战上面广搜的一道练习题可以练习这一部分:Aizu - 0121(AOJ) 七数码问题
解法和上面的思路完全一样
#includecout<1 <return 0;
}
时间在2ms(大概数据很少),内存5440kb,这个还是能接受的
境界2:广搜+哈希
首先需要了解一下逆序数
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。一个排列中所有逆序总数叫做这个排列的逆序数。也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。
逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。
来源_百度百科
这道题里面我们可以用到奇偶排列不会相互转换判断是否有解
int sum=0;
for(int i=0;t[i];i++){if(t[i]=='x')continue;for(int j=0;jif(t[j]=='x')continue;if(t[i]sum++;}
}
if(sum%2==1){cout<<"unsolvable"<continue;
} 然后就是我们可以自己写一个hash来判重
怎么构造hash函数呢?
就是利用康托展开和逆序数进行构造,这一部分在这里略过
代码实现:
首先需要写一个将字符串转成对应数字的函数
int getnum(){int res=0;for(int i=0;t[i];i++)for(int j=i+1;t[j];j++)if(t[j]//x代表的是9大于所有其他的数 对于ascii表来说 x也大于任何数字 所以直接判断res=res+c[8-i];//c是阶乘return res;
} 其次还要写一个转回来的函数
void getstr(int val){int temp[10];int flag[10];memset(flag,0,sizeof(flag));for(int i=0;i<9;i++){temp[i]=val/c[8-i];//删除阶乘val=val%c[8-i];}//得到每一个的逆序数for(int i=0;i<9;i++){int num=0;for(int j=0;j<9;j++){if(flag[j]==0)//未出现则++num++;if(num==temp[i]+1){t[i]=j+'0'+1;if(t[i]=='9')t[i]=='x';flag[j]=1;//标记该数已出现break;}}}
}结构:
char t[1000];
int c[10];
int dy[4]={-1,1,0,0};
int dx[4]={0,0,-1,1};
char dir[4]={'u','d','l','r'};
stack<int> s;
struct Node{int s;int p;Node(){}Node(int S,int P){s=S;p=P;}
};
struct path{//由于string保存缓慢,所以采用这种类似于链式的结构存储移动路径int from;int dir;
}pa[400000];
bool f[400000];完整代码如下:
#include8-i];return res;
}
void getstr(int val){//hash值转棋盘int temp[10];int flag[10];memset(flag,0,sizeof(flag));for(int i=0;i<9;i++){temp[i]=val/c[8-i];val=val%c[8-i];}for(int i=0;i<9;i++){int num=0;for(int j=0;j<9;j++){if(flag[j]==0)num++;if(num==temp[i]+1){t[i]=j+'0'+1;if(t[i]=='9')t[i]=='x';flag[j]=1;break;}}}
}
void bfs(int val,int pos){//广搜queueif(t[j]=='x')continue;if(t[i]if(sum%2==1){cout<<"unsolvable"<continue;}//计算是否能通过变换转移到最终状态memset(f,0,sizeof(f));bfs(state,pos);while(!s.empty()){cout<cout<return 0;
} 第三重境界:广搜+哈希+打表
第二重境界中poj1077已经可以在指定时间内求解,而hdu之所以不行是因为hdu是多组输入,那为了应对这种情况我们可以和境界1类似从终态打表
都挺类似的,直接扔代码
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAX_N=100000;
const int INF = 0x3f3f3f3f;
#define eps 1e-7char t[9];
int c[10];
int dy[4]= {-1,1,0,0};
int dx[4]= {0,0,-1,1};
char dir[4]= {'d','u','r','l'};
stack<int> s;struct node {int s;int p;node(){}node(int S,int P){s=S,p=P;}
};struct way {int from;int dir;
} way[400000];
bool f[400000];int getnum() {int res=0;for(int i=0; t[i]; i++)for(int j=i+1; t[j]; j++)if(t[j]8 -i];return res;
}void getstr(int val) {int temp[10];int flag[10];memset(flag,0,sizeof(flag));for(int i=0; i<9; i++) {temp[i]=val/c[8-i];val=val%c[8-i];}for(int i=0; i<9; i++) {int num=0;for(int j=0; j<9; j++) {if(flag[j]==0)num++;if(num==temp[i]+1) {t[i]=j+'0'+1;if(t[i]=='9')t[i]='x';flag[j]=1;break;}}}
}void pre() {queueelse{while(1) {if(way[state].from==-1) break;cout<cout<return 0;
} 第四重境界：双向广搜+hash
简单来说双向广搜就是从开始和终态两个方向同时搜索，当两部分相互接触时，则产生的连同就是最短路，这样做可以使一些不必要的状态不被遍历到从而减少时间
点此查看图解
此链接中由一个匿名用户的回答的图解很详细的恢复了这个问题
这里有一个会变化的地方就是记录路径不再是一部分了，而是正向搜索的一部分和反向搜索的部分两者路径的加和，可以想象正向搜索是先进先出，而反向搜索的是先进后出，所以使用一个queue来记录正向搜索的路径，使用一个stack记录反向搜索的路径，在找到最短路径后，将路径押入 然后输出即可
stack<int> S;
queue<int> Q;
queue还有一个小优化就是为了保证双向广搜的效果，我们可以增加一个变量来记录两个状态目前扩展了多少顶点，为了保证双向广搜的效果最大，我们必然想要两个部分扩展的顶点尽可能接近。所以我们优先扩展顶点数少的一方向来平衡，在hdu题中，这种优化大概优化了200ms左右。
int cal[3];其他部分都差不多比如hash需要一个状态转hash值的函数还有hash值转状态的函数
getnum();
getstr();其他类似,就不详细讲了,代码如下:(以后的我应该能理清楚自己的思路…..吧)
#include1)<int MAX_N=100000;
const int INF = 0x3f3f3f3f;
#define eps 1e-7char input[10];
char t[10];
int c[10];
struct node{int s;int p;node(){}node(int S,int P){s=S;p=P;}
};struct Path{int from;int dir;
}path[400000];
int f[400000];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
string d[3]={"","udlr","durl"};
stack<int> S;
queue<int> Q;
queue q[3];
int ans;int getnum(){int res=0;for(int i=0;t[i];i++){for(int j=i+1;t[j];j++){if(t[j]8-i];}}return res;
}
void getstr(int val){int tmp[10],flag[10];memset(flag,0,sizeof(flag));for(int i=0;i<9;i++){tmp[i]=val/c[8-i];val=val%c[8-i];}for(int i=0;i<9;i++){int num=0;for(int j=0;j<9;j++){if(flag[j]==0)num++;if(num==tmp[i]+1){t[i]=j+'0'+1;if(t[i]=='9')t[i]=='x';flag[j]=1;break;}}}
}bool g(int a,int b){if(a<0||b<0||a>2||b>2)return false;return true;
}void bfs(int now){node h=q[now].front();q[now].pop();int a=h.p/3;int b=h.p%3;getstr(h.s);for(int i=0;i<4;i++){int y=a+dy[i];int x=b+dx[i];if(!g(y,x))continue;int pos=3*y+x;swap(t[h.p],t[pos]);int te=getnum();if(f[te]!=now){if(f[te]==0){f[te]=now;path[te].from=h.s;path[te].dir=i;q[now].push(node(te,pos));}else{ans=1;if(now==1){S.push(i);int u=h.s;while(path[u].from!=-1){S.push(path[u].dir);u=path[u].from;}u=te;while(path[u].from!=-1){Q.push(path[u].dir);u=path[u].from;}}else{Q.push(i);int u=h.s;while(path[u].from!=-1){Q.push(path[u].dir);u=path[u].from;}u=te;while(path[u].from!=-1) {S.push(path[u].dir);u=path[u].from;}}break;}}swap(t[h.p],t[pos]);}
}
void init(){memset(f,0,sizeof(f));ans=0;while(!q[1].empty())q[1].pop();while(!q[2].empty())q[2].pop();
}
void work(int s,int pos){q[1].push(node(s,pos));q[2].push(node(0,8));f[s]=1;path[s].from=path[s].dir=-1;f[0]=2;path[0].from=path[0].dir=-1;while((!q[1].empty())&&(!q[2].empty())){if(ans==1)break;bfs(1);if(ans==1)break;bfs(2);if(ans==1)break;}
}
int main(){ios::sync_with_stdio(false);c[0]=1;for(int i=1;i<=8;i++)c[i]=c[i-1]*i;while(cin>>t[0]){for(int i=1;i<=8;i++)cin>>t[i];for(int i=0;i<=9;i++)input[i]=t[i];int sum=0;for(int i=0;t[i];i++){if(t[i]=='x')continue;for(int j=0;jif(t[j]=='x')continue;if(t[i]if(sum%2==1){cout<<"unsolvable"<continue;}init();for(int i=0;i<9;i++){if(input[i]=='x'){work(getnum(),i);break;}}if(ans==1){while(!S.empty()){cout<1][S.top()];S.pop();}while(!Q.empty()){cout<2][Q.front()];Q.pop();}cout<elsecout<<"unsolvable"<return 0;
} 之后四个境界大概要过段时间了,因为我虽然理解了这个问题的估价函数(使用曼哈顿距离),但是却无法类推其他估价函数,比如如果换一种题型,那么如何构造出来估价函数就不懂了,大概是能力不到吧,暂时先空吧..
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！