学习笔记--八数码问题

学习笔记—八数码问题

先看道题目

https://www.luogu.org/problemnew/show/P1379

分析

经典的八数码问题,有双向BFS和$IDA$ 的方法，这里使用的是$A$ 启发式搜索.

简要介绍一下$A$ ,就是对于搜索的每一个状态设计一个评估函数$f(state)$,表示当前状态$state$到目标状态所需代价的估计值;还有一个$g(state)$,表示当前状态$state$到目标状态实际需要的最小代价,$A$ 中必须保证$f(state)<=g(state)$才能确保在目标状态第一次被取出时就是最优解（实际一点,比如最少的步数）并且在搜索中每个状态只需扩展一次，设计的估价函数$f(stste)$越接近$g(state)$效率越高.

我们这里用曼哈顿距离设计估价函数，也就是$f(state)=\sum^9_{i=1} (|posx_i-goalx_i|+|posy_i-goaly_i|) $

$posx_i$表示$i$这个数字在九宫格中的横坐标,$posy_i$也就类似的。注意,我们不能统计$0$，否则这样$f(state)$可能会大于实际代价

为了确保每个状态都被拓展一次，我们可以采用康托展开(将$1-n$的全排列映射成$1-n!$中的一个数)或是哈希表(unordered_map/pb_ds::gp_hash_table/map)

同时还要注意,八数码问题有时候是没有解的,我们将九宫格除空格之外的数按从左到右,再从上到下的顺序排成一列数来表示每一个状态，如果初始状态和目标状态的逆序对个数奇偶性不同的话是无解的,可以提前判断一下是否有解来提高效率

题目:

P1379 八数码难题

题目链接：https://www.luogu.org/problemnew/show/P1379

非常简单,甚至不用判断无解

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <utility>
#include <cmath>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define ll long long 
#define ri register int 
#define ull unsigned long long 
using std::pair;
using std::swap;
using std::abs;
using std::priority_queue;
using namespace __gnu_pbds;
template <class T>inline void read(T &x){
	x=0;int ne=0;char c;
	while(!isdigit(c=getchar()))ne=c=='-';
	x=c-48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
	x=ne?-x:x;return ;
}
const int maxn=5;
const int inf=0x7fffffff;
const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
int sta[maxn][maxn];
ll st,goal;
gp_hash_table <ll,bool>g;
pair<int,int>pos[10];
struct Sta{
	ll a;
	int s,f;
	Sta(){;}
	Sta(ll _a,int _s,int _f){a=_a,s=_s,f=_f;}
	bool operator <(const Sta &b)const{
		return f>b.f;
	}
};
int bx,by;//0位置 
inline int get_f(){//估价函数
	int ans=0;
	for(ri i=1;i<=3;i++){
		for(ri j=1;j<=3;j++){
			ans+=abs(i-pos[sta[i][j]].first)+abs(j-pos[sta[i][j]].second);
		}
	}
	return ans;
}
inline ll turn_num(){//转为数字
	ll ans=0;
	for(ri i=1;i<=3;i++){
		for(ri j=1;j<=3;j++){
			ans=ans*10+sta[i][j];
		}
	}
	return ans;
}
inline void turn_sta(ll num){//转为九宫格
	for(ri i=3;i>=1;i--){
		for(ri j=3;j>=1;j--){
			sta[i][j]=num%10;
			num=num/10;
			if(!sta[i][j])bx=i,by=j;
		}
	}
	return ;
}
inline void astar(){
	ll now,nxt;
	int x,y,z;
	Sta tmp;
	priority_queue<Sta>q;
	while(q.size())q.pop();
	turn_sta(st);
	q.push(Sta(st,0,get_f()));	
	g[st]=1;
	while(q.size()){
		tmp=q.top();q.pop();
		now=tmp.a,z=tmp.s;
		if(now==goal){
			printf("%d\n",z);
			return ;
		}
		turn_sta(now);
		for(ri i=0;i<4;i++){
			x=bx+dx[i],y=by+dy[i];
			if(x>=1&&x<=3&&y>=1&&y<=3){
				swap(sta[bx][by],sta[x][y]);
				nxt=turn_num();
				if(g[nxt]){
					swap(sta[bx][by],sta[x][y]);
					continue;
				}
				g[nxt]=1;
				q.push(Sta(nxt,z+1,z+1+get_f()));
				swap(sta[bx][by],sta[x][y]);
			}
		}
	}
	puts("unsolvable");
	return ;
}
int main(){
	/*230187546*/
	int x,y,z;
	pos[0].first=2,pos[0].second=2;
	pos[1].first=1,pos[1].second=1;
	pos[2].first=1,pos[2].second=2;
	pos[3].first=1,pos[3].second=3;
	pos[4].first=2,pos[4].second=3;
	pos[5].first=3,pos[5].second=3;
	pos[6].first=3,pos[6].second=2;
	pos[7].first=3,pos[7].second=1;
	pos[8].first=2,pos[8].second=1;
	read(st);
	goal=123804765;
	astar();
	return 0;
}

