电子地图与最短路径算法结合精简版

电子地图与最短路径算法的结合

专业:信息与计算科学学生姓名:xx远指导老师:宋政芳

[摘要]最短路径问题在图论研究中是一个长盛不衰的经典问题,旨在寻找图中指定两结点间的最短路径。而电子地图如今蓬勃发展,依托计算机成象等技术,直观呈现面画来为人们服务。电子地图需要借助最短路径算法,得出指定起始点至目的地的行进路线,而最短路径算法通过电子地图建立使用渠道,二者的结合相互融合间又相互促进。其结合前提是电子地图的绘制,核心是最短路径算法的实现。

[关键词]电子地图;最短路径算法;数据模型

The Combination of Electronic Map and the Shortest Path

Algorithm

Abstract: The shortest path problem in graph theory is an enduring problem, aims to find the shortest path between two specify nodes of the graph. With the development of electronic maps which depends on computer imaging technology, it service for people intuitively. Electronic map need use a shortest path algorithm, and gets the road from the starting point to destination. This combination promotes the development of each other. Meanwhile the combination is the premise of electronic map in the "drawing" and the core of the realization of the shortest path algorithm.

Key Word: Electronic Map;Shortest Path Algorithm;Data Model

前言

科技让世界更紧密,人们的脚步不断在一个个陌生的城市留下足迹。在陌生的地方,如何到达目的地,如何正确到达目的地,如何快速正确到达目的地,是出行者不得不考虑的问题。随着外出频率和距离的增加,电子地图的使用次数与范围不断增加。

电子地图的应用方面,最主要的有两个领域:一为模拟地貌地形,一为依托最短路径算法实现最短路程的选择。现实民用方面,第二部分无疑更受关注和使用。电子地图与最短路径算法的结合已称为必须,在生活节奏快速的今天更是一种必然。这种结合的作用是显然的,而这种结合的难度也是易见的,前期工作量极大。

电子地图与最短路径算法结合的前提是电子地图的“绘制”,只有将现实道路网络抽象为一般有向图或无向图,才能以此基础去实现算法;电子地图与最短路径算法结合的核心是最短路径算法的实现,实现最短路径算法之后,才能根据实际需求,寻求满意服务。

一、基本概念

在本文里,主要涉及图论,最短路径问题和电子地图三大部分的知识点。

首先介绍图论时,给出了图,度数等基本概念,这些都是最短路径算法实现的基础。同时,对邻接矩阵,邻接表进行定义,依托这两个存储图的方法,实现不同的最短路径算法[]1。

其次介绍最短路径问题时,给出了该问题的基本定义,以及在不同情况,不同要求下的定义,由浅入深,对该类问题的认知不断增加。

最后介绍电子地图时,给出其基本性质,一般特点,以及开发所依托的地理信息系统的信息,让读者在进入课题正式研究介绍前,对课题有一定的了解。

二、最短路径算法

在如今发展中,尚未出现一个明确,可靠的评价标准去评判哪个或哪几个最短路径算法是最优的。随着研究的深入,最短路径算法的种类也不断增加,现在比较常用的最短路径算法有:Dijkstra 算法、Bellman Ford -算法、SPFA 算法、Floyd 算法等,比较有特征的算法有()*A A Star -算法等

[]24-。本文着重介绍Floyd 算法,该算法适用于求多源、无负

权边的最短路径。

1.Floyd 算法的思想:

设(),,D i j k 为从i 到j 中只以顶点集合V 中的某个顶点k 为中间节点的最短路径的长度。若最短路径经过点k ,则()()(),,,,1,,1D i j k D i k k D k j k =-+-;若最短路径不经过点k ,则()(),,,,1D i j k D i j k =-。

因此 ()()()()(),,min ,,1,,1,,,1D i j k D i k k D k j k D i j k =-+-- ()2.1

由上述公式可知:在原有路径的基础上加入其它顶点为中间节点后,若距离缩小,便以新路径替代原有路径。不断更新后,即可得到最短路径。在实际算法中,为节约空间,可以直接在原来空间上进行迭代,从而空间可降至二维。

2.Floyd 算法的实现

对拥有n 个顶点的有向图而言,设置一个n n ?的方阵()k A

,其中除对角线的矩阵元素都等于0外,其它元素()[][]k A i j ()i j ≠表示从i v 到j v 的有向路径长度,k 表示中间节点范围,取值范围为:1,0,1,1n -- 。

()[][]1A i j -表示从i v 直接到j v 的边的长度,即()1A -为邻接矩阵[][]Edge n n ;

()[][]k A i j 表示从i v 到j v ,中间节点的序号不大于k 的最短路径长度;

其递推公式为:

()[][][][]1A i j Edge n n -=

()[][]()[][]()[][]()[][]{}111min ,k k k k A i j A i j A i k A k j ---=+ ()2.2

其中0,1,1k n =-

在Floyd 算法实现中,需要使用到两个数组:n n ?距离数组A ,用来存放一系列的()[][]k A i j ,其中1,0,1,1k n =-- ,其规律为公式()2.2,算法结束时,[][]A i j 为从i v 到j v 的最短路径;过渡数组[][]path i j ,用来表示从i v 到j v 的最短路径上j v 前一个顶点的序号。

Floyd 算法实现的步骤为:

⑴比较[][]A i j 与[][][][]A i k A k j +的大小。若[][][][][][]A i k A k j A i j + ,则修改[][]A i j 为[][][][]A i k A k j +,同时修改[][]path i j 为k ;否则,则不变换;

