时间延伸网络在飓风撤离系统中的应用

1、 武汉理工大学硕士学位论文时间延伸网络在飓风撤离系统中的应用姓名:丁威申请学位级别:硕士专业:计算机应用技术指导教师:熊盛武20210501摘要随着计算机的普及以及地理信息科学的开展,因其强大的功能得到日益广泛和深入的应用。网络分析是的研究热点和难点,而最短路径问题是网络分析中最根本和最关键的问题,国内外大量专家学者对最短路径问题进行过深入研究,提出了多种解决最短路径问题的算法。基于算法的理论根底并针对路径分析的特点,已有的应用系统对算法采用了很多不同的改良方法。鉴于的广泛应用和算法在该应用中的运行效率的重要性,本文通过对最短路径算法的分析,充分利用中空问分布特征,针对中搜索两个特定点的最短路

2、径的应用,从数据结构搜索技术及算法本身对最短路径搜索算法提出了优化和改进,使之更加适合于在两个特定点之自的最短路径查找。本文主要研究工作包括:研究了经典算法的主要思想及其实现;讨论了平面图搜索策略,从问题类型、网络类型和实现方法三个方面对最短路径算法进行系统分类:研究了中的数据结构:分析了各种最短路径算法思想及其应用的数据结构以及各种数据结构的特性:研究了空间分布特征:结合公路交通中查找最短路径的具体情况,分析了传统最短路径算法,提出了一个充分利用自启发算法结合时间延伸网络,来实现了对于飓风来临时候如何有效的在单位时内撤离人群到平安地区的撤离路径选择。最后编程实现了该系统,通过实验验证了该系统

3、的有效性。关键字:自启发算法,最短路径算法,空间分布,路径搜索 .锄 锄, ., . , ,. :. ., . . , . ,. , , 独创性声明本人声明,所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何奉献均已在论文中作了明确的说明并表示了谢意。签名:了数日期:拿:学位论文使用授权书本人完全了解武汉理工大学有关保存、使用学位论文的规定,即:学校有权保存并向困家有关部门或机构送交论文的

4、复印件和电子版,允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库进行检索,可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论文.并向社会公众提供信息效劳。保密的论文在解密后应遵守此规定签名:址导师签名:燃日期:啦武汉理:人学硕十学位论文引 言在如何有效的预测沿海飓风的来临之后,如何在单位时问内有效的速散撤离人民群众是我们值得研究的问题,而撤离系统中找出最短有效的撤离路径问题一直是一个研究热点,而最短路径问题在计算机科学、运筹学、地理信息科学等学科中都起着极重要的作用。的出现是信息技术及其

5、应用开展到一定程度的必然产物。在各类信息管理系统中,是目前开展最快的系统之一,网络分析是空间分析的一个非常重要的方面,而最短路径问题是网络分析中的最根本最关键的问题,因此对应用于的最短路径算法进行研究是有必要的,在研究出有效的最短撤离路径后,我们需要有效的运用在飓风灾难撤离系统中。对于自然灾害的预测人类一直在研究新的预测系统。有了好的预测系统可以在第一时日给我们及时预防。美国飓风给新奥尔良造成了很大的人生财产平安,有了好的预警系统但是如何有效的撤离灾难地区也是需要我们合理的去研究来更小的减轻对人民财产的损失。本文基于自启发算法,将将要受灾的地区划分假设干地区,每个地区在整个在撤离网络中看中一个

6、,两个点自已有公路交通相连,连接两点之间的公路在网络中我们称为一个弧,这样我们可以将受灾地区合理的化为一个撤离网络。为了有效的显示网络中的点有效的撤离人数数量,以及点与点之间的撤离人群的道路交通负载量,在本文中我们提出并建立了“时延伸网络。我们将有效的撤离时间分割给假设干时间片,在每个时片中,每个点都会复制出来,但是每个时间片段中,每个点的撤离人群数量已经点与点之问的撤离负载是会随着时间变化的。在整个时间延伸网络中,我们首先从建立静态网络丌始,而静念网络的建立是基于实践的点已经连接适域点之问的公路。随着时间的推移,我们将时间分割为假设干个时间片段,这样我们可以清晰的显示出整个网络的区域点在整个

7、撤离时间内的情况,在这些时撤离网络点中使得我们能够动态的来选择一条最有效,时间最短,单位时内撤离人数最多的撤离路径。在整个网络中,我们将分为受灾影响的点和绝对平安的点,平安的点在整个网络是不会随着时间的推移受到影响,自始至终都是平安的,而在受灾害影响的网络中,我们的目的是如何有效的将受灾的人民群众平安有效的快速撤离到平安地区。随着时间的推移,有些点处于武汉理:人学硕十学何论文灾害的最沿,这些被影响的区域或者已经被损毁的区域我们必须及时的剔除整个网络,这样我们可以基于有效的区域点已经撤离路径实时有效的来计算整个网络的撤离路径已经撤离人群的数量。武汉理:人学硕十学位论文第章绪论.课题研究背景随着计

