发布时间 : 星期六 文章公园内道路设计建模论文更新完毕开始阅读ac4d6a35f524ccbff12184ec
最短路径问题：
在联结图 G=(V,E)中， 顶点集E-> R+（即是权值为正） ，在点集V中的固定顶点s，寻找s到V中各顶点v的最短路径. Dijkstra算法:
Dijkstra算法是一种解决最短路径问题的非常有效的算法，时间复杂度为 O(|V|2)：
1.Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V| = 1 then stop, otherwise go to step 2.
2.For each v in V\\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v.
3.Find a vertex v which minimizes {L(v): v in V\\Si}, say ui+1. 4.Let Si+1 = Si cup {ui+1}.
5.Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 6.Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V| = 1 then stop, otherwise go to step 2. 对于该问题还有一些更好的算法，下面作一些简单的介绍：
利用最短路径映射 SPM(s,Ω)在O(n(k+logn))时间内求解任意多边形障碍物的ESPO问题的方法是由Reif和Storer提出的。如果给定SPM(s,Ω)，则在O(logn)时间内可以确定包含t的 域，而在0(b+logn)时间内能够确定到t的路径，其中b是路径上线段的数目。Welzl等人利用可视图给出了求解平面上n条线段的ESPO问题的算
17
法，该算法要求 0(n^2)时间。不难修改这个算法使其能处理多边形障碍物，并且具有相同的时间复杂性。
注意，如果使用可视图方法，那么对限界0(n^2)将不可能改进。多边形物体中两个物体(而非点)之间的最短路径的0(n^2)算法是已知的。当n是平行线段集合时，Lee和Preparata提出θ(nlogn)平面扫描算法。线段穿过扫描线并且把最短路径映射到扫描线。平面上没有最短路径的0(n^2)算法能处理避开n条任意相交的线段。 Rohnert给出平面中避开k个凸障碍物最短路径的O(nlogn+k^2)时间的算法。这个时间限界在O(k^2logn+n)时间和O(n+k^2)空间预处理障碍物的条件下达到。预处理包括构造可视图的子图。Rohnert还给出平面中避开k个凸障碍物最短路径的O(knlogn)时间和O(n)空间的算法。后者不需预先处理障碍物，而是利用Dijkstra最短路径算法在线计算可视性。当平面中有k个凸障碍物并且其边界至多相交两次时，Rohnert给出的算法能找到平面中任意两点之间的最短路径，其时间复杂性为O(nlogn+k^2)。这个时间限界在O(nlogn+k^3)时间和O(n+k^2)空间预处理障碍物的条件下达到。(Dijkstra算法见附录三）
18
如图所示即为最短的道路设计方法。最短路径为894.7.
七 模型的评价与推广
7.1模型的评价
本题主要运用Floyd算法，穷举法，欧拉回路和运筹学中的最优化的相关知识建立数学模型，进而求出公园内道路总和与交叉点的函数关系，并充分的结合题目所给的条件，应用MATLAB软件，提高了计算效率和结果的科学性。
模型建立时忽略了题目所未给出的人为因素和自然因素对公园内道路总和的影响，在实际中时建议考虑人为因素和自然因素对所设计的道路结果的影响。 7.2 模型的推广
本题所建立的数学模型虽然解决的是某大学校园公园内道路总和设计的问题，但可以推广到各种城市规划和园林建设等实际问题，这些问题都可以用该模型来解决。
解决该问题时，我们查阅了有关数学建模和运筹学最优化的相关书籍，该模型中所提到的Floyd算法，欧拉回路和动态规划的相关方
19
法均可以直接使用，利用这些方法可以快速方便地解决诸如求最短路径等一些城市规划与园林建设中的实际问题。解决该问题时所用到的数学思想和数学方法，对于解决实际的社会问题也同样具有广泛的教育意义和社会效益。
八 参考文献
【1】《MATLAB程序设计及应用》许丽佳 穆炯 清华大学出版社2011 【2】《最优化理论与方法》傅英定 成孝予 唐应辉 国防工业出版社2005
【3】《优化技术与MATLAB工具箱》赵继俊 机械工业出版社 2011 【4】《最优化方法——MATLAB应用》黄雍检 陶冶 钱祖平 人民邮电出版社 2010
【5】《运筹学（数学规划篇）》吕蓬 潘志 清华大学出版社北京交通大学出版社
20