一、关于随机迷宫生成

1.我们将迷宫定义如下：迷宫由道路和墙组成，且迷宫中道路上的任意两点应互相可达
2.随机迷宫生成算法一般有以下三种，这里只介绍随机prim算法

• 随机prim算法
• 深度优先（递归回溯）算法
• 递归分割（分治）算法

二、prim算法

1、最小生成树

1. 最小生成树:在带权图G=( V,E )中（V为点集，E为边集且每条边带有权值），我们希望找到E的一个无环子集T，使得V中任意两点可达。由于T无环且联通所有点，可知T必为一颗树，称这种边子集T为生成树，称所有满足条件的T中权值和最小的为最小生成树。
2. 举例来说，我们绘制一块pcb电路板，需要把n个针脚布线连接在一起，并希望连线长度总和最小。这里n个针脚即为点集，任意两针脚间的所有可能连线组成这个pcb图的边集，而连线的长度可看做该线的权值。任意一个连接所有针脚且不产生连线回环的连法都是此pcb图的一个生成树，所有生成树中用线长度最短的即为最小生成树.

2、prim算法简介

1. prim是求给定若干点间最小生成树的经典算法。另一种此问题的经典算法是kruskal算法
2. prim算法使用的是贪心策略，其正确性可以证明。
3. 算法流程如下：

• 从边集E中随机选取一点加入集合A
• 考察和A相邻的所有边，找其中权值最小的一条加入A (也就是说A一直是一棵树)
• 当A中包含V中所有点时，算法结束，A为一棵最小生成树

3、正确性证明

1. 使用 循环不变式 来证明算法正确性，关于循环不变式可以参考：循环不变式的思想及其应用
2. prim算法要管理的集合A遵循以下循环不变式：在每遍循环前，A是某最小生成树的一个子集。也就是说，我们要在每一步循环找到一个边（u,v），使得 A∪{（u,v）}也是某最小生成树的子集，我们可以定义满足这个要求的边为安全边
3. 按以下方式使用循环不变式证明正确性

1   A=∅
2   while A不是最小生成树
3		找到安全边（u,v）
4		A=A∪{(u,v)}
5   return A

初始化：在第一行后，A直接满足循环不变式
保持：算法第2~4行一直加入安全边，不会破坏循环不变式
终止：所有加入A的边都属于某最小生成树，则第5行返回的A一定是一个最小生成树

4. 上述策略的重点在于第3行，如何找到一条安全边。（这条安全边是必然存在的，因为循环不变式告诉我们一定存在一个最小生成树T满足A∈T，2~4行时A是T的真子集，一定有边（u,v）∈ T && （u,v）∉ A，此边即为安全边）
5. 为了辨别安全边，先证明以下定理：

• 定理：G=（V,E）是带权联通无向图。设A为E的一个子集，且A属于G的某最小生成树，设（S,V-S）是G中尊重A的任意一个切割，（u,v）是横跨此切割的一条轻量级边。那么（u,v）是A的一条安全边。G=（V,E）是带权联通无向图。设A为E的一个子集，且A属于G的某最小生成树，设（S,V-S）是G中尊重A的任意一个切割，（u,v）是横跨此切割的一条轻量级边。那么（u,v）是A的一条安全边。
• 切割：无向图G的切割是对G点集V的一个划分，切割（S,V-S）指把点集V分成了S和V-S两部分
• 横跨：有切割（S,V-S），点u∈S，点v∈V-S，则称边（u,v）横跨切割（S,V-S）
• 轻量级边：横跨一个切割的所有边中权值最小的边（不一定唯一）
• 尊重：有切割（S,V-S）,若集合A中不含横跨此切割的边，称此切割尊重集合A
• 证明：

设T是包含A的一个最小生成树，有切割（S,V-S）尊重A,它的轻量级边为（u,v）

