精品文档---下载后可任意编辑目录基于贪欲算法的公园内道路设计模型 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 中的不用交叉点模型进行验证，通过合理假设湖边道路
