Introduction
Rat in a maze problem，是用回溯法求解迷宫问题的经典例题。回溯法是一种优选的搜索法，根据择优的条件向前或向后搜索，最终获得目标。当向前搜索到某一步，根据目标函数得到的结果不是最优时，进行回溯，重新选择探索方向。由此得到最优解。
回溯法解决问题的基本步骤一般为：
- 根据给定问题，定义目标函数，并保证该问题至少有一个解
- 确定搜索的空间结构，确保回溯法可以遍历整个解空间
- 通过深度优先算法的形式，搜素整个解空间，并通过适当剪纸来减少冗余的搜索
回溯法的一个应用场景便是解决迷宫问题。
Requirement
In this problem you will solve the Rat in a maze problem, using Stacks and Queues (Lectures 12-14).
The main points we shall be covering are:
- Using Stacks and Queues in an application
- Re-enforcement of the usage and advantages of makefiles / make utility in UNIX/Linux
- Use of abstract data types in C++, and separate compilation
- Use of header files and libraries for Stacks and Queues
Analysis
本题需要采用Stack和Queue来解决迷宫问题。
栈用于存放回溯算法中的搜索路径，由于栈的后进先出特性，可以很容易的实现回溯。
队列用于存放已经搜索过的最优路径，由于队列的先进先出特性，可以很容易的进行目标函数的计算。
目标函数：从(0, 0)走到(N, N)的Taxicab geometry，也就是曼哈顿距离。Tips
题目搜给的迷宫为1
2
3
4
5
6
7
| 011101000100000
010001100111100
011001000000000
001000010111111
001011000010000
001000101010100
000010010000100
|
我们需要利用回溯法，从左上角走到右下角
下面给出程序的回溯搜索算法部分的代码
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
| static bool SearchEngine::DoMove(int movePosition) {
...
switch (movePosition) {
case MOVE_LEFT:
if (SearchEngine::TryMove(MOVE_LEFT) && SearchEngine::Search(MOVE_LEFT, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_UP) && SearchEngine::Search(MOVE_UP, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_DOWN) && SearchEngine::Search(MOVE_RIGHT, length - 1)) {
return false;
}
SearchEngine::DoMove(MOVE_RIGHT);
break;
case MOVE_UP:
if (SearchEngine::TryMove(MOVE_LEFT) && SearchEngine::Search(MOVE_LEFT, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_UP) && SearchEngine::Search(MOVE_UP, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_RIGHT) && SearchEngine::Search(MOVE_RIGHT, length - 1)) {
return false;
}
SearchEngine::DoMove(MOVE_DOWN);
break;
case MOVE_RIGHT:
if (SearchEngine::TryMove(MOVE_UP) && SearchEngine::Search(MOVE_UP, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_RIGHT) && SearchEngine::Search(MOVE_RIGHT, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_DOWN) && SearchEngine::Search(MOVE_RIGHT, length - 1)) {
return false;
}
SearchEngine::DoMove(MOVE_LEFT);
break;
case MOVE_DOWN:
if (SearchEngine::TryMove(MOVE_LEFT) && SearchEngine::Search(MOVE_LEFT, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_RIGHT) && SearchEngine::Search(MOVE_RIGHT, length - 1)) {
return false;
}
if (SearchEngine::TryMove(MOVE_DOWN) && SearchEngine::Search(MOVE_RIGHT, length - 1)) {
return false;
}
SearchEngine::DoMove(MOVE_UP);
break;
default:
break;
}
...
return true;
}
|
