广度优先搜索和双向广度优先搜索求解Matrix67的迷宫问题的C语言实现





问题描述见 http://weibo.com/1915548291/z4eTPtAnv
简单来说,就是一个小迷宫。可以重复走,但是不能倒退。经过每条边都意味着执行一次运算,现在要2011从迷宫口进去,2012从迷宫口出来。
一个思想就是广度优先搜索,能够找到最短的路径。如果对每个状态标记祖先,就能回溯找到完整路径。自己实现了一个简单的Hash,因为最终步数并不多,所以对Hash的要求也不高。
之后又在广度优先搜索的基础上进行修改,实现了双向广度优先搜索。一个点从入口开始搜,一个点从出口开始搜。需要注意的是从出口开始搜的话,所有运算都是相反的。搜的时候会有两个队列,直到两边“碰头”为止。
测试结果中可以看到,双向广度优先搜索明显更快一些。
马上光棍节了,几个常量都定义的全是1,哈哈。

广度优先搜索版本代码下载:http://vdisk.weibo.com/s/hDMoa/1352453367

双向广度优先搜索版本代码下载:http://vdisk.weibo.com/s/hDMoB/1352453384

是在一个配置很低的VPS上测试的。具体测试环境为
gcc version 4.5.2 (Ubuntu/Linaro 4.5.2-8ubuntu4)
CPU:1995 MHz , Cache Size: 512 KB
Memory: 225280 KB

两份代码输出都是一样的,只贴一份了。结果是28步,这是因为只有偶数的时候,我才允许他走除以2的那条边。我假设奇数经过除以2以后会产生小数,容易证明这个小数不可能经过其他路径后被消掉。如果你认为奇数除以2之后的结果下取整也没关系,这个要求也很容易修改,不是什么本质问题。

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
2011 + 7 =
2018 / 2 =
1009 + 7 =
1016 / 2 =
508 + 7 =
515 - 5 =
510 * 3 =
1530 / 2 =
765 + 7 =
772 / 2 =
386 + 7 =
393 * 3 =
1179 - 5 =
1174 / 2 =
587 + 7 =
594 / 2 =
297 + 7 =
304 - 5 =
299 * 3 =
897 - 5 =
892 * 3 =
2676 / 2 =
1338 + 7 =
1345 - 5 =
1340 * 3 =
4020 / 2 =
2010 + 7 =
2017 - 5 =
2012

广度优先搜索代码

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
#include <stdio.h>
#include <memory.h>
#define HASH_SIZE  1111111
#define QUEUE_SIZE 1111111
#define BUF_SIZE 111
 
struct S {
    int pos;
    int value;
    int way;
    struct S *prev;
};
 
typedef struct S Status;
 
int from[] = {0, 2, 6, 8};
        //   {0, 0, 1, 1, 1, 1, 2, 2};
int to[]   = {1, 1, 0, 0, 2, 2, 1, 1};
int way[]  = {0, 1, 0, 1, 2, 3, 2, 3};
 
int equal (Status s1, Status s2) {
    return s1.pos == s2.pos && s1.value == s2.value && s1.way == s2.way;
}
 
int op(int val, int way_id) {
    switch(way_id) {
        case 0: return val + 7;
        case 1: return val % 2 == 0 ? val / 2 : val;
        case 2: return val * 3;
        case 3: return val - 5;
    }
    return val;
}
 
Status hash[HASH_SIZE];
Status *queue[QUEUE_SIZE];
 
int get_key(Status s) {
    int v = s.value * 12 + s.pos * 4 + s.way;
    if (v >= 0) return v % HASH_SIZE;
    else return v % HASH_SIZE + HASH_SIZE;
}
 
Status* insert_hash(Status s) {
    int key = get_key(s);
    while (hash[key].pos != -1 && !equal(hash[key], s)) {
        key++;
        key %= HASH_SIZE;
    }
 
    if (hash[key].pos == -1) {
        hash[key] = s;
        return &hash[key];
    }
 
    return NULL;
}
 
