公园内道路有条件限制的设计最短路径数模论文--本科毕业设计论文.doc

公园内道路设计最优问题

摘 要
对于题中所给的道路设计问题，即研究在约束条件下最小生成树问题。题中所给三个问题，研究在不同现实背景下的最优道路设计问题，根据所给限制条件的增加，层层深入。本文针对题中所述的矩形公园，利用图论中各种成熟的相关算法，对道路和最短的设计方案进行建模求解：
对问题一，分为两个步骤进行建模求解。步骤一利用算法生成总道路和的最小树，步骤二用算法对步骤一生成的道路用是否满足“任意两入口间最短道路长小于二者连线的1.4倍”这一条件进行验算，对于个别不满足的道路进行微调和修改。最终方案中得到的道路总长度为394.5米。
对问题二，在问题一的基础上，我们采用求解欧式距离的斯坦纳点最小树的逐步调优法，根据相应理论通过离散概率随机抽取相应的斯坦纳点进行扰动，直到得到最优解。经验算确定，最终方案得到的道路总长度为362.1米。
对问题三，我们利用题中的限制条件，分析了所给的人工湖位置与入口的坐标的数据特点，先确定了在不加道路交叉点情况下，仅利用湖四周的道路，即可满足任意入口间最短路径1.4倍条件的可利用的最短道路，再利用问题二中的方法添加了一个斯坦纳点，并在其邻域内进行扰动后得到最优解。经验算确定，最终方案得到的道路总长度为324.6米。
最后本文还结合实际情况，对模型的优缺点进行了分析与评价，并提出了改进和推广方向。

关键词：最小生成树；约束条件；算法；算法；求解欧式距离的斯坦纳点最小树的逐步调优法；二叉堆
目 录
1. 问题重述 1
1.1. 问题背景 1
1.2. 问题要求 1
1.3. 问题提出 1
2. 问题分析 2
2.1. 问题一的分析 2
2.2. 问题二的分析 2
2.3. 问题三的分析 3
3. 模型假设 3
4. 符号说明及名词解释 3
4.1. 基本符号 3
5. 模型建立与求解、检验 4
5.1. 问题一 4
5.1.1. 问题解析 4
5.1.2. 模型建立与求解、检验 7
5.2. 问题二 9
5.2.1. 问题解析 9
5.2.2. 模型建立与求解、检验 9
5.3. 问题三 9
5.3.1. 问题解析 9
5.3.2. 模型建立与求解、检验 9
6. 结果表示 9
6.1. 问题一 9
6.2. 问题二 9
6.3. 问题三 9
7. 模型的评价、优化及推广 9
7.1. 模型的评价 9
7.2. 模型的优化 9
7.3. 模型的推广 9
8. 参考文献 9
9. 附件清单 9