8、算机的普及以及地理信息科学的开展,因其强大的功能得到日益广泛和深入的应用。网络分析作为最主要的功能之一,是地理信息系统的重要组成局部,在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的和局设计中发挥了重要的作用,是研究的一个热点和难点。而最短路径问题是网络分析最根本最关键的问题,在交通网络结构的分析、交通运输线路的选择、通讯线路的建造与维护、运输货流的最小本钱分析、城市公共交通网络的;划等方面,都有直接应用的价值。最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其他的度量,如时间、费用、线路容量等。相应地,最短路径问题就成为最快路径问题、最低费用问题等。最短路径算法不仅足资源

9、分配、路线设计及分析等优化问题的根底,交通网络分析中的其它问题,如最可靠路径问题、最大容量路径问题、各种各样的路径导航问题也都可以归并到最短路径问题类型中。其实,无论是距离最短、时间最快还是费用最低,它们的核心算法都是最短路径算法。对于最短径算法的相关研究层出不穷,其各种最短路径算法的分析评述可参见文献。目前在应用领域,对最短路径搜索问题的研究和应用较多,其中最短路径搜索算法的效率问题是普遍关注和在实际应用中迫切需要解决的问题。所采用的算法主要是来源于图论领域中的称为的算法,该算法运行的结果是某一顶点到其它所有顶点的最短路径。算法由于适应网络拓扑的变化,性能稳定,因而在计算机网络拓扑路径选择以

10、及中得到广泛的应用。例如,从美国开展起来的一项重要的移动效劳 位置效劳,方便地帮助用户查找位置信息,做到问路不求人,在“问路不求人功能模块寻找最短路径采用的就是算法。算法的优点还有程序设计简单,通用性强。但将传统算法直接应用于中的最短路径查找是不适当的,首先算法不是针对特定两点的,而在的最短路径寻找中,往往是需要查找两个特定点之问的最短或近似最短路径,因而效率较低力口之传统武汉理:人学硕十学何论文算法中采用邻接矩阵数据结构,占用空问十分巨大,严重浪费计算机的资源,很不适合中结点量巨大的实际情况,最重要的是,传统算法是一个解决平面中源点到其它所有点的最短路径的通用算法,运用中没有去考虑处理对织的

11、空问分佰特征。因此,在通用性和完备性的意义上,算法无疑是非常优秀的,但基于空问分布特征和中最短路径查找的具体情况,其在算法本身的改良及效率的的进一步提高是完全有必要的。.国内外研究现状.技术应用研究现状地理信息系统 ,别是能够收集、管理、查询、分析、操作以及表现与地理相关的数据信息的计算机信息系统,能够为分析、决策提供重要的支持平台。它广泛地应用于地学、资源管理、土地规划、环境监测、防灾减灾、电力行业、交通管理、城市规划、科研、教育和国防等领域,在我国国民经济建设中发挥着越来越重要的作用。目世界上常用的软件已达多种。它们大小不一,风格各异。国外较著名的有/,等;国内较著名的有/,和等。虽然起步

12、晚,但它开展快,目前已成功地应用到一百多个领域。尽管现存的地理信息系统软件很多,但对于它的研究应用,归纳概括起来有两种情况。一是利用系统来处理用户的数据;二是在的肇础上,利用它的开发函数库二次开发出用户的专用的地理信息系统软件。目自,.已成功地应用到了包括资源管理、自动制图、设施管理、城市和区域的规划、人和商业管理、交通运输、石油和天然气、教育、军事等九大类别的一百多个领域。在美囡及兴旺囡家,地理信息系统的应用普及环境保护、资源保护、灾害预测、投资评价、城市规划建设、政府管理等众多领域。近年来,随我国经济建设的迅速开展,也加速了地理信息系统应用的进程,在城市规划管理、交通运输、测绘、环保、农业

13、、制罔等领域发挥了重要的作用,取得了良好的经济效益和社会效益。由于是“关系到国家平安的战略性技术,因此开发拥有自主知识产权的国产武汉理:人学硕十学位论文系统平台,研究和掌握中的前沿关键技术,对我国的开展和应用有着非常重要的意义们。.最短路径算法研究现状最短路径问题?一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。国内外大量专家学者对此问题进行了深入研究。经典的图论与不断开展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。它们在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色。现在的研究热点,一是针对实际应用中网络特征优化运行结构,在统一时间复杂度的蓬础上尽

