基于Floyd算法的道路优化设计问题.docx

数学建模基于 Floyd算法的公园道路优化设计问题小组编号：02小组成员：队员1聪- 建模队 员 2汪涛- 建模队 员 3胡娜- 建模队 员 4薛向龙- 建模队 员 5蔡诗聂- 编程队 员 6杨志诚- 编程.2012 年 7 月 21 日基于 Floyd 算法的公园道路优化设计问题摘要本文主要研究了以公园内部道路修建为背景的路径优化问题。对于问题一， 已知四个交叉点的情况下， 考虑到边缘道路不计入修建道路总长的题目要求和最短道路长不大于两点连线1.4 倍前提要求，首选边缘路径，将那些无需借助交叉点即可满足1.4 倍前提要求的点从考虑范围内剔除。然后对剩余不满足条件的路径运用Kruskal 算法，生成最小生成树的路径， 再在此基础上， 利用 Floyd 算法，找出其中不符合1.4 倍约束的路径的边，综合对其路径进行调整并将满足条件的所有路径的边用穷举法进行筛选，最终选取最优路径， 其总路程为 S3