1. 问题重述
1.1. 问题背景
西安某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美化校园环境，也是想为其学生提供更的生活条件。
假设主要设计对象为一个矩形公园，其相关数据为：长200米，宽100米，1至8各入口的坐标分别为：
.
根据题目所给数据，运用数学建模方法，将实际复杂的问题理想模型简化，设计出满足题目要求的公园内道路，有很重要的现实意义。
1.2. 问题要求
从实际情况出发，对道路的设计有以下几个要求：
1) 让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长）；
2) 任意的两个入口之间的最短道路长不大于两点连线的1.4倍；
3) 公园内新修的道路只能通过8个路口与四周相连；
4) 公园内总的道路长度和最小。
1.3. 问题提出
从实际情况及上述要求出发，依据相关条件和数据解决：
问题一 ：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。
问题二 ：现公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。
问题三 ：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达题中湖四周的边。重复完成问题二 的任务。其中矩形湖的相关坐标：
R1(140,70) , R2(140,45) , R3=(165,45) , R4=(165,70).
2. 问题分析
从人性化角度考虑，公园道路应满足让任意两个入口相连，以保证游人不管怎样都可以走出公园。另外，由于公园内部设有观赏景点或是休息座椅，所建设道路要经过这些地点。而这些地点又分为修公园前就有的和公园建好后才修建的，还可分为道路可以通过的和不可以通过的（如湖、花坛等），这些情况都对应于不同的道路设计方案。
对于校方而言，所建道路在满足上述设计需要的基础上，道路长度和越短则消耗的资金越少。故道路长度和为主要考察的对象。
2.1. 问题一的分析
问题一规定了一些必须经过的点。这来源于实际中所修道路要通向那些在公园建设之前就已存在的观赏景点的情况。用数学模型分析解决这一问题对此类情况有重要意义。
问题一属于有限制条件的最小树生成问题。解决最小树问题，一般采用算法和算法。根据所学知识、题中数据特点和结果要求，我们选择使用算法解决最小树问题。为验算是否满足题中所给两点间1.4倍直线距离的要求，我们采用算法解决最短路径问题。
2.2. 问题二的分析
同问题一相比，问题二没有规定公园内必须通过的点。这来源于实际中公园内的景点及设施都是在设计公园道路后才建的情况。用数学模型分析解决这一问题对此类情况有重要意义。
问题二属于斯坦纳最小生成树问题。考虑到任意两点之间可以直接相连，我们采用求解欧式距离的斯坦纳点最小树的逐步调优法。
2.3. 问题三的分析
问题三在问题二的基础上增加了限制条件，考虑到实际中公园等休闲场所在道路规划前即有人工湖等情况，问题三即是从这一情形中抽象出来的。因此对于问题三的研究很有现实意义。
问题三属于约束条件下的斯坦纳最小树问题。显然，在问题二的基础上，道路是不能通过人工湖的，因此，问题二可看作问题三的简化。考虑到重建模型的复杂性和时间的紧迫性，我们利用了问题二所建模型，针对问题二得到的结果，在此基础上进行了相关优化，直到获得最优解。
3. 模型假设
1) 假设所有道路均为直线；
2) 假设任意两点间均可修建道路，即公园内土质及其它条件对修路不产生影响（第三问的湖泊除外）；
3) 假设所有道路均为无向的，不存在单行道，即道路为同一条路；
4) 对于问题一，假设除了题中所给道路交叉点外，不再另外添加点。
5) 对于问题三，假设矩形湖的四周也可以利用，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长。
4. 符号说明及名词解释
4.1. 基本符号
符号
意义

第个入口

从第个入口到第个入口的行走路线

5. 模型建立与求解、检验
5.1. 问题一
5.1.1. 问题解析
该问题给出了四个道路交叉点：A、B、C、D，在所设计道路要让任意两个入口相连（可以利用公园的矩形边），道路只能与公园的8个入口相连而不能与四周其他点相连，任意的两个入口之间的最短道路长不大于两点连线的1.4倍，两点间所建道路为直线的前提下，我们所关心的问题是，如何设计出公园内道路设计的最优方案，使得道路长度和最短。
我们将问题一的求解分为两个步骤：一、使用算法解决最小树问题；二、采用算法验算步骤一生成的树是否满足题中所给的两点间1.4倍直线的距离要求并进行人工微调修正。

5.1.1.1. 步骤一：
通过分析道路长度和最短的要求，我们发现这个问题和最小生成树问题联系最为紧密，于是考虑用贪心法求解最小生成树的算法的一些研究成果以及相关的图论知识来建立该问题的数学模型。
我们先引入最小生成树的简单定义：
给定一个无向连通带权图中的每一条边权值为。如果的子图'是一个包含中所有定点的子图，那么'称为的生成树，如果'的边的权值最小，那么'称为的最小生成树。
对于算法，其中心思想是每次添加权尽可能小的边，使新的图无圈，直到生成最优树为止，其步骤如下：
1) 把内的所有边按照权的非减次序排列；
2) 按1)排列的次序检查中的每一条边，如果这条边与已得到的边不产生圈，则取这一条边为解的一部分；
3) 若已取得n-1条边，算法终止。此时以为顶点集，以取到的n-1条边为边集的图即为最优树。
对于问题一，题中仅给定几个固定点的坐标，并不知道相应的边。为简单起见，我们先假设任意两点之间都是可以相连的，通过相关程序，即可算出任意两点间的距离，并作为距离矩阵输出。其中，将任意两点间的距离即作为该边的权。
此时，可将距离矩阵作为算法的加权矩阵，进行输入，即可得到由算法处理的最小树。附注：利用该算法时，不考虑由外矩形边框所引入的圈。

