基于kruskal算法的动物园道路设计最优化分析

本文讨论的是动物园道路设计最优化问题，即在动物园的任意入口之间的最短道路径不大于两点连线的1.5倍的前提下，使得新修路的总路程最短，并绘出相应的道路设计图。 　　　问题一给定了四个固定的道路交叉点，问题二则在问题一的基础上增加了位置固定的海洋馆作为约束条件，必须考虑问题一得到的最优解所建立的路径是否穿过该海洋馆。穿过，则做进一步的局部优化；否则，最优解不变。 　　　本文按照问题的顺序，依次分析解决问题一和问题二，对问题给定的图形根据图论的相关知识进行抽象，把动物园抽象为一个图来进行分析。 对于问题一，考虑到矩形动物园周边已经建好道路，而且总长中不计入矩形四边的长度，所以我们优先考虑使用周边道路。第一步先利用SPSS算出任意两个点（M1-M8，ABCD）之间的距离以及1.5倍的距离；第二步是利用最小生成树原理，结合Kruskal算法得出最小生成树；第三步是参照依照约束条件对最小代价数进行优化，得到最短距离1927.1071米。 对于问题二，问题一的基础上增加了一个矩形海洋馆，可继续借助第一个问题的模型。由于道路不能穿过海洋馆，但可以到达四边，第一个问题的最优解并没有受到海洋馆位置的限制，所以最短距离依旧是1927.1071米。