北京地铁换乘次数及相关规划的研究.doc

北京地铁换乘次数及相关规划的研究北师大实验中学 高一9班 柯伟辰（准考证号0351） 指导教师 黎栋材摘要：本文通过图论、集合论等方式，研究了北京地铁中换乘次数的问题，并且根据研究所得的结果对地铁的规划提出了建议。关键词：北京 地铁 换乘 规划。本人郑重声明：所呈交的数学应用论文是本人在指导教师的指导下独立进行研究的成果，除文中已经注明引用的内容外，本文不含其它个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。论文作者签名： 2010年3月18日问题背景近几年，北京市的地下交通得到了极大的发展，地铁线路由2000年的2条发展到现在的8条（不包括机场线），极大方便了人们的出行。但是，与此同时，地铁线路的增多也给人们的换乘带来了不便。很多时候，从一站到另外一站，中间要换乘两三次地铁，非常麻烦。那么，在不考虑其他因素（如人流量、地上公共交通等）的情况下，有没有办法尽量减少地铁旅客的换乘次数呢？现在的换乘次数分析现在北京的地铁线路图如下： 最多换乘多少次？从目前的地铁线路来看，最多换乘的次数为3次。这可以用图论的相关知识或用集合论证明。证明1：图论将每条线路用一个结点表示，如果两条线路之间能够换乘，那么就在两个结点间连一条无向边。八通线4号线2号线1号线8号线10号线5号线13号线由于不论是哪一站，一定属于这张图里面的某个节点，所以事实上只要求出这张图中任意两点的最短路的最大值即可。将图的每个结点编为1、2、38号，将其输入计算机，使用floyd算法或dijkstra算法，就可以求出这个最大值。程序代码请见附录。证明2：集合论 把19个换乘站按照从西到东，从北到南的顺序依次编成号1、219，代表19个元素；把8条线路编成字母a、bi，代表9个集合，则：a（1号线）=4，5，11，15，16，17，18b（2号线）=3，4，6，10，12，14，15c（4号线）=1，3，5，6d（5号线）=8，9，10，11，12e（8号线）=7f（10号线）=1，2，7，9，13，16g（13号线）=2，3，8，13，14h（八通线）=17，18输入电脑后会发现对于任意两个元素、，一定存在两个集合m、n，使得m,n 且 mn空集。设mn，则从甲地到乙地所必需倒车的次数为三次，因为设甲地所在的线路为集合a所代表的线路，乙地所在的线路为集合b所代表的线路，a、b上必有换乘站，再设a、b上任意两个元素为、，则 a线路（甲地）m线路n线路b线路（乙地），共需换乘三次，换乘站分别为、。由此，我们可以看出，目前的地铁线路内最多的换乘次数为3次。可以发现，这种最长的路线有这么几种：1. 八通线8号线（八通线1号线10号线8号线）2. 八通线13号线（八通线1号线10号线13号线）3. 8号线2号线（8号线10号线5号线2号线 等） 这就是目前北京的地铁中，换乘最不方便的3条线路。修一条新的地铁，将换乘次数减少到两次 能不能修一条新的地铁，将以上线路中的3次换乘改为两次呢？事实上这是一个在上面的图里加上1个结点，并且由这个结点引出若干条边的问题。但是，新增结点的同时又不能让换乘这趟地铁的次数达到3次。那么，这个点放在哪里合适，又应该和谁连起来呢？当然，再次说明，这里只考虑换乘次数最少，运营里程、客流量之类的其他因素暂不考虑。 首先，无论这个结点在哪儿，它必须引出几条边，连接起8号线、2号线、13号线和八通线。这样，通过这个结点只要两次就可以完成这4条路线的换乘。x号线 这幅图中现在已经不存在3次换乘，从任意的起点到任意的终点，都只需2次换乘就可以达到。这条x号线如果在地铁图中修建，大致是这样的：这样，不仅解决了换乘问题，而且在一定程度上还分担了2号线、5号线、10号线的压力。同时它还是穿过2、3环的线路，也可以缓解陆上交通的压力。不考虑8号线、八通线的情况 当然，8号线和八通线比较特殊，一条是用于奥运期间的客流运输、另一条则处于远郊区县，出于各种原因，它们的换乘比较不方便。那么，如果不考虑这两条线路的话，根据上面的方法容易证明只需要换乘2次就可以到达任意一条地铁。事实上，这幅图已经不可能再优化了。因为如果想要达到一次换乘，新修地铁线路是不可能的，因为至少中间将会有x线路的存在。比如1号线x号线13号线，还是两次换乘，没有意义。所以，仅从换乘的角度讲，这幅图已经是最优，没有再新建结点、优化换乘次数的必要。结语至此，我们已经基本了解了北京地铁的换乘现状以及它所存在的若干缺陷，并且根据这些对未来北京地铁的规划提出了一个假设。当然，文中的假设毕竟只是纸上谈兵，因为还需要考虑到各种其他因素。不过，地铁换乘的问题作为使地铁乘客感到不便的重要因素之一，应该得到地铁运营部门和规划部门的重视。不管怎么说，地下交通作为缓解地面交通压力、减少空气污染、方便人们出行的重要交通方式，理应得到提倡和大力发展。换乘只是地铁发展中众多问题中的一个。还有诸如南北城地铁密度严重不均、1、2号线地铁设施老化等问题存在。我们希望有关部门能够重视起这些问题，希望北京市的地铁事业能够早日达到国际先进水平，使百姓的交通出行更加顺畅。附录：floyd算法和dijkstra算法（部分资料引自百度百科） 这两种算法都是图论中的重要算法，在计算机、运筹学等学科中起到重要作用。对于给定的有向图或者无向图（边的权值不为负），这两种算法都能够算出任意两点间的最短路。 floyd算法通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵a=a(i,j) nn开始，递归地进行n次更新，即由矩阵d(0)=a，按一个公式，构造出矩阵d(1)；又用同样地公式由d(1)构造出d(2)；最后又用同样的公式由d(n-1)构造出矩阵d(n)。矩阵d(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称d(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为o(n3);其状态转移方程如下： mapi,j:=minmapi,k+mapk,j,mapi,jmapi,j表示i到j的最短距离，k是穷举i,j的断点 dijkstra算法 dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权回路。 解决以上的地铁换乘问题时，我所采用的是dijkstra算法（当然floyd也可以），穷举起点和终点，就可以求出最短路的最大值。程序代码如下（c+）。#includeusing namespace std;struct etype int num; etype* next; etype* *edges;int n; int m;int maxr;bool stepped20; /记录每个点是不是已经到达过int dis2020; /记录起点到终点的最短路径的长度int link2020; /记录找到的结果void dijk(int s) /以s为起点进行dijkstra搜索 int i; int now; for(i=1;i=n;i+) steppedi=false; dissi=-1; /一开始全不让结点可达 disss=0; /起点可达 while(true) int min=9999999; for(i=1;i=n;i+) if(steppedi=false & dissinum=-1 | dissnow+1num) disse-num=dissnow+1; e=e-next; steppednow=true; int maxlen=0;int end10;int p=0; for(i=1;imaxlen) maxlen=dissi; memset(end,0,sizeof(int)*10); p=0; endp=i; else if(dissi=maxlen) p+; endp=i; if(maxlenmaxr) maxr=maxlen; memset(link,0,sizeof(int)*400); for(i=0;i10;i+) if(endi!=0)linksendi=linkendis=1; else if(maxlen=maxr) for(i=0;inm; int i; edges= new etype*n+1; memset(link,0,sizeof(int)*20*20); for(i=1;i=n;i+)edgesi=0; int k1,k2; for(i=1;ik1k2; etype* temp; temp=new etype(); temp-num=k2; temp-next=edgesk1; edgesk1=temp; etype* temp2; temp2=new etype(); temp2-num=k1; temp2-next=edgesk2; edgesk2=temp