5.1.1.2. 步骤二：
通过分析题中要求，任意的两个入口之间的最短路径不大于两点间连线的1.4倍，我们采用算法对于步骤一生成的树进行验算。
我们先引入算法的简单定义：
算法是解决关于带权图(权为非负数)的单源最短路径问题的一种贪心算法，它要一个一个地按路径长度递增序找出从某个源点出发到所有其他顶点的最短路径。算法是按长度递增的次序生成从源点到其他定点的最短路径，则当前正在生成的最短路径上除终点以外，其余的顶点的最短路径均已生成（将源点的最短路径看作是已生成的源点到其自身的长度为0的路径）。
可利用算法对步骤一所生成的道路中任意两入口间的最短距离进行求解得到一个矩阵，再与这两入口间距离的矩阵的1.4倍进行作差，找出负数（即不符合要求）对应的道路，进行人工合理化调整修改后即可得到最优结果。

对问题一的求解过程用流程图表示如下：

形成
距离矩阵
利用程序求任意两点
间的距离

由kruskal算法程序
最小树
最短路径矩阵
Dijkstra算法
1.4倍距离矩阵
差距
作为输入
输出
作差
倍
最优解
调整

5.1.2. 模型建立与求解、检验
5.1.1.1. 步骤一：
将数据输入由算法对应的程序（见附录），仅仅考虑生成最小树，得到如下结果：
算出来的结果：
边端点 距离 是否在最小支撑树
(1,2) 30 √
(1,3) 140 ×
(1,4) 1.868154e+002 ×
(1,5) 1.414214e+002 ×
(1,6) 1.011187e+002 ×
(1,7) 1.004988e+002 ×
(1,8) 3.201562e+001 √
(1,9) 8.077747e+001 ×
(1,10) 4.472136e+001 ×
(1,11) 1.077033e+002 ×
(1,12) 1.180042e+002 ×
(2,3) 110 ×
(2,4) 1.581139e+002 ×
(2,5) 1.220656e+002 ×
(2,6) 1.011187e+002 ×
(2,7) 1.077033e+002 ×
(2,8) 5.590170e+001 ×
(2,9) 75 ×
(2,10) 4.123106e+001 √
(2,11) 8.062258e+001 ×
(2,12) 9.552487e+001 ×
(3,4) 6.403124e+001 √
(3,5) 1.077033e+002 ×
(3,6) 1.600781e+002 ×
(3,7) 1.802776e+002 ×
(3,8) 1.619413e+002 ×
(3,9) 1.331353e+002 ×
(3,10) 1.264911e+002 ×
(3,11) 5.656854e+001 √
(3,12) 8.321658e+001 ×
(4,5) 9.433981e+001 ×
(4,6) 1.724094e+002 ×
(4,7) 1.964688e+002 ×
(4,8) 2.015564e+002 ×
(4,9) 1.520691e+002 ×
(4,10) 1.603122e+002 ×
(4,11) 8.062258e+001 ×
(4,12) 8.732125e+001 ×
(5,6) 85 ×
(5,7) 110 ×
(5,8) 1.415097e+002 ×
(5,9) 7.433034e+001 ×
(5,10) 100 ×
(5,11) 60 ×
(5,12) 3.041381e+001 √
(6,7) 25 √
(6,8) 8.276473e+001 ×
(6,9) 2.915476e+001 √
(6,10) 6.020797e+001 ×
(6,11) 1.040433e+002 ×
(6,12) 8.544004e+001 ×
(7,8) 7.566373e+001 ×
(7,9) 4.716991e+001 ×
(7,10) 6.708204e+001 ×
(7,11) 1.252996e+002 ×
(7,12) 1.092016e+002 ×
(8,9) 7.071068e+001 ×
(8,10) 4.272002e+001 ×
(8,11) 1.209339e+002 ×
(8,12) 1.234909e+002 ×
(9,10) 3.640055e+001 √
(9,11) 7.826238e+001 ×
(9,12) 6.519202e+001 √
(10,11) 80 ×
(10,12) 8.077747e+001 ×
(11,12) 3.041381e+001 √
（其中，“√”表示两端点是连通的，“×”表示两端点不连通）
由上述数据，可得初步公园道路图：

