本科生毕业设计

上海电力学院本科毕业设计（论文）题目：电子地图与最短路径算法的结合院系：数理学院专业年级：信息与计算科学专业2009级学生姓名：xx远学号：20092426指导教师：宋政芳2013年6月3日摘要最短路径问题在图论研究中是一个长盛不衰的经典问题，旨在寻找图中指定两结点间的最短路径；而电子地图如今蓬勃发展，依托计算机成象等技术，直观的为人们服务。电子地图需要借助最短路径算法，得出指定起始点至目的地，并且同时满足需求的行进路线。二者的结合，在促进彼此发展的同时，更为人们提供越发显著的帮助。而探讨二者结合，一方面要学习最短路径问题，了解当前已知的最短路径算法，如适用于单源非负的Dijkstra算法，所有顶点之间的可负的Floyd算法等；另一方面要懂得电子地图是如何将现实中的交通网络数据化，抽象为一般有向图。电子地图与最短路径算法结合的前提是电子地图的“绘制”：无论是对哪种最短路径算法，他们得以实施，实现的前提都是有向图或无向图的出现。而在“绘制”电子地图时，最为关键的就是建立城市交通网络数据模型。电子地图与最短路径算法结合的核心是最短路径算法的实现：如何在已知的交通有向图或无向图上，实现最短路径算法，得到所求路径，并保证准确有效的到达，是电子地图与最短路径二者结合最突出，最核心的问题。关键词：电子地图；最短路径算法；数据模型TheCombinationofElectronicMapandtheShortestPathAlgorithmAbstractTheshortestpathproblemingraphtheoryisanenduringproblem,aimstofinddiagramsspecifytheshortestpathbetweentwonodes.Withthedevelopmentofelectronicmapswhichdependsoncomputerimagingtechnology,itserviceintuitivelyforpeople.Electronicmapneeduseashortestpathalgorithm,andgetstheroadfromthestartingpointtodestination,andmeetsthedemandofrouteatthesametime.Thecombinationofboth,inpromotingthedevelopmentofeachotheratthesametime,morepeoplegainincreasinglysignificanthelp.Andexplorethiscombination,ontheonehandtostudytheshortestpathproblem,understandthecurrentlyknownshortestpathalgorithm,suchasDijkstraalgorithmdisposeforsingle-sourcenon-negative,Floydalgorithmmanagebetweenallverticesofthealgorithmcanbenegative,ontheotherhandtounderstanddigitalelectronicmapishowtorealtrafficnetwork,theabstractistypicallydirectedgraph.Electronicmapcombinedwiththeshortestpathalgorithmisthepremiseofelectronicmapinthe"drawing":forallofshortestpathalgorithm,theycanimplement,implementationisthepremiseofdirectedgraphorundirectedgraph.Inthe"drawing"electronicmap,thekeyistosetuptheurbantrafficnetworkdatamodel.Electronicmapcombinedwiththeshortestpathalgorithmisthecoreoftherealizationoftheshortestpathalgorithm:howtoachievetheshortestpathalgorithmintheknowntrafficdirectedgraphorundirectedgraph,getdemandingpath,andensuretheaccurateandeffectivereach,isthemostprominentandthemostcoreprobleminthecombinationbetweenelectronicmapandshortestpathalgorithm.KeyWords：ElectronicMap；ShortestPathAlgorithm；TheDataModel目录TOC\o"1-5"\h\z\o"CurrentDocument"摘要IAbstractII引言1\o"CurrentDocument"1基本概念2\o"CurrentDocument"1.1图论基本概念21.1.1图的基本概念21.1.2邻接矩阵31.1.3邻接表3\o"CurrentDocument"1.2最短路的基本概念41.2.1最短路问题41.2.2单目标最短路径问题41.2.3单对结点间的最短路径问题4\o"CurrentDocument"1.3电子地图的基本概念51.3.1电子地图的基本性质51.3.2电子地图的一般特点51.3.3地理信息系统GIS5\o"CurrentDocument"2最短路问题的各种算法6Dijkstra算法6Dijkstra算法的原理6Dijkstra算法实现7Bellman-Ford算法7Bellman-Ford算法的原理7Bellman-Ford算法实现8\o"CurrentDocument"SPFA算法8SPFA算法的思想9SPFA算法的实现9\o"CurrentDocument"Floyd算法9Floyd算法的思想9Floyd算法的实现10\o"CurrentDocument"2.5其他算法——A*(A-Star)算法10\o"CurrentDocument"3城市交通网络数据模型11\o"CurrentDocument"3.1电子地图数据需满足的技术要求12\o"CurrentDocument"3.2电子地图基础数据的整理123.2.1道路，建筑物的录入123.2.2坐标系的转换123.2.3地形图的分层、缩编123.2.4地形图的接边与图幅分幅133.3城市交通网络数据模型的管理133.3.1格网管理133.3.2道路网络数据区域管理133.3.3索引数据的管理13\o"CurrentDocument"4电子地图与最短路径算法的结合15\o"CurrentDocument"4.1竞赛原题154.2问题分析16\o"CurrentDocument"4.3建立道路的网络数据模型17\o"CurrentDocument"4.4管械范围求解174.5调度方案的求解194.6平台增加个数及位置的求解20结论23参考文献24\o"CurrentDocument"附录25致谢28引言科技让世界更紧密，人们的脚步不断在一个个陌生的城市留下足迹。在陌生的地方，如何到达目的地，如何正确到达目的地，如何快速正确到达目的地，是出行者不得不考虑的问题。随着外出频率和距离的增加，卫星导航系统在我们生活中扮演的角色不断提高。独立的卫星导航系统，在军事方面，可以摆脱外国的封锁，建立独立自主的国防体系；在战略方面，可以对他国形成一定威胁力，为信息化建设提供保障；在民用方面，更可以创新搭载平台，促进和推动经济社会发展。而卫星导航系统最日常，最普及，最为人所用，为人所知的用途，就是与我们生活息息相关，出门必备的电子地图！电子地图，即数字地图，是利用计算机技术，以数字方式存储和查阅的地图。电子地图凭借可以进行任意比例尺、任意范围绘图输出，非常容易进行修改，缩短成图时间，与此同时，更可以方便地与卫星影像、航空照片等其他信息源结合，生成新的图种，通过于机，电脑等信息渠道等优势而被人们接受。在电子地图的应用方面，最主要的有两个领域：其一是利用电子地图的等高线和高程点可以生成数字高程模型，将地表起伏以数字模拟形式表现出来，直观立体地表现地貌形态；其一是利用最短路径算法，将两地行进路线完整，完美的表现出来。现实民用方面，无疑最短路领域更是电子地图应用的重中之重！就目前而言，全球各大国对卫星导航系统展开了激烈的竞争，由于我国进入该领域时间较晚，即便北斗的卫星已经成功发射了十六颗卫星，但与美国GPS全球定位系统，俄罗斯“格洛纳斯”系统，欧洲“伽利略”系统在民用方面还有一定的不足，我们日常生活中接触到的电子地图几乎都是以GPS为载体，我们自己的“电子地图”迫切需要与最短路径算法相结合。电子地图与最短路径算法的结合已称为必须，在生活节奏快速的今天更是一种必然。这种结合的作用是显然的，而这种结合的难度也是易见的，前期工作量极大。电子地图与最短路径算法结合的前提是电子地图的“绘制”：在研究最短路径算法时，可以发现无论是对哪个算法，其得以实施，实现的前提都是图。将现实的网络抽象为一般有向图或无向图，然后根据点，边等信息实现算法，而在“绘制”电子地图时，最为关键的就是建立城市交通网络数据模型。电子地图与最短路径算法结合的核心是最短路径算法的实现：二者的结合，从某种角度上看，就是如何在电子地图上实现最短路径算法，如何在已知的抽象得出的有向图或无向图上，实现最短路径算法，得到所求路径，并保证准确有效的到达，是电子地图与最短路径二者结合最突出，最核心的问题。