∵T为一个最小生成树，连通图中任意两点
∴点u,v间存在简单路径p∈T
∵点u,v分处于切割两侧
∴必存在边（x,y）∈ p且横跨切割（S,V-S）
∵T中无环，p唯一
∴删除边（x,y）会使T被分解为两个连通分量
∴将（u,v）加入这两个连通分量可以生成新的生成树T'

∵权值w((u,v))<=w((x,y))
∴w(T')<=w(T)
∴T'也是最小生成树

∵切割（S,V-S）尊重A
∴(x,y)∉ A
又∵A∈T
∴A∈T'
∴A∪{(u,v)}∈T'
∴(u,v)是A的安全边

6. 进一步证明以下推论：

• 推论：G=（V,E）是带权联通无向图。设A为E的一个子集，且A属于G的某最小生成树，设C=(Vc,Ec)为森林Ga=(V,A）中的一个连通分量（树）。如果边(u,v)是连接C和Ga中某其他连通分量的一个轻量级边，则（u,v）对A是安全的。
• 证明：

∵切割（Vc,V-Vc）尊重集合A
又∵(u,v)是横跨此切割的一条轻量级边
∴由以上定理，（u,v）对A安全

7. prim算法和kruskal算法是对于这一推论的两个应用形式。对于prim算法，可以认为初始化时Ga中的连通分量包括初始边和剩下的n-2个点，Ga中除了这个初始边不断变大，其他树都是根节点状态。每次循环加入一条和A相邻的权值最小的边，实际就是在森林Ga中选一个最近的根节点状态的树加入那个大树中，直到所有点都加入为止。

三、prim算法和迷宫生成

1、迷宫生成和最小生成树的联系

通过如下方法将迷宫生成问题和求最小生成树建立联系：

• 把迷宫看做这个样子，左边是用类似数组表示的迷宫，把墙简化后比较容易看
  
• 这是迷宫初始化的样子，所有墙壁都是封死的，路径格处于独立状态。如果把迷宫看作带权图G，则点集V即4为简化图中显示的9个路径格，边集E则是任意相邻两路径格间连线的集合，可以看作所有路径权值都相等。
• 设迷宫入口为左上角的路径格，出口为右下角的路径格，则生成一个迷宫的实质就是找G的一个最小生成树T，T包含所有路径格，不成环，且其中任意两个路径格连通。（事实上当不必连通所有格，只要连通了起点和终点，也可以算迷宫生成完毕，只是这样的迷宫不完整）
• 把起点加入空集A，则森林Ga中包含9棵根节点状态的树，接下来要不断在E中找安全边，使Ga中的根节点状态的树元素都加入到集合A中，直到Ga中只剩A一个元素（或者Ga中某树包含起点和终点）为止。

2、prim迷宫生成算法

• 思想

  1. 初始化迷宫为墙壁全部封死状态（如上图）
  2. 把起点加入集合A
  3. 找集合A中点周围的墙（非边界墙），选择其中任意一个判断墙两边的两个路径点是否都属于集合A，若不是则打破此墙，使新路径点加入集合A
  4. 重复，直到A中包含所有路径点为止

• 具体落实到编程上（注意，以下流程中要把墙的厚度看做 0，即使用上图右侧的那种视角）

  1. 让迷宫全是墙.
  2. 选一个单元格作为迷宫的通路，然后把它的邻墙放入列表
  3. 当列表里还有墙时
     1. 从列表里随机选一个墙，如果这面墙分隔的两个单元格只有一个单元格被访问过，那就从列表里移除这面墙，即把墙打通，让未访问的单元格成为迷宫的通路，再把这个格子的墙加入列表
     2. 如果墙两面的单元格都已经被访问过，那就从列表里移除这面墙
  4. 列表里已经没有墙了，结束

• 生成的迷宫示意图，代码见我的RL测试平台开源项目
  

3、可以参考这些文章

1. 三种迷宫生成算法概述，这篇文章里关于prim的描述我觉得更接近克鲁斯卡尔算法
2. 三大迷宫生成算法 ，这篇文章里有示例代码供参考