14、可能地提高算法的运行效率;二是对网络特征进行限制,如要求网络中的边具有整数权值等,以便采用基数堆等数据结构设计算法的运行结构;三是采用有损算法,如限制范围搜索、限定方向搜索及限制几何层次递归搜索:四是采用拓扑层次编码路径视图,对最短路径进行局部实例化编码存储;血足采用并行算法,为并行计算效劳。据统计,目;矿提出的此类最短路径的算法哺大约有种。等人对其中的种进行了测试,结果显示有种效果比拟好,它们分别是 、 。以及 。其中算法的根底是图增长论,用两个队列实现了一个双端队列结构来支持搜索过程,较适合于计算单源点到其他所有点的最短距离。后两种算法那么是基于算法,采用桶结构明显提高了永久标记点的搜索速

15、度。.最短路径算法在中的研究、应用现状路径寻优是网络分析中的一个根本问题蚰。目前基于的最短路径搜索算法研究很多。但用得最广泛的还是来源于图论领域中的称为的算法,该算法运行的结果是某一顶点到其他所有顶点的最短路径。算法的优点赴程序设计简单,通用性强;缺点是算法不是针对特定两点的,因而效率较低;加之邻接矩阵占用空十分巨大,不适合中海量数据的实际情况,严重浪费计算机的资源。这方面的改良研究是地理信息系统领域一个非常有实际意义武汉理:人学硕十学位论文的问题。图论中的最优路径算法是针对所有的实际问题而抽象出的最一般的模型。两点问的路径既可以表示长度,也可以表示工程时间、工程费用等各种属性,因此,在通用性

16、和完备性的意义上,算法无疑是非常优秀的。然而,针对某些特殊的问题,无疑应该有更加高效的算法。因此针对应用中的具体情况对算法进行改良是有必要的,也是一个研究的热点。在应用上还没有实际的运用系统,无论在撤离还是在军队运输上都是有着很重要的研究意义。.论文的研究目标、内容和技术路线.研究目标本文研究的问题为基于算法的最短路径算法分析及它在网络分析巾的应用和改良,主要是要解决基于空白分布特征的算法的改良题。本文将对现有的一些算法的改良方法进行学习、比拟和总结,然后根据中最短路径查找的实际情况,试图从网络结构的拓扑表示数据结构以及算法中快速搜索技术的实现入手,找出一种在应用中能有更高效率的改良算法,并最

17、终实现该改良算法的代码编制和运行。.主要研究内容、研究经典算法的主要思想及其实现:讨论了平面图搜索策略,从题类型、网络类型和实现方法方面对最短路径算法进行系统分类;、研究中的数据结构:分析各种最短路径算法思想及其应用的数据结构以及各种数据结构的特性;、对最短路径算法在实时化和并行化方面的开展进行了讨论;、研究空玎分布特征:结合公路交通中查找最短路径的具体情况,基于自启发算法的时延伸网络结合算法的路径搜索完成了飓风来临时撤离路径的选择与调度。最后编程实现该系统。武汉理:人学硕十学位论文第章 最短路径算法根底.最短路径算法概述最短路径计算分静念最短路计算和动态最短路计算。静态路径最短路是指外界环境

18、不变情况下计算出的最短路径。主要有算法,算法,?算法。动念路径最短路是在外界环境不断发生变化的情况下计算出的最短路径。如游戏中敌人或障碍物不断移动的情况,典型的有?算法。本文讨论的应用中最短路径问题是在公路交通网络中进行,属于静态最短路径计算,因此这罩主要对静态最短路径下的传统路径算法进行分析。对?算法不作介绍。.各种最短路径算法的思想最短路径问题是图论研究中的一个经典算法问题,旨在寻找图由结点和路径组成的中两结点之问的最短路径。 算法具体的形式包括:确定起点的最短路径、题.即起始结点,求最短路径的问题。确定终点的最短路径问题与确定起点的问题相反,该问题是终结结点,求最短路径的问题。在无向网中

19、该闯题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径点,求两结点之的最短路径。全局最短路径问题.求图中所有的最短路径。蚪于解决最短路径题的算法被称做“最短路径算法, 有时被简称作“路径算法。垃短路径问题是图论研究中的一个经典算法问题, 旨在寻找图由结点和路径组成的中两结点之问的最短路径。 算法具体的形式包括:确定起点的最短路径问题.即起始结点,求最短路径的问题。确定终点的最短路径问题.与确定起点的问题相反,该问题是终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转确实定起点的问题。确定起点终点的最短路径问题.即起点和终点,

20、求两结点之间的最短路径。全局最短路径问题.求图中所有的最短路径。用于解决最短路径问题的算法被称做“垃短路径算法,有时被简称作“路径算法。最常用的路径算法有:武汉理。:人学硕十学位论文算法、?算法【引、算法、.算法、.算法、算法。传统的最短路径算法包括计算固定起点到其余各点的最短路径的算法、求解每对顶点、日最短路径的算法和求解带负权有向图的最短路径的算法,它们主要用于求解从某一点到其它点的路程或费用最小,其路径权为各边的权之和。.算法原理算法思想算法足很有代表性的最短路算法,在很多专业课程中都作为根本内容进行了详细的介绍,如数据结构、图论、运筹学等等。传统的算法用于寻求从一固定起点到其余各点的最

