基于贪婪算法的公园内道路设计模型

《基于贪婪算法的公园内道路设计模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于贪婪算法的公园内道路设计模型摘要本题通过公园内部规划设计道路，在已有的边界条件下，找出相应的最短路径最优解，可利用贪婪算法，通过局部优化逐步逼近最优解。对问题1，以给定的四个交叉点的情况下，寻找公园内的最短道路最优解，并满足约束条件。根据贪婪算法的基本原理，可以先用经典算法prim或kruskal对组成的点集构造最小生成树，再用floyd算法逐个筛选在最小生成树下的解，通过边和点集的不断更换，求得任意两点间的最短路径矩阵，进而求解最短道路的最优集。对问题2，考虑到交叉点的位置选取与交叉点数目对问题的双重影响，通过列举0,1,2,3四个情况下可能存在的交叉点进

2、行建模。特别考虑到，任意两点间的最短路径要满足小于1.4两点间直线距离，可以利用椭圆的相关性质，在矩形区域相做交叉点的交点点集，简化问题2对交点位置的穷举过程。利用局部优化，在矩形区域内分别建立H型交叉点模型和双Y型交叉点模型，再通过交叉点数目的变化，求解得两种模型下的最优解，并进行对比，分析此两种模型下的最优程度，做出评判标准和相应交叉点坐标。对问题3，利用公园内增加矩形湖这一约束条件，对问题2中的不用交叉点模型进行验证，通过合理假设湖边道路存在并不计入总道路长，简化模型的操作，通过交替迭代法，建立在H型交叉点模型和双Y型交叉点模型基础上的局部最优解。再根据穷

3、举法，对矩形区域内所有的点进行最优求解。并通过交替迭代法与穷举法的多次使用，逐步逼近全局最优解。对3个问题的综合分析后，贪婪算法下的最短路径最优解还可以在城市规划中，利用不同交叉点模型的局部优化程度的不同性，按功能和价值等对城市进行合理规划。关键词：贪婪算法局部最优解最小生成树Floydprim逐次逼近11问题重述现计划建一个形状为矩形公园，公园计划有若干个入口，需要建立一个模型去设计道路让任意两个入口相连，使总的道路长度和最小（公园四周不计入总长），前提要求是任意的两个入口之间的最短道路长不大于两点连线的1.4倍。设计对象可为如图1所示，长200米，宽100米

4、的矩形公园。要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点，现要完成以下问题：1、假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。通过建立模型并给出算法使公园内道路的总路程最短，画出道路设计，计算新修路的总路程。2、现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。3、若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，示意图见图2，重复完成问题2的任务。图1公园入口坐标2

5、问题分析本题是一个道路设计的最优化的问题，即是如何利用已有的边界，使公园内部新修路总长最小，同时满足以下两个约束条件：K1:任两个入口连通；K2:任两个入口的最短路径不超过其直线距离的1.4倍。2.1问题1的分析找出四个交叉点下的最小路问题，可以根据prim算法，可以求得公园内四个交叉点下的最小生成树，在此条件下利用Floyd算法计算出任意两点之间2的最短路径，做出最短路径矩阵并进行校对。2.2问题2的分析在问题1的基础上，解决问题2的关键在于交叉点的数目与位置的分析与求解，利用本题中对最小路径的1.4倍约束，容易发现若以其中任意两点为焦点利用椭圆的几何性质就可

6、以求得交叉点大致范围，同时在交叉点数目m为{1,2,3….}时，再次利用问题1求解此条件下的最小路径问题。2.3问题3的分析利用问题2中的不同交叉点模型下的最短路径最优解，主要分析此条件下的路径与湖的交叉问题，通过合理的假设令湖边的路长不计入总路长，利用穷举法，对最优路径逐步逼近得到最优解。3模型假设1、忽略道路宽度，交叉点的不影响道路长度；2、问题3中的沿湖道路长度不计入总道路长度；3、所有的道路均为直线，门与交叉点均为点参与计算；4、任意两点间最短路径不构成环路。4符号说明在模型构建过程中，为简化说明，将主要参与模型中计算的量用符号表示，如表1所示：表1运算

7、符号说明符号说明Pi公园入口数（i=1,2,3….8）Ai公园内的点数（i=1,2,3…n）m公园内的交叉点数（m=n-8）dij从i点到j点的距离Ddij所构成的距离矩阵DsD矩阵的控制矩阵Ds=1.4Dsij从i点到j点的最短路径距离S从i点到j点的最短距离矩阵xij0~1决策变量Xxij所构成的决策变量矩阵3根据上述说明，符号间还满足下列关系：d11d1nDddn1nn其中，Ds1.4D，同时s11s1nxx111nSXsn1snnxn1xnn其中xij满足

8、0-1决策变量0，表