公园内道路有条件限制的设计最短路径数模论文(编辑修改稿)

公园内道路有条件限制的设计最短路径数模论文(编辑修改稿)内容摘要：

问题一相比，问题二没有规 定公园内必须通过的点，属于斯坦纳最小生成树问题。 考虑到任意两点之间可以直接相连，我们采用求解欧式距离的斯坦纳点最小树的逐步调优法。 我们先引入斯坦纳最小树的定义： 定义 已知 欧式平面上任给 的 有限点集  12, , , nR v v v ，欲求出一个 点 集 12, , , kS s s s ， 使 点集 RS 的连线 长度最短 所构成 的图，必然是边数最少的连通图，因此它为树，称为 斯坦纳最小树 ，记为 SRT。 R 中的点为 SRT 上的固定点， S 中的点称为 SRT 上的斯坦纳点 ，简称为 斯坦纳点。 由于本问题可以自由 添 加道路交叉点，我们引入 SRT 的一些性质： 性质 1 SRT 上每个点之多关联三条边，而每个斯坦纳点恰好关 联三条边。 性质 2 SRT 上，关联于同一点的任何两边的夹角不小于 120 ；关联于同一斯坦纳点的任何两边的夹角恰为 120。 性质 3 若  12, , , nR v v v ，则 SRT 中斯坦纳点的个数不大于 2n。 性质 4 欧式斯坦纳最小树的每个斯坦纳点都 必定包含在全部正则点的最小凸包内。 添加斯坦纳点的斯坦纳最小树，往往会比 不添加斯坦纳点的最优树的长度更短些。 即若以  mLR和  sLR分别表示点集 R 的最优树和斯坦纳最小树的长 12/33 度，必有    smL R L R。 例如，给出三点 A 、 B 、 C ， 组成边长为 1 的正三角形。 对点集  ,R A B C 的斯坦纳最小树的长度为 3 ，而最优树长度为 2。 因此，   3 0 .8 6 62smLRLR 。 也就是说，添加斯坦纳点 后可以节省约 13%的长度。 引入以下定理： 定理    32smLRLR 下面我们 介绍 最小逐步调优法的原理： 设正则点集 Z 中有 n 个点  2n ，坐标为  , , 1, 2, ,iix y i n。 并记 m in m in | 1 , 2 ,iX x i n，  m a x m a x | 1 , 2 ,iX x i n，  m in m in | 1, 2 ,iY y i n，  m a x m a x | 1 , 2 ,iY y i n。 根据性质 4，辅助点的投放范围可以控制在矩形   m i n , m a x m i n , m a xR X X Y Y之内。 本文逐步调优法的思路是这样的 ： 首先求出正则点集 Z 的最小生成树 0T ,相应的树长为 0||T。 设 k 表示辅助点数，让 k 分别取值 1 到 2n ，对于 每 一个 k 值，在范围 R 内随机投放 k 个 辅助点，产生辅 助 点集 F ， 然后用 Prim 算法计算出由 nk 个点组成的集 ZU 的最小生成树。 这样就获得 2n 棵树，根据它们的树 长，计算出一个概率分布 ， 树长越短者，相应的概率越大。 然后按此分布随机抽样，树长越短，被抽 中 的概率就越大。 对被抽中的树，对其每个辅助点，在一个小领域范围内随机作扰动，产生一个新的近似解，这样重复多次择优记录最好者， 若比原来的要好，则替换它，否则不变。 重 算概率分 布，再抽 样调优，这样重复到预定循环次数为止。 这里不直接选树长最短者来调优，是为了避免算法陷入 局部极值，不是 最短的树也有机会被抽中。 上述过程完成后，还需做最后的调整 ： 删掉 1 度和 2 度的辅助点 （ 若有的话 ） ，利用 求解斯坦纳点坐标的计算 式，并把 3 度辅助点调整到最优 位置 ，使其变为斯坦纳点。 13/33 完成以上过程后，获得一个近似最优解 *T ，若树长 * 0| | | |TT ， 则输出 *T ，否则输出 0T。 下面我们阐述一下 逐步调优法的实施 步骤 ： Prim 算法求出正则点集 Z 的最小生成树 0T。 k 取值 1 到 2n ，在矩形 R 内随机投放 k 个 辅助点， 产生辅 助 点集F ， 然后用 Prim 算法计算出由 nk 个点组成的集 ZU 的最小生成树 ，树长记为 ||kT。 1||k kS T，21kk njjSPS ，  1, 2, , 2kn，这样得到了一个离散的概率分布，并记1kkiiqP，  1, 2, , 2kn。 [0， 1]均匀分布的随机数 r ，若满足 1kkq r q  ，则对 kT 的辅助点位置作扰动，不是随机重投，而是每个辅助点在一个半径为 h 的邻域内随机走一步（当然不能走出 R 的范围）。 这一步重复大约 20 次，择优记录最好者，若比原来的要好，则替换它，否则 kT 不变。 3 和 4，知道大道预设的最大迭代次数位置，此时的最好解记为*T。 *T 中辅助点的度。 *T 的辅助点。 若有 1 度辅助点，则显然应把该点连同关联边删去；若有 2 度辅助点，则应把该点连同关联边删去，但要添加一条连接两个邻点的边。 若有 3 度辅助点，一般它不是斯坦纳点，需要矫正。 按照斯坦纳点的坐标计算公式，把该 3 度辅助点移动到该坐标位置上，调整后得到新的 *T。 6 和 7，大约 10 次， 若 最后 树长 * 0| | | |TT ， 则输出 *T ，否则输出0T。 如果有 1 度辅助点被删除，则会影响相邻点的度；如果有两个 3 度辅助点相邻，则校正了 1 个辅助点成斯坦纳点后，另一个辅助点可能又变得不在最佳位置。 因此，第 7 步的重复是必要的，反复多次调优，才能逐步逼近最优位置。 14/33 . 模型建立 与求解、检验 根据上述的逐步调优法，由本题 8n ，随机分布 k  1,2, ,6k  个斯坦纳点，通过离散概率随机抽取相应的斯坦纳点进行扰动，直到得到最优解 ，并解出新修路的总长度为 米。 其对应的 公园道路设计图 如下： 利用问题一中相同 的 Dijkstra 算法 对结果进行验算，看所求得道路是否满足 倍这一条件。 所得到的 judge 矩阵为： 由于矩阵中无负元素，故 检验得 所求道路满足题目要求。 . 问题三 . 问题 解析 问题三在问题 二的基础上增加了约束条件 —— 不能经过道路的区域，这也给 15/33 题目增加了很大的难度。 为此，我们在分析了数据特点及湖位置的基础上，根据问题一中的计算任意两入口间折线距离的方法，我们 确定了 在不添加道路交叉点的情况下 就可满足折线距离小于两入口直线距离 倍的条件的 几条 边。 经 过 分析 ， 只有入口 25PP 和 入口 26PP 在不添加道路交叉点的情况下不 能 满足题中要求。 故只需要添加 一个 道路交叉点使 2 5 6,P P P 这三点满足两入口直线距离的 倍这一条件 ，并且使新增的道路总长度最小；经分析，该点即为斯坦纳点。 在 问题二 的基础上，利用 欧式距离斯坦纳最小树的逐步调优法进行相关 扰动 ， 最终 确定斯坦纳点 并进行验算。 . 模型建立 与求解、检验 根据问题二的理论依据，因为 有 2 5 6,P P P 三个点，故只需要添加一个斯坦纳点即可。 利用迭代 思想 ，在该点的邻域内进行扰动 ，添加道路交叉点使 2 5 6,P P P 这三点满足两入口直线距离的 倍 ，并且使道路 总长度尽可能小。 经多次验算，我们确定了一个斯坦纳点  55,80S。 计算可得道路长度和为 米， 其相应的公园道路设计图为： 同问题一、问题二一样的验算原理，可算得此设计满足题中各要求。 6. 结果表示 . 问题一 16/33 道路设计图： 问题一方案 新修路的总路程： 米 . 问题二 道路设计图： 问题二方案 新修路的总长度： 米 . 问题三 道路设计图： 17/33 问题三方案 新修路的总长度： 米 7. 模型的评价 、优化及 推广 . 模型的评价 1) 问题一的求解思路是先用 kruskal 算法得到是不带环的最小树， 把 边加入最小树再利用 Dijkstra 算法 依据题中条件进行验算，这样得到的结果可能不是最优解； 2) 问题一中，模型一 利用 kruskal 算法 和 Dijkstra 算法 分两个步骤得到精确最优解的前提是假设所修道路均为直线， 公园内部有且仅有给出的四个道路交叉点。 而事实上 是可以再添加道路交叉点的 ， 此类 问题 便同问题二一样 属于 NP 难问题，也就是说 ,，当问题含有其他约束条件时 ,，要想求得真正的最优解是不现实的，为此， 必需采取灵活多样的方式和方法 , 求近似得最优解； 3) 问题二在问题一的基础上 可随意添加道路交叉点，添加点的个数和位置均不确定， 成为 NP 难问题，无法找到精确最优解。 本问题中的算法都只是近似算法 , 所得最优设计方案 也只是近似最优解； 4) 问题二、三所用算法利用人工扰动精度不高且效率较低； 5) 问题 三求解是在 可利用湖的四边而不算入所修总路程的假设下，具 有一定的理想局限性。 18/33 . 模型的优化 我们发现，在问题一的步骤二中用 Dijkstra 算法 对最短路径进行验算 的 时间代价较高， 若用传统的方法通过扫描整个网络图的顶点来搜索最小值，总时间代价为  2On ，如果将模型应用到顶点数多的环境中，那么效率将非常低。 经查阅相关文献 [2]后，我们认为利用二叉堆来进行优化，便可快速访问到具有最小值的点，时间代价仅为  logOn。 具体思路如下： 设 S 为最短距离已确定的顶点集（看作红点集）， VS 是最短距离尚未确定的顶点集（看作蓝点集）。 初始化时，只有源点 s 的最短距离是已知的( ( ) 0)Ds   ，其余各点的估计最短距离 D 值均设为无穷大。 用数组 Dv记录从源点 s 到达 v 外中间不经过任何蓝点（若有中间点，则必为红点）的“最短”路径长度（简称估计距离）。 经过一次循环后，红点集 Ss ，其余各点的估计最短距离 D 值更新为该点到源点而中间不经过任何点的边的权值。 若路径不存在则仍为无穷大； 在蓝点集中选择一个最短距离最小的蓝点 k 来扩充红点集是Dijkstra 算法的关键。 若能快速访问到具有最小 D 值的蓝点，则可大大减少算法的时间复杂度。 若用传统的方法通过扫描整个网络图的顶点（即穷举法）来搜索最小值，总时间代价为  2On。 在 Dijkstra 算法中，由于累计权值决定的最短路径具有优先程度差异特征，所以若将未被处理的顶点的最短路径 D 值构造优先级队列，则可大大提高算法的效率。 用堆来实现优先级队列是很自然的。 堆是一种抽 象数据结构，由一系列元素集合构成，每个元素有个实数类型的关键字。 而二叉堆是一种最普 及的数据结构，它可被视为一棵完全二叉树。 堆有最大堆和最小堆两种。 最小堆结构必须满足以下性质：除了根节点，每个节点的值不小于其父节点的值．这样，堆中的最小元素就存在根节点中。 因为具有 n 个元素的二叉堆是一棵完全二叉树，其高度为 logn。 所以对于二叉堆的操作例如 insert (插入 )和removemin (从堆中删除并返回最有最小关键字的元素 )，其作用时间至多与树的高度成正比，为  logOn。 所以，将未被处理的顶点以 D 值大小为顺序保存在一个最小堆中，可以使用  logOn次搜索找出下一个最近顶点。 每次改变 Dx值时， 都可以通过先删除再重新插入的方法改变顶点菇在堆中的位 置。 为了实现优 19/33 先更新需要将每个 顶点连同它的数组下标存储在堆中，其时间复杂度在算法实现部分分析。 对于问题二采用的求斯坦纳最小树的逐步调优法，由于离散概率的不确定性，所以采用 迭代的 次数较多，过程较繁 ，相应地，效率也就降低了。 针对这一问题， 可以采用 多路径并行搜索蚁群算法的并行搜索机制进行相关优化。 其具体原理 如下： 多路径并行搜索蚁群算法将每只蚂蚁的求解过程分解为 m条路径并行的搜索，其中 m为终端节点的个数。 每条路径对应从一个终端节点出发，直至满足某个条件终止。 利 用该方法路径搜索的终止条件是刚访问过的节点已经出现在其他路径上，即当前路径与其他路径发生相交，则当前路径设置为不活跃状态，本路径终止搜索节点。 若当前蚂蚁的所有的路径都终止时，蚂蚁在该轮 迭代中搜索节点的过程也终止。 蚂蚁在这步操作完成之后即得到一个节点的集合，该集合由这 m条路径上的所有节点构成，包括了所有终端节点和当前蚂蚁认为必要的一些中间节点，这个过程极为蚂蚁选择节点的过程。 . 模型的推广 由于本题采用图论模型的方法求解 ， 分析了在不同的限制条件下道路长度和最短的数学模型及求解， 并提出能够找到该近似算法或原则，可 以较好的推广到解决 交通网络、输油管道、 灾情巡视线路、投递、旅行商等实际问题。 8. 参考文献 [1] 林健良，施美珍，朱晓清，何明芳。 求解欧式距离斯坦纳最小树的逐步调优法。 广州：华南理工大学理学院， 20xx。 [2] 林小玲，何建农，周勇。 带限制条件的最短路径算法与实现。 福州 ：福州大学学报（自然科学版）， 20xx。 [3]。