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