问题的提出.doc

一、问题的提出:
1、假定公园内确定要使用4个道路交叉点为:A(50,75),B(40,40),C(120,40),D(115,70)。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计,计算新修路的总路程。
2、现在公园内可以任意修建道路,如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标,画出道路设计,计算新修路的总路程。
3、若公园内有一条矩形的湖,新修的道路不能通过,但可以到达湖四周的边,以此为前提,重复完成上一问题中的任务。
二、问题的分析:
本题是一个道路设计的最优化的问题,即是如何设计路径使公园内部新修路总长最小,但要满足以下两个控制条件:
1、任两个入口连通;
2、。
三、模型的假设:
1、任意两点之间修的路均为直线;
2、不考虑地形高低起伏的影响,假设地面高度均相当;
3、假设问题三中的湖的四周的路已然存在且不计入所需修路的总长;
4、交叉路口,路的交叉处不影响修路的总长。
四、模型的建立:
1)、总的前提下:
主要设计对象可假设为如图所示的矩形公园,其相关数据为:长200米,宽100米。
八个入口坐标:P1(20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),
P6(35,100),P7(10,100),P8(0,25)。
3、使得需要修路的总和最小,。
、问题一:
公园内确定要使用4个道路交叉点,分别为:A(50,75),B(40,40),C(120,40),D(115,70)。这4个道路交叉点和8个入口的位置分布如图1所示,对已知的12个点中,需要找到符合条件的最短路径。首先利用floyd算法,做出最小生成树,并除去可以利用公园周边的道路,最终结果如图2所示;其次对结果中的最小生成树,对任意两入口之间的距离利用图1中的最小路径进行检验,。如果均满足条件,那么最小生成树的结果就是最佳路径,如果有不满足条件的路径,就利用贪婪算法和穷举法在最小生成树的基础上进行最佳路径的适当调整,从而得出符合条件的最佳路径。
3)、问题二:
相对第一问来说,第二问没有提供转折点。所以我们必须确定至少需要几个转折点和确定转折点的位置,其余的部分可以借鉴问题一的解法求出最优解。其中对于转折点的个数和位置的确定,根据限制条件:。我们可以利用以两点连线为2c,,两点作为焦点,做出所有满足条件的点的椭圆集合,再根据全部椭圆的重叠情况从而得出至少需要的转折点的个数和转折点的大致所在地。最后在转折点的大致所在地利用穷举法选出使得路径的总和最短,找出最佳路径。
、问题三:
基于第二问,公园内部多出了一个矩形的湖泊。根据实际情况可知,公园内的湖泊周边的道路是存在的。从而利用同样的画椭圆的方法做出满足条件的最佳路径,得出最优解。
模型的求