文章目录
- 一、关于随机迷宫生成
- 二、prim算法
-
- 三、prim算法和迷宫生成
- 1、迷宫生成和最小生成树的联系
- 2、prim迷宫生成算法
- 3、可以参考这些文章
一、关于随机迷宫生成
1.我们将迷宫定义如下：迷宫由道路和墙组成，且迷宫中道路上的任意两点应互相可达
2.随机迷宫生成算法一般有以下三种，这里只介绍随机prim算法
- 随机prim算法
- 深度优先（递归回溯）算法
- 递归分割（分治）算法
二、prim算法
1、最小生成树
最小生成树:在带权图G=( V,E )中（V为点集，E为边集且每条边带有权值），我们希望找到E的一个无环子集T，使得V中任意两点可达。由于T无环且联通所有点，可知T必为一颗树，称这种边子集T为生成树，称所有满足条件的T中权值和最小的为最小生成树。- 举例来说，我们绘制一块pcb电路板，需要把n个针脚布线连接在一起，并希望连线长度总和最小。这里n个针脚即为点集，任意两针脚间的所有可能连线组成这个pcb图的边集，而连线的长度可看做该线的权值。任意一个连接所有针脚且不产生连线回环的连法都是此pcb图的一个生成树，所有生成树中用线长度最短的即为最小生成树.
2、prim算法简介
- prim是求给定若干点间最小生成树的经典算法。另一种此问题的经典算法是kruskal算法
- prim算法使用的是贪心策略，其正确性可以证明。
- 算法流程如下：
- 从边集E中随机选取一点加入集合A
- 考察和A相邻的所有边，找其中权值最小的一条加入A (也就是说A一直是一棵树)
- 当A中包含V中所有点时，算法结束，A为一棵最小生成树
3、正确性证明
- 使用 循环不变式 来证明算法正确性，关于循环不变式可以参考：循环不变式的思想及其应用
- prim算法要管理的集合A遵循以下循环不变式：在每遍循环前，A是某最小生成树的一个子集。也就是说，我们要在每一步循环找到一个边（u,v），使得 A∪{（u,v）}也是某最小生成树的子集，我们可以定义满足这个要求的边为
安全边 - 按以下方式使用循环不变式证明正确性
1 A=∅
2 while A不是最小生成树
3 找到安全边（u,v）
4 A=A∪{(u,v)}
5 return A
初始化：在第一行后，A直接满足循环不变式
保持：算法第2~4行一直加入安全边，不会破坏循环不变式
终止：所有加入A的边都属于某最小生成树，则第5行返回的A一定是一个最小生成树
- 上述策略的重点在于第3行，如何找到一条安全边。（这条安全边是必然存在的，因为循环不变式告诉我们一定存在一个最小生成树T满足A∈T，2~4行时A是T的真子集，一定有边（u,v）∈ T && （u,v）∉ A，此边即为安全边）
- 为了辨别安全边，先证明以下定理：
- 定理：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的安全边
- 进一步证明以下推论：
- 推论：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安全
- 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迷宫生成算法
3、可以参考这些文章
- 三种迷宫生成算法概述，这篇文章里关于prim的描述我觉得更接近克鲁斯卡尔算法
- 三大迷宫生成算法 ，这篇文章里有示例代码供参考
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
