C++代写：CS3530 Rat In A Maze Problem

发表于 | 分类于
Rat in a maze problem，是用回溯法求解迷宫问题的经典例题。回溯法是一种优选的搜索法，根据择优的条件向前或向后搜索，最终获得目标。

Introduction

Rat in a maze problem，是用回溯法求解迷宫问题的经典例题。回溯法是一种优选的搜索法，根据择优的条件向前或向后搜索，最终获得目标。当向前搜索到某一步，根据目标函数得到的结果不是最优时，进行回溯，重新选择探索方向。由此得到最优解。
回溯法解决问题的基本步骤一般为：

  1. 根据给定问题，定义目标函数，并保证该问题至少有一个解
  2. 确定搜索的空间结构，确保回溯法可以遍历整个解空间
  3. 通过深度优先算法的形式，搜素整个解空间，并通过适当剪纸来减少冗余的搜索

回溯法的一个应用场景便是解决迷宫问题。

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

  1. Re-enforcement of the usage and advantages of makefiles / make utility in UNIX/Linux
  2. Use of abstract data types in C++, and separate compilation
  3. 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;
}