摘要：在这篇论文中，主要研究了两大问题，第一个问题是如何用计算机创造尽量复杂的迷宫，一般常用的方法是随机prim，随机dfs，递归分割，本文分别实现了这三种算法的功能和具体代码，并对它们进行了比较，得出随机prim算法生成的迷宫有更大的复杂度与迷惑性。本文接下来又对随机prim算法探索了两种优化路线，一种是用枚举筛选法处理随机prim来得到更复杂更完美的迷宫，另一种是针对随机prim没有环的缺点进行了算法改进，最终得到有环迷宫，本文对这两种方法进行了介绍和分析。第二个问题是探索传统迷宫的求解方法，本文对BFS,记忆化搜索，循环队列SPFA这三种传统迷宫求解的方法进行了比较，最终得出循环队列SPFA方法是最优最可靠的结论。

【关键词】迷宫；递归分割；随机Prim；DFS

目录

摘要

Abstract

1 绪言-1

1.1 引言-1

1.2研究背景-1

1.3存在的问题-2

2相关算法与工具-3

2.1设计与解决迷宫的一般方法-3

2.1.1设计迷宫-3

2.1.2走出迷宫-4

2.2相关的工具-4

3各种构造迷宫方法的研究-5

3.1深度优先构建迷宫-5

3.2随机Prim构建迷宫-6

3.3递归分割构建迷宫-8

3.4随机prim的改进-13

3.4.1随机prim的改进（枚举迷宫）-13

3.4.2随机prim的改进（环型迷宫）-16

3.4.3 两种方法的比较-19

3.5生成迷宫方面的总结与未来设想-19

4各种解决迷宫方法的研究-20

4.1 BFS搜索-20

4.2记忆化搜索-21

4.3 SPFA求最短路-21

4.3.1 SPFA算法的介绍-21

4.3.2 SPFA的定理-21

5总结-22

参考文献-22

致    谢-25