机器博弈中的数据结构与基本方法（三）-----博弈树的搜索之九宫重排问题
九宫重排问题，如下图所示，九宫重排（或称八数码问题）是人工智能中一个经典问题，这里利用DFS解决这个问题。
通过设置一个OPEN表和一个CLOSE表记录尚未遍历和遍历过的状态，直至找到目标状态或遍历完所有状态，如果遍历完所有状态还木有找到目标状态则无解。
代码
1 #include <cstdio>
2 //利用深度优先搜索
3 //构造OPEN表和CLOSE表
4 typedef struct {
5 int State[5][5];
6 int FatherState[5][5];
7 }OPEN;
8 typedef struct {
9 int Order;
10 int State[5][5];
11 int FatherState[5][5];
12 }CLOSE;
13 OPEN OpenList[500000];
14 CLOSE CloseList[500000];
15 int OpenCount = -1, CloseCount = -1;
16 //判断位置是否合法的辅助数组
17 int Position[5][5] = {
18 {-1, -1, -1, -1, -1},
19 {-1, 1, 1, 1, -1},
20 {-1, 1, 1, 1, -1},
21 {-1, 1, 1, 1, -1},
22 {-1, -1, -1, -1, -1}
23 };
24 //将某一状态存入OPEN表
25 void Push(int a[][5], int b[][5]){
26 OpenCount++;
27 for (int i = 0; i < 5; i++){
28 for (int j = 0; j < 5; j++){
29 OpenList[OpenCount].State[i][j] = a[i][j];
30 OpenList[OpenCount].FatherState[i][j] = b[i][j];
31 }
32 }
33 }
34 //比较连个状态是否完全相同
35 int Compare(int a[][5], int b[][5]){
36 for (int i = 0; i < 5; i++){
37 for (int j = 0; j < 5; j++){
38 if (a[i][j] != b[i][j]){
39 return 0;
40 }
41 }
42 }
43 return 1;
44 }
45
46 void Move(int a[][5]){
47 int temp[5][5];
48 int i, j, m, n, flag1 = 0, flag2;
49 //找到0的位置
50 for (i = 0; i < 5; i++){
51 for (j = 0; j < 5; j++){
52 if (0 == a[i][j]){
53 flag1 = 1;
54 break;
55 }
56 }
57 if (flag1){
58 break;
59 }
60 }
61 //复制数组
62 for (m = 0; m < 5; m++){
63 for (n = 0; n < 5; n++){
64 temp[m][n] = a[m][n];
65 }
66 }
67 if (-1 != Position[i][j-1]){ //方向 1
68 a[i][j] = a[i][j-1];
69 a[i][j-1] = 0; //移动数字
70 flag2 = 0;
71 for (int k = 0; k <= OpenCount; k++){ //检查当前状态是否在OPEN表中
72 if (Compare(OpenList[k].State, a)){
73 flag2 = 1;
74 break;
75 }
76 }
77 if (!flag2){
78 for (int k = 0; k <= CloseCount; k++){//检查当前状态是否在CLOSE表中
79 if (Compare(CloseList[k].State, a)){
80 flag2 = 1;
81 break;
82 }
83 }
84 }
85 if (!flag2){ //若果都不在就加入OPEN表
86 Push(a, temp);
87 }
88 for (m = 0; m < 5; m++){ //复原数组a,做下一移动方向的判断
89 for (n = 0; n < 5; n++){
90 a[m][n] = temp[m][n];
91 }
92 }
93 }
94
95
96 if (-1 != Position[i][j+1]){ //方向 2
97 a[i][j] = a[i][j+1];
98 a[i][j+1] = 0; //移动数字
99 flag2 = 0;
100 for (int k = 0; k <= OpenCount; k++){
101 if (Compare(OpenList[k].State, a)){
102 flag2 = 1;
103 break;
104 }
105 }
106 if (!flag2){
107 for (int k = 0; k <= CloseCount; k++){
108 if (Compare(CloseList[k].State, a)){
109 flag2 = 1;
110 break;
111 }
112 }
113 }
114 if (!flag2){
115 Push(a, temp);
116 }
117 for (m = 0; m < 5; m++){
118 for (n = 0; n < 5; n++){
119 a[m][n] = temp[m][n];
120 }
121 }
122 }
123
124 if (-1 != Position[i+1][j]){ //方向 3
125 a[i][j] = a[i+1][j];
126 a[i+1][j] = 0; //移动数字
127 flag2 = 0;
128 for (int k = 0; k <= OpenCount; k++){
129 if (Compare(OpenList[k].State, a)){
130 flag2 = 1;
131 break;
132 }
133 }
134 if (!flag2){
135 for (int k = 0; k <= CloseCount; k++){
136 if (Compare(CloseList[k].State, a)){
137 flag2 = 1;
138 break;
139 }
140 }
141 }
142 if (!flag2){
143 Push(a, temp);
144 }
145 for (m = 0; m < 5; m++){
146 for (n = 0; n < 5; n++){
147 a[m][n] = temp[m][n];
148 }
149 }
150 }
151
152 if (-1 != Position[i-1][j]){ //方向 4
153 a[i][j] = a[i-1][j];
154 a[i-1][j] = 0; //移动数字
155 flag2 = 0;
156 for (int k = 0; k <= OpenCount; k++){
157 if (Compare(OpenList[k].State, a)){
158 flag2 = 1;
159 break;
160 }
161 }
162 if (!flag2){
163 for (int k = 0; k <= CloseCount; k++){
164 if (Compare(CloseList[k].State, a)){
165 flag2 = 1;
166 break;
167 }
168 }
169 }
170 if (!flag2){
171 Push(a, temp);
172 }
173 for (m = 0; m < 5; m++){
174 for (n = 0; n < 5; n++){
175 a[m][n] = temp[m][n];
176 }
177 }
178 }
179 }
180
181 //主函数
182 int main(int argc, char const *argv[])
183 {
184 //输出位置
185 freopen("ans.txt", "w", stdout);
186 //起始状态
187 int a[5][5], w[5][5]={
188 {-1, -1, -1, -1, -1},
189 {-1, 1, 3, 4, -1},
190 {-1, 8, 2, 5, -1},
191 {-1, 7, 0, 6, -1},
192 {-1, -1, -1, -1, -1}
193 };
194 //目标状态
195 int result[5][5] = {
196 {-1, -1, -1, -1, -1},
197 {-1, 1, 2, 3, -1},
198 {-1, 8, 0, 4, -1},
199 {-1, 7, 6, 5, -1},
200 {-1, -1, -1, -1, -1}
201 };
202
203 Push(w, w);
204 while (-1 != OpenCount){//OPEN表不为空
205 CloseCount++;
206 //每完成一次移动，该状态即可放入CLOSE表中
207 for (int i = 0; i < 5; i++){
208 for (int j = 0; j < 5; j++){
209 CloseList[CloseCount].State[i][j] = OpenList[OpenCount].State[i][j];
210 CloseList[CloseCount].FatherState[i][j] = OpenList[OpenCount].FatherState[i][j];
211 }
212 }
213 CloseList[CloseCount].Order = CloseCount;
214 //更新当前状态
215 for (int i = 0; i < 5; i++){
216 for (int j = 0; j < 5; j++){
217 a[i][j] = OpenList[OpenCount].State[i][j];
218 }
219 }
220 OpenCount--;
221 if (Compare(result, a)){ //如果达到了目标状态则技术循环
222 break;
223 } else {
224 Move(a); //继续移动
225 }
226 }
227 //输出到达目标状态的着法
228 for (int k = 0; k <= CloseCount; k++){
229 printf("No: %d\n", CloseList[k].Order);
230 printf(" Parent\t\tChild\n");
231 for (int i = 1; i < 4; i++){
232 for (int j = 1; j < 4; j++){
233 printf("%3d", CloseList[k].FatherState[i][j]);
234 }
235 printf("\t");
236 for (int j = 1; j < 4; j++){
237 printf("%3d", CloseList[k].State[i][j]);
238 }
239 printf("\n");
240 }
241 }
242 return 0;
243 }
View Code
结果
No: 0
Parent Child
1 3 4 1 3 4
8 2 5 8 2 5
7 0 6 7 0 6
No: 1
Parent Child
1 3 4 1 3 4
8 2 5 8 0 5
7 0 6 7 2 6
No: 2
Parent Child
1 3 4 1 0 4
8 0 5 8 3 5
7 2 6 7 2 6
No: 3
Parent Child
1 0 4 1 4 0
8 3 5 8 3 5
7 2 6 7 2 6
No: 4
Parent Child
1 4 0 1 4 5
8 3 5 8 3 0
7 2 6 7 2 6
No: 5
Parent Child
1 4 5 1 4 5
8 3 0 8 3 6
7 2 6 7 2 0
No: 6
Parent Child
1 4 5 1 4 5
8 3 6 8 3 6
7 2 0 7 0 2
No: 7
Parent Child
1 4 5 1 4 5
8 3 6 8 0 6
7 0 2 7 3 2
No: 8
Parent Child
1 4 5 1 0 5
8 0 6 8 4 6
7 3 2 7 3 2
No: 9
Parent Child
1 0 5 1 5 0
8 4 6 8 4 6
7 3 2 7 3 2
No: 10
Parent Child
1 5 0 1 5 6
8 4 6 8 4 0
7 3 2 7 3 2
No: 11
Parent Child
1 5 6 1 5 6
8 4 0 8 4 2
7 3 2 7 3 0
No: 12
Parent Child
1 5 6 1 5 6
8 4 2 8 4 2
7 3 0 7 0 3
No: 13
Parent Child
1 5 6 1 5 6
8 4 2 8 0 2
7 0 3 7 4 3
No: 14
Parent Child
1 5 6 1 0 6
8 0 2 8 5 2
7 4 3 7 4 3
No: 15
Parent Child
1 0 6 1 6 0
8 5 2 8 5 2
7 4 3 7 4 3
No: 16
Parent Child
1 6 0 1 6 2
8 5 2 8 5 0
7 4 3 7 4 3
No: 17
Parent Child
1 6 2 1 6 2
8 5 0 8 5 3
7 4 3 7 4 0
No: 18
Parent Child
1 6 2 1 6 2
8 5 3 8 5 3
7 4 0 7 0 4
No: 19
Parent Child
1 6 2 1 6 2
8 5 3 8 0 3
7 0 4 7 5 4
No: 20
Parent Child
1 6 2 1 0 2
8 0 3 8 6 3
7 5 4 7 5 4
No: 21
Parent Child
1 0 2 1 2 0
8 6 3 8 6 3
7 5 4 7 5 4
No: 22
Parent Child
1 2 0 1 2 3
8 6 3 8 6 0
7 5 4 7 5 4
No: 23
Parent Child
1 2 3 1 2 3
8 6 0 8 6 4
7 5 4 7 5 0
No: 24
Parent Child
1 2 3 1 2 3
8 6 4 8 6 4
7 5 0 7 0 5
No: 25
Parent Child
1 2 3 1 2 3
8 6 4 8 0 4
7 0 5 7 6 5
View Code
备注
这个八数码问题可以做成一个类似2048的游戏，不过挑战难度显然更高，不过现在GUI正在学习，恐怕要过一段时间才能做出demo。
本书最后一个是关于MAX-MIN启发式搜索，但是看的不是很明白，也从来没用过，等到以后需要再来略作研究。