算法得出的最小树对应的路径图（初步结果）

5.1.1.2. 步骤二：
步骤一生成的只是最小树，而不一定满足题中的要求——任意的两个入口之间的最短道路长不大于两点连线的1.4倍。
下面先对步骤一所生成的各道路中任意两入口间最短的折线距离利用算法进行求解，储存到矩阵中，设这个矩阵用表示，
=

设储存这两入口间直线距离的矩阵用表示，
=

将矩阵和1.4倍的矩阵进行作差，得到矩阵，

将矩阵和1.4倍的矩阵作差得到矩阵，
=

找出中的负数（即不符合要求）对应的道路，即和两条折线道路大于两入口直线距离的1.4倍，需要进行人工合理化调整修改。经过合理地分析与尝试，我们将修改后的公园内道路确定为：

修正后的公园道路设计图（优化结果）

下面对修改后的道路进行合理化的验证。
修改后再利用算法新生成的公园道路中任意两入口间的最短距离进行求解，得到新的矩阵，记为，
=

任意两入口的直线距离所储存的矩阵不变，仍为

=

同理，再将矩阵和1.4倍的矩阵进行作差，得到矩阵，
=

由中再无负数元素，可验证得到修改后的道路满足题中各条件，即为最优解。
5.2. 问题二
5.2.1. 问题解析
同问题一相比，问题二没有规定公园内必须通过的点，属于斯坦纳最小生成树问题。考虑到任意两点之间可以直接相连，我们采用求解欧式距离的斯坦纳点最小树的逐步调优法。
我们先引入斯坦纳最小树的定义：
定义 已知欧式平面上任给的有限点集 ，欲求出一个点集，使点集的连线长度最短所构成的图，必然是边数最少的连通图，因此它为树，称为斯坦纳最小树，记为。中的点为上的固定点，中的点称为上的斯坦纳点，简称为斯坦纳点。
由于本问题可以自由添加道路交叉点，我们引入的一些性质：
性质1 上每个点之多关联三条边，而每个斯坦纳点恰好关联三条边。
性质2 上，关联于同一点的任何两边的夹角不小于；关联于同一斯坦纳点的任何两边的夹角恰为。
性质3 若，则中斯坦纳点的个数不大于。
性质4 欧式斯坦纳最小树的每个斯坦纳点都必定包含在全部正则点的最小凸包内。
添加斯坦纳点的斯坦纳最小树，往往会比不添加斯坦纳点的最优树的长度更短些。即若以和分别表示点集的最优树和斯坦纳最小树的长度，必有。例如，给出三点、、，组成边长为1的正三角形。对点集的斯坦纳最小树的长度为，而最优树长度为2。因此，。也就是说，添加斯坦纳点后可以节省约13%的长度。
引入以下定理：
定理
下面我们介绍最小逐步调优法的原理：
设正则点集中有个点，坐标为。并记，
，
，
。
根据性质4，辅助点的投放范围可以控制在矩形之内。
本文逐步调优法的思路是这样的：
首先求出正则点集的最小生成树,相应的树长为。设表示辅助点数，让分别取值1到，对于每一个值，在范围内随机投放个辅助点，产生辅助点集，然后用算法计算出由个点组成的集的最小生成树。这样就获得棵树，根据它们的树长，计算出一个概率分布，树长越短者，相应的概率越大。然后按此分布随机抽样，树长越短，被抽中的概率就越大。对被抽中的树，对其每个辅助点，在一个小领域范围内随机作扰动，产生一个新的近似解，这样重复多次择优记录最好者，若比原来的要好，则替换它，否则不变。重算概率分布，再抽样调优，这样重复到预定循环次数为止。这里不直接选树长最短者来调优，是为了避免算法陷入局部极值，不是最短的树也有机会被抽中。上述过程完成后，还需做最后的调整：删掉1度和2度的辅助点（若有的话），利用求解斯坦纳点坐标的计算式，并把3度辅助点调整到最优位置，使其变为斯坦纳点。
完成以上过程后，获得一个近似最优解，若树长，则输出，否则输出。
下面我们阐述一下逐步调优法的实施步骤：
1.用算法求出正则点集的最小生成树。
2.依次让k取值1到，在矩形R内随机投放k个辅助点，产生辅助点集，然后用算法计算出由个点组成的集的最小生成树，树长记为。
3.记，，，这样得到了一个离散的概率分布，并记，。
4.产生一个[0，1]均匀分布的随机数，若满足，则对的辅助点位置作扰动，不是随机重投，而是每个辅助点在一个半径为的邻域内随机走一步（当然不能走出的范围）。这一步重复大约20次，择优记录最好者，若比原来的要好，则替换它，否则不变。
5.重复步骤3和4，知道大道预设的最大迭代次数位置，此时的最好解记为。
6.统计中辅助点的度。
7.检查和优化的辅助点。若有1度辅助点，则显然应把该点连同关联边删去；若有2度辅助点，则应把该点连同关联边删去，但要添加一条连接两个邻点的边。若有3度辅助点，一般它不是斯坦纳点，需要矫正。按照斯坦纳点的坐标计算公式，把该3度辅助点移动到该坐标位置上，调整后得到新的。
8.重复步骤6和7，大约10次，若最后树长，则输出，否则输出。如果有1度辅助点被删除，则会影响相邻点的度；如果有两个3度辅助点相邻，则校正了1个辅助点成斯坦纳点后，另一个辅助点可能又变得不在最佳位置。
因此，第6、7步的重复是必要的，反复多次调优，才能逐步逼近最优位置。
5.2.2. 模型建立与求解、检验
根据上述的逐步调优法，由本题，随机分布个斯坦纳点，通过离散概率随机抽取相应的斯坦纳点进行扰动，直到得到最优解，并解出新修路的总长度为363.1米。其对应的公园道路设计图如下：

