B题 公园内道路优化.doc

一、问题重述（一）问题背景校园是师生学习生活的重要场所。为了美化校园环境并为其学生提供更好的生活条件，西安某大学计划建一个形状为矩形或其他不规则图形的公园。（二）问题重述公园计划有若干个入口，我们需要建立一个模型去设计道路让任意两个入口相连，使总的道路长度和最小。条件与要求：1） 默认矩形公园的四条边上存在已经建好的道路，此道路不计入道路总长；2）任意的两个入口之间的最短道路长不大于两点连线的1.4倍。3）公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。图 1 公园及入口示意图主要设计对象可假设为如图所示的长200米宽100米的矩形公园，1至8各入口的坐标分别为：P1(20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),P6(35,100),P7(10,100),P8(0,25). 我们面临的问题是：问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70)。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。图 2 一种可能的道路设计图问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。问题三：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，示意图见图3。重复完成问题二的任务。图3 有湖的示意图其中矩形的湖为R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)。二、问题分析1、问题一：我们初步认为确定使用的、也是仅使用的四个交叉点，为了实现使公园内总路程最短的设计目标，考虑到公园四周的边不计入道路总长的前提，我们把问题化简为满足限制条件（任意两个入口之间的最短道路长不大于两点连线的1.4倍）的十二个点间的最小生成树模型，运用克鲁斯卡尔（Kruskal）算法，后期通过人为修正，最终得出最短路径。2、问题二：在“现在公园内可以任意修建道路”的前提下，联系并比较问题一，在问题二中我们首先要解决的问题是确定交叉点。在离散化和赋权基础上，我们通过建立概率场确定出点的数目和大致位置。然后构建两种模型解决最终问题：1.寻找概率最大的点，再运用最小生成树算法得出路径；2.按照局部优化思想，把区域分成两部分，找出费马点确定交叉点并连接路径。3、问题三：结合实际应用，在问题二基础上，问题三增设限制为“公园内有一条矩形湖，新修道路不能通过”。然而我们在问题二中求出最短路径经过矩形湖，所以我们需要对问题二所得优化路径进行调整。由于问题二运用局部最优思想，并且考虑到修改交叉点对全局的影响，我们只需集中针对湖附近的交叉点，运用穷举法，最终实现修正.三、模型假设与约定1）考虑到对实际建设的影响和方便数据处理，我们将路径长度精确到0.1米；2）为了简化模型，我们约定可以忽略实际道路宽度，将实际问题抽象为点线（入口与道路交会处为点，道路为线）问题；3）假设问题一中仅使用给定的四个交叉点；4） 假设问题三中矩形湖四周的边没有路，即沿湖行走需要新修道路；5）计算两个入口间最短道路长时边界道路长度不可不计；6）假定满足最短总长度的道路设计同时也满足设计审美。四、符号说明及名词定义G赋权连通图V赋权连通图中的顶点E赋权连通图中的边d两点间的距离S具有永久标号的顶点集表示从顶点: 到的一条路的权的父亲点，用以确定最短路的路线D邻接矩阵b最小生成树输出矩阵最短道路的总路程h概率场权值离散化：把无限空间中有限的个体映射到有限的空间中去。在本文中指规划区域抽象成点集。局部优化：把区域分割后分别优化，并且各区域间互不影响。费马点：在一个三角形中到三个顶点距离之和最小的点。长径比：一个点与两个焦点连线长度之和与焦点距离的比值。五、问题一（一）模型建立本题确定使用4个道路交叉点A( 50,75 )，B( 40,40 )，C( 120,40 )，D( 115,70 ) ，要求设计道路使公园内道路路程最短（重申：四周道路默认已建，不计入总路程）。我们将8个路口和4个交叉点简化为12个点，因此最短路径是由12个点形成的赋权连通图的最小生成树。基于上述分析，我们建立了最小生成树模型，该模型运用克鲁斯卡尔（Kruskal）算法求解。再运用迪杰斯特拉（Dijkstra）算法对结果进行修正模型。1.克鲁斯卡尔（Kruskal）算法步骤如下：设G=(V,E)是一个顶点数为的赋权连通图。 （1）把赋权连通图的边按权递增的顺序排列（如果有两条以上的边权相等，则这些边之间的顺序可以任意）。 （2）选择边e1 E，使得(e1)尽可能小。 （3）若已选好边e1，e2，ei，则从E/e1，e2，ei中选取ei+1，使得： （i）Ge1，e2，ei+1为无圈图； （ii）(ei+1)是满足（1）的尽可能小的权。 （4）若已选得条边，则停止，否则转（3）。在得到最小生成树之后，我们运用两点间距离公式： （1.1）2.迪杰斯特拉（Dijkstra）算法（并且结合任意的两个入口之间的最短道路长不大于两点连线的1.4倍的限制条件）对每条路径进行修正。修正步骤如下：（1）运用迪杰斯特拉（Dijkstra）算法求处一点到其他任意一点间最短路径。（2）运用公式（1.1）求处两点间连线距离。（3）比较两者长度，若不满足1.4倍的限制条件，则从起点增加一条到其他任意点的连线，并转（1）。（4）将所有点间最短路径未利用的边删去。迪杰斯特拉（Dijkstra）算法步骤：（1）赋初值：令。，令，。（2）更新，：，若，则令，（3）设是使取最小值的中的顶点，则令，。（4）若，转（2）；否则停止。用上述算法求处的就是到的最短路的权，从的父亲点标记追溯到，就得到到的最短路的路线。（二）模型求解考虑到默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长，第一步先针对可以利用已存在道路并且满足两个入口之间的最短道路长不大于两点连线的1.4倍的点进行筛选，再对剩余点在数学上抽象为“矩阵”，以矩阵的行和列表示入口和交叉点的地点，以矩阵中由行列所确定的位置表示两点间连线，以矩阵中点的权值表示两点连线的距离。用点对的方法表示两点间的连线，如P1和P2的连线表示为 (P1,P2) ，而可利用已存在道路的只有8个入口，利用两点间距离公式（1.1）筛选满足两个入口之间的最短道路长不大于两点连线的1.4倍的点，最终得到需要通过交叉点或两点连线的点对有：( 1,5 )，( 1,6 )，( 1,8 ) ，( 2,5 )，( 2,6 ) ，( 2,7 )，( 3,4 )，( 3,5 )，( 3,6 )，( 3,7 )，( P1,A )，( P1,B )，( P1,C )，( P1,D )，( P2,A )，( P2,B )，( P2,C )，( P2,D )，( P3,A )，( P3,B )，( P3,C )，( P3,D )，( P4,A )，( P4,B )，( P4,C )，( P4,D )，( P5,A )，( P5,B )，( P5,C )，( P5,D )，( P6,A )，( P6,B )，( P6,C )，( P6,D )， ( P7,A )，( P7,B )，( P7,C )，( P7,D )， ( P8,A )，( P8,B )，( P8,C )，( P8,D )。现在建立1212的邻接矩阵，由于矩形的四条边上存在已经建好的道路不计入道路总长，则可利用已存在道路的两点间权值为0，建立邻接矩阵如下（三）结果展示我们用Matlab 2012编写克鲁斯卡尔（Kruskal）算法程序，将邻接矩阵输入最小生成树模型中，得到结果为：矩阵中，权值为0的点表示两点不连通，有数值则说明两点连通。我们用几何画板 5.0.4根据所的矩阵绘制相应的路径图，如下：由于P2与P8，P6与P7在矩阵中的权值为0，即在计算最小生成树时两点重合，因此，在（P2，8）和（P8，8），（P6，A）和（P7，A）中较短的一条。修正后的路径图为：我们利用修正模型，发现在该路径中（P5，D）这条路径不满足小于1.4倍连线长的限制，并加以修正，得到满足条件下的最短路径，路径图为：最短路径长度为：六、问题二 在此问题中我们通过两种不同思路，尝试找到满足条件最短路径。（一）思路一1.模型建立按照题设“两个入口之间的最短道路长不大于两点连线的1.4倍”来考虑P1至P8中的任意两点Pi、Pj，若有一点M使，则M必在以Pi和Pj为焦点、为长轴的椭圆内部（含边界）。显然这一点M最好落在线段PiPj上时,路径最短。由于越长路径就越大，而这样的M就越不可能成为交叉点。而由于针对面积计算量较大，且结合实际情况，只需将面离散为点进行计算。基于上述分析，我们建立离散化模型，将平面离散为100200，间距为1米的点阵。我们还建立概率场模型，引入长径比的概念来衡量M的可能情况，称这个比值为M的权值，记做h。由题中区域图易得：把权值作为Z变量用Matlab 2012可以画出区域内的一个三维赋权图。我们考虑权的峰值也就是图中相对于旁边位置比较高的点。通过权值的意义可以得出结论这个或者这些点理论上最可能成为交叉点。我们先记录这个或者这些点的坐标，通过观察按照以下条件排除不可能作为交叉点的点：（1） 交叉点不可能出现在边框上。因为这样的点没有意义。（2） 交叉点不可能很接近边框的位置。因为这样的位置靠近一边而远离另一边，按照顺序不等式的思想会产生最偏离极值的值。（3） 摒弃多个交叉点聚集在一起的情形，只留下其中最合理的点。因为考虑到模型建立在道路设计的实际问题中，这样的点既不美观也妨碍通行，没有考虑的必要。 接下来是一个已知点与边框求最短距离的问题。 与第一问相同，我们假设这些点形成一个赋权完全图，然后采取最小生成树算法。将数据以矩阵形式导入后用Matlab 2012进行处理，得出一个邻接矩阵。根据邻接矩阵我们可以利用几何画板 5.0.4初步作出路径图。再考虑“任意的两个入口之间的最短道路长不大于两点连线的1.4倍”这一题设条件，我们可以增加或者删除一些连线，对图做细微修改，得出最终结论。2.模型求解求解过程及结果展示 使用VC+6.0程序输出这八个点之间的距离矩阵：使用Matlab 2012编写程序画出以P1到P8中任意两点为焦点形成椭圆的相交图： 因为椭圆数目过多而对各个点的影响差别较大，所以结合问题一的求解，我们最终选择了优化后的十个点对作为基础，以这些点对为焦点按照模型建立给出的步骤编写C语言程序，求出区域中所有点的权值，输出在矩阵里。由于含20000个点，数目太大，故在此不一一输出，只在附录中给出C语言程序。把权值做为区域中点的高，借助Matlab 2012作出图像： 取两个权的峰值点做区域中新加入的点，分别记为Q1、Q2，用几何画板 3.0.4作图如下： 那么可以求得此图中十个点的邻接矩阵： 把矩阵带入最小生成树算法再按照模型建立中的方法修改得到最终连线图：那么，在思路一中最短总路程：（二）思路二1.模型建立同样结合赋权完全图的思想，由权值最高点的分布可以确定区域中最可能有两个交叉点，记为Q1、Q2。那么我们可以把图分为分别以这两个点为中心的两部分。因为全局最优建立在局部最优的基础上，所以我们先对这两部分进行优化，获得最短路径，再把两部分做合理地连接即可得到一种全局最优的路径。考虑到路径的最优是使距离和最小，那么可以应用三角形中的费马定理做交叉点。图的右侧存在P3、P4、P5三个入口，而经过反复计算可以看出P3到P5的路径很难做到满足“任意的两个入口之间的最短道路长不大于两点连线的1.4倍”条件。故在右半部分中以仅有的三个点P3、P4、P5为顶点做三角形求出其费马点Q2，此时一定最小。 至此有半部分优化完毕，考虑左半部分的取点问题。同样应用找费马点的思想确定区域中间的交叉点。因为受权值最高点分布的影响，显然这个点最可能的是P2、P5、P6或P2、P5、P7形成的费马点。故分别找出并计算。2.模型求解求解过程及结果展示对于左半部分的优化，当取P2、P5、P6的费马点为Q1（62,78）时可以得到路径Q1P2、Q1P5、Q1P6。因为P1P8沿左下角边框的距离长于P1P8长度的1.4倍，所以必须连接P1P8。至此得到经验证符合题意“任意的两个入口之间的最短道路长不大于两点连线的1.4倍”的路径： 此时最短总路程。 当取P2、P5、P7的费马点为Q1（55,69）时可以得到路径Q1P2、Q1P5、Q1P7。同理连接P1P8可以得到路径，但是经过计算可以发现连接Q1和P7显然不如连接邻近的Q1和P6省距离。故删去Q1P7连接Q1P6得到路径： 此时最短总路程。 综上所述，在思路二中最短路程为。综合考虑思路一和思路二，优先选择路程较短的思路二结果。七、问题三（一）模型建立本题在公园内出现一矩形湖，其范围为：R1(140,70),R2(140,45),R3(165,45),R4(165,70)在第二问中求出的最短路径通过湖，因此我们需要对问题二所得优化路径进行调整。由于问题二运用局部最优的思想，并且考虑到修改交叉点对全局的影响，我们只需集中针对湖附近的交叉点，进行修正即可。如下图所示，将最短路径中连线（P5，Q2）与湖的交点定为M，N，因为假设湖的周围没有路，若沿湖走需重新修路，因此根据三角形两边之和大于第三边可知当路径过湖的顶点R4时路程较短。基于上述分析，我们以Q2（173，44）为圆心，取适当距离为半径，建立湖路径优化模型，在离散化区域内用运用穷举法进行修正。综合考虑Q2点的位置对整体路径产生的影响，我们取半径为18，建立原型离散化区域，计算区域内点为交叉点时最短路径的长度进行比较修正。（二）模型求解求解过程我们用VC编写了C语言程序进行运算得到最优点：结果展示：通过比较可以得出，当Q2（173，44）变为Q2（181，48）时，总路径较为优化。用几何画板画出此时路径为：计算最短路径为：八、模型评价与提高（一）优点（1）我们建立的离散化模型，在考虑实际问题对精确度要求的同时简化了数据的计算量；（2）我们根据点的权值建立概率场，这样可以充分考虑每个点是交叉点的可能性，没有遗漏；（3）我们在模型的建立中引入椭圆和费马点，使解析化的思想结合几何方法，取长补短地从不同方向逼近最优解；（4）我们在考虑问题时引入局部优化思想，通过对各部分寻求最短路径达到全局最大程度上的优化；（5）最小生成树模型和修正模型结合问题背景与问题本身，综合考虑了各个方面，讨论总结并除去实际情况中次要因素的影响，在建立模型前给出严格的限制条件，使得模型得到合理的简化。（二）缺点（1）在寻求较优解的过程中我们反复用到人为逻辑判断对路径进行修正，这就降低了模型的可移植性；（2）因为编程能力有限，我们不能在寻求最小生成树的同时加入题目要求的1.4倍判断条件，这就导致在程序得出结果后我们需要对路径进行人为修正；（3）考虑到时间精力的限制，为了简化模型，寻求最短路径，我们在模型假设中作出“假定满足最短总长度的道路设计同时也满足设计审美”，然而实际情况是最短（此论文寻找的最优）路径不一定同时满足设计，景观布置，维护等各方面的实际最优。（三）改进方法 我们希望通过学习更加高级的算法（比如蚁群算法(ant colony optimization, ACO），应用到解决求解最短路径中去。但是由于考虑到算法的难度与时间的限制，我们根据自身相关知识储备情况，没能在本文中给出具体应用解决过程。九、模型推广（1）本模型反复应用的最小生成树算法可以广泛推广到各种路径优化的设计中；（2）本模型用到的概率场思想在粒子不规则运动、数学概型及生物制药领域都有深入的应用。十、参考文献1西北工业大学数学建模指导委员会，数学建模简明教程，北京市：高等教育出版社，2008.9；2孙祥，徐流美等,Matlab7.0基础教程，清华大学出版社，2005.5；3方世昌，离散数学，西安市：西安电子科技大学出版社，2009.1；4严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，2009.7；5谭浩强，C程序设计（第三版），清华大学出版社，2005.7；6 盛骤，谢式千，潘承毅，概率论与数理统计（第四版），浙江大学出版社，2010.11。十一 、附录（一）最小生成树的克鲁斯卡尔（Kruskal）算法function b,u,w=mintrees(a,k)if nargout=1k=1;endm,n=size(a);for i=1:mfor j=1:nif a(i,j)=0a(i,j)=inf;endendendb=zeros(n);u(1)=k;j=1;v=zeros(1,n);v(k)=1;for o=1:n-1sn=ones(3,n)*inf;for xk=1:jk=u(xk);p=max(a(k,:);for i=1:nif v(i)1&a(k,i)pp=a(k,i);endendfor i=1:nif v(i)1&a(k,i)=pbreak;endendsn(1 2 3,k)=i,p,u(xk);endw(j),k=min(sn(2,:);j=j+1;u(j)=sn(1,k);b(sn(1,k),sn(3,k)=sn(2,k);v(u(j)=1;end（二）修正模型中迪杰斯特拉（Dijkstra）算法n =size(w,1);w1 =w(1,: );for i=1: n l(i) =w1(i); z(i) =1;ends =;s(1) =1;u =s(1);k =1lzwhile kl(u) +w(u,i) l(i) =l(u) +w(u,i); z(i) =u; end end end end l z ll=l for i =1: n for j 1:k if i =s(j) ll(i) =ll(i); else ll(i) =inf; end end end lv =inf; for i =1: n if ll(i)lv lv =ll(i); v =i; end end lv; v; s(k+1) =v; k =k+1; u =s(k); endlz（三）问题二中所有点的权值输出程序#include#includeint i=0,j=0;double h101201=0;double d1=0,d2=0;void judge(int x,int y,int p,int q)d1=sqrt(i-x)*(i-x)+(j-y)*(j-y)+sqrt(i-p)*(i-p)+(j-q)*(j-q);d2=sqrt(x-p)*(x-p)+(y-q)*(y-q);hij=hij+d2/d1;int main()double x=0;FILE *fp;if(fp=fopen(data.txt,w)=NULL)printf(error);for(i=0;i=100;i+)for(j=0;j=200;j+)judge(20,0,120,100);judge(20,0,35