1基本概念1.1图论基本概念1.1.1图的基本概念一集元素及其之间的某种关系称之为图。具体来说，图通常就是一个二元组(V,E)，其中集合V为顶点集，集合E是顶点集V中元素组成的无序对的集合，称为边集川。例1给定G=(V,E),其中(1.1)V={v,v,v,v}(1234E={(v,v),(v,v),(v,v),(v,v121314(1.1)这便定义了一个无向图G,如下图1.1图1.1无向图G无向图：每条边都是无向边的图G。有向图：每条边都是有向边的图D。混合图：既有有向边又有无向边的图。自回路：一条边的两端重合。简单图：不含平行边和自回路的图。一条无向边可以用一对方向相反的有向边代替，因此一个无向图可以用这种方法转化为一个有向图。重数：两顶点间若有几条边，称这些边为平行边，两顶点Sb间平行边的条数成为(a,b)的重数。多重图：含有平行边的图。逆图：把一个有向图D的每条边都反向由此得到的图称为D的逆图。赋权图：每条边都赋上了值。出度:与顶点相连的边数称为该定点的度数，以该定点为始边的边数为出度。入度：以该定点为终边的边数为入度。度数为零的定点称为孤立点；度数为一的点为悬挂点。

无向完全图：在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。完全有向图：在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图。竞赛图：阶图中如果其底图是无向完全图，则称此有向完全图为竞赛图。V2图1.2V2图1.2赋权有向图1.1.2邻接矩阵邻接矩阵为储存图中“边”信息的一种方法，为表示各个顶点之间关系的矩阵。设G(V,E)是一个具有n个顶点的图，则图的邻接矩阵是一个nxn的二维数组，用Edge[n][n]表示，定义为:Edge[iEdge[i][j]=权值，若(i,j)eEs,否则上述图1.2中的邻接矩阵为:32ssss0s14ss04s3s0ss50s10200Edge=1.1.3邻接表因为邻接矩阵无法存储含有自身环或有重边的图，而且在图的边数较少时，使用邻接矩阵会浪费大量存储空间，所以这时使用另一种存储方式——邻接表。邻接表，就是把从同一个顶点出发的边连接在同一个称为边链表的单链表

中。边链表的每一个结点代表着一条边，称为边结点。对于有向图，每个边结点有三个域：该边终点的序号，该边的权值，以及指向下一个边结点的指针。在邻接表中，还有一个存储顶点信息的顶点数组⑵。图1.3图1.3邻接表1.2最短路的基本概念1.2.1最短路问题给出的是一有向加权图G=(V,E)，在其上定义的加权函数W:EtR为从边到实型权值的映射。路径P=(%,v1七)的权是指其组成边的所有权值之和：w(p)=Zw(p)=Zw(v.,v,)i=1定义u到v间最短路径的权为min8{w(p):Rtv)如果存在由R到V的通路如果不存在(1.2(1.3)从结点u到结点v的最短路径定义为权w(p)=5(r,v)的路径。1.2.2单目标最短路径问题找出从每一结点v到某指定结点u的一条最短路径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。1.2.3单对结点间的最短路径问题对于某给定结点u和V，找出从u到v的一条最短路径。如果我们解决了源结点为u的单源问题，则这一问题也就获得了解决。对于该问题的最坏情况，从渐进意义上看，目前还未发现比最好的单源算法更快的方法。1.3电子地图的基本概念从狭义的角度，电子地图是以数字地图数据为数据基础，以计算机系统为处理平台，在屏幕上实时显示的地图；而广义的来说，电子地图是指屏幕地图和支持其显示的地图软件的总称E。1.3.1电子地图的基本性质⑴电子地图是一种模拟地图产品，仍具有地图的三个基本特征：分色，比例尺，标度；⑵电子地图中数据来源数字地图；⑶电子地图采集及设计都是在计算机平台环境下实现；⑷电子地图表达载体为屏幕。1.3.2电子地图的一般特点⑴电子地图数据的集成性；⑵使用电子地图过程中的交互性：区别于纸质地图，可以让用户交互操作；⑶信息表达的多样性：地图载负量极大扩展；⑷多级缩放和多尺度数据：快速、高效的信息检索与地图分析；⑸多维和动态可视化：使地图效果更加突出；⑹共享性及其低成本性：可存储于地图数据库中，方便复制更新编辑，容易再版。1.3.3地理信息系统GIS地理信息系统，又被称作地学信息系统或资源与环境信息系统，是一种特定的空间信息系统。GIS系统是在计算机硬、软件系统支持下，对整体或局部地球表层空间——含盖大气层在内一一中相关地理分布数据进行采集、储存、管理、运算、分析、显示和描述的技术系统。在地理数据方面，GIS中分为两类：空间数据，与空间要素几何特性有关；属性数据，提供空间要素的信息。在应用方面，GIS技术能够在科学调查、资源管理、财产管理、发展规划、绘图和路线规划中发挥重要作用，如在自然灾害发生时计算出救援反应时间，规律自然保护区等【4］。

2最短路问题的各种算法根据有向网或无向网中各边权值情形及求解的需要，最短路径问题大致分为了以下四类，并分别用不同的算法求解：⑴求单源最短路径，且边的权值非负——Dijkstra算法。单源最短路径指的是固定为一个顶点为源点，然后从源点出发到其他各个顶点的最短路径；⑵求单源最短路径，且边的权值可以为负，但不存在负权值的回路——Bellman-Ford算法；⑶Bellman-Ford算法的改进SPFA算法；⑷求所有顶点之间的最短路径，且边的权值可以为负，但不存在负权值回路Floyd算法⑸。21Dijkstra算法该时效性较好，时间复杂度为O(V*V+E)，可以用优先队列进行优化，优化后时间复杂度变为OV*lgn)。2.1.1Dijkstra算法的原理从出发点出发，每次扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，从而保证了算法的正确性。图2.1Dijkstra算法的执行流程

2.1.2Dijkstra算法实现图2.1Dijkstra算法的执行流程该算法的实现中，需要设置三个数组，即距离数组dis(n)，标记数组s(n),过渡数组path(n)，三个数组构成了一个集合八对从源点七到其他各顶点七(i从1到n)的最短路及其长度而言渡数组path(n)中，path(i)表小从v到v的最短路径上v前一个顶点的序号，若path(i)=0，表小从v至Uv直达且该路径最短；i0i反之，采用“倒序追踪”，得到从v至h最短路径的行进路线。初始时，若v至0v0i0i之间有边，则path(i)=0;若v至Uv,之间无边，则path(i)=-1。得到初始集合T，Dijkstra算法实现的步骤为：⑴在s(i)=0所对应的dis(i)中寻找最小值dis(j)及j;⑵将j对应的s(j)改为1，表示从v0到v.已找到最短路径；⑶在v已经找到最短路径后，检查所有标记数组s(k)=0所对应的顶点七,若顶点v与".有直接相连的边edge[j][k]，且dis(j)+edge[j][k]Ydis(k)，说明从v直接到」的路径，大于先从v到v，在从v到v的路径，此时修改距离数0k0jjk组中dis(k)=dis(j)+edge[j][k]，过渡数组中path(k)=j;反之则不需要改动⑷由改动的距离数组dis(n)，标记数组s(n)，过渡数组path(n)组成一个新的集合T，重新进行上述步骤，只要标记数组s(n)中所有元素均为1。2.2Bellman一2.2Bellman一Ford算法该算法适用于带负权值的单源最短路径问题，其限制条件为：图中不能包含权值总和为负值的回路，即不存在负权值回路。图2.2左负右正的回路全职总和Bellman-Ford算法的原理在n个顶点且无负权值回路的有向图中，如果从顶点v0到七存在最短路径，则该路径至多有n-1条边，即经历了所有n个顶点。对计算从源点v0到其他顶点v的最短路径，Bellman-Ford算法就是构造出一个最短路径长度数组序列：disJi]，dis2[i]，dis3[i]^-disn-1[i]。disjli]说明对计算从源点七到顶点七的最短路径最多一共有j条边，其中j取值范围为1到n-1。算法最终就得到了disn-Ji]，为V到y的最短路径。初始时：0idis1[i]=Edge[0旺](2.1)递推中：{isk-1[i],minbisk-1[j]+Edge[j]k]}}disk[i]=min(2.2)其中：j=0,1-n-1,j丰i;k=2,3…n-12.2.2Bellman-Ford算法实现该算法的实现中，需要设置两个数组，即距离数组dis(n)，过渡数组path(n)，对从源点v0到其他各顶点vi(i从1到n)的最短路径及其长度而言：距离数组dis(n)用来储存一系列的disk[n]，其中k=1,2…n-1；而过渡数组path(n)中，path(i)依然表示从V至h的最短路径上v前一个顶点的序号。0iiBellman-Ford算法实现的步骤为：⑴初始时，dis[i]=Edge[0][i]，选择一个计数变量s，并令s=0，而若V0到V之间有边，则path(i)=0;若V至0V之间无边，则path(i)=-1;i0i⑵比较dis[i]与min{dis[j]+Edge[j][i]}大小，若min{dis[j]+Edge[j][i]}小于dis[i]，则path()=。将dis[i]改为两者的最小值，且s在原来值的基础上加一，艮口s=s+1;⑶重复第二步，直到0000s=n-1，此时dis(n)代表着从V到v(i从1到n)的最短路径，根据path(n)值采用倒向追踪得到各个最短路径的行进路线。从Bellman-Ford算法实现的步骤可以看出，其时间复杂度为O(n3)，而空间复杂度为O(n2)。2-3SPFA算法该算法是采用队列方式Bellman-Ford算法进行优化，主要根据了“每个顶点的最短路径不会更新次数太多”的特点。SPFA算法时效性相对较好，采用一系列松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。其可以在O(km)的时间复杂度内求出源点到其他各个顶点的最短路径，并且可以处理负权值边。k为每个顶点入队列的平均次数，通常情况下k=2。SPFA算法的思想若有向加权图G不存在负权回路，即最短路径一定存在。用邻接表来存储图G。初始时将源点加入队列，每次从队列中取出一点，并对所有与其相连的顶点进行松弛操作(该算法实现步骤⑴)。若某个顶点松弛成功，则将该点入队。重复这个过程，直到队列为空。即采取动态逼近法：设立一个先进先出队列用来保存待优化的结点，优化时每次取出队首结点v，并且用y点当前的最短路径估计值对离开y点所指向的结iii点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的jjj队列中，就将v点放入队尾。以此方式，直至队列空为止。jSPFA算法的实现与Bellman-Ford算法类似，该算法的实现中使用两个数组，即距离数组dis(i)，用来记录源点v0到其他各顶点v.(i从1到n)最短路径；过渡数组path(i)，对从源点v到其他各顶点v(i从1到n)最短路径中v前一个顶点的序号。0ii初始时，dis(0)二0，其余元素均为8；path(i)均为0；并将源点v0放入队列。SPFA算法实现的步骤为：⑴取出队列的头顶点j，扫描从v.出发的每一条边，设边的终点为v，该边的权值为w。若dj(Xdi()，则修改dis(i)为dis(j)+w，同时修改path(i)为j，此时若i不在当前队列中，将i放入队列中；若dis(j)+w>dis(i)，不变动；⑵重复执行步骤⑴，直到队列为空。2-4Floyd算法该算法适用于求多源、无负权边的最短路径，其时间复杂度为O(NA3)，空间复杂度为O(Na2)。2.4.1Floyd算法的思想该算法的原理是动态规划：设D(i,j,k)为从i到j中只以顶点集合V中的某个顶点k为中间节点的最短路径的长度。若最短路径经过点k，则D(i,j,k)=D(kk-1)^Dkjk-1);若最短路径不经过点k，则D(i,j,k)=D(i,j,k-1)。因此D(i,j,k)=min(D(i,k,k-1)+D(k,j,k-1),D(i,j,k-1))(2.3)由公式(2.3)可知：在原有路径的基础上加入其它顶点为中间节点后，若距离缩小，便以新路径替代原有路径。不断更新后，即可得到最短路径。在实际算法中，为节约空间，可以直接在原来空间上进行迭代，从而空间可降至二维。2.4.2Floyd算法的实现对拥有n个顶点的有向图而言，设置一个nxn的方阵A(k)，其中除对角线的矩阵元素都等于0外，其它元素A(Mi][j](i丰j)表示从y到七的有向路径长度，k表示中间节点范围，取值范围为：-1,0,1…,n-1。A(-1)[i][j]表示从七直接到七的边的长度，即A(-1)为邻接矩阵Edge[n][n]；A(k)[i][j]表示从y到y.,中间节点的序号不大于k的最短路径长度；其递推公式为：A(-1)[i][j]=Edge[n][n]A(k)[i][j]=minIa(k-1)[i][j],A(-1)[i]k]+A(-1)[k][j]}(2.4)其中k=0,1—,n-1在Floyd算法实现中，需要使用到两个数组：nxn距离数组A，用来存放一系列的A(k)[i][j]，其中k=-1,0!..,n-1，其规律为公式(2.4)，算法结束时，A[i][j]为从y至0y的最短路径；过渡数组path[i][j]，用来表示从y至0y的最短ijij路径上p前一个顶点的序号。Floyd算法实现的步骤为：⑴比较A[i][j]与A[i][k]+A[k][j]的大小。若A[i][k]+A[k][j]YA[i][j]，则修改A[i][j]为A[i][k]+A[k][j]，同时修改path[i][j]为k;否则，则不变换；(2)k=k+1，重复步骤⑴，直到k=n时，结束算法，此时A[i][j]为从y.到p的最短路径。2.5其他算法一—A*(A-Star)算法该算法是一种静态路网中求解最短路最有效的方法。公式表示为：

f(n)=g(n)+h(n)(2.5)公式中：f(n)是第n节点从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到第n节点的实际代价，h(n)是从第n节点到目标节点最佳路径的估计代价。保证找到最短路径条件，关键在于估价函数h(n)的选取：若估价值h(n)<n到目标节点的距离实际值，搜索的点数多，搜索范围大，效率低，但能保证得到最优解。若估价值h(n)>n到目标节点的距离实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。估价值与实际值越接近，估价函数取得就越好。3城市gK1g17gKRKK3城市gK1g17gKRKK1|-;孔£K-将最短路径算法应用于电子地图之前，需要完成地图的数据化，将现实中的交通网络抽象转化为有向图。首先，基于GIS制定一个面向城市交通需求预测的交通网络数据模型框架；其次，在此框架内对模型的具体内容包括网络拓扑结构、数据库表的结构的表示方法等作进一步的探讨，并给出一个模型实例；再次，针对交通规划中路网方案动态调整的具体特点，对该模型实例进行拓展；最后，得到适合动态路网的数据模型［句。数据是描述事物的符号记录，模型是现实世界的抽象，而数据模型代表着一种实体和实体之间的关系，这些实体和关系被用于创建真实事物或现象的表示形式。网络数据模型是现实世界中的网络系统——排水系统，交通系统等一一的抽象表示.构成网络系统的最基本元素是各个实体以及这些实体之间连接交汇点，前者通常被称为网线或路段，后者一般称为节点。在该网络模型中主要实体包括：形状点、线段、弧段、节点、弧段序列、道路名称、通行条件、交通指示牌等。3.1电子地图数据需满足的技术要求⑴电子地图必须具有较高精确性，包括地理位置数据的精确性和实际地物信息的准确性；⑵电子地图必须提供完备的地物属性信息：一方面是电子地图进行查询检索的需要，另一方面也是进行实际智能交通分析及相关导航应用的客观需要；⑶电子地图对硬件设备有一定要求：电子地图，如车载系统、手持式设备等环境下，硬件条件相对特殊，对导航电子地图的要求也相应地更加苛刻；⑷电子地图数据必须满足全网道路数据的连通性。3.2电子地图基础数据的整理3.2.1道路，建筑物的录入在电子地图中，最基础的是交通道路的位置、走向，长度，以及建筑物的所在区域，要把这些信息已电子地图形式展现，首先需将其录入进系统，构成地形图；3.2.2坐标系的转换因为在收集、录入的时候，工程量较大，故人员较多，而可能采用的不同的坐标模式，这样的话可能会在同一副地图中出现两种坐标系的情况，这样就好导致很大的误差，故需要转化为同一的坐标系标准，将采集，收集到的地形图以指定的单位划入指定的区域；3.2.3地形图的分层、缩编将已经得到的图形按照分层标准对其进行分层，选定标准的比例尺，如1:1000，因不同团队，不同地形的收集到的信息量差异，反应在地图上的信息状况也大不相同，可能局部详细，局部粗糙，而经过处理后，图形中字体大小和线形比例以及块符号的缩放比例可以完成统一修改，但是块符号的密度，经过处理，可能会使一些信息量会产生叠加的情况，此时只能通过人工判断来对图面进行整饰修改，补删一定信息量；3.2.4地形图的接边与图幅分幅地形图在做分层缩编时是以块为单位进行分层整理的，整理过的图要进行接边处理。考虑到实际情况，交接处会产生地物不一制，或者是接边不到位和图形重叠的情况，故在接边过程中阵对图面做整饰处理，不对图形和属性进行一致性接边，尽量保持块区域信息量的完整【7］。3.3城市交通网络数据模型的管理3.3.1格网管理电子地图的使用过程中，使用一定区域范围的道路数据和背景数据的情况非常普遍，因此对城市交通网络数据模型（下简称数据模型）的管理，可以把整个地图区域以格网为单位进行分区管理。格网管理方式为采用层-块-格网的三级线性树状逻辑结构。这种树结构的线性分层分区管理方式，能够大大加快数据信息的检索速度。格网的划分一般有两种情况：一种以一定角度的经度线和纬度线作为边界；另一种以基准点的东西轴和南北轴的平行线为边界线。后者适合于格网为区域较小的数据管理，前者适合于区域较大的数据管理。3.3.2道路网络数据区域管理为了加快路径规划速度，数据模型管理，可以采用创建道路网络数据的管理方式。道路网络数据是在路径规划的过程中为了使用尽可能大范围的数据，以由任意的多边形定义的区域为单位来存放，存在区域根据其外接长方形进行管理。这部分数据为了处理大范围的概略网络数据而进行了分层管理。在同一数据层上，区域之间不允许有重叠，并且上层数据区域必须与下层数据区域相同或者由其合并而成。道路网络数据采用这种线性树状结构，可以提高路径规划时数据访问的效率，加快路径规划的速度。3.3.3索引数据的管理数据模型中基础数据的地点数据的检索，可以通过多种多样的操作顺序来实现。这些操作顺序的检索，如电话号码检索、邮政编码检索、设施检索等，虽然这些检索方式之间存在差异，但对数据模型中地点数据都能实现共用。作为检索结果所需要的地点信息，根据用途或属性的不同可能需要各种不同数据信息。这些信息如果用一个地点信息来表示则会显得冗长，所以有必要准备由多个适当的数据信息构成一个地点信息来共用。在数据模型的管理中，可由实现特定检索方式的检索关键字数据，作为检索结果的共有的基础索引数据，并将其组合为目录的形式划分区域进行管理。4电子地图与最短路径算法的结合在把交通网络抽象为有向图后，以此为基础对交通分配进行建模并求解，但是，交通网络的有向图只是对网络拓扑结构的描述。这仅仅是网络数据模型中的一部分，即便如此，由于交通网络是带转向的网络，普通的有向图也无法对其进行完全的描述，尚有待补充研究；而实际的交通网络还包含大量的空间数据和属性数据，这些数据如何组织、存储，如何与网络拓扑有机的联系起来，更值得考虑。假设有一张地图，其中边上的权值表示两点之间的距离。那么该如何找到起始地点到其他各个地点的最短路径？这些都需要借助最短路径算法！在已经得到的道路数据模型的基础上，按照各种最短路径算法的要求，从相连的地点出发，找到满足要求的路线，即最短路径！约就分钾上海.白站港镇E己公园.浦站六灶镇题挤镇除有镇三此镇下沙镣1惠南很卷港镇制#魄$(2010削脆号位道道通Cata©Navlnfc&上海浦东图吓以场乘坐川南批约1小时36普钟乘坐地铁约就分钾上海.白站港镇E己公园.浦站六灶镇题挤镇除有镇三此镇下沙镣1惠南很卷港镇制#魄$(2010削脆号位道道通Cata©Navlnfc&上海浦东图吓以场乘坐川南批约1小时36普钟乘坐地铁W号线约41始钟闸北国S122近年来，电子地图与最短路径算法结合的问题得到了人们的广泛关注，这在4.1竞赛原题“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1（A区和全市六区交通网络与平台设置的示意图）给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2（全市六区交通网络与平台设置的相关数据表）。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60kmh）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。4.2问题分析本文以实现警察的刑事执法、治安管理、交通管理、服务群众四大职能为宗旨，利用有限的警务资源，根据城市的实际情况与需求合理地设置了交巡警服务平台、分配各平台的管辖范围及调度警务资源。⑴根据题目所给数据，确定各节点之间的相邻关系和距离，利用Floyd算法及matlab编程求出两点之间的最短距离，使其尽量满足能在3分钟内有交巡警平台警力到达案发结点的原则，节点去选择平台，把节点分配给离节点距离最近的平台管辖，据此，我们得到了平台的管辖区域划分。⑵我们对进出该区的13条交通要道实现快速全封锁的问题，我们认定在所有调度方案中，某种方案中耗时最长的的围堵时间最短即最佳方案，利用0-1变量确定平台的去向，并利用线性规划知识来求解指派问题，求得了最优的调度方案。⑶在确定增添平台的个数和具体位置的问题中，我们将尽量保证每个节点都有一个平台可以在三分钟内到达作为主要原则来求解。我们先找出到达每个平台的时间都超过三分钟的节点，并尝试在这些节点中选取若干个作为新的平台，求出合理的添加方案【8-12］。4.3建立道路的网络数据模型图4.2A区交通图其程序为：lp1003图4.2A区交通图其程序为：lp1003u-Hu-Hluu图4.3全市交通图其程序为："膈二-二二:60050040030020010004.4管械范围求解此问要求我们利用数据及附图，将各路口节点划分给最适合的服务平台，并要求各服务台管辖的范围内有突发事件发生时，尽量能在3分钟内有交巡警到达事发地（此时交巡警的行驶距离为3km），换算到比例图上，也就是30mm。本题，不考虑其他因素，只注重唯一因素——距离。所以，我们第一步用刊。州算法求

出各个节点之间的最短距离D。⑴根据题中所给的各个节点的坐标，用matlab计算出任意两点之间的距离，得到92x92的邻接距离矩阵:TOC\o"1-5"\h\z'dd1112dd2122d1.92]d2.92"d1.92]d2.92"d92.1d92.2d)92.927其中d,,分两种情况：当第i个节点与第j个节点相邻时，djj为两个节点的相邻距离。不相邻时，d^为一个充分大的数。⑵运用Floyd算法，求出任意92个节点到任意92个节点的最短距离，得到最短距离矩阵，根据问题需要，我们截取所得矩阵前20行，即任意20个服务平台间到任意72个节点（没有建立平台的节点）的最短距离矩阵D:W11D12D1.72]TOC\o"1-5"\h\zDDD21222.72D=:!:"D20"D20.1D20•2D20.72>因为服务平台的编号为1到20，所以取D的前二十行，后七十二列为观察对象。在观察对象中，取出每列的最小值，计入到原本为设为全0的20x72的矩阵A的相应的位置。对于每一列而言，每列的最小值是最有可能小于3分钟的，如果最小值都不满足这个条件，那么对于这列对应的节点而言，就不存在三分钟可以到达的平台,所用程序为：pingtai.⑶由此，最后每个节点都会归属于某个服务平台，用matlab编程得出结果并绘制了管辖区域图如表4.1.

表4.1服务平台管辖范围服务平台编号管辖范围（节点编号）管辖容量11、67、68、69、71、73、74、75、76、781022、39、40、43、44、70、72733、54、55、65、66544、57、60、62、63、64655、49、50、51、52、53、56、58、59966、47277、30、32、48、61588、33、46399、31、34、35、4551010、2621111、2721212、2521313、22、23、2441414、2121515、28、2931616、36、37、3841717、41、4231818、80、81、82、8352020、84、85、86、872020、84、85、86、87、88、89、90、91、92104.5调度方案的求解本题可以使用运筹学中的指派方法来解决：如果发生重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全面封锁。在全面封锁时，既需要使用最短的时间，还必须保证一个平台的警力只能封锁一个路口，这样就必然会多出7个平台。先根据给出的数据，设立出指派问题的条件矩阵C。C为2020，其中前十三列是A区13个出口到二十个平台的最短路距离，剩余的七列用零补齐。得到C之后，使用linprog算法，就得到我们需要的调度方案，其程序为：zhipai。

根据前一问的解答我们可以得出任意服务平台/到任意出口/的最短距离d，引入0-1变量a10表示，服务平台不封锁j出口a=<歹［1表示i服务平台封锁j出口（4.1）（（4.1）（4.2）Z=min{maxad}.1—ijiji=1J=1约束条件:Fav1st:{J=1艺a21ijIi=1第一个约束表示要求每个服务台只能去1个或0个出口。第二个约束表示每个出入路口有且仅有一个服务平台的警力支持。综上，我们利用linprog编程得出了最优调度方案，结果见表4.2：表4.2出口平台调度方案调度组合12345678910111111平台编号24578910111213141516出口编号38624830291422241223212816距离：mm393.5245.81048277380532470通过分析这些线路，我们知道线路最长的组合为8号平台到达29号节点，它所花的时间即为封锁路口的最终时间，且这个时间约为10分钟。4.6平台增加个数及位置的求解本问要求在第1小问的前提下，根据服务平台的工作量不均衡及出警时间的不合理来增加服务平台的具体个数及位置，使整个交巡警服务平台系统趋于合理化。在第一小问中，我们选择D每一列的最小值，把该节点划分给离他最近的平台管辖。但这样的话，一方面会导致一部分的平台管辖的节点过多，其辖区内部的总案发率过高，而现实中，各平台辖区案发率应该相差不大。另一方面，少量节点到每个平台的最短距离都大于30mm，即到任何平台的时间都超过3min,所以，我们就需要增设一些平台。对于平台添加的原则是添加平台后使得所有节点都有平台可以在三分钟内到达。首先，我们以距离出发，选择D前二十行中，其最小值大于30的列，把这些节点之间的距离从D中提取出去，组成一个方阵。在这个方阵中，选择两节点之间距离小于30mm，小于30说明此两点可以在3min内到达彼此。故可以任意删去一列，删去先出现的列。现在得到需要添加的最多平台数就是上面剩下的那些列对应的节点〃。提取这些节点D中所在行，加上之前的20行，组成一个新的最短距离矩阵B。其中A,B均为20+nx92的矩阵，A是全0阵，B是D中的一部分，进行五次迭代，出现我们需要的平台及对应的辖区。迭代的规则是：⑴在B中选取每列的最小值，赋给A中相应的行列位置。⑵找到A中不为0的位置对应的案发率，把每个位置的距离数字乘以各自的案发率，并除去速度10，平台自身案发率乘以0.5加上。所得数字为每一个平台的判断数。⑶逐行判断，如果某行的判断上数大于所有节点案发率平均数乘以2的话，就把该行中的最大数字在B中置为0。⑷重复上述三步，五次。图4.4迭代前综合指标曲线分布与直方图1234567891011121314151617181920293961表4.3调整后服务平台管辖范围服务平台编号管辖范围（节点编号）管辖容量服务平台编号管辖范围（节点编号）管辖容量TOC\o"1-5"\h\z1、67、68、69、71、73、74、75、76、78102、43、44、70、7253、54、55、65、6654、57、60、62、63、6465、49、50、51、52、53、56、5986、5827、30、32、47、4858、33、4639、34、35、45410、26211、27212、25213、22、23、24414、21215、31216、36、37317、41、42、92418、80、81、82、83、91619、77、79320、84、85、86、87、88、89、90829、28239、38、403611结论进入二十一世纪后，信息化，数字化，虚拟化逐渐成为科技的主流方向，传统意义上的地图已经不能满足人们如今的需求，也不能适应当今的快节奏。电子地图以其不断升级中的功能越来越受到人们的重视，关注以及应用。而电子地图中最重要的功能一一根据客户需求，制订最佳路线一一的实现，依赖于道路的数字模拟和最短路径算法。在现今的导航领域和电子地图市场里，我国有着很大的发展空间，北斗导航系统的运行，更为这些搭建了良好平台，提供了竞争的可能，我国拥有足够的基础，能力以及需求去发展电子地图交通网络，而这也是本文的研究背景。在本文中，首先介绍了最短路径算法和电子地图的基本信息，通过了解这些信息后，对电子地图与最短路径的结合有初步的概念，知道研究的主要方向；其次就是对目前主流的五种最短路径算法学习，对比，实现，了解这些算法的原理和实现步骤；最后以“2011高教社杯全国大学生数学建模竞赛题目”中B题为例，具体问题，具体分析，具体解决：电子地图与最短路径算法结合的前提是电子地图的绘制，在所举事例中，已知了各顶点的坐标以及顶点间道路连接情况的信息，而这在现实应用上，可以通过信息采集得到。拥有信息后，通过matlab软件，对道路建立了数据模型，也就是电子地图的绘制，在这个过程中，需要繁琐但又严谨的工作；而电子地图与最短路径算法结合的核心是最短路径算法的实现，在所举事例中，题目要求是封锁路口，也就是需要整体警力在一定时间内到达指定位置。通过算法编程，实现了介绍的五大算法中的Floyd算法，从而得出了多平台到达多位置的选择。通过软件的调试，给出了合理的解决方案，从而得出如何进行电子地图与最短路径的结合。参考文献高随祥.图论与网络流理论[M].北京:高等教育出版社,2009:1-16.陈磊.电子地图与最短路径算法的结合[J].赤峰学院学报,2009,25(5):26-27.商细云.城市电子地图设计研究[J].太原重型机械学院学报,2004,25(1):49-53.赵明君.建立动态导航中的电子地图数据结构模型[J].数字通信世界,2007,7(9):3-9.王桂平，王衍.图论算法理论、实现及应用[M].北京:北京大学出版社,2011.131-244.郭耀煌，李军.满载问题的车辆路线安排[J].系统工程学报,1995,17(2):17-18.严寒冰，刘迎春.基于GIS的城市道路网最短路径算法探讨[J].计算机学报，2004,23(2):17-23.胡运权，郭耀煌，钱颂迪等.运筹学[M].北京:清华大学出版社,2005.251-285.姜启元.数学模型第四版[M].北京:高等教育出版社,2011.73-88.郭耀煌.运筹学原理与方法[M].成都:西南交通大学出版社,1994.112-177.TriggsB,McLauchlanP,HartleyR,etal.Bundleadjustment-Amodernsynthesis[J].VisionAlgorithms:TheoryandPractice,2000,13(5):47-71.YUDong-kai,LIUYu-shu.StudyonaroutingalgorithmbasedonIchnography[J].JournalofBeijingInstituteofTechnology,2001,21(1):31-34.附录程序：lp1003fork=1:1:928n1=daolu(k,1);n2=daolu(k,2);ifn1<=92ifn2<=92a=jiedian(n1,2);b=jiedian(n1,3);c=jiedian(n2,2);d=jiedian(n2,3);plot([ac],[bd]);holdonendendendx1=jiedian(1:20,2);y1=jiedian(1:20,3);plot(x1,y1,'ro');holdonforn=1:1:92x=jiedian(n,2);y=jiedian(n,3);plot(x,y