21、短路径,它是迪杰斯特拉提出的一个按路径长度递增的次序产生最短路径的算法。算法的根本思想是生成一棵以固定起点为根的最短路径生成树【】。根到树中每个结点的路径即为根到该点的最短路径,因为传统算法所求问题的网络中不存在负权,所以这棵最短路径生成树在生成过程中将对各结点按其距固定起点的远近以及点间的邻接关系来逐个地参加到树中,先近后远。一般的表述通常有两种方式,一种用永久和临时标号方式算法也被称为标号作业法,通过不断地迭代产乍所有的永久标号,一种是用,表方式,下面分别对两种方式进行介绍。标号原理先在所有与固定起点相邻接的点中找到离起点最近的点,递归地,设已找到这棵最短路径生成树的一局部?由与起点距离最

22、短的个结点和相应的条坡氟路径构成,此时,这个结点到起点的最短路径长度将作为它们各自的永久标号。而距离起点最近的第个结点可这样来确定:对所有无标记的结点,构成条从起点到它的路径,在这条路径中先择最短的一条,其长度值作为结点的暂时标号。用同样的方法获得其它无标号结点的暂时标号,最后在所有的暂时标号中选择最小的一个,这个具最小标号的结点设为?即是我们要找的第个结点,将?的标号作为其永久标号,最短路径生成树生成到?。上述过程重复到所有结点都有了永久标号。标号方式算法步骤武汉理:人学硕十学何论文:具有永久标号的结点集;:表示算法中的固定起点:结点的标号,即起点到的最短路径长度;:结点的父亲结点,用以确定

23、最短路径链;:算法中的当玎结点;输入:加权图的带权邻接矩阵 ×.初始化:卜,令,【】,卜。.对,假设卜,那么卜卜,坟卜.设?足使取最小值的中的结点,令卜【?】,俨?.假设,那么转至,否那么停止假设用带权的邻接矩阵来表示带权有向图,表示弧,上的权那么用语言描述的算法如下:,/数纽存放结采路径,数组存放各最短路径长度;/】算法求有向图的顶点到其余啥得行可顶点的最短路径及其带权长度假设为,那么是从到当前求得最短路径上的顶点;/为当且仅当,即已经求得从到的最短路径:;.;/对每个结点作相应的初始化,;/每个结点的初始最长路径长度为到的弧长,如无弧,那么为;.;/设空路径;/;/初始化,、,顶

24、点属于集附;/当所知离顶点的最近距离;.;/顶点在中;/顶点离顶点更近;/离顶点最近的参加集合武汉理:人学硕十学位论文;/更新当最短路径及距离【】【】【】【】/修改【】和【】,?;【】【】;【】【】;/算法表算法步骤创立两个表,和。表保存所有已生成而未考察的节点,表保存已访问过的节点。.访问路网中离起始点最近且没有被访问过的点,把这个点放入组中等待检查。.从表中找出距起始点最近的点,找出这个点的所有子节点,把这个点放到表中。.遍历考察这个点的子节点。求出这些子节点距起始点的距离值,放子节点刘表中。.重复,步,直到表为空,或找到目标点。室算法传统的算法用于寻求每对顶点间的最短路径,此问题虽然可用

25、重复算法来完成,但需要大量的重复计算。算法更适宜解决此类问题,此只介绍其步骤。:距离:到的距离:到的最短路径上的;一个顶点:输入带权邻接矩阵; ,卜;武汉理:人学硕十学位论文,?算法一启发式算法?算法思想?.算法是一种静态路网中求解最短路最有效的方法。公式表示为:,其中是节点从初始点到目标点的估价函数,是在状态空间中从初始节点到节点的实际代价,是从到目标节点最正确路径的估计代价。保证找到最短路径最优解的条件,关键在于估价函数的选取:估价值到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低,但能得到最优解。如果估价值实际值,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解

26、。估价值与实际值越接近,估价函数取得就越好。例如对于几何路网来说,可以取两节点间的直线距离做为估价值,即?;这样估价函数在值一定的情况下,会或多或少受估价值的制约,节点距目标点近,值小,值相对就小,能保证最短路的搜索向终点的方向进行。可见?明显优于算法的毫无方向的向四周搜索。算法主要借助按路径长度递增的次序产生最短路径,将道路网抽象成为结点集合和弧段集合,根据路网中道路的权值可以构建一个带权仃向图,在算法分析之,将静态路径网络中的所有结点分为临时标记点和永久标记点两种类型并分别以表的形式存储,表中存放所有未考察过的临时标记结点,而表用于记录已访问过的并已经确定到起始结点最短距离的永久标记结点,

