A*算法解决八数码问题_八数码问题a*搜索算法(c++)

A*算法核心

A*算法是启发式算法的一种，其核心部分在于估值函数的设计：f(n)=g(n)+h(n),其中f(n)是每个试探点的估值,h(n)为当前节点到目标节点地估值.算法主要流程如下:
首先将起始点s放入open表,将close表置空.
(1).如果OPEN表不为空，从表头取一个结点n，如果为空算法失败。
(2).判断n结点是否是目标点,如果是终止算法,否则继续搜索
(3).将n的所有后继结点展开，就是从n可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表，并把s放入CLOSE表，同时计算每一个后继结点的估价值f(n)，将OPEN表按f(x)排序，最小的放在表头，重复算法，回到(1)

八数码问题

八数码问题又称重排九宫问题，在一个 3*3 的棋盘上，随机放置 1 到 8 的数
字棋子，剩下一个空位，如图所示。数字可以移动到空位（编程时，空位可用 0
代替，且可以理解为是空位的上、下、左、右移动），经过若干次移动后，棋局
到达指定目标状态

解决思路: 可以将给g(n)设为从初始状态移动到当前状态地次数,h(n)设为当前状态与目标状态相异的格子数,利用优先队列按照f(n)的大小排列open表,则可利用 A * 算法搜索出移动次数最少的方案.
代码:

#include<stdio.h>   //f(n)=g(n)+h(n) 
#include<stdlib.h>
#include<iostream>
#include<cstring>
#include<queue>
#include<set>

#define TRUE      1
#define FALSE     0
#define OK        1
#define ERROR     0
#define OVERFLOW -1
using namespace std;

typedef int Status;
typedef int ElemType;
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//方向数组 

struct Matrix{ //矩阵结构体 
	int a[5][5];
	bool operator<(Matrix x)const{
		for(int i=1;i<=3;i++)
			for(int j=1;j<=3;j++)
				if(a[i][j]!=x.a[i][j]) return a[i][j]<x.a[i][j];
		return false;
	}
	
}st;//st为目标矩阵 

struct MatrixState{ //移动过程状态矩阵结构体
	Matrix m;
	int pos; //记录状态编号 
	int g; //到达此状态移动的步数
	int h; //与目标状态不同的格子数
	
	MatrixState(){}
	MatrixState(Matrix x,int p,int t){
		m=x;
		pos=p;
		g=t;
		h=0;
		for(int i=1;i<=3;i++){
			for(int j=1;j<=3;j++)
				if(x.a[i][j]!=st.a[i][j])
					h++;
		}
	}
	bool operator<(MatrixState x)const{
		return g+h>x.g+x.h; //按照g+h从小到大排列 
	}
}path[100005]; //path是用于存储移动过程中产生的状态结构体数组 
int pre[1000005];//pre数组用于存储每个状态的前一个状态的结构体编号 

void DefinMatrix(){
	//定义目标矩阵 
	st.a[1][1] = 1; 
	st.a[1][2] = 2;
	st.a[1][3] = 3;
	st.a[2][1] = 8;
	st.a[2][2] = 0;
	st.a[2][3] = 4;
	st.a[3][1] = 7;
	st.a[3][2] = 6;
	st.a[3][3] = 5;
}

void InputMatrix(Matrix &x){
	//输入初始状态矩阵 
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
			scanf("%d",&x.a[i][j]);
}

void PrintPath(int x){
	//输出路径
	if(x==1){
		for(int i=1;i<=3;i++){
			for(int j=1;j<=3;j++){
				printf("%d ",path[x].m.a[i][j]);
			}
			printf("\n");
		}
		printf("\n");
		return ;
	}
	PrintPath(pre[x]);
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			printf("%d ",path[x].m.a[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

int Calreorder(Matrix x){
	//计算矩阵x的一维排列的逆序值
	//若逆序值的奇偶性与目标状态不一致则无解 
	int Y=0,a[9];
	a[0]=x.a[1][1];
	a[1]=x.a[1][2];
	a[2]=x.a[1][3];
	a[3]=x.a[2][3];
	a[4]=x.a[3][3];
	a[5]=x.a[3][2];
	a[6]=x.a[3][1];
	a[7]=x.a[2][1];
	a[8]=x.a[2][2];
	for(int i=1;i<9;i++){
		if(a[i]!=0)
			for(int j=0;j<i;j++){
				if(a[j]>a[i])
					Y++;
			}
	}
	return Y;
}

bool Check(Matrix x){
	//检测输入是否合法
	int b[9]={0},c=0;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(x.a[i][j]>=0&&x.a[i][j]<9&&!b[x.a[i][j]]){
				c++;
				b[x.a[i][j]]++;
			}
		}
	}
	if(c==9)
		return true;
	return false;
}

bool JudgeSolution(Matrix x){
	//判断是否有解 
	if(!Check(x))
		return false;
	int Y;
	Y=Calreorder(x);
	//cout<<Y<<endl;
	if(Y%2==0)
		return true;
	return false;	
}

void AstarSearch(MatrixState M,int &step,int &cnt){
	//A*搜索 
	set<Matrix> s; //用于判断状态矩阵是否重复的集合 
	priority_queue<MatrixState> OPEN;
	OPEN.push(M);
	s.insert(M.m);
	path[1]=M;
	
	while(!OPEN.empty()){
		MatrixState F=OPEN.top();
		OPEN.pop();
		
		if(!F.h){
			step=F.g;
			while(path[cnt].h) cnt--;
			return ;
		}
		
		int fx=0,fy=0,p=F.pos;
		for(int i=1;i<=3;i++){
			for(int j=1;j<=3;j++)
				if(F.m.a[i][j]==0){
					fx=i;
					fy=j;
					break;
				}
			if(fx&&fy) break;
		}
		//cout<<fx<<" "<<fy<<endl;
		for(int i=0;i<4;i++){ //将0向四个方向移动 
			int nx=fx+dx[i],ny=fy+dy[i];
			
			if(nx>=1&&nx<=3&&ny>=1&&ny<=3){
				swap(F.m.a[fx][fy],F.m.a[nx][ny]);
				if(!s.count(F.m)){ //如果集合中没有此状态 
					//cout<<s.size()<<endl;
					s.insert(F.m);
					
					MatrixState mm(F.m,cnt+1,F.g+1);
					OPEN.push(mm);
					path[++cnt]=mm;
					pre[cnt]=p;
				}
				swap(F.m.a[fx][fy],F.m.a[nx][ny]);
			}
		}
	}
}

int main(){
	DefinMatrix();
	Matrix x;
	printf("请输入八数码初始状态：\n");
	InputMatrix(x);
	if(JudgeSolution(x)){
		MatrixState M(x,1,0);
		int steps,pa=1;
		AstarSearch(M,steps,pa);
		printf("所需步数:\n%d\n",steps);
		printf("\n移动过程:\n");
		PrintPath(pa);
	}
	else
		printf("此状态无解!\n"); 
	
	return 0;
}
/*
3 8 1
7 5 0
2 1 4

4 8 1
7 5 0
3 6 2

6 3 5
8 7 4
1 2 0

3 8 2
0 1 4
7 6 5

1 3 0
8 7 4
6 2 5

3 0 2
8 5 4
7 6 1

1 0 3
7 2 4
8 6 5

8 3 4
7 1 5
6 2 0

1 3 4
7 8 5
2 6 0

*/
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251