⑵1k k =+,重复⑴,直到k n =时,结束算法,此时[][]A i j 为从i v 到j v 最短路径[]5。

三、电子地图

将最短路径算法应用于电子地图之前,需要完成地图的数据化,将现实中的交通网络抽象转化为有向图。

首先, 基于GIS 制定一个面向城市交通需求预测的交通网络数据模型框架;其次,在此框架内对模型的具体内容包括网络拓扑结构、数据库表的结构的表示方法等作进一步的探讨,并给出一个模型实例;再次,针对交通规划中路网方案动态调整的具体特点,对该模型实例进行拓展;最后,得到适合动态路网的数据模型。

在该网络模型中主要实体包括:形状点、线段、弧段、节点、弧段序列、道路名称、通行条件、交通指示牌等。

四、电子地图与最短路径算法的结合

本文以“2011高教社杯全国大学生数学建模竞赛题目”中B 题——交巡警服务平台的设置与调度——的第一小问为例,探讨电子地图与最短路径算法的结合。

1.问题分析

本文以实现警察的刑事执法、治安管理、交通管理、服务群众四大职能为宗旨,利用有限的警务资源,根据城市的实际情况与需求合理地设置了交巡警服务平台、分配各平台的管辖范围及调度警务资源。

⑴根据题目所给数据,确定各节点之间的相邻关系和距离;

⑵认定在所有调度方案中,某种方案中耗时最长的的围堵时间最短即最佳方案; ⑶尽量保证每个节点都有一个平台可以在三分钟内到达作为主要原则来求解。

2.地图模拟

电子地图与最短路径算法结合精简版

电子地图与最短路径算法结合精简版

图4.1 建立的数据模型 3. Floyd 算法解决问题

⑴用该算法求出各个节点之间的最短距离D 。根据题中所给的各个节点的坐标,用matlab 计算出任意两点之间的距离,得到9292?的邻接距离矩阵:

???????? ??=?????92922921929222221

9211211d d d d d d d d d d

其中ij d 分两种情况:当第i 个节点与第j 个节点相邻时,ij d 为两个节点的相邻距离。不相邻时,ij d 为一个充分大的数[]68-。

⑵运用该算法,求出任意92个节点到任意92个节点的最短距离,得到最短距离矩阵,根据问题需要,我们截取所得矩阵前20行,即任意20个服务平台间到任意72个节点(没有建立平台的节点)的最短距离矩阵D :

???????? ??=?????72202201207222221

7211211D D D D D D D D D D

因为服务平台的编号为1到20,所以取D 的前二十行,后七十二列为观察对象。在观察对象中,取出每列的最小值,计入到原本为设为全0的7220?的矩阵A 的相应的位置。

对于每一列而言,每列的最小值是最有可能小于3分钟的,如果最小值都不满足这个条件,那么对于这列对应的节点而言,就不存在三分钟可以到达的平台。

⑶由此,最后每个节点都会归属于某个服务平台,用matlab 编程得出结果并绘制了管辖区域图。

三、结论

电子地图与最短路径算法结合的前提是电子地图的绘制,在所举事例中,已知了各顶点的坐标以及顶点间道路连接情况的信息,而这在现实应用上,可以通过信息采集得到。拥有信息后,通过matlab 软件,对道路建立了数据模型,也就是电子地图的绘制,在这个过程中,需要繁琐但又严谨的工作;

而电子地图与最短路径算法结合的核心是最短路径算法的实现,在所举事例中,题目要求是封锁路口,也就是需要整体警力在一定时间内到达指定位置。通过算法编程,实现了介绍的五大算法中的Floyd 算法,从而得出了多平台到达多位置的选择。

通过软件的调试,给出了合理的解决方案,从而得出如何进行电子地图与最短路径的结合。

参考文献

[1] 高随祥.图论与网络流理论[M].北京:高等教育出版社,2009:1-16.

[2] 陈磊.电子地图与最短路径算法的结合[J].赤峰学院学报,2009,25(5):26-27.

[3] 商细云.城市电子地图设计研究[J].太原重型机械学院学报,2004,25(1):49-53.

[4] 赵明君. 建立动态导航中的电子地图数据结构模型[J].数字通信世界,2007,7(9):3-9.

[5] 王桂平,王衍.图论算法理论、实现及应用[M].北京:北京大学出版社,2011:131-244.

[6] 严寒冰,刘迎春.基于GIS 的城市道路网最短路径算法探讨[J].计算机学

报,2004,23(2):17-23.

[7] 郭耀煌.运筹学原理与方法[M].成都:西南交通大学出版社,1994:112-177.

[8] Triggs B,McLauchlan P,Hartley R,et al.Bundle adjustment-A modern synthesis[J].Vision

Algorithms:Theory and Practice,2000,13(5):47-71.

指导老师评语:(250字左右)

附录:

程序floyd.m

function [D,path]=floyd(A)

n=length(A);

D=A;

path=zeros(n);

for i=1:n

for j=1:n

if D(i,j)~=inf

path(i,j)=j;%j->i

end

end

end

for k=1:n

for i=1:n

for j=1:n

if D(i,k)+D(k,j)

D(i,j)=D(i,k)+D(k,j);

path(i,j)=path(i,k);

end

end

end

end

相关推荐
相关主题
热门推荐