利用问题一中相同的算法对结果进行验算，看所求得道路是否满足1.4倍这一条件。所得到的矩阵为：

由于矩阵中无负元素，故检验得所求道路满足题目要求。
5.3. 问题三
5.3.1. 问题解析
问题三在问题二的基础上增加了约束条件——不能经过道路的区域，这也给题目增加了很大的难度。为此，我们在分析了数据特点及湖位置的基础上，根据问题一中的计算任意两入口间折线距离的方法，我们确定了在不添加道路交叉点的情况下就可满足折线距离小于两入口直线距离1.4倍的条件的几条边。经过分析，只有入口和入口在不添加道路交叉点的情况下不能满足题中要求。故只需要添加一个道路交叉点使这三点满足两入口直线距离的1.4倍这一条件，并且使新增的道路总长度最小；经分析，该点即为斯坦纳点。在问题二的基础上，利用欧式距离斯坦纳最小树的逐步调优法进行相关扰动，最终确定斯坦纳点并进行验算。
5.3.2. 模型建立与求解、检验
根据问题二的理论依据，因为有三个点，故只需要添加一个斯坦纳点即可。利用迭代思想，在该点的邻域内进行扰动，添加道路交叉点使这三点满足两入口直线距离的1.4倍，并且使道路总长度尽可能小。经多次验算，我们确定了一个斯坦纳点。计算可得道路长度和为324.6米，其相应的公园道路设计图为：