27、分析主要过程如下:初始化表,除起始结点到自身的距离为外,其他结点默认到原点的距离为无穷大:从表中找出距离起始结点最近的结点,把这个点从表中移到表中:遍历考察第步中找到的点的所有邻接结点,根据此已确定点到源点的武汉理:人学硕十学何论文最短距离修改其邻接结点源点的最短距离值:重复第、步,直到表为空或找到目标点,假设表为空,表示无最短路径解,甭那么起始点到中途所找到的目标点之闻的线路为最短路径。下面为上述过程的类伪码描述。,/用算法求有向网的源点到各顶点的最短路径长度;【卜;/设置初始的点集及最短距离/对点集中每个顶点/设置初始的估计距离为,;?;:/在当点集中选估计距离最小的顶点等丁:/点集中所有

28、表中点的估计距离均为时,/表示这些顶点的最短路径不存在:/将点从表中移至表中/调整表中剩余结点的估计距离【】【】【】【】【】/借助点使原值变小时,用新路径的长度修改】,使离更近。在算法中,第步会大量的重复执行,这一步中的主要动作如下列图所示:武汉理:人学硕十学位论文如上图所示,这个过程中最重要的动作就是从当前所有临时标记结点中找到一个离源点最近的结点并将其标记为永久标记结点,这个过程也可以表述为将当日矿步骤中找到的临时标记点从临时标记点表中移到永久标记点表中,这中日涉及到查自和最正确结点选择两个问题,对最短路径算法的优化大多也是基于此展丌。钎法的时问复杂度为,算法能保证得出下确解,大局部情况能

29、得到最优解,在网络数据比拟复杂时往往得不出最优解。由算法第步可知,查找过程中需要遍历当前结点的所有邻接结点,由图可以看到算法从起始点开始向周闭层层计算扩展,在计算大量节,到达目标点,虽然结果有保证,但速度慢,效率低。武汉理:人学硕十学位论文算法搜索的过程模拟对于起始点固定单源点的空间路径分析,不存在大范围障碍的情况下,算法能较好地分析出最优路径,并且可以保证能得到结果,反之,效果就很差,如图.所示。上图中浅色虚线表示用算法实现的路径,虽然是一种可行的方案,但却消耗很多时间,并且结果不优,在这种情况下,该算法已经失去“最优分析的意义。.牛算法原理在算法提出以前,?算法的思想便在工程、机械及其他领

30、域被提是武汉理:人学硕十学位论文入们对优化过程、提高效率的一种探索,但现代?算法的算法实现过程借鉴了算法的思想,只是应用到最优路径分析过程中时,?改变算法中无序搜索的情况,采用了启发式搜索 ,其核心思想可用下式表示:坟其中表示当前搜索到的结点的估价值,表示当前点到源点的估价,足当前点到目标点的估价,在一定的情况下,的选取或多或少会影响的值,例如在平面路网中,可以简单地采用当前结点到目标结点之间的欧几晕德距离作为估价,这样可以使得搜索方向逐步趋向于终点,速度明显优于算法中毫无方向的搜索,如下列图所示:一 .;一.一?一;一一一一一一:?一?一?一?。?一?一一一奇?咛。 .÷。. 一?

31、,呷一一一,一,寺.;.?.一;.,?一.一,一.?,. ,? 一一 一一一一, 一一?一一一一?一一一一.一图.?算法的搜索过程模拟武汉理:人学硕十学?:论文圈.所示是和算法使用同一个路网,相同的起点终点,用?算析的结果,计算的点数从起始点逐渐向目标点方向扩展,计算的节点数量比少很多,效率很高,且能得到最可行解。?算法思想?.算法是一种静态路网中求解最短路最有效的方法。公式表示为,其中是节点从初始点到目标点的估价函数,是在状态空间中从初始节点到节点的实际代价,是从到目标节点最正确路径的估计代价。保证找到最短路径最优解的条件,关键在于估价函数的选取:估价值到目标节点的距离实际值,这种情况下,搜

32、索的点数多,搜索范围大,效率低,但能得到最优解。如果估价值实际值,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。估价值与实际值越接近,估价函数取得就越好。例如对于几何路网来说,可以取两节点白的直线距离做为估价值,即?:这样估价函数在值一定的情况下,会或多或少受估价值的制约,节点距目标点近.值小,值相对就小,能保证最短路的搜索向终点的方向进行。可见?明娃优于算法的毫无方向的向四周搜索。?算法过程:创立两个表,表保存所有已生成而未考察的节点,表中记录已访问过的节点。遍历当前节点的各个节点,将节点放入中,取节点的子节点,算的估价值。从表中驳估价值最小的节点:节点目标节点;比拟两个的估价值/

