关于贪婪算法的公园内道路设计模型.pdfVIP

基于贪婪算法的公园内道路设计模型 摘要 本题通过公园内部规划设计道路，在已有的边界条件下，找出相应的最 短路径最优解，可利用贪婪算法，通过局部优化逐步逼近最优解。 对问题 1，以给定的四个交叉点的情况下，寻找公园内的最短道路最优解， 并满足约束条件。根据贪婪算法的基本原理，可以先用经典算法 prim 或 kruskal 对组成的点集构造最小生成树，再用 floyd 算法逐个筛选在最小生成 树下的解，通过边和点集的不断更换，求得任意两点间的最短路径矩阵，进 而求解最短道路的最优集。 对问题 2，考虑到交叉点的位置选取与交叉点数目对问题的双重影响，通 过列举 0,1,2,3 四个情况下可能存在的交叉点进行建模。特别考虑到，任意 两点间的最短路径要满足小于 1.4 两点间直线距离，可以利用椭圆的相关性 质，在矩形区域相做交叉点的交点点集，简化问题 2 对交点位置的穷举过程。 利用局部优化，在矩形区域内分别建立 H 型交叉点模型和双 Y 型交叉点模型， 再通过交叉点数目的变化，求解得两种模型下的最优解，并进行对比，分析 此两种模型下的最优程度，做出评判标准和相应交叉点坐标。 对问题3，利用公园内增加矩形湖这一约束条件，对问题 2 中的不用交叉 点模型进行验证，通过合理假设湖边道路存在并不计入总道路长，简化模型 的操作，通过交替迭代法，建立在 H 型交叉点模型和双 Y 型交叉点模型基础 上的局部最优解。再根据穷举法，对矩形区域内所有的点进行最优求解。并 通过交替迭代法与穷举法的多次使用，逐步逼近全局最优解。 对 3 个问题的综合分析后，贪婪算法下的最短路径最优解还可以在城市 规划中，利用不同交叉点模型的局部优化程度的不同性，按功能和价值等对 城市进行合理规划。 关键词：贪婪算法 局部最优解 最小生成树 Floyd prim 逐次逼近 1 1 问题重述 现计划建一个形状为矩形公园，公园计划有若干个入口，需要建立一个 模型去设计道路让任意两个入口相连，使总的道路长度和最小 （公园四周不 计入总长），前提要求是任意的两个入口之间的最短道路长不大于两点连线的 1.4 倍。设计对象可为如图 1 所示，长 200 米，宽 100 米的矩形公园。 要求公园内新修的道路与四周的连接只能与 8 个路口相通，而不能连到 四周的其它点，现要完成以下问题： 1、假定公园内确定要使用4个道路交叉点为：A(50,75) ，B(40,40) ， C(120,40)，D(115,70 ）。通过建立模型并给出算法使公园内道路的总路程最短， 画出道路设计，计算新修路的总路程。 2 、现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建 立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的 总路程。 3、若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周 的边，示意图见图2 ，重复完成问题2 的任务。 图1 公园入口坐标 2 问题分析 本题是一个道路设计的最优化的问题，即是如何利用已有的边界，使公 园内部新修路总长最小，同时满足以下两个约束条件： K1:任两个入口连通； K2:任两个入口的最短路径不超过其直线距离的 1.4 倍。 2.1 问题 1 的分析 找出四个交叉点下的最小路问题，可以根据 prim 算法，可以求得公园内 四个交叉点下的最小生成树，在此条件