本文主要是介绍HDU 1043 ,POJ 1077 Eight,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
八数码问题
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
2 3 4 1 5 x 7 6 8
ullddrurdllurdruldr
一、数据如何存储和表示?
1、可以用整形来表示八数码的状态,x可以当作“9”,“0”不好处理,例如终态12345678x,可以表示成整数123456789,
2、用数组来存储,这里x可以用0或9来表示。
二、数据如何拓展?
1、对于int型整数,数据的拓展就是对这个数的处理,例如对于整数
1 2 3 1 2 3
4 5 6 4 5 9
7 8 9 x上移一位变成的状态是 7 8 6 即整数123459786
2、对于数组,数据拓展就是将该数组看成是二维数组,对此二维数组行和列的处理
三、如何记录路径?
1、构造一张邻接表,链式或者是连续存储都可以,记录每个节点的父节点和所有子节点,最后从目的节点递归输出最短路径,不用耗费大量内存记录走过的路径,所以极力推荐此种实现方法,具体应用可以参见
LeetCode OJ:Word Ladder II 解题思路过程详谈
2、因为此题只是记录udlr,所以可以用string来记录,不过因为对每个路径都需要存储走过的路径,太耗内存,所以不推荐
四、如何判重?
1、对于int型数组,可以构造一个大数组,记录是否访问,如vis[123456789]表示123456789状态是否访问,优点:快速。缺点:大量数据浪费,int类型大小的局限性
2、对于数组,可以将数组变成int型,再进行操作
3、用map来存,避免大量浪费
4、用康托拓展判重
五、状态转移如何建立?
1、最简单的无非是广搜,
(1)正向广搜
(2)反向广搜,将所有可能点都记录下来,用string[]大数组存储所有路径,当输入数据次数较多时比较适用,因为广搜只进行1次,内存消耗太大
2、双向广搜
3、A*算法
4、IDA*算法
这里提供一个使用双向广搜+map+int型存储数据版,答案不对,仅供参考
#include <iostream>
#include <map>
using namespace std;typedef struct{int x,w;char s;
}aaa;
aaa dui[500000],du[500000];
char www[500000];
int fang[4][2]={1,0,-1,0,0,1,0,-1};
int jin[9]={100000000,10000000,1000000,100000,10000,1000,100,10,1};
map<int,int> a;
char w[3][3];
int main()
{freopen("C:\\in.txt","r",stdin);for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>w[i][j];int many,ji,ji1,zan,zan2,x,y,tt,ww,ta,wa,q;many=0;char w2[9];for(int i=0;i<3;i++)for(int j=0;j<3;j++)w2[many++]=w[i][j];many=0;for(int i=0;i<3;i++)for(int j=0;j<i;j++)if((w2[i]-'0')<(w2[j]-'0')&&w2[i]!='x'&&w2[j]!='x')many+=1;if(many%2==0){int e,s;s=0;for(int i=0;i<3;i++)for(int j=0;j<3;j++){if(w[i][j]!='x')s=s*10+(w[i][j]-'0');else s=s*10+9;}tt=ww=ta=wa=1;dui[ww].w=s;e=123456789;du[wa].w=e;a[s]=1;a[e]=2;bool neng=false;if(s==e)neng=true;while(!neng){ji=0;ji1=0;for(int i=0;i<9;i++)if((dui[tt].w/jin[i])%10==9){ji=i;break;}for(int i=0;i<9;i++)if((du[ta].w/jin[i])%10==9){ji1=i;break;}for(int i=0;i<4;i++){x=ji/3;y=ji%3;if(x+fang[i][0]<3&&x+fang[i][0]>=0&&y+fang[i][1]<3&&y+fang[i][1]>=0&&neng==false){s=dui[tt].w;zan=s/jin[ji];zan2=s/jin[(x+fang[i][0])*3+(y+fang[i][1])];zan=zan%10;zan2=zan2%10;s=s-zan*jin[ji]-zan2*jin[(x+fang[i][0])*3+(y+fang[i][1])];s=s+zan2*jin[ji]+zan*jin[(x+fang[i][0])*3+(y+fang[i][1])];if(a[s]!=1){if(a[s]==2)neng=true;a[s]=1;ww++;dui[ww].w=s;dui[ww].x=tt;if(i==0)dui[ww].s='d';if(i==1)dui[ww].s='u';if(i==2)dui[ww].s='r';if(i==3)dui[ww].s='l';}}x=ji1/3;y=ji1%3;if(x+fang[i][0]<3&&x+fang[i][0]>=0&&y+fang[i][1]<3&&y+fang[i][1]>=0&&neng==false){s=du[ta].w;zan=s/jin[ji1];zan2=s/jin[(x+fang[i][0])*3+(y+fang[i][1])];zan=zan%10;zan2=zan2%10;s=s-zan*jin[ji1]-zan2*jin[(x+fang[i][0])*3+(y+fang[i][1])];s=s+zan2*jin[ji1]+zan*jin[(x+fang[i][0])*3+(y+fang[i][1])];if(a[s]==0){a[s]=2;wa++;du[wa].w=s;du[wa].x=ta;if(i==0)du[wa].s='u';if(i==1)du[wa].s='d';if(i==2)du[wa].s='l';if(i==3)du[wa].s='r';}}}ta++;tt++;}ji=0;q=ww;while(q!=1){ji++;www[ji]=dui[q].s;q=dui[q].x;}for(int i=ji;i>=1;i--)printf("%c",www[i]);ji=0;q=1;while(du[q].w!=dui[ww].w)q++;while(q!=1){ji++;www[ji]=du[q].s;q=du[q].x;}for(int i=1;i<=ji;i++)printf("%c",www[i]);printf("\n");}elseprintf("unsolvable\n");return 0;
}
再提供一个反向广搜版+康托版
/*
HDU 1043 Eight
思路:反向搜索,从目标状态找回状态对应的路径
用康托展开判重*/
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int MAXN=1000000;//最多是9!/2
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//康拖展开判重
// 0!1!2!3! 4! 5! 6! 7! 8! 9!
bool vis[MAXN];//标记
string path[MAXN];//记录路径
int cantor(int s[])//康拖展开求该序列的hash值
{int sum=0;for(int i=0;i<9;i++){int num=0;for(int j=i+1;j<9;j++)if(s[j]<s[i])num++;sum+=(num*fac[9-i-1]);}return sum+1;
}
struct Node
{int s[9];int loc;//“0”的位置int status;//康拖展开的hash值string path;//路径
};
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//u,d,l,r
char indexs[5]="durl";//和上面的要相反,因为是反向搜索
int aim=46234;//123456780对应的康拖展开的hash值
void bfs()
{memset(vis,false,sizeof(vis));Node cur,next;for(int i=0;i<8;i++)cur.s[i]=i+1;cur.s[8]=0;cur.loc=8;cur.status=aim;cur.path="";queue<Node>q;q.push(cur);path[aim]="";while(!q.empty()){cur=q.front();q.pop();int x=cur.loc/3;int y=cur.loc%3;for(int i=0;i<4;i++){int tx=x+dir[i][0];int ty=y+dir[i][1];if(tx<0||tx>2||ty<0||ty>2)continue;next=cur;next.loc=tx*3+ty;next.s[cur.loc]=next.s[next.loc];next.s[next.loc]=0;next.status=cantor(next.s);if(!vis[next.status]){vis[next.status]=true;next.path=indexs[i]+next.path;q.push(next);path[next.status]=next.path;}}}}
int main()
{freopen("C:\\in.txt","r",stdin);char ch;Node cur;bfs();while(cin>>ch){if(ch=='x') {cur.s[0]=0;cur.loc=0;}else cur.s[0]=ch-'0';for(int i=1;i<9;i++){cin>>ch;if(ch=='x'){cur.s[i]=0;cur.loc=i;}else cur.s[i]=ch-'0';}cur.status=cantor(cur.s);if(vis[cur.status]){cout<<path[cur.status]<<endl;}else cout<<"unsolvable"<<endl;}return 0;
}
再提供一个A*+康托版
#include<stdio.h>
#include<queue>
#include<string>
#include<iostream>
#include<algorithm>using namespace std;
const int MAXN=1000000;
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//康拖展开判重
// 0!1!2!3! 4! 5! 6! 7! 8! 9!bool vis[MAXN];//标记
string path;//记录最终的路径
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//方向向量
char indexs[5]="udlr";//正向搜索
struct Node
{int data[9];int f,g,h;int loc;//“0”的位置,把“x"当0int status;//康拖展开的hash值string path;//路径bool operator==(const Node &t){return status==t.status;}bool operator<(const Node &t)const{return f>t.f;}
}start,goal;//起始和终止点int Cantor(int s[])//康拖展开求该序列的hash值
{int sum=0;for(int i=0;i<9;i++){int num=0;for(int j=i+1;j<9;j++)if(s[j]<s[i])num++;sum+=(num*fac[9-i-1]);}return sum+1;
}
int ABS(int x){return x<0?(-x):x;}
int Distance(Node suc, Node goal, int i) {//计算方格的错位距离 int h1,h2; //h1表示suc中i所处位置,h2表示goal中i所处的位置for(int k = 0; k < 9; k++) { if(suc.data[k] == i)h1 = k; if(goal.data[k] == i)h2 = k; } return ABS(h1/3 - h2/3) + ABS(h1%3 - h2%3);
}
int Fvalue(Node suc, Node goal, float speed) {//计算 f 值 int h = 0; for(int i = 1; i <= 8; i++) h = h + Distance(suc, goal, i); return h*speed + suc.g; //f = h + g(speed 值增加时搜索过程以找到目标为优先因此可能 不会返回最优解)
} bool Astar()
{memset(vis,false,sizeof(vis));Node cur,next;priority_queue<Node> q;q.push(start);while(!q.empty()){cur=q.top();q.pop();if(cur==goal){path=cur.path;return true;}int x=cur.loc/3;int y=cur.loc%3;for(int i=0;i<4;i++){int tx=x+dir[i][0];int ty=y+dir[i][1];if(tx<0||tx>2||ty<0||ty>2)continue;next=cur;next.loc=tx*3+ty;next.data[cur.loc]=next.data[next.loc];next.data[next.loc]=0;next.status=Cantor(next.data);if(!vis[next.status]){vis[next.status]=true;next.path=next.path+indexs[i];if(next==goal){path=next.path;return true;}next.g++;//g值next.f=Fvalue(next,goal,1);//f值q.push(next);}}}return false;
}
int main()
{freopen("C:\\in.txt","r",stdin);char ch;//目的节点初始化startfor(int i=0;i<8;i++)goal.data[i]=i+1;goal.data[8]=0;goal.status=46234;//123456780对应的康拖展开的hash值//endwhile(cin>>ch){//起始节点初始化startif(ch=='x') {start.data[0]=0;start.loc=0;}else start.data[0]=ch-'0';for(int i=1;i<9;i++){cin>>ch;if(ch=='x'){start.data[i]=0;start.loc=i;}else start.data[i]=ch-'0';}start.status=Cantor(start.data);//康拖hash值start.g=0;start.f=Fvalue(start,goal,1);//计算f值//endif(Astar()){cout<<path<<endl;}else cout<<"unsolvable"<<endl;}return 0;
}
最后再提供一个IDA*版,比A*更简洁更快
/*
POJ 1077 Eight
C++
Memory 168K
Time 32MS
*/
#include <iostream>
#include <string>
using namespace std;const unsigned int M = 1001;
int dir[4][2] = {1, 0, // Down -1, 0, // Up 0,-1, // Left 0, 1 // Right
};
typedef struct STATUS{int data[3][3];int r,c;//0所在的位置
}STATUS;
char dirCode[] = {"dulr"};
char rDirCode[] = {"udrl"};
char path[M]; // 最优解
STATUS start, goal = { 1,2,3,4,5,6,7,8,0,2,2 }; // 起始和终止状态
int maxDepth = 0; // 深度边界//计算h值,作为IDAstar算法的评估函数
int dist(STATUS suc, STATUS goal, int k) {//计算方格的错位距离 int si,sj,gi,gj; //si,sj表示suc中k所处位置,gi,gj表示goal中k所处的位置for(int i=0;i<3;i++)for(int j=0;j<3;j++){if(suc.data[i][j]==k){si=i;sj=j;}if(goal.data[i][j]==k){gi=i;gj=j;}}return abs(si-gi) + abs(sj-gj);
}
int H(STATUS suc, STATUS goal) {//计算 h 值 int h = 0; for(int i = 1; i <= 8; i++) h = h + dist(suc, goal, i); return h;
}
//计算h值结束
//IDAstar算法开始bool dfs(STATUS cur,int depth,int h,char preDir){//IDA*估值函数剪枝//当前局面的估价函数值+当前的搜索深度 > 预定义的最大搜索深度时剪枝if(depth+h>maxDepth)return false;if(memcmp(&cur, &goal, sizeof(STATUS)) == 0 ) {path[depth] = '\0'; return true; } STATUS next;for(int i=0;i<4;++i){if(dirCode[i]==preDir)continue;//不能回到上一状态next=cur;next.r = cur.r + dir[i][0]; next.c = cur.c + dir[i][1]; if( !( next.r >= 0 && next.r < 3 && next.c >= 0 && next.c < 3 ) ) continue; swap(next.data[cur.r][cur.c], next.data[next.r][next.c]); //置换变成新的状态int nexth=H(next,goal);//重新计算h值path[depth] = dirCode[i]; if(dfs(next, depth + 1, nexth, rDirCode[i])) return true; }return false;
}
int IDAstar(){int h = H(start,goal); maxDepth = h; while (!dfs(start,0, h, '\0')) maxDepth++; return maxDepth;
}
//IDAstar算法结束
//是否可解
bool IsSolvable(const STATUS &cur)
{int i, j, k=0, s = 0;int a[9];for(i=0; i < 3; i++){for(j=0; j < 3; j++){if(cur.data[i][j]==0) continue;a[k++] = cur.data[i][j];}}for(i=0; i < 8; i++){for(j=i+1; j < 8; j++){if(a[j] < a[i])s++;}}return (s%2 == 0);
}
//初始状态赋值
void input(){char c;for(int i=0;i<3;i++){for(int j=0;j<3;j++){cin>>c;if(c=='x'){start.data[i][j]=0;start.r=i;start.c=j;}else start.data[i][j]=c-'0';}}
}
int main(){freopen("C:\\in.txt","r",stdin);input();if(IsSolvable(start)){IDAstar(); cout<<path<<endl; } else cout<<"unsolvable"<<endl; return 0;
}
这篇关于HDU 1043 ,POJ 1077 Eight的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!