文档介绍：编程
编程
建模
建模
组别: 7
建模
组员:
公园道路设计问题
组别:___________
建模
目录
基于贪婪算法的公园内道路设计模型 1
摘要 1
1 问题重述 2
2 问题分析 2
3
3
3
3 模型假设 3
4 符号说明 3
5 模型的建立与求解 4
4
4
6
8
8
9
11
14
14
14
18
6模型评价 19
20
20
7模型推广 20
8参考文献 21
9附录 21
基于贪婪算法的公园内道路设计模型
摘要
本题通过公园内部规划设计道路,在已有的边界条件下,找出相应的最短路径最优解,可利用贪婪算法,通过局部优化逐步逼近最优解。
对问题1,以给定的四个交叉点的情况下,寻找公园内的最短道路最优解,并满足约束条件。根据贪婪算法的基本原理,可以先用经典算法prim或kruskal对组成的点集构造最小生成树,再用floyd算法逐个筛选在最小生成树下的解,通过边和点集的不断更换,求得任意两点间的最短路径矩阵,进而求解最短道路的最优集。
对问题2,考虑到交叉点的位置选取与交叉点数目对问题的双重影响,通过列举0,1,2,3四个情况下可能存在的交叉点进行建模。特别考虑到,,可以利用椭圆的相关性质,在矩形区域相做交叉点的交点点集,简化问题2对交点位置的穷举过程。利用局部优化,在矩形区域内分别建立H型交叉点模型和双Y型交叉点模型,再通过交叉点数目的变化,求解得两种模型下的最优解,并进行对比,分析此两种模型下的最优程度,做出评判标准和相应交叉点坐标。
对问题3,利用公园内增加矩形湖这一约束条件,对问题2中的不用交叉点模型进行验证,通过合理假设湖边道路存在并不计入总道路长,简化模型的操作,通过交替迭代法,建立在H型交叉点模型和双Y型交叉点模型基础上的局部最优解。再根据穷举法,对矩形区域内所有的点进行最优求解。并通过交替迭代法与穷举法的多次使用,逐步逼近全局最优解。
对3个问题的综合分析后,贪婪算法下的最短路径最优解还可以在城市规划中,利用不同交叉点模型的局部优化程度的不同性,按功能和价值等对城市进行合理规划。
关键词:贪婪算法局部最优解最小生成树 Floyd prim 逐次逼近
1 问题重述
现计划建一个形状为矩形公园,公园计划有若干个入口,需要建立一个模型去设计道路让任意两个入口相连,使总的道路长度和最小(公园四周不计入总长),。设计对象可为如图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:。
找出四个交叉点下的最小路问题,可以根据prim算法,可以求得公园内四个交叉点下的最小生成树,在此条件下利用Floyd算法计算出任意两点之间的最短路径,做出最短路径矩阵
并进行校对。
在问题1的基础上,解决问题2的关键在于交叉点的数目与位置的分析与求解,,容易发现若以其中任意两点为焦点利用椭圆的几何性质就可以求得交叉点大致范围,同时在交叉点数目m为{1,2,3….}时,再次利用问题1求解此条件下的最小路径问题。
利用问题2中的不同交叉