电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

数学建模论文基于贪婪算法的公园内道路设计模型

数学建模论文基于贪婪算法的公园内道路设计模型_第1页
1/17
数学建模论文基于贪婪算法的公园内道路设计模型_第2页
2/17
数学建模论文基于贪婪算法的公园内道路设计模型_第3页
3/17
精品文档---下载后可任意编辑目录基于贪欲算法的公园内道路设计模型 1摘要 1 问题重述 2 问题分析 问题 1 的分析 问题 2 的分析 问题 3 的分析 3 模型假设 4 符号说明 5 模型的建立与求解 问题 1 模型建立与求解 问题 1 模型的建立 问题 1 模型的求解 问题 2 模型的建立与求解 问题 2 模型的建立 问题 2 模型的求解 问题 2 模型的结果对比 问题 3 模型的建立与求解 问题 3 模型的建立 问题 3 模型的求解 问题 3 模型结果分析 6 模型评价 模型的优点 模型的缺点 7 模型推广 8 参考文献 9 附录 基于贪欲算法的公园内道路设计模型摘要本题通过公园内部规划设计道路,在已有的边界条件下,找出相应的最短路径最优解,可利用贪欲算法,通过局部优化逐步逼近最优解。对问题 1,以给定的四个交叉点的情况下,寻找公园内的最短道路最优解,并满足约束条件。根据贪欲算法的基本原理,可以先用经典算法 prim 或 kruskal 对组成的点集构造最小生成树,再用 floyd 算法逐个筛选在最小生成树下的解,通过边和点集的不断更换,求得任意两点间的最短路径矩阵,进而求解最短道路的最优集。对问题 2,考虑到交叉点的位置选取与交叉点数目对问题的双重影响,通过列举 0,1,2,3四个情况下可能存在的交叉点进行建模。特别考虑到,任意两点间的最短路径要满足小于1.4 两点间直线距离,可以利用椭圆的相关性质,在矩形区域相做交叉点的交点点集,简化问题 2 对交点位置的穷举过程。利用局部优化,在矩形区域内分别建立 H 型交叉点模型和双 Y型交叉点模型,再通过交叉点数目的变化,求解得两种模型下的最优解,并进行对比,分析此两种模型下的最优程度,做出评判标准和相应交叉点坐标。对问题 3,利用公园内增加矩形湖这一约束条件,对问题 2 中的不用交叉点模型进行验证,通过合理假设湖边道路存在并不计入总道路长,简化模型的操作,通过交替迭代法,建立在H 型交叉点模型和双 Y 型交叉点模型基础上的局部最优解。再根据穷举法,对矩形区域内所有的点进行最优求解。并通过交替迭代法与穷举法的多次使用,逐步逼近全局最优解。对 3 个问题的综合分析后,贪欲算法下的最短路径最优解还可以在城市规划中,利用不同交叉点模型的局部优化程度的不同性,按功能和价值等对城市进行合理规划。关键词:贪欲算法局部最优解最小生成树 Floyd prim 逐次逼近1 问题重述现计划建一个形状为...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

数学建模论文基于贪婪算法的公园内道路设计模型

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部