同问题一、问题二一样的验算原理，可算得此设计满足题中各要求。
6. 结果表示
6.1. 问题一
道路设计图：

问题一方案新修路的总路程：394.5米
6.2. 问题二
道路设计图：

问题二方案新修路的总长度：363.1米
6.3. 问题三
道路设计图：

问题三方案新修路的总长度：324.6米
7. 模型的评价、优化及推广
7.1. 模型的评价
1) 问题一的求解思路是先用算法得到是不带环的最小树，把边加入最小树再利用算法依据题中条件进行验算，这样得到的结果可能不是最优解；
2) 问题一中，模型一利用算法和算法分两个步骤得到精确最优解的前提是假设所修道路均为直线，公园内部有且仅有给出的四个道路交叉点。而事实上是可以再添加道路交叉点的，此类问题便同问题二一样属于难问题，也就是说,，当问题含有其他约束条件时,，要想求得真正的最优解是不现实的，为此，必需采取灵活多样的方式和方法, 求近似得最优解；
3) 问题二在问题一的基础上可随意添加道路交叉点，添加点的个数和位置均不确定，成为难问题，无法找到精确最优解。本问题中的算法都只是近似算法, 所得最优设计方案也只是近似最优解；
4) 问题二、三所用算法利用人工扰动精度不高且效率较低；
5) 问题三求解是在可利用湖的四边而不算入所修总路程的假设下，具有一定的理想局限性。
7.2. 模型的优化
我们发现，在问题一的步骤二中用算法对最短路径进行验算的时间代价较高，若用传统的方法通过扫描整个网络图的顶点来搜索最小值，总时间代价为，如果将模型应用到顶点数多的环境中，那么效率将非常低。经查阅相关文献[2]后，我们认为利用二叉堆来进行优化，便可快速访问到具有最小值的点，时间代价仅为。具体思路如下：
设为最短距离已确定的顶点集（看作红点集），是最短距离尚未确定的顶点集（看作蓝点集）。初始化时，只有源点的最短距离是已知的，其余各点的估计最短距离值均设为无穷大。用数组记录从源点到达外中间不经过任何蓝点（若有中间点，则必为红点）的“最短”路径长度（简称估计距离）。经过一次循环后，红点集 ，其余各点的估计最短距离值更新为该点到源点而中间不经过任何点的边的权值。若路径不存在则仍为无穷大；在蓝点集中选择一个最短距离最小的蓝点来扩充红点集是算法的关键。若能快速访问到具有最小值的蓝点，则可大大减少算法的时间复杂度。若用传统的方法通过扫描整个网络图的顶点（即穷举法）来搜索最小值，总时间代价为。在算法中，由于累计权值决定的最短路径具有优先程度差异特征，所以若将未被处理的顶点的最短路径值构造优先级队列，则可大大提高算法的效率。用堆来实现优先级队列是很自然的。堆是一种抽象数据结构，由一系列元素集合构成，每个元素有个实数类型的关键字。而二叉堆是一种最普及的数据结构，它可被视为一棵完全二叉树。堆有最大堆和最小堆两种。最小堆结构必须满足以下性质：除了根节点，每个节点的值不小于其父节点的值．这样，堆中的最小元素就存在根节点中。因为具有个元素的二叉堆是一棵完全二叉树，其高度为。所以对于二叉堆的操作例如(插入)和(从堆中删除并返回最有最小关键字的元素)，其作用时间至多与树的高度成正比，为。所以，将未被处理的顶点以值大小为顺序保存在一个最小堆中，可以使用次搜索找出下一个最近顶点。每次改变值时，都可以通过先删除再重新插入的方法改变顶点菇在堆中的位置。为了实现优先更新需要将每个顶点连同它的数组下标存储在堆中，其时间复杂度在算法实现部分分析。
对于问题二采用的求斯坦纳最小树的逐步调优法，由于离散概率的不确定性，所以采用迭代的次数较多，过程较繁，相应地，效率也就降低了。针对这一问题，可以采用多路径并行搜索蚁群算法的并行搜索机制进行相关优化。其具体原理如下：
多路径并行搜索蚁群算法将每只蚂蚁的求解过程分解为m条路径并行的搜索，其中m为终端节点的个数。每条路径对应从一个终端节点出发，直至满足某个条件终止。利用该方法路径搜索的终止条件是刚访问过的节点已经出现在其他路径上，即当前路径与其他路径发生相交，则当前路径设置为不活跃状态，本路径终止搜索节点。若当前蚂蚁的所有的路径都终止时，蚂蚁在该轮迭代中搜索节点的过程也终止。蚂蚁在这步操作完成之后即得到一个节点的集合，该集合由这m条路径上的所有节点构成，包括了所有终端节点和当前蚂蚁认为必要的一些中间节点，这个过程极为蚂蚁选择节点的过程。
7.3. 模型的推广
由于本题采用图论模型的方法求解，分析了在不同的限制条件下道路长度和最短的数学模型及求解，并提出能够找到该近似算法或原则，可以较好的推广到解决交通网络、输油管道、灾情巡视线路、投递、旅行商等实际问题。
8. 参考文献
[1] 林健良，施美珍，朱晓清，何明芳。求解欧式距离斯坦纳最小树的逐步调优法。广州：华南理工大学理学院，2011。
[2] 林小玲，何建农，周勇。带限制条件的最短路径算法与实现。福州：福州大学学报（自然科学版），2004。
[3] 张瑾，马良。最小树问题及其应用。上海，开封：科学技术与工程，2008。
[4] 杨凌云。图的最小树问题及其求解。开封：电脑知识与技术，2009。
9. 附件清单
1. 附件1：算法求最小生成树的代码及结果显示；
2. 附件2：求已知道路的情况下任意两入口间最短距离的函数代码；
3. 附件3：构造的距离矩阵，为只包含联通边的距离矩阵；
4. 附件4：求解斯坦纳点的C语言代码；
5. 附件5：问题二中部分斯坦纳点扰动过程
6. 附件6：利用外矩形边框验算任意两点间距离的1.4倍条件的C语言代码；
7. 附件7：问题二最优解情况下路径生成及验算代码；
8. 附件8：针对问题三的斯坦纳点的扰动代码。