POJ1077 Eight

题目链接:http://poj.org/problem?id=1077

要打印方案,我用了一个$naive$的方法,就是记录每个状态是从哪个状态转移过来的($A*$保证扩展到每一个状态时一定是花费最少的步数)，同时再用一个哈希表记录它是进行哪个操作转移过来的，最后递归打印即可

当然还有其他方法这里不赘述.由于POJ好像不资瓷pbds和unordered_map,只好用map

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <utility>
#include <cmath>
#include <map> 
#define ll long long 
#define ri register int 
#define ull unsigned long long 
using namespace std;
template <class T>inline void read(T &x){
	x=0;int ne=0;char c;
	while(!isdigit(c=getchar()))ne=c=='-';
	x=c-48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
	x=ne?-x:x;return ;
}
const int maxn=5;
const int inf=0x7fffffff;
const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
const char ch[4]={'u','l','r','d'};
int sta[maxn][maxn];
ll st,goal;
map <ll,ll> pre;
map <ll,int> dir;
pair<int,int>pos[10];
struct Sta{
	ll a;
	int s,f;
	Sta(){;}
	Sta(ll _a,int _s,int _f){a=_a,s=_s,f=_f;}
	bool operator <(const Sta &b)const{
		return f>b.f;
	}
};
int bx,by;//0位置 
inline int get_f(){
	int ans=0;
	for(ri i=1;i<=3;i++){
		for(ri j=1;j<=3;j++){
			if(sta[i][j]==0)continue;
			ans+=abs(i-pos[sta[i][j]].first)+abs(j-pos[sta[i][j]].second);
		}
	}
	return ans;
}
inline ll turn_num(){
	ll ans=0;
	for(ri i=1;i<=3;i++){
		for(ri j=1;j<=3;j++){
			ans=ans*10+sta[i][j];
		}
	}
	return ans;
}
inline void turn_sta(ll num){
	for(ri i=3;i>=1;i--){
		for(ri j=3;j>=1;j--){
			sta[i][j]=num%10;
			num=num/10;
			if(!sta[i][j])bx=i,by=j;
		}
	}
	return ;
}
void print(ll x){
    /*234150768*/
	if(x==st)return ;	
	print(pre[x]);
	putchar(ch[dir[x]]);
	return ;
}
inline void astar(){
	ll now,nxt;
	int x,y,z;
	Sta tmp;
	priority_queue<Sta>q;
	while(q.size())q.pop();//puts("wtf");
	turn_sta(st);
	q.push(Sta(st,0,get_f()));	
	while(q.size()){
		tmp=q.top();q.pop();
		now=tmp.a,z=tmp.s;
		if(now==goal){
			//printf("%d\n",z);
			//printf("%lld***\n***",pre[st]);
			print(goal);
			return ;
		}
		//printf("*%lld\n",now);
		turn_sta(now);
		for(ri i=0;i<4;i++){
			x=bx+dx[i],y=by+dy[i];
			if(x>=1&&x<=3&&y>=1&&y<=3){
				swap(sta[bx][by],sta[x][y]);
				nxt=turn_num();
				if(!pre[nxt]){
					pre[nxt]=now;
					dir[nxt]=i;
					q.push(Sta(nxt,z+1,z+1+get_f()));
				}
				swap(sta[bx][by],sta[x][y]);
			}
		}
	}
	puts("unsolvable");
	return ;
}
int main(){
	int num[10];
	char x[2];
	pos[0].first=3,pos[0].second=3;
	pos[1].first=1,pos[1].second=1;
	pos[2].first=1,pos[2].second=2;
	pos[3].first=1,pos[3].second=3;
	pos[4].first=2,pos[4].second=1;
	pos[5].first=2,pos[5].second=2;
	pos[6].first=2,pos[6].second=3;
	pos[7].first=3,pos[7].second=1;
	pos[8].first=3,pos[8].second=2;
	//read(st);
	st=0;
	for(ri i=1;i<=9;i++){
		scanf("%s",x);
		if(x[0]=='x')st=st*10,num[i]=inf;
		else st=st*10+x[0]-'0',num[i]=x[0]-'0';
	}
	//printf("%lld\n",st);
	int cnt=0;
	for(ri i=1;i<=9;i++){
		if(num[i]==inf)continue;
		for(ri j=i+1;j<=9;j++){
			if(num[j]<num[i]){cnt++;}
		}
	}
	//printf("%d\n",cnt);
	if(cnt%2==1){
		puts("unsolvable");
	}
	else{
		pre[st]=19260817;
		goal=123456780;
		astar();
	}
	return 0;
}