33、注意是同一个节点的两个不同路径的估价值的估价值小于表的估价值更新表中的估价值;/取最小路径的估价值 比拟两个的估价值/注意是同一个节点的两个不同路径的估价值武汉理:人学硕学何论文的估价值小于表的估价值更新表中的估价值;把节点放入/取最小路径的估价值 求的估价值;并将插入表中;/还没有排序/将节点插入表中:按照估价值将表中的节点排序:/实际上是比拟表内节点的大小,从最小路径的节点向下进行。/?算法和算法的区别在于有无估价值,算法相当于算法中估价值为的情况。用算法实现?算法。?算法也可以直接用算法程序实现,到达和?完全一样的计算效果,且非常简单。以邻接矩阵为例,更改原来邻接矩阵行列元素.为?:起始

34、点到目标点的方向卜,是终点。为到路段的权重或距离,其中:、的作用相当于估价值到的直线距离:到的直线距离。原理:到方向符合,取?中值小的作为前进方向,因为如果是相反方向?会很大,山此也能到达向目标方向寻路的作用。针对算法的理论根底和?算法的启发,出现了种各样对最优路径算法的优化,对于单源点静念网络的最优路径算法优化整体有两个方向,一种足强调最优路径算法优化的非特性,及主要借助计算机及图论的理论根底进行优化,优化的毛要成果是选择更适宜的数据结构及查询算法来到达优化的目的:另一种那么是充分考虑网络数据的特性,挖掘数据的特殊性可能舀:算法分析过程中提供的智能性。.各种最短路径算法中常用的数据结构以及各

35、种数据结构的特性从上面的介绍中可见,在传统的最短路径算法中,比拟常用的数据结构是邻接矩阵,其最大的好处就是算法设计简单操作方便,但当结点数较大时,武汉理:人学硕十学何论文其占用存储空问会变得很大。因此在一些实际应用中,就需要考虑采用别的数据结构,因此对最短路径算法中常用的一些数据结构作一个简单归纳,见下表:表几种图存储结构比拟表名 称 实现 优点 缺 点 时间复杂方法 度二维 .易判断两点日的关系 占用空间大或邻接矩阵 数组 .容易求得顶点的度邻接表 链表 .节省空间 .不易判断两.易得到项点的出度 点间的关系 或.不易得到顶点的入度十字链表 链表 .节省空间 结构比拟复杂同邻接表.易得到顶点

36、的出度和入度链表多重表 链表 .节省空间 结构比拟复杂 同邻接表.易判断两点日的关系.各种最短路径算法的适用情况不同的路径算法有其不同的适用情况,根据本章前面的介绍,可将传统路径算法的适用情况归纳如下表:表几种算法比拟迪杰斯特拉算法佛洛伊德算法 矩阵算法适用范闱 有向图,无向图 有向图,无向图 无向图,改良后可用于有向图功能 每次求得一个源 求得所有顶点间 求得所有顶点间点至其余各点的 的最短路径 的最短路径最短路径时问复杂度矿 刀否匕.不 求得次短路径 否 否武汉理:人学硕十弓乏俺论文.最短路径算法在实时化和并行化方面的开展展望最短路径算法在实时化方面的开展。目,静态的最短路径算法已经十分完

37、善。但是,在实践中,网络特征可能时刻会发生变化,要求最短路径算法必须能够实时地自动更新。这类问题主要集中在交通网络的实时导航、通勤、调度和计算机互联网的数据传递路由等方面。最短路径算法在并行化方面的展望。随着计算机处理数据量的逐渐增多,传统的串行计算机的负荷也逐渐加重。运行在效劳器端的最短路径算法必须向耩于图分解的并行算法的方向开展,以满足大量的实时最短路径查询的需要。关于最短路径并行算法的讨论有两种类型,一种基于较抽象的并行计算模型,不限制处理器的数目,研究给定问题的计算复杂度在并行计算的情况下能降到什么程度。如果已经到达下界,再设法减少处理器的数目,或放松对处理器间耦含程度的一些不尽合理或

38、不尽现实的要求;另一类研究那么针对实际的并行计算系统,其处理器数是有限的至少不可能与问题规模相当,研究如何设计或实现某个或某类问题的并行求解。此类并行算法的设计往往还伴有在实际系统上的计算实例和性能分析。由于对处理器的数目进行了合理的限制,并行计算系统在实践中更有价值,是最短路径问题算法并行化研究的趋势所在。.最短路径算法系统分类最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。困内外大量专家学者对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。它们在空问复杂度、时间复杂度、易实现性及应用范围等方面各具特色。.问

39、题类型分类按照起始、终结节点及路径的数目和特征,最短路径问题可分为种类型,即单对节点日最短路径、所有节点问最短路径、那么最短路径、实时最短路径和指定必经节点的最短路径问题。其中又可衍生出其他一些特殊的最短路径问题,如限制弧段数目最短路径、含环路径等。分类体系见下列图:武汉理:人学硕十学何论文习 园圈径隘嚣 短路径 絮踹陬翮臃羔哦径 经转点 弧嚣羽障含环 戳制 “。囝园图分类体系图.网络类型分类按照刚络特征与表示方法的差异,最短路径问题可按下列图所示体系进行分类。值得注意的足,采用邻接矩阵方法来存储网络拓扑数据,虽然可以在时内完成,是否是一条网络边的查询,但对最短路径算法最关键的关联节点查询,其