附件1
Kruskal函数
function Kruskal(w,MAX)
%此程序为最小支撑树的Kruskal算法实现
%w为无向图的距离矩阵，故为对称矩阵
%MAX为距离矩阵中∞的实际输入值
%时间：2011年6月22日0:07:53
len=length(w); %图的点数
edge=zeros(len*(len-1),3); %用于存储图中的边
count=1; %图中的边数
for i=1:len-1 %循环距离矩阵，记录存储边
for j=i+1:len
if w(i,j)~=MAX
edge(count,1)=w(i,j);
edge(count,2)=i;
edge(count,3)=j;
count=count+1;
end
end
end
edge=edge(1:count-1,:); %去掉无用边
[~,index]=sort(edge(:,1)); %所有边按升序排序
i=3; %其实测试边数为3条（3条以下无法构成圈，即无需检测）
while 1
x=findcycle(edge(index(1:i),:),len); %检测这些边是否构成圈
if x
index(i)=0; %若构成圈，则将该边对应的index项标记为0，以便除去
else
i=i+1; %若没有构成圈，则i加1，加入下一边检测
end
index=index(index>0); %将构成圈的边从index中除去
if i==len
break; %找到符合条件的点数减一条的边，即找到一个最小支撑树
end
end
index=index(1:len-1); %截短index矩阵，保留前len-1项
%%%%%%%%%%%% 结果显示 %%%%%%%%%%%%%
s=sprintf('\n\t%s\t%s\t %s\t','边端点','距离','是否在最小支撑树');
for i=1:count-1
edge_tmp=edge(i,:);
if ~isempty(find(index==i,1))
s_tmp=sprintf('\n \t (%d,%d)\t %d\t %s\t',edge_tmp(2),edge_tmp(3),edge_tmp(1),'√');
else
s_tmp=sprintf('\n \t (%d,%d)\t %d\t %s\t',edge_tmp(2),edge_tmp(3),edge_tmp(1),'×');
end
s=strcat(s,s_tmp);
end
disp(s);
end
function isfind=findcycle(w,N)
%本程序用于判断所给的边能否构成圈：有圈，返回1；否则返回0
%w：输入的边的矩阵
%N：原图的点数
%原理：不断除去出现次数小于2的端点所在的边，最后观察是否有边留下
len=length(w(:,1));
index=1:len;
while 1
num=length(index); %边数
p=zeros(1,N); %用于存储各点的出现的次数（一条边对应两个端点）
for i=1:num %统计各点的出现次数
p(w(index(i),2))=p(w(index(i),2))+1;
p(w(index(i),3))=p(w(index(i),3))+1;
end
index_tmp=zeros(1,num); %记录除去出现次数小于2的端点所在的边的边的下标集合
discard=find(p<2); %找到出现次数小于2的端点
count=0; %记录剩余的边数
for i=1:num
%判断各边是否有仅出现一次端点——没有，则记录其序号于
index_tmp
if~(~isempty(find(discard==w(index(i),2),1)) || ~isempty(find(discard==w(index(i),3),1)))
count=count+1;
index_tmp(count)=index(i);
end
end
if num==count %当没有边被被除去时，循环停止
index=index_tmp(1:count); %更新index
break;
else
index=index_tmp(1:count); %更新index
end
end
if isempty(index) %若最后剩下的边数为0，则无圈
isfind=0;
else
isfind=1;
end
end