int check(Status now, Status t) {
    if (now.pos == t.pos && now.value == t.value) {
        int num_buf[BUF_SIZE];
        int way_buf[BUF_SIZE];
 
        int i, n = 0;
        way_buf[n] = -1;
        num_buf[n++] = now.value;
        way_buf[n] = now.way;
        now = *now.prev;
 
        while (now.prev != NULL) {
            num_buf[n++] = now.value;
            way_buf[n] = now.way;
            now = *now.prev;
        }
 
        num_buf[n++] = now.value;
 
        for (i = n - 1; i > 0; i--) {
            printf("%d", num_buf[i]);
            switch (way_buf[i]) {
                case 0 : printf(" + 7 = \n"); break;
                case 1 : printf(" / 2 = \n"); break;
                case 2 : printf(" * 3 = \n"); break;
                case 3 : printf(" - 5 = \n"); break;
            }
        }
        printf("%d\n", num_buf[i]);
 
        return 1;
    }
    return 0;
}
 
void BFS(Status s, Status t) {
    memset(hash, -1, sizeof(hash));
 
    Status *p_now =  insert_hash(s);
 
    queue[0] = p_now;
 
    int top = 0, rear = 1, i;
 
    while (top < rear) {
        p_now = queue[top++];
        Status next;
 
        for (i = from[p_now->pos]; i < from[p_now->pos + 1]; i++) {
            if (p_now->way != way[i]) {
                next.pos = to[i];
                next.value = op(p_now->value, way[i]);
                if (next.value == p_now->value) {
                    continue;
                }
                next.way = way[i];
                next.prev = p_now;
 
                if (1 == check(next, t)) {
                    break;
                }
 
                Status *result = insert_hash(next);
                if (result) {
                    queue[rear++] = result; 
                }
            }
        }
        if (i < from[p_now->pos + 1]) {
            break;
        }
    }
}
 
int main() {
    Status s, t;
    s.pos = 0; s.value = 2011; s.prev = NULL; s.way = -1;
    t.pos = 2; t.value = 2012;
 
    BFS(s, t);
 
    return 0;
}

测试结果:
real 0m0.061s
user 0m0.033s
sys 0m0.027s

双向广度优先搜索代码

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
#include <stdio.h>
#include <memory.h>
#define HASH_SIZE  1111111
#define QUEUE_SIZE 1111111
#define BUF_SIZE 111
 
struct S {
    int pos;
    int value;
    int way;
    int flag;
    struct S *prev;
};
 
typedef struct S Status;
 
int from[] = {0, 2, 6, 8};
        //   {0, 0, 1, 1, 1, 1, 2, 2};
int to[]   = {1, 1, 0, 0, 2, 2, 1, 1};
int way[]  = {0, 1, 0, 1, 2, 3, 2, 3};
 
int equal (Status s1, Status s2) {
    if (s1.pos == s2.pos && s1.value == s2.value) {
        return s1.flag == s2.flag && s1.way == s2.way
            || s1.flag != s2.flag && s1.way != s2.way;
    }
    return 0;
}
 
int op(int val, int way_id) {
    switch(way_id) {
        case 0: return val + 7;
        case 1: return val % 2 == 0 ? val / 2 : val;
        case 2: return val * 3;
        case 3: return val - 5;
    }
    return val;
}
 
int op_rev(int val, int way_id) {
    switch(way_id) {
        case 0: return val - 7;
        case 1: return val * 2;
        case 2: return val % 3 == 0 ? val / 3 : val;
        case 3: return val + 5;
    }
    return val;
}
 
Status hash[HASH_SIZE];
Status *queue1[QUEUE_SIZE];
Status *queue2[QUEUE_SIZE];
 
int get_key(Status s) {
    int v = s.value * 3 + s.pos;
    if (v >= 0) return v % HASH_SIZE;
    else return v % HASH_SIZE + HASH_SIZE;
}
 
Status* insert_hash(Status s, int *flag) {
    int key = get_key(s);
    while (hash[key].pos != -1 && !equal(hash[key], s)) {
        key++;
        key %= HASH_SIZE;
    }
 
    if (hash[key].pos == -1) {
        hash[key] = s;
        *flag = 1;
    }
    else {
        *flag = 0;
    }
    return &hash[key];
}
 
