算法分析与设计论文.doc

本文档系作者精心整理编辑，实用价值高。题 目：浅析Floyd算法在校车安 排与站点优化中的应用班 级：计算机科学与技术082姓 名： 学 号：指导教师：浅析Floyd算法在校车安排与站点优化中的应用摘要：本文主要论及了Floyd算法在校车安排与站点优化中的应用问题，该问题中涉及到求解最短距离以及教师及其他工作人员对这种安排的满意度等问题。关于这些问题的解决，可以利用计算机计算求解结果，然后统一实施安排。在具体实施过程中，提出一些假设，分析了每个问题在求解时所使用的算法，并编写了相应的程序代码，而且以表格和图表的形式给出了相关的结果。一、问题描述近年来，许多高校都建有新校区，但是师资的限制常常使得教师和其他工作人员每天不得不往返于新校区与老校区。由于每天到新校区的教师和工作人员可能会很多，使得往往需要安排多辆校车去服务，校车安排不合理将直接影响学校的开支和工作人员的满意度等。因此，如何合理、有效的设置乘车点安排车辆，让教师和工作人员尽量满意是个十分重要的问题。现在我们需要考虑如下两个问题：问题1：如要建立n个停车点，为使住居于各区的人员到最近乘车点的距离最小，应该将校车乘车点建立在哪n个点。建立一般模型，并给n=2,3时的结果。问题2：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，应将校车乘车点应建立在哪n个点。建立一般模型，并给n=2,3时的结果。二、问题假设 假设教师和工作人员的满意度仅与他们到乘车点的距离有关系，并简单的认为距离近则满意度高，距离原则满意度低。 假设每辆校车都尽量装满人，不考虑乘车人数等因素对教师和工作人员满意度的影响。 不考虑教师及工作人员的等车时间。 假设每个站点之间的路况都一样，忽略现实中的道路状况不同所带来的影响。 假设在乘车点区间内人员的乘车距离为零。 假设每个区的教师和其他工作人员都选择到距离自己最近的一个固定的乘车点进行乘车。三、问题的形式化在优化选择校车站点的过程中，从实际情况出发，我们可以知道乘车点的距离和小区的人数都会对教师及其他工作人员乘坐校车出行时的满意度有所影响。人数较多的小区代表了更多数人的意见，也就是乘车满意度。因此，对于人数较多的小区而言，如果站点安排不够合理，将会对整体满意度产生极大的影响。因而，在安排站点位置的时候，我们要考虑这些因素。设置好乘车点之后，每个人走的路程相加所得的和最小时，教师及其他工作人员的乘车总体满意度也就最高。当我们考虑各区人数的差异时，就只需在前一问题的基础上用路程之和乘以各小区人数，所得值越小则表明满意程度越高。本题主要是解决校车安排和站点优化使得教师及其他工作人员对校车的安排的满意度达到最大，在以上对问题的假设的基础之上，要想使各位的满意度最大，就必须使乘车站点建立在最优的区域之内。在解决第一个问题时运用最短路径的思想求解出最小距离的n个乘车站点。而问题二则是在问题一的基础上计算出所有各区人员乘以各区距离的总距离矩阵，并设计程序用各区域人员至乘车点的最小距离来表示满意度最大，通过求解出建立站点的区域做进一步处理得出其满意度。各区域之间的连接分布图大致有以下几种：CEDABACBABCAB行注：()线型：两区域间仅一条路径。()树型：两区域连接到同一结点。()环型：多个区域连接成一个环。()星型：多个区域均连接到同一结点。四、算法分析与问题求解1、Floyd算法求解最短路正如前文分析所述，乘车点距离是影响乘车点优化选择的关键因素，教师及其他工作人员乘车时首先考虑选择的是距离自己最近的乘车点进行乘车。因此，我们有必要求出各个小区间的最短距离，对此我们使用Floyd算法进行求解。Floyd算法是求解每对顶点间最短路的算法，算法的基本思想是直接在图的带权邻接矩阵中用插入顶点的方法依次构造出n个矩阵D（1）、D（2）、D(n)，使最后得到的矩阵D(n)成为图的距离矩阵，同时也需要求出插入点矩阵以便得到两点间的最短路径。Floyd算法求任意两点间的最短路，算法步骤：Step1：把图用邻接矩阵表示出来，如果从到有路可达，则，其中表示该路的长度；否则NULL。Step2：定义一个矩阵用来记录所插入点的信息，表示从到需要经过的点，初始化。Step3：把各个顶点插入图中，比较插点后的距离与原来的距离，如果的值变小，则。在矩阵中包含有两点之间最短道路的信息，而在矩阵中则包含了最短通路的信息。比如，要寻找从到的路径，根据，假如D（4,1）=2则说明从到经过，走过的路径为、，如果D（5,2）=2，说明与直接相连。 编写求解最短路代码，部分核心伪代码如下：注：Floyd算法求最短路径，输入矩阵a为各点的带权邻接矩阵，输出矩阵D为各点间最短距离，矩阵R为最短路径。n=size(a,1);D=a;for(i=1,i=n;i+)for(j=1;j=n;j+)R(i,j)=j;for( k=1,k=n;i+)for(i=1;i=n;j+)for(j=1,j=n;i+)if D(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);将数据代入以上模型中，可以得到如下表1所示结果（部分结果）：表1区域123456104004N7009101140240008N30051074034N8N060081010404700 30030060002104405910510810210023061140740104044023002、基于最短路径的站点优化针对问题1，在不考虑校区人数的前提下，又根据前边的假设我们已经知道：教师及其他工作人员都选择去距离自己最近的站点乘车，为了解决个乘车点的优化设置问题，我们从区域到所有乘车点的所有距离中选出最小的作为该区域的乘车距离，并对所有区域求和算出总乘车距离，最后我们遍历乘车点位置所有可能的情况找出使总乘车距离最小的组合，作为乘车点的设置方案。设计步骤如下：注：dti表示t区到i区的最短距离，N表示小区总数目，St表示t区教师和工作人员到最近乘车点的距离，ni表示以ni区为乘车点(0n=N)。当N=2时，以n1, n2区为乘车点时，St=mindn1t,dn2t，从而。因为有N个区，这样就有种选择乘车点位置的方法，共有个，编程选出最小值的，此时值对应的n1,n2值即为乘车点应选择的区。 相关核心代码如下：int min(int x,int y)/*比较两个数的值，并返回较小的值*/ int z; z=xy?x:y; return(z);void main() int i,j,t,s=0;int uNN=0;int aNN=此为D矩阵每个值按顺序排列;for(i=0;iN;i+)for(j=i+1;jN;j+)for(t=0;tN;t+)s=s+min(ait,ajt); uij=s; s=0; int n1=0,n2=0,m=10000000000; for(i=0;iN;i+) for(j=0;jN;j+) if(uij!=0&uijm) m=uij; n1=i+1; n2=j+1; 当N=3时，以n1,n2,n3区为乘车点时，St=mindn1t,dn2t,dn3t，从而。因为有N个区，这样就有种选择乘车点位置的方法，共有个，编程选出最小值的，此时值对应的n1,n2,n3值即为乘车点应选择的区。 相关的核心代码如下所示：int min(int x,int y,int w)int z;z=(xy?x:y)w?(xy?x:y):w;return(z);void main() int i,j,k,t,s=0;int uNNN=0;int aNN= 此为D矩阵每个值按顺序排列;for(i=0;iN;i+)for(j=i+1;jN;j+)for(k=j+1;kN;k+)for(t=0;tN;t+)s=s+min(ait,ajt,akt); uijk=s;s=0; int n1=0,n2=0,n3=0,m=10000000000; for(i=0;iN;i+)for(j=0;jN;j+)for(k=0;kN;k+) if(uijk!=0&uijkm) m=uijk; n1=i+1; n2=j+1;n3=k+1; 将相关数据代入以上程序中求解，我们可以得到乘车点设置，如表2所示结果：表2乘车点数目乘车点位置所有人员到乘车点最近距离之和S差分项Si-Si-112433640-218,3124402-9238318,22,3219816-4586由表中的结果我们发现，随着乘车点数目增加，总乘车距离的减小幅度呈递减的趋势，这与实际经验相符。不难看出，当较小时，适当增加乘车点数目能够有效缩短乘车距离；通过分析差分项Si-Si-1，我们可以预见的是：当达到某个值以后，乘车点数目的增加对缩短乘车距离的贡献将变得相对减小。3、基于满意度的站点优化 问题1中，在不考虑每个乘车区域人数分布的情形下，我们给出了比较合理的乘车点位置。然而，这样做所得出的结果不足以更加实际的反映客观情况。所以在第二个问题中，我们增加了乘车人数分布的条件。解决该问题的算法思路：由前面假设，我们已经知道教师及工作人员选择乘车点时都考虑去距离自己最近的乘车点。我们将个人的乘车距离作为个人的满意度的衡量尺度。考虑到每个区的人数不同，将每个区的人员到自己最近的乘车点乘车所走的最短距离加起来所得到的和最小时，那么教师和其他工作人员的总体满意度也就越高。设计步骤如下：注：Pt表示t区的乘车人数，dij 表示i区与j区的最短路径值，St表示t区教师和工作人员到最近乘车点的距离，W总作为有教师和工作人员乘车满意度衡量标准。在第1问中我们已经求得：当N=2时，以n1, n2区为乘车点时，St=mindn1t,dn2t，以t区人数Pt乘以距离S作为Wt值，即Wt=Pt*St，W总=。同理我们可以求得：当N=3时，St=mindn1t,dn2t,dn3t，从而，即得：Wt=Pt*St，W总=。 N=2时，求解乘车点的区域时的核心代码如下：int min(int x,int y)int z; z=xy?x:y; return z;void main() int i,j,t,s=0; int uNN=0;int vNN=0;int aNN=此为D矩阵每个值按顺序排列;int pN=以每个区的人数定义一个一维数组;for(i=0;iN;i+)for(j=i+1;jN;j+)for(t=0;tN;t+)vit=ait*pt;vjt=ajt*pt;s= s+min(vit,vjt); uij=s; s=0;int n1=0,n2=0,m=10000000000; for(i=0;iN;i+) for(j=0;jN;j+) if(uij!=0&uijm) m=uij; n1=i+1; n2=j+1; printf(%dnnn,ui-1j-1); N=3时，求解乘车点的区域时的核心代码如下：int min(int x,int y,int w)int z; z=(xy?x:y)w?(xy?x:y):w; return(z);void main() int i,j,t,k,s=0;int u505050=0;int v5050=0;int a5050= 此为D矩阵每个值按顺序排列;int p50=以每个区的人数定义一个一维数组;for(i=0;i50;i+)for(j=i+1;j50;j+)for(k=j+1;k50;k+)for(t=0;t50;t+) vit=ait*pt;vjt=ajt*pt;vkt=akt*pt;s= s+min(vit,vjt,vkt); uijk=s; s=0; int n1=0,n2=0,n3=0,m=10000000000; for(i=0;i50;i+) for(j=0;j50;j+) for(k=0;k50;k+) if(uijk!=0&uijkm) m=uijk; n1=i+1; n2=j+1; n3=k+1; printf(%dnnn,ui-1j-1k-1);将相关数据代入上述代码中，所得结果如表3所示：表3乘车点数目N乘车点位置i满意度最小区域内工作人员总行走距离S总行走距离223,35623001374075321,26,41516801145438五、小 结本文主要是浅析了Floyd算法在校车安排与站点优化中的应用问题。为了求解出各区域间的距离，我们建立了有权无向图，方便了求解过程。利用图论中的Floyd算法求解出了各个区域之间的最短路径，得到了D矩阵和R矩阵（其中D矩阵直观的表达出任意两个区之间的最短路径，R矩阵又列出了任意两个区最短路径具体的路线），进而成功解决了如何安排有限个站点使得教师及其他工作人员获得满意度最高的问题。在具体的实现过程中，也涉及到了搜索算法方面的相关内容，当数据量比较多时程序的运算量比较大，增加了系统的负担。然而，对于本题在求解最短路径时也可以运用Dijkstra算法进行解决，而在求解教师及其他工作人员的