|
|
楼主 |
发表于 2007-12-23 01:06:42
|
显示全部楼层
原来我的PC机也不慢啊。
在修改了程序错误之后，我把昨天的程序在我的PC机上运行了一下，完成全部搜索，该算法总共走了141,390,059步（包括试探），用时332秒。
修改后的新算法（老程序改了几个数字，加了几个限制），完成全部搜索，总共走了12864步，用时0.013秒。
我先是手算，确定了计算方法，发现可能的解很多，便开了一个数组t(k,i,j)，i是行号，j是列号，存放的数据是红心的朝向，
未走过=0，朝东=1，朝西=2，朝北=3，朝南=4，朝上=5，朝下=6。
这个数组其实是个堆栈，因为在手算的时候我就注意到，每走出一步，就会多出几个可能性，每一种还未验证过的可能性都被压入堆栈，堆栈指针为n。
24-27行描述了一个开始，堆栈指针n=0，红心朝上。
这里出现了一个数组u，它是用来记录这一步是从哪个方向走来的，从东面=1，从西面=2，从北面=3，从南面=4。
由于这个题目是上下对称的，若它有一个非对称解，那么必然就有一个镜像，即必有偶数个解。因为磁铁版主说了，解唯一，所以解必然不是非对称的。于是，我们就只要考虑上面一半区域里的走法。
接下去就是从寒武此刻所在位置向东南西北4个方向试探。
32行的mp是此刻红心的朝向。试探时调用了一个子程序position(mp, dir)，用来得到翻动之后红心的朝向，其实就是一张表，
mp=1 6, 5, 1, 1, 原红心向东，向东、西、北、南翻动后的朝向分别为 下、上、东、东
mp=2 5, 6, 2, 2, 原红心向西，向东、西、北、南翻动后的朝向分别为 上、下、西、西
mp=3 3, 3, 6, 5, 原红心向北，向东、西、北、南翻动后的朝向分别为 北、北、下、上
mp=4 4, 4, 5, 6, 原红心向南，向东、西、北、南翻动后的朝向分别为 南、南、上、下
mp=5 1, 2, 3, 4, 原红心向上，向东、西、北、南翻动后的朝向分别为 东、西、北、南
mp=6 2, 1, 4, 3, 原红心向下，向东、西、北、南翻动后的朝向分别为 西、东、南、北
先设定试探行动的指针，n_new=n
向东试探，36行计算的mp_new就是向东翻动后红心的朝向，试探成功的条件是：
37行：
if (tj[ n] < 7) 不在右边界上；
if (!t[ n][ ti[ n]][ tj[ n] + 1]) 右边的格子没走过；
if (mp_new != 5) 红心不朝上
如果成功，39-48行就把堆栈指针n_new增加，把它送入第n_new层堆栈保存起来，寒武在这次试探中此时所处的位置则记录在ti[n_new]和tj[n_new]中。如果不成功则什么也不做。
然后向西试探，试探成功的条件是53行：
if (tj[ n]) 不在左边界上；
if (ti[ n]) 不在第1行（如果在第1行，向西走是进入死区）；
if (!t[ n][ ti[ n]][ tj[ n] - 1]) 左边的格子没走过；
if (mp_new != 5) 红心不朝上
然后向北试探，试探成功的条件是69行：
if (ti[ n]) 不在上边界上；
if (tj[ n] < 7) 不在最右边一列（如果在最右边，向上走是进入死区）；
if (tj[ n]) 不在最左边一列（如果在最左边，向上走是进入死区）；
if (!t[ n][ ti[ n] - 1][ tj[ n]]) 上边的格子没走过；
if (mp_new != 5) 红心不朝上
然后向南试探，试探成功的条件是85行：
if (ti[ n] < 3) 不在下边界上；
if (!t[ n][ ti[ n] + 1][ tj[ n]]) 下边的格子没走过；
if (mp_new != 5) 红心不朝上
现在，四个方向都试探过了。如果有路可走，就有 n_new>n，那几条路也已送入堆栈，寒武不必留在原地，所以，102-109行把原来在堆栈n中的内容去除，寒武则到堆栈最上层的那个位置，开始新的探索（109、115行）。
如果四个方向的试探都失败了（n_new=n），先检查，是不是每个空格都走过了（118行），如果还有空格，说明刚才寒武所在位置n是条死胡同，放弃它，把指针往下移一下（120行），站到下面一层所记录的位置上（121行）。如果n<0，说明所有可能性都已试过了，结束计算（122行）。
如果四个方向的试探都失败了，并且每个空格都走过了，那么，这条路就走到头了，我们只要看看这条路的尽头是不是寒武要去的地方就可以了。
124行： if (ti[ n] == 3) 在下边界上
既然路的尽头在下边界上，那么，只要寒武按照刚才的路径向下镜像复制下去，就可以找到公主了。
126-133行只是把记录每一步是从哪个方向来的，改为要向哪个方向走，便于根据输出结果绘图。
以下是新算法的完整的程序。
1 #include <ansi_c.h>
2 #include <math.h>
3 #include <stdio.h>
4 #include <stdlib.h>
5
6 // free=0, e=1, w=2, n=3, s=4, t=5, b=6
7 // move e(right)=1, w(left)=2, n(up)=3, s(down)=4
8
9 int position(int mp, int direction)
10 {
11 short int n[ 6][ 4] = {6, 5, 1, 1, 5, 6, 2, 2, 3, 3, 6, 5, 4, 4, 5, 6, 1, 2, 3, 4, 2, 1, 4, 3};
12 return n[ mp - 1][ direction - 1];
13 }
14
15 #define MM 1000
16 short int t[ MM][ 4][ 8], u[ MM][ 4][ 8], v[ 4][ 8], ti[ MM], tj[ MM];
17
18 int main (void)
19 {
20 int i, j, k, n, nn, ss, n_new, mp, mp_new;
21
22 ss = time(0);
23 nn = 0;
24 n = 0;
25 ti[ n] = tj[ n] = 0;
26 for (i = 0; i < 4; i++) for (j = 0; j < 8; j++) t[ 0][ i][ j] = u[ 0][ i][ j] = 0;
27 t[ 0][ 0][ 0] = 5;
28
29 L_0:
30 nn++;
31 n_new = n;
32 mp = t[ n][ ti[ n]][ tj[ n]];
33 // printf("%d\n", mp);
34
35 // right
36 mp_new = position(mp, 1);
37 if (tj[ n] < 7) if (!t[ n][ ti[ n]][ tj[ n] + 1]) if (mp_new != 5)
38 {
39 n_new++;
40 for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
41 {
42 t[ n_new][ i][ j] = t[ n][ i][ j];
43 u[ n_new][ i][ j] = u[ n][ i][ j];
44 }
45 ti[ n_new] = ti[ n];
46 tj[ n_new] = tj[ n] + 1;
47 t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
48 u[ n_new][ ti[ n_new]][ tj[ n_new]] = 1;
49 }
50
51 // left
52 mp_new = position(mp, 2);
53 if (tj[ n]) if (ti[ n]) if (!t[ n][ ti[ n]][ tj[ n] - 1]) if (mp_new != 5)
54 {
55 n_new++;
56 for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
57 {
58 t[ n_new][ i][ j] = t[ n][ i][ j];
59 u[ n_new][ i][ j] = u[ n][ i][ j];
60 }
61 ti[ n_new] = ti[ n];
62 tj[ n_new] = tj[ n] - 1;
63 t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
64 u[ n_new][ ti[ n_new]][ tj[ n_new]] = 2;
65 }
66
67 // upword
68 mp_new = position(mp, 3);
69 if (ti[ n]) if (tj[ n] < 7) if (tj[ n]) if (!t[ n][ ti[ n] - 1][ tj[ n]]) if (mp_new != 5)
70 {
71 n_new++;
72 for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
73 {
74 t[ n_new][ i][ j] = t[ n][ i][ j];
75 u[ n_new][ i][ j] = u[ n][ i][ j];
76 }
77 ti[ n_new] = ti[ n] - 1;
78 tj[ n_new] = tj[ n];
79 t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
80 u[ n_new][ ti[ n_new]][ tj[ n_new]] = 3;
81 }
82
83 // downword
84 mp_new = position(mp, 4);
85 if (ti[ n] < 3) if (!t[ n][ ti[ n] + 1][ tj[ n]]) if (mp_new != 5)
86 {
87 n_new++;
88 for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
89 {
90 t[ n_new][ i][ j] = t[ n][ i][ j];
91 u[ n_new][ i][ j] = u[ n][ i][ j];
92 }
93 ti[ n_new] = ti[ n] + 1;
94 tj[ n_new] = tj[ n];
95 t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
96 u[ n_new][ ti[ n_new]][ tj[ n_new]] = 4;
97 }
98 // printf("nn=%d, n=%d\n", nn, n);
99
100 if (n_new > n)
101 {
102 for (k = n; k < n_new; k++) for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
103 {
104 t[ k][ i][ j] = t[ k + 1][ i][ j];
105 u[ k][ i][ j] = u[ k + 1][ i][ j];
106 ti[ k] = ti[ k + 1];
107 tj[ k] = tj[ k + 1];
108 }
109 n = n_new - 1;
110 if (n > MM - 4)
111 {
112 printf("not finifshed\n");
113 goto L_end;
114 }
115 goto L_0;
116 }
117
118 for (i = 0; i < 4; i++) for (j = 0; j < 8; j++) if (!t[ n][ i][ j])
119 {
120 n--;
121 if (n >= 0) goto L_0; // if (n) goto L_0;
122 else goto L_end;
123 }
124 if (ti[ n] == 3)
125 {
126 for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
127 {
128 if (u[ n][ i][ j] == 1) v[ i][ j - 1] = 1;
129 else if (u[ n][ i][ j] == 2) v[ i][ j + 1] = 2;
130 else if (u[ n][ i][ j] == 3) v[ i + 1][ j] = 3;
131 else if (u[ n][ i][ j] == 4) v[ i - 1][ j] = 4;
132 }
133 v[ ti[ n]][ tj[ n]] = 0;
134
135 for (i = 0; i < 4; i++)
136 {
137 for (j = 0; j < 8; j++) printf("%d-%d ", t[ n][ i][ j], v[ i][ j]);
138 printf("\n");
139 }
140 printf("\n");
141 }
142 n--;
143 if (n >= 0) goto L_0; // if (n) goto L_0;
144 L_end:
145 printf("nn=%d, time=%ds\n", nn, time(0)-ss);
146 scanf("%d", &i);
147 return 0;
148 } |
|
楼主: 944f4fe875fb39d
发表于 2007-12-22 17:00:14
发表于 2007-12-22 19:35:05