void output(Status now1, Status now2) {
    int num_buf[BUF_SIZE];
    int way_buf[BUF_SIZE];
 
    int i, n = 0;
    way_buf[n] = -1;
    num_buf[n++] = now1.value;
    way_buf[n] = now1.way;
    now1 = *now1.prev;
 
    while (now1.prev != NULL) {
        num_buf[n++] = now1.value;
        way_buf[n] = now1.way;
        now1 = *now1.prev;
    }
 
    num_buf[n++] = now1.value;
 
    for (i = n - 1; i > 0; i--) {
        printf("%d", num_buf[i]);
        switch (way_buf[i]) {
            case 0 : printf(" + 7 = \n"); break;
            case 1 : printf(" / 2 = \n"); break;
            case 2 : printf(" * 3 = \n"); break;
            case 3 : printf(" - 5 = \n"); break;
        }
    }
    printf("%d", num_buf[i]);
 
    while (now2.prev != NULL) {
        switch (now2.way) {
            case 0 : printf(" + 7 = \n"); break;
            case 1 : printf(" / 2 = \n"); break;
            case 2 : printf(" * 3 = \n"); break;
            case 3 : printf(" - 5 = \n"); break;
        }
        now2 = *now2.prev;
        printf("%d", now2.value);
    }
    printf("\n");
}
 
void BFS(Status s, Status t) {
    memset(hash, -1, sizeof(hash));
 
    Status *p_now, next;
    int top1 = 0, rear1 = 1, top2 = 0, rear2 = 1, i, k, flag;
 
    queue1[0] = insert_hash(s, &flag);
    queue2[0] = insert_hash(t, &flag); 
 
 
    while (top1 < rear1 || top2 < rear2) {
        int rear = rear1;
        next.flag = 0;
        for (k = top1; k < rear; k++) {
            p_now = queue1[k];
            for (i = from[p_now->pos]; i < from[p_now->pos + 1]; i++) {
                if (p_now->way != way[i]) {
                    next.pos = to[i];
                    next.value = op(p_now->value, way[i]);
                    if (next.value == p_now->value) {
                        continue;
                    }
                    next.way = way[i];
                    next.prev = p_now;
 
                    Status *result = insert_hash(next, &flag);
                    if (result->flag != next.flag) {
                        output(next, *result);
                        break;
                    }
                    if (flag) {
                        queue1[rear1++] = result; 
                    }
                }
            }
            if (i < from[p_now->pos + 1]) {
                break;
            }
        }
        if (k < rear) {
            break;
        }
        top1 = rear;
 
        rear = rear2;
        next.flag = 1;
        for (k = top2; k < rear; k++) {
            p_now = queue2[k];
            for (i = from[p_now->pos]; i < from[p_now->pos + 1]; i++) {
                if (p_now->way != way[i]) {
                    next.pos = to[i];
                    next.value = op_rev(p_now->value, way[i]);
                    if (next.value == p_now->value) {
                        continue;
                    }
                    next.way = way[i];
                    next.prev = p_now;
 
                    Status *result = insert_hash(next, &flag);
                    if (result->flag != next.flag) {
                        output(*result, next);
                        break;
                    }
                    if (flag) {
                        queue2[rear2++] = result; 
                    }
                }
            }
            if (i < from[p_now->pos + 1]) {
                break;
            }
        }
        if (k < rear) {
            break;
        }
        top2 = rear;
 
    }
}
 
int main() {
    Status s, t;
    s.pos = 0; s.value = 2011; s.prev = NULL; s.way = -1;
    t.pos = 2; t.value = 2012; t.prev = NULL; t.way = -1;
 
    BFS(s, t);
 
    return 0;
}

测试结果:
real 0m0.040s
user 0m0.013s
sys 0m0.027s

如果你喜欢我的博客,请订阅本博客的RSS以更方便的阅读
欢迎关注我的新浪微博:http://weibo.com/diaorui1987