40、复杂度均为。这就决定了基于邻接矩阵的最短路径算法时间复杂度没有降低的可能。此外,采用邻接矩阵存储网络拓扑数据的空间复杂度为,。这样,对于一个包含个节点的交通网络,仅邻接矩阵就至少需要的存储空问,这显然是不现实的。文献和文献分别提出采用最大相关边法和最大相关点法存储网络拓扑数据,只不过是邻接矩阵的一种简化。由于图中各个节点的度数不同,这种方法仍然存在大量的数据冗余,造成存储审问的浪费,并非如文献所描述的“采用最大相关点法存储网络拓扑数据可以数卣倍节省内存,在此根底上,利用节点号与矩阵行号之间的对应关系实现判断矩阵的快速查询和计算,必将提高运算速度。邻接矩阵的表达方法,只是过去在小型网络的所有节点

41、对之日最短路径算法中曾有应用。在现在动辄具有上万节点的大型网络中,采用邻接矩阵存储拓扑数据既不现实,也无必要。与邻接知阵的窄.复杂度效率比拟已经没有意义。邻接表是另一种存储网络拓扑的数据结构,它是一种链式存储结构,在网络相关算法中应用广泛。在交通领域武汉理:人学硕十学位论文内,将蚓络的顺序邻接表与逆向邻接表通常称为 表与表.。对于节点查询而言,邻接表中关联节点查询时间复杂度仅为/。此外,对于交通网络等稀疏图./,采用邻接表数据结构存储网络拓扑数据空问复杂度仅为,不存在存储空间的浪费,当和路径或路段相关的信息较多时更是如此。邻接表数据结构已被证明是网络表达中最有效率的数据结构,在最短路径算法中得

42、到了广泛应用加,.筇,】。罔络特征及太。水办上?.,. 围 困园圆圈圈篙州络 同络 网络¨图圜圈圆圆圈自卤国圈图圈亘巫垂匝亘囹匝匦困臣回。一圆圈.实现方面分类另种最短路径算法分类方法是按实现技术分类,分类方法如图.所示。其中路径搜索技术中的通用技术是最短路径算法研究的重点所在。路径搜索通用技术又可分为组合技术和代数方法两种。组合技术主要是指标号算法。标号算法也是绝大多数最短路径算法的核心局部【。按照不同的标谚节点处理策略,标号算法又可分为标号设定,简称和标号改丌,简称两大体系。代数方法通过运筹学中的线性规划形式化、所定义代数系统中的联立线性方程集形式化和矩阵乘法等方法来求最短路武汉理

43、:人学硕十学位论文径问题。算法又称为最短优先搜索算法,最早由荷兰数学家于年提出基于堆结构和桶结构优先级队列的算法是研究得最深入、应用也最广泛的算法。算法的广泛应用使之已成了算法的代:。其他算法多为算法的不同实现方式。值得注意的,算法描述的是算法的实现方法,与网络的存储结构无关【。不同的实现方法决定了不同的时间复杂度,并非如文献中所述:“算法需采用矩阵形式表达网络拓扑,其时间复杂度为刀,并且当网络节点与弧段数到达数量级以上时因不能定义数组而无法采用算法。事实上,只有当采用最原始的无序联接表作为运行结构时算法时间复杂度才为。当采用叉堆、二项堆或堆优先级队列来实现算法时,其时间复杂度为或旺引,采用桶

44、结构基数堆实现的算法,在假定弧段足整数权值前提下,复杂度为/为最大整数权值,而基数堆和堆相结合的算法复杂度仅为/【】。文献【】中提出算法的时间复杂度为矿,并将其作为所提出的单源最短路径算法的比拟根底,更是不讵确。算法又称为列表搜索算法。其代表性算法包括?算法、.算法、算法】、门限算法引、拓扑排列算法和 算法等。实际上,所有的或算法都可总结为一种更为一般性的算法的特例。不同之处在于处理图中所标识节点时采用的优先级队列系统各不相同】。算法在优先级队列处理的每一步.都能得到一条由源点到其余节点的最短路径,由此当仅需:最短路径时,当终点跳优先级队列时即可结束。但算法不能处理含负权边的网络;而锊法处理:

