1、装 订 线 公园内道路设计最优问题 摘 要 对于题中所给的道路设计问题，即研究在约束条件下最小生成树问题。题 中所给三个问题，研究在不同现实背景下的最优道路设计问题，根据所给限制 条件的增加，层层深入。本文针对题中所述的矩形公园，利用图论中各种成熟 的相关算法，对道路和最短的设计方案进行建模求解： 对问题一，分为两个步骤进行建模求解。步骤一利用 算法生成总道krusal 路和的最小树，步骤二用 算法对步骤一生成的道路用是否满足“任意Dijkstra 两入口间最短道路长小于二者连线的 1.4 倍”这一条件进行验算，对于个别不 满足的道路进行微调和修改。最终方案中得到的道路总长度为 394.5 米
2、。 对问题二，在问题一的基础上，我们采用求解欧式距离的斯坦纳点最小树 的逐步调优法，根据相应理论通过离散概率随机抽取相应的斯坦纳点进行扰动， 直到得到最优解。经验算确定，最终方案得到的道路总长度为 362.1 米。 对问题三，我们利用题中的限制条件，分析了所给的人工湖位置与入口的 坐标的数据特点，先确定了在不加道路交叉点情况下，仅利用湖四周的道路， 即可满足任意入口间最短路径 1.4 倍条件的可利用的最短道路，再利用问题二 中的方法添加了一个斯坦纳点，并在其邻域内进行扰动后得到最优解。经验算 确定，最终方案得到的道路总长度为 324.6 米。 最后本文还结合实际情况，对模型的优缺点进行了分析与
3、评价，并提出了 改进和推广方向。 关键词：最小生成树；约束条件； 算法； 算法；求解欧式距离krusalDijkstra 的斯坦纳点最小树的逐步调优法；二叉堆 目 录 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. 问
4、题二 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/33 1. 问题重述 1.1. 问题背景 西安某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美 化校园环境，也是想为其学生提供更的生活条件。 假设主要
5、设计对象为一个矩形公园，其相关数据为：长 200 米，宽 100 米， 1 至 8 各入口的坐标分别为：2340,5,160,2,50PP .56781,P 根据题目所给数据，运用数学建模方法，将实际复杂的问题理想模型简化， 设计出满足题目要求的公园内道路，有很重要的现实意义。 1.2. 问题要求 从实际情况出发，对道路的设计有以下几个要求： 1) 让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边 上存在已经建好的道路，此道路不计入道路总长）； 2) 任意的两个入口之间的最短道路长不大于两点连线的 1.4 倍； 3) 公园内新修的道路只能通过 8 个路口与四周相连； 4) 公园内总
6、的道路长度和最小。 1.3. 问题提出 从实际情况及上述要求出发，依据相关条件和数据解决： 问题一 ：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)， C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立 模型并给出算法。画出道路设计，计算新修路的总路程。 问题二 ：现公园内可以任意修建道路，如何在满足条件下使总路程最少。 建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的 2/33 总路程。 问题三 ：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达题 中湖四周的边。重复完成问题二 的任务。其中矩形湖的相关坐
7、标： R1(140,70) , R2(140,45) , R3=(165,45) , R4=(165,70). 2. 问题分析 从人性化角度考虑，公园道路应满足让任意两个入口相连，以保证游人不 管怎样都可以走出公园。另外，由于公园内部设有观赏景点或是休息座椅，所 建设道路要经过这些地点。而这些地点又分为修公园前就有的和公园建好后才 修建的，还可分为道路可以通过的和不可以通过的（如湖、花坛等），这些情 况都对应于不同的道路设计方案。 对于校方而言，所建道路在满足上述设计需要的基础上，道路长度和越短 则消耗的资金越少。故道路长度和为主要考察的对象。 2.1. 问题一的分析 问题一规定了一些必须经过
8、的点。这来源于实际中所修道路要通向那些在 公园建设之前就已存在的观赏景点的情况。用数学模型分析解决这一问题对此 类情况有重要意义。 问题一属于有限制条件的最小树生成问题。解决最小树问题，一般采用 算法和 算法。根据所学知识、题中数据特点和结果要求，我们选krusalprim 择使用 算法解决最小树问题。为验算是否满足题中所给两点间 1.4 倍直l 线距离的要求，我们采用 算法解决最短路径问题。Dijkstra 2.2. 问题二的分析 同问题一相比，问题二没有规定公园内必须通过的点。这来源于实际中公 园内的景点及设施都是在设计公园道路后才建的情况。用数学模型分析解决这 一问题对此类情况有重要意义
9、。 问题二属于斯坦纳最小生成树问题。考虑到任意两点之间可以直接相连， 3/33 我们采用求解欧式距离的斯坦纳点最小树的逐步调优法。 2.3. 问题三的分析 问题三在问题二的基础上增加了限制条件，考虑到实际中公园等休闲场所 在道路规划前即有人工湖等情况，问题三即是从这一情形中抽象出来的。因此 对于问题三的研究很有现实意义。 问题三属于约束条件下的斯坦纳最小树问题。显然，在问题二的基础上， 道路是不能通过人工湖的，因此，问题二可看作问题三的简化。考虑到重建模 型的复杂性和时间的紧迫性，我们利用了问题二所建模型，针对问题二得到的 结果，在此基础上进行了相关优化，直到获得最优解。 3. 模型假设 1)
10、 假设所有道路均为直线； 2) 假设任意两点间均可修建道路，即公园内土质及其它条件对修路不产 生影响（第三问的湖泊除外）； 3) 假设所有道路均为无向的，不存在单行道，即道路 为同一条路；,ijjiPP和 道 路 4) 对于问题一，假设除了题中所给道路交叉点外，不再另外添加点。 5) 对于问题三，假设矩形湖的四周也可以利用，即默认矩形的四条边上 存在已经建好的道路，此道路不计入道路总长。 4. 符号说明及名词解释 4.1. 基本符号 符号 意义iP 第 个入口iij 从第 个入口到第 个入口的行走路线ij 4/33 5. 模型建立与求解、检验 5.1. 问题一 5.1.1. 问题解析 该问题给
11、出了四个道路交叉点：A、B、C、D，在 所设计道路要让任意 1 两个入口相连（可以利用公园的矩形边）， 道路只能与公园的 8 个入口相连 2 而不能与四周其他点相连， 任意的两个入口之间的最短道路长不大于两点连 3 线的 1.4 倍， 两点间所建道路为直线的前提下，我们所关心的问题是，如何 4 设计出公园内道路设计的最优方案，使得道路长度和最短。 我们将问题一的求解分为两个步骤：一、使用 算法解决最小树问题；krusal 二、采用 算法验算步骤一生成的树是否满足题中所给的两点间 1.4 倍直Dijkstra 线的距离要求并进行人工微调修正。 5.1.1.1. 步骤一： 通过分析道路长度和最短的
12、要求，我们发现这个问题和最小生成树问题联 系最为紧密，于是考虑用贪心法求解最小生成树的 算法的一些研究成果krusal 以及相关的图论知识来建立该问题的数学模型。 我们先引入最小生成树的简单定义： 给定一个无向连通带权图 中的每一条边 权值为 。如,GVE,VW,CV 果 的子图 是一个包含 中所有定点的子图，那么 称为 的生成树，如GG 果 的边的权值最小，那么 称为 的最小生成树 。 对于 算法，其中心思想是每次添加权尽可能小的边，使新的图无圈，krusal 直到生成最优树为止，其步骤如下： 1) 把 内的所有边按照权的非减次序排列；N 2) 按 1)排列的次序检查 中的每一条边，如果这条
13、边与已得到的边N 不产生圈，则取这一条边为解的一部分； 3) 若已取得 n-1 条边，算法终止。此时以 为顶点集，以取到的 n-1V 条边为边集的图即为最优树。 5/33 对于问题一，题中仅给定几个固定点的坐标，并不知道相应的边。为简 单起见，我们先假设任意两点之间都是可以相连的，通过相关程序，即可算出 任意两点间的距离，并作为距离矩阵输出。其中，将任意两点间的距离即作为 该边的权。 此时，可将距离矩阵作为 算法的加权矩阵，进行输入，即可得到krusal 由 算法处理的最小树。附注：利用该算法时，不考虑由外矩形边框所引krusal 入的圈。 5.1.1.2. 步骤二： 通过分析题中要求，任意的
14、两个入口之间的最短路径不大于两点间连线的 1.4 倍，我们采用 算法对于步骤一生成的树进行验算。Dijkstra 我们先引入 算法的简单定义： 算法是解决关于带权图(权为非负数)的单源最短路径问题的一种贪ijkstra 心算法，它要一个一个地按路径长度递增序找出从某个源点出发到所有其他顶 点的最短路径。 算法是按长度递增的次序生成从源点 到其他定点的最Dijkstr s 短路径，则当前正在生成的最短路径上除终点以外，其余的顶点的最短路径均 已生成（将源点的最短路径看作是已生成的源点到其自身的长度为 0 的路径）。 可利用 算法对步骤一所生成的道路中任意两入口间的最短距离进Dijkstra 行求
15、解得到一个矩阵，再与这两入口间距离的矩阵的 1.4 倍进行作差，找出负 数（即不符合要求）对应的道路，进行人工合理化调整修改后即可得到最优结 果。 6/33 对问题一的求解过程用流程图表示如下： 形成 距离矩阵 利用程序求任意两点 间的距离 由 kruskal 算法程序 最小树 最短路径矩阵 Dijkstra 算法 1.4 倍距离矩阵 差距 作为输入 输出 作差 倍1.4 最优解 调整 7/33 5.1.2. 模型建立与求解、检验 5.1.1.1. 步骤一： 将数据输入由 算法对应的程序（见附录），仅仅考虑生成最小树，krusal 得到如下结果： 算出来的结果：krusal 边端点 距离 是否
16、在最小支撑树 (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 (
17、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)
18、1.724094e+002 (4,7) 1.964688e+002 (4,8) 2.015564e+002 (4,9) 1.520691e+002 8/33 (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
19、.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+
20、001 (10,11) 80 (10,12) 8.077747e+001 (11,12) 3.041381e+001 （其中，“”表示两端点是连通的，“”表示两端点不连通） 由上述数据，可得初步公园道路图： 9/33 5.1.1.2. 步骤二： 步骤一生成的只是最小树，而不一定满足题中的要求任意的两个入口 之间的最短道路长不大于两点连线的 1.4 倍。 下面先对步骤一所生成的各道路中任意两入口间最短的折线距离利用 算法进行求解，储存到矩阵中，设这个矩阵用 表示，Dijkstra D = 设储存这两入口间直线距离的矩阵用 表示，distance =distance 将 矩阵和 1.4 倍的 矩阵
21、进行作差，得到矩阵 ，Ddistancejudge 将矩阵 和 1.4 倍的矩阵 作差得到矩阵 ，distancejudge =judge 找出 中的负数（即不符合要求）对应的道路，即 和 两judge 15P25P 算法得出的最小树对应的路径图（初步结果）krusal 10/33 条折线道路大于两入口直线距离的 1.4 倍，需要进行人工合理化调整修改。经 过合理地分析与尝试，我们将修改后的公园内道路确定为： 下面对修改后的道路进行合理化的验证。 修改后再利用 算法新生成的公园道路中任意两入口间的最短距离Dijkstra 进行求解，得到新的矩阵，记为 ， = 任意两入口的直线距离所储存的矩阵
22、不变，仍为distance =distance 修正后的公园道路设计图（优化结果） 11/33 同理，再将 矩阵和 1.4 倍的 矩阵进行作差，得到矩阵 ，Ddistancejudge =judge 由 中再无负数元素，可验证得到修改后的道路满足题中各条件，即为最优解。judge 5.2. 问题二 5.2.1. 问题解析 同问题一相比，问题二没有规定公园内必须通过的点，属于斯坦纳最小生 成树问题。考虑到任意两点之间可以直接相连，我们采用求解欧式距离的斯坦 纳点最小树的逐步调优法。 我们先引入斯坦纳最小树的定义： 定义 已知欧式平面上任给的有限点集 ，欲求出一个点12,nRv 集 ，使点集 的连
23、线长度最短所构成的图，必然是边数最少12,kSs RS 的连通图，因此它为树，称为斯坦纳最小树，记为 。 中的点为 上的STSRT 固定点， 中的点称为 上的斯坦纳点，简称为 斯坦纳点。T 由于本问题可以自由添加道路交叉点，我们引入 的一些性质：R 性质 1 上每个点之多关联三条边，而每个斯坦纳点恰好关联三条边。SR 性质 2 上，关联于同一点的任何两边的夹角不小于 ；关联于同T 120 一斯坦纳点的任何两边的夹角恰为 。120 性质 3 若 ，则 中斯坦纳点的个数不大于 。12,nRv SRTn 性质 4 欧式斯坦纳最小树的每个斯坦纳点都必定包含在全部正则点的最 小凸包内。 12/33 添加
24、斯坦纳点的斯坦纳最小树，往往会比不添加斯坦纳点的最优树的长度 更短些。即若以 和 分别表示点集 的最优树和斯坦纳最小树的长mLRs R 度，必有 。例如，给出三点 、 、 ，组成边长为 1 的正三角sABC 形。对点集 的斯坦纳最小树的长度为 ，而最优树长度为 2。因,ABC3 此， 。也就是说，添加斯坦纳点后可以节省约 13%的长度。30.862smLR 引入以下定理： 定理 32smLR 下面我们介绍最小逐步调优法的原理： 设正则点集 中有 个点 ，坐标为 。并记Zn,1,2ixyn ，ii|1,2iXxn ，ma|i ，in|,iYy 。ax|12in 根据性质 4，辅助点的投放范围可以
25、控制在矩形 之内。min,i,maxRXY 本文逐步调优法的思路是这样的： 首先求出正则点集 的最小生成树 ,相应的树长为 。设 表示辅Z0T0|Tk 助点数，让 分别取值 1 到 ，对于每一个 值，在范围 内随机投放 个k2nkR 辅助点，产生辅助点集 ，然后用 算法计算出由 个点组成的集FPrimnk 的最小生成树。这样就获得 棵树，根据它们的树长，计算出一个概ZU 率分布，树长越短者，相应的概率越大。然后按此分布随机抽样，树长越短， 被抽中的概率就越大。对被抽中的树，对其每个辅助点，在一个小领域范围内 随机作扰动，产生一个新的近似解，这样重复多次择优记录最好者，若比原来 的要好，则替换它
26、，否则不变。重算概率分布，再抽样调优，这样重复到预定 13/33 循环次数为止。这里不直接选树长最短者来调优，是为了避免算法陷入局部极 值，不是最短的树也有机会被抽中。上述过程完成后，还需做最后的调整：删 掉 1 度和 2 度的辅助点（若有的话），利用求解斯坦纳点坐标的计算式，并把 3 度辅助点调整到最优位置，使其变为斯坦纳点。 完成以上过程后，获得一个近似最优解 ，若树长 ，则输出 ，*T*0|T* 否则输出 。0T 下面我们阐述一下逐步调优法的实施步骤： 1.用 算法求出正则点集 的最小生成树 。PrimZ0T 2.依次让 k 取值 1 到 ，在矩形 R 内随机投放 k 个辅助点，产生辅助
27、点2n 集 ，然后用 算法计算出由 个点组成的集 的最小生成树，树长FrikZU 记为 。|kT 3.记 ， ， ，这样得到了一个离散的概率1|kS21knjSP,2n 分布，并记 ， 。1 kiq, 4.产生一个0，1 均匀分布的随机数 ，若满足 ，则对 的辅助r1kkqrkT 点位置作扰动，不是随机重投，而是每个辅助点在一个半径为 的邻域内随机h 走一步（当然不能走出 的范围）。这一步重复大约 20 次，择优记录最好者，R 若比原来的要好，则替换它，否则 不变。kT 5.重复步骤 3 和 4，知道大道预设的最大迭代次数位置，此时的最好解记为 。*T 6.统计 中辅助点的度。* 7.检查和优
28、化 的辅助点。若有 1 度辅助点，则显然应把该点连同关联边T 删去；若有 2 度辅助点，则应把该点连同关联边删去，但要添加一条连接两个 邻点的边。若有 3 度辅助点，一般它不是斯坦纳点，需要矫正。按照斯坦纳点 的坐标计算公式，把该 3 度辅助点移动到该坐标位置上，调整后得到新的 。*T 8.重复步骤 6 和 7，大约 10 次，若最后树长 ，则输出 ，否则输*0|T 出 。如果有 1 度辅助点被删除，则0T 14/33 会影响相邻点的度；如果有两个 3 度辅助点相邻，则校正了 1 个辅助点成斯坦 纳点后，另一个辅助点可能又变得不在最佳位置。 因此，第 6、7 步的重复是必要的，反复多次调优，才
29、能逐步逼近最优位置。 5.2.2. 模型建立与求解、检验 根据上述的逐步调优法，由本题 ，随机分布 个斯坦纳8nk1,26 点，通过离散概率随机抽取相应的斯坦纳点进行扰动，直到得到最优解，并解 出新修路的总长度为 363.1 米。其对应的公园道路设计图如下： 利用问题一中相同的 算法对结果进行验算，看所求得道路是否满足Dijkstra 1.4 倍这一条件。所得到的 矩阵为：udge 由于矩阵中无负元素，故检验得所求道路满足题目要求。 15/33 5.3. 问题三 5.3.1. 问题解析 问题三在问题二的基础上增加了约束条件不能经过道路的区域，这也 给题目增加了很大的难度。为此，我们在分析了数据
30、特点及湖位置的基础上， 根据问题一中的计算任意两入口间折线距离的方法，我们确定了在不添加道路 交叉点的情况下就可满足折线距离小于两入口直线距离 1.4 倍的条件的几条边。 经过分析，只有入口 和入口 在不添加道路交叉点的情况下不能25P26P 满足题中要求。故只需要添加一个道路交叉点使 这三点满足两入口直线256, 距离的 1.4 倍这一条件，并且使新增的道路总长度最小；经分析，该点即为斯 坦纳点。在问题二的基础上，利用欧式距离斯坦纳最小树的逐步调优法进行相 关扰动，最终确定斯坦纳点并进行验算。 5.3.2. 模型建立与求解、检验 根据问题二的理论依据，因为有 三个点，故只需要添加一个斯坦纳2
31、56,P 点即可。利用迭代思想，在该点的邻域内进行扰动，添加道路交叉点使 这三点满足两入口直线距离的 1.4 倍，并且使道路总长度尽可能小。经256,P 多次验算，我们确定了一个斯坦纳点 。计算可得道路长度和为 324.65,80S 米，其相应的公园道路设计图为： 同问题一、问题二一样的验算原理，可算得此设计满足题中各要求。 16/33 6. 结果表示 6.1. 问题一 道路设计图： 问题一方案新修路的总路程：394.5 米 6.2. 问题二 道路设计图： 问题二方案新修路的总长度：363.1 米 6.3. 问题三 17/33 道路设计图： 问题三方案新修路的总长度：324.6 米 7. 模型
32、的评价、优化及推广 7.1. 模型的评价 1) 问题一的求解思路是先用 算法得到是不带环的最小树，把边加krusal 入最小树再利用 算法依据题中条件进行验算，这样得到的结果Dijt 可能不是最优解； 2) 问题一中，模型一利用 算法和 算法分两个步骤得到精krusalDijkstra 确最优解的前提是假设所修道路均为直线，公园内部有且仅有给出的 四个道路交叉点。而事实上是可以再添加道路交叉点的，此类问题便 同问题二一样属于 难问题，也就是说,，当问题含有其他约束条件NP 时,，要想求得真正的最优解是不现实的，为此，必需采取灵活多样的 方式和方法, 求近似得最优解； 3) 问题二在问题一的基础
33、上可随意添加道路交叉点，添加点的个数和位 置均不确定，成为 难问题，无法找到精确最优解。本问题中的算法NP 都只是近似算法, 所得最优设计方案也只是近似最优解； 4) 问题二、三所用算法利用人工扰动精度不高且效率较低； 5) 问题三求解是在可利用湖的四边而不算入所修总路程的假设下，具有 18/33 一定的理想局限性。 7.2. 模型的优化 我们发现，在问题一的步骤二中用 算法对最短路径进行验算的时Dijkstra 间代价较高，若用传统的方法通过扫描整个网络图的顶点来搜索最小值，总时 间代价为 ，如果将模型应用到顶点数多的环境中，那么效率将非常低。2On 经查阅相关文献2后，我们认为利用二叉堆来
34、进行优化，便可快速访问到具有 最小值的点，时间代价仅为 。具体思路如下：logOn 设 为最短距离已确定的顶点集（看作红点集）， 是最短距离尚未确S VS 定的顶点集（看作蓝点集）。初始化时，只有源点 的最短距离是已知的s ，其余各点的估计最短距离 值均设为无穷大。用数组 记录从()0Ds DDv 源点 到达 外中间不经过任何蓝点（若有中间点，则必为红点）的“最短”路v 径长度（简称估计距离）。经过一次循环后，红点集 ，其余各点的估计Ss 最短距离 值更新为该点到源点而中间不经过任何点的边的权值。若路径不存 在则仍为无穷大；在蓝点集中选择一个最短距离最小的蓝点 来扩充红点集是k 算法的关键。若
35、能快速访问到具有最小 值的蓝点，则可大大减少算Dijkstra D 法的时间复杂度。若用传统的方法通过扫描整个网络图的顶点（即穷举法）来 搜索最小值，总时间代价为 。在 算法中，由于累计权值决定的最2Onijkstra 短路径具有优先程度差异特征，所以若将未被处理的顶点的最短路径 值构造D 优先级队列，则可大大提高算法的效率。用堆来实现优先级队列是很自然的。 堆是一种抽象数据结构，由一系列元素集合构成，每个元素有个实数类型的关 键字。而二叉堆是一种最普及的数据结构，它可被视为一棵完全二叉树。堆有 最大堆和最小堆两种。最小堆结构必须满足以下性质：除了根节点，每个节点 的值不小于其父节点的值这样，
36、堆中的最小元素就存在根节点中。因为具有 个元素的二叉堆是一棵完全二叉树，其高度为 。所以对于二叉堆的操作n logn 例如 (插入)和 (从堆中删除并返回最有最小关键字的元素)，其isertremovin 作用时间至多与树的高度成正比，为 。所以，将未被处理的顶点以lO 19/33 值大小为顺序保存在一个最小堆中，可以使用 次搜索找出下一个最DlogOn 近顶点。每次改变 值时，都可以通过先删除再重新插入的方法改变顶点菇Dx 在堆中的位置。为了实现优先更新需要将每个顶点连同它的数组下标存储在堆 中，其时间复杂度在算法实现部分分析。 对于问题二采用的求斯坦纳最小树的逐步调优法，由于离散概率的不确
37、定 性，所以采用迭代的次数较多，过程较繁，相应地，效率也就降低了。针对这 一问题，可以采用多路径并行搜索蚁群算法的并行搜索机制进行相关优化。其 具体原理如下： 多路径并行搜索蚁群算法将每只蚂蚁的求解过程分解为 m 条路径并行的搜 索，其中 m 为终端节点的个数。每条路径对应从一个终端节点出发，直至满足 某个条件终止。利用该方法路径搜索的终止条件是刚访问过的节点已经出现在 其他路径上，即当前路径与其他路径发生相交，则当前路径设置为不活跃状态， 本路径终止搜索节点。若当前蚂蚁的所有的路径都终止时，蚂蚁在该轮迭代中 搜索节点的过程也终止。蚂蚁在这步操作完成之后即得到一个节点的集合，该 集合由这 m
38、条路径上的所有节点构成，包括了所有终端节点和当前蚂蚁认为必 要的一些中间节点，这个过程极为蚂蚁选择节点的过程。 7.3. 模型的推广 由于本题采用图论模型的方法求解，分析了在不同的限制条件下道路长度 和最短的数学模型及求解，并提出能够找到该近似算法或原则，可以较好的推 广到解决交通网络、输油管道、灾情巡视线路、投递、旅行商等实际问题。 8. 参考文献 1 林健良，施美珍，朱晓清，何明芳。求解欧式距离斯坦纳最小树的逐步调 优法。广州：华南理工大学理学院，2011。 2 林小玲，何建农，周勇。带限制条件的最短路径算法与实现。福州：福州 大学学报（自然科学版），2004。 3 张瑾，马良。 最小树问
39、题及其应用。上海，开封：科学技术与工程，Steinr 2008。 20/33 4 杨凌云。图的 最小树问题及其求解。开封：电脑知识与技术，steinr 2009。 9. 附件清单 1. 附件 1： 算法求最小生成树的 代码及结果显示；krusal MATLB 2. 附件 2：求已知道路的情况下任意两入口间最短距离的 函数Dijkstra 代码；MATLB 3. 附件 3：构造的距离矩阵 ， 为只包含联通边的距离矩阵；dist 4. 附件 4：求解斯坦纳点的 C 语言代码； 5. 附件 5：问题二中部分斯坦纳点扰动过程 6. 附件 6：利用外矩形边框验算任意两点间距离的 1.4 倍条件的 C 语
40、言代码； 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+
41、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 21/33 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; %若构成圈，则将该边对应的 ind
42、ex 项标记为 0，以便除去 else i=i+1; %若没有构成圈，则 i 加 1，加入下一边检测 end index=index(index0); %将构成圈的边从 index 中除去 if i=len break; %找到符合条件的点数减一条的边，即找到一个最小支撑树 end end index=index(1:len-1); %截短 index 矩阵，保留前 len-1 项 % 结果显示 % s=sprintf(nt%st%st %st,边端点,距离, 是否在最小支撑树 ); for i=1:count-1 edge_tmp=edge(i,:); if isempty(find(ind
43、ex=i,1) s_tmp=sprintf(n t (%d,%d)t %dt %st,edge_tmp(2),edge_tmp(3),edge_tmp(1),); else s_tmp=sprintf(n t (%d,%d)t %dt %st,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：原图的点数 %原理：不断除去出现次数小于
44、2 的端点所在的边，最后观察是否有边留下 len=length(w(:,1); index=1:len; 22/33 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(pD(j)+A
45、(j,k) D(k)=D(j)+A(j,k); parent(k)=j; end end end distance=D(e); % the shortest distance path 24/33 if parent(e)=0 return; end path=zeros(1,2*n); % path preallocation t=e; path(1)=t; count=1; while t=s path=p path(1:count); t=p; count=count+1; end if count=2*n error(The path preallocation length is t
46、oo 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 0 110
47、 300 300 300 300 300 300 300 300 300; 300 110 0 300 300 300 300 300 300 300 300 300; 300 300 300 0 130 300 300 300 300 300 300 300; 300 300 300 130 0 85 300 300 300 300 300 300; 300 300 300 300 85 0 25 300 300 300 300 300; 300 300 300 300 300 25 0 85 300 300 300 300; 300 300 300 300 300 300 85 0 300
48、 300 300 300; 300 300 300 300 300 300 300 300 0 300 300 300; 300 300 300 300 300 300 300 300 300 0 300 300; 300 300 300 300 300 300 300 300 300 300 0 300; 300 300 300 300 300 300 300 300 300 300 300 0; s=sqrt(x(i)-x(j).2+(y(i)-y(j).2); for k=1:1:length(i) 25/33 dist(i(k),j(k)=s(k); dist(j(k),i(k)=s(k); end distance=zeros(length(x); %distance 为任意两点间距离矩阵 d=zeros(8); judge=zeros(8); for p=1:1:8 for q=(p+1):1:8 distance(p,q)=sqrt(x