UVA652 Eight

题目链接: https://cn.vjudge.net/problem/UVA-652

这道题由于多组数据发现各个$A*$好像不太行,于是就先一遍BFS扩展出所有状态同时记录路径,这一次没用哈希表用了康拓展开，然而不知道为何WA掉了。。。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <utility>
#include <iostream>
#define ll long long 
#define ri register int 
#define ull unsigned long long 
using namespace std;
template <class T>inline void read(T &x){
	x=0;int ne=0;char c;
	while(!isdigit(c=getchar()))ne=c=='-';
	x=c-48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
	x=ne?-x:x;return ;
}
const int maxn=5;
const int inf=0x7fffffff;
const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
const char ch[4]={'u','l','r','d'};
const int fac[10]={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int sta[maxn][maxn];
ll st,goal;
struct Sta{
	ll a;int v;
	Sta(){;}
	Sta(ll _a,int _v){a=_a,v=_v;}
};
int bx,by;//0位置 
int num[10],len[500005];
char path[500005][75];
inline ll turn_num(){
	ll ans=0;
	for(ri i=1;i<=3;i++){
		for(ri j=1;j<=3;j++){
			ans=ans*10+sta[i][j];
			num[(i-1)*3+j]=sta[i][j];
		}
	}
	return ans;
}
inline int cal_cantor(){
	int sml=0,x=0;
	for(ri i=1;i<=9;i++){
		sml=0;
		for(ri j=i+1;j<=9;j++){
			if(num[j]<num[i])++sml;
		}
		x+=fac[9-i]*sml;
	}
	return x+1;
} 
inline void turn_sta(ll p){
	for(ri i=3;i>=1;i--){
		for(ri j=3;j>=1;j--){
			sta[i][j]=p%10;
			p=p/10;
			if(sta[i][j]==9)bx=i,by=j;
		}
	}
	return ;
}
bool vis[500005];
inline void bfs(){
	ll now,nxt;
	int x,y,z,pre_val,val;
	Sta tmp;
	queue<Sta>q;
	while(q.size())q.pop();//puts("wtf");	
	turn_sta(goal);
	z=turn_num();
	val=cal_cantor();
	vis[val]=1;
	q.push(Sta(goal,val));	
	while(q.size()){
		tmp=q.front();q.pop();
		now=tmp.a,pre_val=tmp.v;
		turn_sta(now);
		for(ri k=0;k<4;k++){
			x=bx+dx[k],y=by+dy[k];
			if(x>=1&&x<=3&&y>=1&&y<=3){
				swap(sta[bx][by],sta[x][y]);
				nxt=turn_num();
				val=cal_cantor();				
				//printf("%d %d %lld %d %d\n",x,y,nxt,val,pre_val);
				if(!vis[val]){
					vis[val]=1;
					for(ri i=1;i<=len[pre_val];i++){
						path[val][i]=path[pre_val][i];
					}
					len[val]=len[pre_val];
					path[val][++len[val]]=ch[k];
					q.push(Sta(nxt,val));
				}
				swap(sta[bx][by],sta[x][y]);
			}
		}
	}
	return ;
}
int main(){
	/*234150768*/
	/*123456780*/
	/*
	2	
	2 3 4 1 5 x 7 6 8	
	2 3 4 1 5 x 7 6 8
	*/
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int t,val;
	char kkk;
	read(t);
	goal=123456789;
	memset(vis,0,sizeof(vis));
	bfs();
	while(t--){
		st=0;
		for(ri i=1;i<=9;i++){
			cin>>kkk;//scanf("%s",x);
			if(kkk=='x')st=st*10,num[i]=9;
			else st=st*10+kkk-'0',num[i]=kkk-'0';
		}
		val=cal_cantor();
		//printf("%d %d\n",val,len[val]);
		if(!vis[val]){
			puts("unsolvable");
		}
		else{
			for(ri i=len[val];i>=1;i--)putchar(path[val][i]);
			puts("");
		}
		if(t)puts("");
	}
	return 0;
}