45、诲点时,可能需要屡次进出优先级队列,因此源点到终点的:最短路径需到算法结束时才能得到。算法可处理含负权边的网络。长期以来,专家学者们对和算法的效率比拟进行了深入的研究。文献【认为,对于稠密图,算法优于.算法;而对于稀疏图,虽然有指数形式的最坏时间界.算法仍然是最优的。文献的研究结果也说明.算法可与最好的算法媲美。文献【的研究结果说明,对于不同网络形式,各种算法效率差异很大,但并没有一种算法针对各种网络形式均有较好的效率。对于矩形规那么格网型网络,中的和算法效率最高;武汉理:人学硕十学何论文对于稠密网络,双桶算法和门限算法效率最高;对于非平面的规那么格网型网络,算法和堆结构的算法效率最高;对于无

46、环图,算法和拓扑排列算法效率最高【值得注意的是,理论上最优的算法不一定在实践中最优。例如,文献【提出的基于堆的算法较之算法在理论上具有更小的时间复杂度【引,但在实践中,算法效明显高于算法¨叭。.本章小结本章对静态路径最短路径计算中的传统算法进行了概述,重点介绍了本文将在第五章中进行改良的传统算法思想及其实现,最后对最短路径算法进行了一个系统分类。武汉理:人学硕十学位论文第章根本理论介绍.概述.的概念电子计算机的兴起极大地推动了地学的开展,人们开始有可能用电子计算机来收集、存储和处理各种与空间和地理分布有关的图形和属性数据,并希望通过计算机对数据的分析来直接为管理和决策效劳。这种与的结

47、合即地学与计算机科学的结合就导致了地理信息科学的问世。地理信息系统,简称。顾名思义,地理信息系统是处理地理信息的系统。地理信息是指直接或间接与地球上的空间位置有关的信息,又常称为空.信息。一般来说,可定义为:用于采集、存储、管理、处理、检索、分析和表达地理空数据的计算机系统,是分析和处理海量地理数据的通用技术。从系统应用角度可进一步定义为:由计算机系统、地理数据和用户甜成,通过对地理数据的集成、存储、检索、操作和分析,生成并输出各种地理信息,从而为土地利用、资源评价与管理、环境监测、交通运输、经济建设、城市规划以及政府部门行政管理提供新的知识,为工程设计和规划、管理决策效劳。.的开展简史及应用

48、现状开展简史。人类生活在地球上,%以上的信息与地球上的空间位置彳.关。的出现足信息技术及其应用开展到一定程度的必然产物。从开展现状和趋势来看.地理信息系统技术是一门综合性的技术,它的开展是与地理学、地图学、摄影测量学、遥感技术、数学和统计科学、信息技术等有关学科的发展分不丌的。的开展可分为四个阶段:第一个阶段是初始开展阶段,世纪年代世界上第一个系统由加拿大测量学家.提出并建立,主要用于自然资源的管理和规划:第二个阶段是开展稳固阶段,世纪年代山于计算机硬件和软件技术的飞速开展,尤其是大容量存储设备的使用,促进武汉理:人学硕十学位论文了朝实用的方向开展,不同专题、不同规模、不同类型的各具特色的地理

49、信息系统在世界各地纷纷付诸研制,如美国、英国、德国、瑞典和日本等国对的研究都投入了大量的人力、物力和财力;第三个阶段是推广应用阶段,世纪年代,逐步走向成熟,并在全世界范围内全面推广,应用领域不断扩大,并与卫星遥感技术结合,开始应用于全球性的问题,这个阶段涌现出一大批软件,如/,等:第四个阶段是蓬勃开展阶段,世纪年代,随着地理信息产品的建立和数字化信息产品在全世界的普及,成为确定性的产业,并逐渐渗透到各行各业,成为人们生活、学习和工作不可缺少的工具和助手。地理信息系统的研制与应用在我国起步较晚,虽然历史较短,但开展势头迅猛。我国的开展可分为三个阶段。第一阶段从年到年,为准备阶段,主要经历了提出建

50、议、组建队伍、培训人才、组织个别实验研究等阶段。机械制图和遥感应用,为的研制和应用做了技术和理论上的准备。第二阶段从年到年,为起步阶段,完成了技术引进、数据标准和标准的研究、空间数掘库的建立、数掘处理和分析算法及应用软件的丌发等环节,对进行了理论探索和区域性的实验研究。第三个阶段从年到现在,为初步开展阶段,我闺的研究和应用进入有组织、有方案、有目标的阶段,逐步建立了不同层次、不同;模的组织机构、研究中心和实验室。研究逐步与国民经济建设和社会生活需求相结合,并取得了重要进展和实际应用效益。主要表现在四个方面:制定了国家地理信息系统标准,解决信息共享和系统兼容问题,为全国地理信息系统的建立做准备。应用型开展迅速。在引进的根底上扩充和研制了一批软件。:始出版有关地理信息系统理论、技术和应用等方面的书籍,设立了地理信息系统专业,培养了大批人彳,并积极丌展国际合作,参与全球性地理信息系统的讨论和实验。应用现状。世.己年代以,国外城市交通资料主要通过关系型数掘库柬管理属性资料,空开数据那么是以图形式存放与管理