附件2
Dijkstra函数
function [distance,path]=dijkstra(A,s,e)
% [DISTANCE,PATH]=DIJKSTRA(A,S,E)
% returns the distance and path between the start node and the end node.
%
% A: adjcent matrix
% s: start node
% e: end node

% initialize
n=size(A,1); % node number
D=A(s,:); % distance vector
path=[]; % path vector
visit=ones(1,n); % node visibility
visit(s)=0; % source node is unvisible
parent=zeros(1,n); % parent node

% the shortest distance
for i=1:n-1 % BlueSet has n-1 nodes
temp=zeros(1,n);
count=0;
for j=1:n
if visit(j)
temp=[temp(1:count) D(j)];
else
temp=[temp(1:count) inf];
end
count=count+1;
end
[value,index]=min(temp);
j=index; visit(j)=0;
for k=1:n
if D(k)>D(j)+A(j,k)
D(k)=D(j)+A(j,k);
parent(k)=j;
end
end
end
distance=D(e);

% the shortest distance path
if parent(e)==0
return;
end
path=zeros(1,2*n); % path preallocation
t=e; path(1)=t; count=1;
while t~=s && t>0
p=parent(t);
path=[p path(1:count)];
t=p;
count=count+1;
end
if count>=2*n
error(['The path preallocation length is too short.',...
'Please redefine path preallocation parameter.']);
end
path(1)=s;
path=path(1:count);

附件3
x=[20,50,160,200,120,35,10,0,50,40,120,115];
y=[0,0,0,50,100,100,100,25,75,40,40,70];
i=[1 1 2 3 3 5 6 6 9 11 9];
j=[2 8 10 4 11 12 7 9 10 12 12];
dist =
[ 0 30 300 300 300 300 300 300 300 300 300 300;
30