网络分析的的毕业论文.doc 50页

'网络分析的的毕业论文第一章绪论二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视，最短路径问题是图论中的一个典范问题，它已经被应用于众多领域.最短路径问题最直接的应用当数在地理信息领域，如：GIS网络分析、城市规划、电子导航等.在交通咨询方面，寻找交通路网中两个城市间最短的行车路线就是最短路径问题的一个典型的例子.在网络通信领域，信息包传递的路径选择问题也与最短路径问题息息相关.举个例子，OPSF开放路由选择协议，每个OPSF路由器都维护一个描述自治系统拓扑结构的数据库，通过这个数据库构建最短路径树来计算路由表，从而跟踪自治系统范围内到每个目标的最短路径.在图象分割问题中，最短路径也有直接的应用：在语音识别中，一个主要的问题就是区别同音词，例如，to、two、too.为解决这个问题，我们需要建一个图，顶点代表可能的单词，边连接相邻的单词，边上的权代表相邻的可能行大小.这样图中的最短路径，就是对句子的最好解释.由于最短路径问题的广泛应用，很多学者都对此进行了深入的研究，也产生了一些经典的算法.近些年来，对最短路径研究的热度依然不减，并且时间复杂度降得越来越低.所以在本课题中我们将提出不仅是以前我们学习过的一些经典的算法，我们还将提出一些以前没有学习过的更有应用空间的算法.以及各算法之间的比较.最后还将把这些算法在现实中的应用最一些简单的介绍.50 第二章网络的最短路问题的基础知识2.1图的基本概念（1）图定义：一个（无向）图G是一个有序二元组（V，E），其中是顶点集，是边集，且是一个无序二元组，它表示该边连接顶点与.图1就是一个图.说明：在保持图的点边关系不变的情况下，图形的位置、大小、形状都是无关紧要的.若，则称连接与；点和称为的顶点，称或与关联，与是邻接的顶点；如果两条边有一个公共顶点，则称这两条边是邻接的；（2）环定义：两个顶点重合为一点的边称为环(如图图1中).V1V2V3V4V5图1（3）重边定义：如果有两条边的顶点是同一对顶点，则称这两条边为重边（如图1中与50 中有两条边相连）.（4）孤立点定义：不与任何边关联的点称为孤立点（如图1中）；（5）无环图定义：没有环的图称为无环图；（6）简单图：定义：既没有环也没有重边的图称为简单图.设G=（V，E）是一个简单图，则显然有.（7）完全图定义：若上式中等号成立，则说明该图中每对顶点间恰有一条边相连，称此图为完全图.（8）补图定义：一个简单图的补图是与有相同顶点的简单图，且中两个点相邻当且仅当它们在中不相邻.（9）二分图定义：一个图G=（V，E），若存在V的一个分划（，），使得每条边有一个顶点在中，另一个在中，则称为二分图.（10）子图、支撑子图定义：设有两个图，，如果，，则称为的支撑子图.（11）点导出子图定义：设有图G=（V，E），是的非空子集，若以为点集，以两点均在中的所有边为边集的子图称为由导出的的子图，记为，简称点导出子图.（12）边导出子图定义：若是的一个非空子集，则以为边集以50 中边的所有顶点作为点集的子图，称为由导出的的子图，记为，简称边导出子图.（13）度：定义：图中顶点的度为与关联的边的数目（与关联的每个环算作两条边），记为.结论：设G=（V，E）是一个图，则，即度数为奇数的顶点有偶数个.2.2有向图（1）有向图定义：一个有向图是一个有序二元组，其中是顶点集，称为的弧集，为一个有序二元组.称为连向的弧，为的出弧，的入弧；称为得尾，称为的头；称为的前继，称为的后继.图2就是一个有向图.V1V2V3图2（2）环定义：头和尾重合的弧称为环.（3）重弧定义：若两条弧有相同的头和尾，则称这两条弧为重弧.（4）简单有向图定义：没有环和重弧的有向图称为简单有向图‘（5）基图定义：把有向图中每条弧用边来代替，得到一个无向图，称为得基图.50 （6）完全有向图定义：设G=（V，E）是一个简单有向图，则，若等号成立，则称这样的图为完全有向图.（7）出度、入度定义：有向图中顶点的出弧的数目称为的出度，记为；顶点入弧的数目称为的入度，记为.结论：设G=（V，E）是一有向图，则类似地可以定义有向图的子图，支撑子图，点，边导出之子图的概念.（8）网络定义：设是一个图，若对的每一条边都赋以一个实数，称为边的权，则连同边上的权称为一个网络，记为.同样可以定义有向网络.在此主要讨论网络上的各种优化问题.无向网络可以转化为有向网络，具体做法为：把无向网络中每条边代之以一对弧（）和（），且两条弧的权都等于边的权.2.3连通性（1）途径、迹、路定义：设有图G=（V，E），如果它的某些顶点与边可以排成一个非空的有限交错序列，这里该途径中边互不相同，则称为迹；如果顶点互不相同，则称它为路.显然路必为迹，但反之未必.（2）闭路径定义：如果某途径至少含一条边，且起点与终点重合，则称它为一条闭途径.类似可定义闭迹和回路（又称圈）.注意：若为简单图，则两个顶点间边若存在必是唯一的，故由到50 的一条途径可以用顶点序列表示.（1）连通图：定义：图中若存在一条从顶点到的途径，则称与是连通的.如果图中任何两个顶点都是连通的，则称是连通图.例如，完全图是连通的.二分图，，则只要，中有一个大于1，则一定不是连通图.（2）连通子图定义：如果是的子图，且是连通的，则称为的连通子图.（3）极大连通子图定义：如果为的连通子图，且不存在连通子图，使是的子图.图的极大连通子图又称为的连通分支.（4）有向途径定义：设有一个有向图，中某些顶点与弧组成的非空有限序列这里，，且，则称它为从到的有向途径.类似可定义有向迹，有向路，有向闭途径，有向闭迹，有向回路（有向圈）.当是简单有向图时，从到的一条有向途径可简记为（）.（5）强连通定义：中若既存在一条从顶点到的有向途径，又存在从到的有向途径，则称和是强连通的.如果中任意两顶点都是强连通的，则称是强连通的.（6）强连通分支定义：的极大强连通子图称为强连通分支.注：若强连通，则恰有一个强连通分支.结论：若为有个连通分支的简单无向图，则的邻接矩阵为准对角矩阵50 若为有个强连通分支的简单有向图，则的邻接矩阵为准上三角矩阵2.4割集（1）割边定义：设有图，是的一条边，如果从中删去，使它的连通分支数量增加1，则称是的割边.显然，的一条边是割边当且仅当该边不包含在的任何闭迹中.（2）边割定义：设是的一个非空子集，，记，如果，且从中删去这些边后，的连通分支至少增加1，则称是的一个边割.（3）割集定义：若是一个边割，且的任何真子集都不是边割，则称它为极小边割，的极小边割又称为割集.结论：任给图，设是图的圈，是图的割集，用表示的边集.如果，那么.（4）弧割定义：设是一个有向图，记，如果，则从中删去这些弧以后，的强连通分支数至少增加1，称它为的一个弧割.的极小弧割称为有向割集.50 2.5最短路问题定义：所谓最短路径是指如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条有向路径使得沿此路径上各弧的权值总和达到最小.50 第三章网络的最短路问题的算法研究3.1最短路问题的提出某旅客要从杭州乘飞机前往奥地利的萨尔斯堡，因为他害怕乘飞机，所以要选择一条航线，使得在空中飞行的时间尽可能的少.问题是如何选择航线以达到要求.为此构造一个无向网络总可以化成有向网络，故下面只讨论有向网络的最短路问题.设是一有向网络，为中一条有向路，称为路的权或路长.现寻找网络中自某一指定顶点到另一指定顶点的最短有向路.3.2Bellman最短路方程设有一个有向网络，.若用表示自顶点到顶点的最短有向路长，用表示弧（）的长度，若，则定义，则对一切有且当且仅当弧在自顶点到顶点的最短有向路上.因为所有均表示自到的最短路长，因此这些最短路必有最后一条弧（），且该有向路上自到的一段也是最短路，故有Bellman最短路方程：即自点到各点最短路长度必满足Bellman最短路方程.反过来，Bellman最短路方程的解是自点到其余各点最短路的长度.3.3无负回路网络的最短有向路的Ford算法50 3.3.1Ford算法的基本思想Ford算法的思想是逐次逼近，每次逼近求出网络从到其余各顶点的带某种约束的最短路，这里的约束是路中弧数.第一次逼近是从到其他任意顶点由一条弧组成的所有路中找一条最短路，记其长度为;第二次逼近是从到由不多于两条弧组成的所有路中找一条最短路，记其长度为.一般地，第次逼近是从到由不多于条弧组成的路中找一条最短的，记其长度为.因为中自到的最短路至多含个顶点，条弧，所以最多次逼近即可.即为中自到的最短路长.3.3.2Ford算法的步骤为方便起见，定义.第一步置，，.第二步令.第三步若，停止;否则令，返回第二步.3.3.3实例求如下图所示网络中从顶点到其余各点的最短路.V3V2V6V1V5V450 解求解过程如下:因此从到的最短路径分别为，，，，，路长分别为1，2，-3，0，2.3.4求正权网络中有向最短路的Dijkstra算法3.4.1Dijkstra算法的基本思想对网络中每个顶点赋以一个标号，用来记录从顶点到该顶点的最短路的长度（此时称为永久标号）或最短路长度的上界（此时称为暂时标号）.算法开始时，只有顶点被赋予永久标号，其它顶点被赋予暂时标号.一般地，算法在被暂时标号的顶点中寻找一个顶点，其暂时标号最小，然后将赋予永久标号，且对其余暂时标号的顶点按方式修正其标号.算法在所有顶点均被赋予永久标号终止.3.4.2Dijkstra算法的理论依据（1）对于中任一顶点，其永久标号是从顶点到该顶点的最短路的长度.（2）对于中任一顶点，其暂时标号是从顶点出发，只经过中顶点到达该顶点的最短路的长度.3.4.3Dijkstra算法的算法步骤最短路径问题是指在一个赋权图的两个指定节点和之间找出一条具有最小权的路.Dijkstra算法是一个解最短路径问题的算法，这个算法不仅可以找到最短的，路径而且可以给出从到图中所有节点的最短路径.50 其基本步骤如下:(1)设，对所有的节点来说，设，并将标号为0，，为和w之间的权值(距离).(2)按照每个未标号的节点w计算，，表示点t到点w之间的权值(距离).若被修改了说明在当前得到的到w的最优路径上t和w相邻用记录下来在所有中选择一个最小的即，未标号.将s标号为，表示节点到s的最优路径的长度为且与s相邻.(3)若终点v已标号，则停止.得到一条从到v的最优路径，否则，转向(2)再计算.3.4.4Dijkstra算法的应用举例G以具体实例说明Dijkstra算法的具体应用.例1.利用Dijkstra算法求图1中节点A到其它各节点的最优路径.K202.93.2D18N4.43.53.24.5B16HEY4.12.2PL144.223.44.5AI125.62.934.22.2OMC103.4JF3.542.2380246X8图1101214相应的权值为：50 根据Dijkstra算法的实现步骤其计算过程可归纳为表1所示.从表1中可以看出从到的最短路径为——————且到的距离为=18.3在求到最短路径的过程中到其余各点的最短路径也相应求出.若以计算一次为计算单位，则利用Dijkstra算法计算到最短路径时所需的计算次数=15+14+13++2=119次表1采用Dijkstra算法求解A到其他各节点最优路径的过程序号ABCDEFGHIJKLMNOP1-4.23.42-4.23.4/A9.06.93-4.2/A-8.68.36.94---8.68.36.9/C11.910.95---8.58.3/B-10.311.210.96---8.6/B--11.510.311.210.97------11.510.3/D11.210.913.513.78------11.5-11.210.9/F13.513.713.19------11.5--11.2/E-13.513.713.110------11.5/D---13.513.713.111----------13.513.713.1/J16.112----------13.5/H13.7-18.016.113-----------13.7/H-15.916.114-------------15.9/L16.118.715--------------16.1/M18.33.4.5Dijkstra算法的不足50 在现行电子地图中，网络模型的规模常常较大，节点数多达上千或上万，并且对网络模型的查询也要求实时性，因此Dijkstra算法虽然在理论上是可行的，但在实际应用中不尽人意，当网络模型中节点数和边数较多的情况下，算法的计算量较大时间花费较多效率非常低.3.4.6改进Dijkstra算法的基本思想及实现表1中的数值大多数是，都是无用运算，如果节点数量很大，将极其浪费运算时间.由于，节点是否在上次已经被计算出最短路径未知，当前节点是否与节点是否相连也未知，也就是未知，这时是已知的，故本次计算的到底是不是，取决于上一步数值和的数值，从表达式可以看出，只要这两个数值不都是，本次计算的就不会是，所以在上面Dijkstra算法的实现步骤第(2)步时，先判断一下，只要原来的，的数值中至少有一个不是，才进行下面的计算，这样就保证了当预见是时，不对它进行计算，避免了大量无效的计算，提高了搜索效率.下面仍以一个具体实例来说明改进的Dijkstra算法的具体应用.例2利用改进的Dijkstra算法求图1中节点A到其他各节点的最优路径，此例的计算过程和Dijkstra算法基本一致，只是表1中所有标记的部分在改进Dijkstra算法中被省去了，利用改进的Dijkstra算法计算到最短路径时所需计算次数为次，由此可见，改进的Dijkstra算法确实减小了计算量(在程序设计中，判断语句所花费的时间可以忽略，并不增大计算量).3．4．7实验对比为了更好地说明改进的Dijkstra算法的有效性，利用C语言自行编制了最短路径搜索程序并进行了仿真实验，采用自绘制的地图，共5张，第一张图16个节点，共24条弧;第二张图32个节点，共55条弧;第三张图43个节点，共75条弧;第四张图62个节点，共111条弧;第五张图78个节点，共139条弧，计算结果如表2所示.50 从表2可以看出，两种算法的计算量有很大的区别，改进的Dijkstra算法较之经典Dijkstra算法在计算量方面有很大幅度的减少，而且这种减少的程度在节点数目增加(地图更大，更复杂)时，会变得越来越明显.对于实际系统，由于地图都会很大，使用改进Dijkstra算法的改进效果将非常显著.表2改进Dijkstra算法和经典Dijkstra算法计算次数比较节点数经典Dijkstra算法改进的Dijkstra算法1611947(39.5%)32465134(28.8%)43861234(27.2%)621830441(24.1%)782926540(18.5%)注:表中的百分数表示改进算法计算量与经典算法计算量的百分比3．5算法的问题和改进3.5.1算法的基本思想算法在人工智能中是一种典型的启发式搜索算法.通过选择合适的估价函数，指导搜索朝着最有希望的方向前进，以求得最优解.算法中关键是求估价函数:其中，是从起点到当前节点已付出的代价，是从当前节点到目标节点的代价估计函数，必须保证(其中是从当前点到目标点的实际最小代价).3.5.2算法的步骤算法的搜索步骤如下:(1)给起始节点标记，对它的没有标记过的子节点进行扩展;(2)对每一个子节点计算评价函数值，按评价值的大小进行排列，找出评价值最小的节点，并给它作标记，如果当前节点就是目标节点，则停止搜索;50 (3)否则，对最新被标记的节点进行第(2)步处理并记录最短路径.3.5.3算法分析算法是利用对问题的了解和对问题求解过程和解的了解，寻求某种有利于问题求解的启发信息，从而利用这些启发信息去搜索最优路径.它不用遍历整个地图，而是每一步搜索都根据启发函数朝着某个方向搜索.当地图很大很复杂时，它的计算复杂度大大优于Dijkstra算法，是一种搜索速度非常快、效率非常高的算法.但是，相应的算法也有它的缺点.启发性信息是人为加入的，有很大的主观性，直接取决于操作者的经验，对于不同的情形要用不同的启发信息和启发函数，且他们的选取难度比较大，很大程度上找不到最优路径.下面通过一个具体加以实例说明.例3利用算法求图1中从点出发到点的最优路径.解:在本例中将评价函数中的取为当前节点到起始节点的最短距离，而取为当前节点到目标节点的欧氏距离，在应用算法时除采用上面Dijkstra算法所用过的拓扑结构外，还应该再给定所有节点的坐标如各点坐标为(0，13)，(3，16)，(3，11)，….根据算法的具体实现步骤可求得从到的最短路径—————其距离是=16.6.查看表1可知，用Dijkstra算法搜索的最优路径是—————，路径长度15.9，很明显算法没有找到最优路径，而且通过比较两条路径可以发现:当采用算法搜索路径时，从第二个节点就把最优路径舍弃了.3.5.4算法改进思想及实现为了克服最优路径可能被轻易舍弃的缺点，本文提出采用多次搜索的方法，用增大计算量为代价来换取尽量多的最优路径备选结果.具体的方法如下:将经典算法搜索出原始最优路径中的节点依次进行封堵后，再按照经典50 算法搜索在每一次封堵情况下的最优路径.最后将这些新的最优路径与原始最优路径进行对比以便确定最后的最优路径.现举例说明改进算法的具体应用.例4.利用改进的算法求图1中从点出发到点的最优路径.(1)按算法寻找路径得到:—————，路径长度16.6;(2)封闭此路径中节点后得到的最优路径为:—————，路径长度15.9;(3)封闭此路径中节点后得到的最优路径为:—————，路径长度17.1;(4)封闭此路径中节点后得到的最优路径为:—————，路径长度17.2;(5)封闭此路径中节点后得到的最优路径为:—————，路径长度18.7;对前面求得的5种路径长度进行对比，得到最优路径—————，其长度为15.9，从而将此路径定为改进算法求得的最优路径.查看表1可知此路径正是采用Dijkstra算法时求得的最优路径.3.5.5实验对比为了进一步验证改进算法的有效性利，用C语言自行编制了最短路径搜索程序并进行了仿真实验.以78个节点(含1个起始节点，77个待规划节点)的地图作为对象得到的仿真结果.采用经典算法对77个节点分别进行路径规划，有45个找到了最优路径而采用改进的算法对77个节点进行路径规划时，有68个找到了最优路径，有8个节点虽未找到最优路径但得到了比经典算法更短的路径，只有1个节点和经典算法结果一致.这充分说明改进的算法较之经典的算法在搜索最优路径的成功率方面具有明显的优势.3.6结论本文对经典Dijkstra算法和算法进行了改进，改进后的算法具有以下特点.50 (1)改进的Dijkstra算法能在很大程度上节省计算量，提高路径规划的速度.(2)改进的算法虽在一定程度上增大了计算量(但远远小于Dijkstra算法的计算量)，却大大增大了搜索到最优路径的成功率.3.7混合步长网络漫游最短路算法3.7.1引言网络最短路问题一直是网络理论与实践的重要研究课题之一，是在工农业生产及各项经济活动中非常具有实用价值的一门计算技术，是系统工程和运筹学研究的一个重要分枝．随着图与网络理论的不断发展与完善和计算技术、计算手段的不断进步，为新的网络最短路算法的研究提供了前提和条件．经过深入的研究探索和实践，本文提出一种任意路权网络最短路的新算法——混合步长网络漫游法．3.7.2网络漫游法原理在一个给定的任意路权网络图中，为该网络的点集合，为该网络的弧集合，为网络各弧的权数集合．确定一个点作为漫游网络的起点，并记该点的漫游路长为零，其余各点的漫游路长，以此作为初始状态．之后，每一步都以当前漫游点的路长来修正其余相关连点的路长，并选择一个新的漫游点，如此往复，直至不再有可以漫游的点为止．若从起始点到任意点的直接路长为（为网络的顶点数，若两点和之间没有直接的弧连接，则），则以修改各点的初始漫游路长，作为第一步各点的漫游路长，并选择所对应的点作为第一步的漫游点，称之为当前漫游点．一般而言，经过步漫游到达第点，则第点为当前漫游点，该点的当前漫游路长为．为寻找下一步的漫游点，要计算，并以作为点第步的漫游路长，选择点作为第50 步的漫游点，如此循环，直至各能够到达的点均已漫游过且各点已不存在更短的漫游路长时，漫游终止．同时得到了从起始点到各点的最短路．3.7.3网络漫游法的特点3.7.3.1混合步长每次从当前漫游点寻找下一漫游点时，采用了算式，所以，下一漫游点的路长不只是第步中的最短路，而且是在第步、第步、…、第1步、第0步中的最短路，是当前步长内所有步数能够到达该点的最短路．3.7.3.2路长递减性由于采用了算式作为第点的第步的路长，它小于等于步之内任一步长的路长，具有递减性．3.7.3.3条件记忆性由第k步的当前漫游点寻找下一漫游点时，是在除当前点之外的其它点中寻找．其余的点分为两类，一类是还没有漫游过的点，它自然属于寻找的范围；另一类是已经漫游过的点，这类点分为两种情况，其一是该点记录的步步长之内的最短路值是该点作为漫游点时的路长，则该点不在寻找之列，即该点已漫游过这件事是在记忆之中的，其二是该点虽然已漫游过，但在其后的漫游中更新了该点漫游时的路长值，则该点在寻找范围之列，即对该点已漫游过这一事实失去记忆，如同没有漫游过的点一样．也就是说，若该点作为漫游点时的路长值一直保持为该点的最短漫游路长，则对该点保持记忆；若该点作为漫游点时的路长值已发生变化，则对该点的漫游失去记忆．3.7.4网络漫游法的算法50 对于给定的任意路权网络，按照如下步骤进行网络漫游，只要网络中不含负回路，最终总可以求得从起始点到其所能到达的所有点的最短路．当然，也可以从终点反向漫游，以求得从网络的任意一点到终点的最短路．3.7.4.1确定漫游起始状态若求从某点到其它各点的最短路，则以作为漫游的起始点（当前漫游点），并记该点的起始漫游路长为零，其余各点的漫游路长为无穷大（注：若求其它各点到终点的最短路，则以作为漫游起点，进行反向漫游即可）．3.7.4.2从当前漫游点向外探索计算从当前漫游点走到其它各点所产生的路长3.7.4.3确定各点新的漫游路长将各点的与其当前的最短路长进行比较，选取较小者作为该点新的漫游路长，即．3.7.4.4作漫游标记当从本漫游点向外探索之后则对其作一标记，表示此点已漫游过．在以后的漫游中保持此标记，直到该点有更短的漫游路长出现时，则除去该点的漫游标志．3.7.4.5确定新的漫游点在当前没有作漫游标记的点中，选取所对应的点作为新的漫游点．返回3.2继续漫游．50 3.7.4.6漫游终止条件当给当前漫游点标上漫游标记，而其它点要么是标有漫游标记的点，要么是路长为无穷大的点，故找不到新的漫游点，则算法终止．3.7.5算例网络漫游法求最短路可以采用手工表上作业法，也可以采用计算机程序算法．手工表上作业法对于一般的网络而言是简便易行、步骤清晰．对于较复杂的网络则采用计算机程序算法为宜．现以例演示手工表上作业法（见图1和表1）．表1任意路权网络漫游法表上作业法示例50 3.7.5.1算法说明①步长为零的行为起始状态行，点为漫游起点并标记当前漫游点标记（），它的起始路长为零，其余各点的起始路长为无穷大．②步长1-6都分成了两行，上面一行称为计算行，它是从当前漫游点走到下一漫游点的总路长；下面一行称为选取行，它要做三件事：a选取者作为第点的当前漫游路长．b将上一步的漫游点标记（）在本步中改变为已漫游标记[]．如果某一点在上一步中就是带有已漫游标记的，且新的漫游路长，则保留其漫游标记，否则，去掉漫游标记．c从当前选取行中没有漫游标记[]的数值中，选定一最小值，并做上当前漫游点标记（）．50 ③如果当前选取行中已不存在不带漫游标记的有限数值，则漫游终止，当前选取行中的数值就是从起始点到各点的最短路长．3.7.5.2寻找最短路线从表中最后一行的最短路长向上寻找，只观察各步的选取行，当遇到某选取行的值大于当前值时，则横向寻找该步的漫游点，并从该漫游点以同样的方法向上寻找，直到起始点为止．这其间所经过的漫游点的集合就是所对应的最短路线．如本例中查找从起始点到点的最短路线，如表中虚箭线所示，其路线为：．同样地，可以找到所有点的漫游路线．3.7.6结束语本文探讨的网络最短路的一种新算法—混合步长网络漫游法，既具有T—P标法的简易性，又具有负路权的特性，而且便于手工表上作业.对于计算机算法的设计思路将进一步研究，且已获初步成果.3.7.7混合步长网络漫游最短路算法的进一步研究混合步长网络漫游最短路算法，阐述了混合步长网络漫游的算法原理、特点和具体的算法步骤．本文将进一步就该方法的可行性定理、负回路的检测、最大漫游次数进行研究．3.7.7.1网络漫游可行性定理定理1在一不存在负回路的任意路权网络中，若从起始点到任意一点有路可走，则通过网络漫游一定可以到达该点．证明：因为在混合步长网络漫游中，从起始点开始向外探索，且的初始路长为零，其余各点的初始路长为无穷大．50 又第步的探索所得到的任意点j的路长为，其中，为当前漫游点，为点至之间直接路权．每一步探索都可能改变其它各点的漫游路长，，且可能扩大已探索点的范围，即各个点的漫游路长是单调非增的．又网络中不存在负回路，即从一点出发不可能再直接回到这一点．最多经过步就可以探索到点，使其成为可漫游点，并最终成为已漫游点．从而得到从起始点到该点的最短路及最短路长．[证毕]3.7.7.1负回路的检测问题上述网络漫游法可行性定理是在网络中不存在负回路的前提下得出的．如果网络中存在负回路，则不论是手工表上作业法，还是计算机程序算法都会出现无限循环现象．如果在进行网络漫游前不能确定网络中是否含有负回路，或者要确定这一事实要花太多的精力而跳过这一步，则在进行网络漫游的同时要进行负回路的检测，一旦检测到负回路的存在，则算法终止．所谓负回路，就是在网络图中存在的一个回路，且构成该回路的各弧的路权之和为负值．如果从某点出发经过若干步直接的漫游之后又回到该点，则标志网络中存在负回路．这里所说的直接漫游就是指下一个漫游点是由当前漫游点(所对应的点)直接计算路长所确定下来的，否则就是非直接漫游．需特别注意的是，网络漫游法允许而且可能某一点的多次漫游，而并不存在负回路，但它必须是非直接的．所以，当某点再次被漫游时，就要检测此点两次漫游之间的所有漫游是否都是直接的，若其中有一步是非直接的，则说明再次漫游该点是非直接的，否则，就是直接漫游，它表明网络中存在负回路．下面以手工表上作业法漫游网络来演示负回路的检测．50 在图1所示的网络图中存在着负回路用手工表上作业法漫游网络时应该能够发现这种现象，否则就会无限漫游循环．如表1所示，当点再次漫游时（表中第5步），就应该进行检测，判断是否存在从点又回到点的回路．图1存在负回路的任意路权网络示意判断的方法是：从当前漫游点（表中第5步点）向上探索，当遇到大于当前漫游路长值时（包括计算行和选取行），横向搜索该行的漫游标记，遇到漫游标记时以同样的方法继续向上探索，如此进行下去．如果能够到达当前漫游点的上一次漫游的位置（表1中第2步的），则找到了负回路；如果在探索的过程中从某一步的计算行转了方向，而找不到上一漫游点，则表明当前漫游为非直接漫游，即再次漫游该点并不表明存在负回路．如表1中第5步点的再次漫游，从该点沿虚箭线向上探索，当探索到第2步时，从计算行转了方向而找不到上一漫游点，所以点的再次漫游不能说明存在负回路．再如表1中的第6步，点再次漫游，从该点沿实箭线向上探索并接连虚箭线，可以一直探索到第2步点的上一次漫游，它表明网络中存在以为顶点的负回路，这一探索的路线正是网络中负回路的逆向，即检测到负回路．表1混合步长网络漫游手工表上作业法的检测负回路功能示例50 3.7.7.3网络漫游次数定理定理2（起始漫游定理）在不存在负回路的网络中，起始点的漫游次数为1．证明：起始点为漫游的出发点（记起始漫游为1次），且规定其漫游路长为零，其余各点的漫游都是本点的直接漫游．如果从某一点再次回到起始点，则必然存在直接漫游负回路，而与假设矛盾．在不存在负回路的网络中，起始点的漫游次数一定为1．定理3（相邻漫游定理）网络中某顶点的最大漫游次数小于等于指向该点的各相邻点漫游次数之和．50 证明：在网络中某顶点得以漫游，则表明存在从起始点到该点的路．一般而言，是可以漫游点，而、、指向的点，则点的每次漫游势必经过、、之一，即必有、、之一先于点漫游．点的最大漫游次数不会超过直接指向该点的各点漫游次数之和．命题得证．定理4（最小漫游定理）若网络中某点存在可以漫游的相邻入度点，则该点的漫游次数至少为1．证明：若网络中有弧，且为可漫游点，即存在从起始点到点的路，适得点得以漫游．也就必然存在从起始点到点的路，适得点得以漫游，即点至少漫游一次．问题得证．3.7.7.4结束语本文就作者所提出的“混合步长网络漫游最短路算法”进行了进一步的探讨，研究了网络漫游法的可行性问题、负回路检测问题、最大漫游次数问题以及计算机算法原理．但是，其理论还不十分完善，诸如最大漫游次数与图的结构之间的关系、各点均达到最大漫游次数时网络图的性质、任意两顶点之间漫游路长的算法等等许多问题还有待于进一步的研究．50 第四章最短路问题的应用4.1多条最短路算法的优化城市交通设施的建设远远落后于汽车的增长，由此造成的城市交通道路的堵塞和拥挤已成为世界各大城市面临的共同难题，其解决办法就是大力发展智能交通系统(ITS)，改变现有的交通管理模式.ITS研究中的一项基础的研究工作就是如何确定最佳出行路线，也就是要确定任意两点间最短路问题.由于实际交通网络系统中存在着路段堵塞现象，所以仅仅给出任意两点间的一条最短路显然是不够的，应给出多条最短路供给ITS系统判别并选出最佳出行路线.4.1.1算法的优选总结现有的算法就不难发现当今算法可分为两大类.一是枚举法，它通过依赖函数在与局部梯度相关的方向上移动来寻找局部最优，即先找到局部最优，再沿最佳允许方向处理函数.枚举法现在很多情况和规模上被认可，但效率很低，由于很多实际问题的网络都很大，以至于搜索一次需要的计算量很大，运算速度缓慢，但它能一次算出多条最短路，而这恰恰是我们所需要的；二是随机算法，它是利用随机技术来实现的.根据随机技术的不同又可分为遗传算法和模拟退火算法.就目前较为热门的遗传算法而言，它是一种基于自然选择原理和自然遗传机制的搜索(寻优)算法，将达尔文进化论中的“适者生存”与利用随机信息进行变化相结合.说到随机性，遗传算法不是简单的随机走动，而是有效地利用、开发原有信息，并带着期望改善的性能去推测新的搜索点.因此在处理大型网络时比较有效，但它无法一次算出多条最短路.比较上述两类算法的优、劣之后，决定选取枚举法来进行优化后使用.因为找到多条最短路是最终的目标，随机算法虽能有效地处理大型网络，但却无法搜索到多条最短路，进行优化也比较困难；枚举法虽在处理大型网络时效率较低，但却能搜索到多条最短路，且优化也较容易些.50 枚举法中的算法又可分为求解一条最短路算法和求解多条最短路算法.文献[2]、[3]中均给出了在稀疏网络中一条最短路的优化，但都不适于求解多条最短路问题.在求解多条最短路算法中又包含两个算法，既二重扫除法(Shier)和推广的福劳德算法(Floyd).其中用二重扫除算法求任意两点间K条最短路需用O(KN3)时间，(其中N为节点数，KN3为运算次数，O(KN3)表示进行KN3次运算所用的时间)；而推广的福劳德算法需用O(2N3).因此当K大于1时，推广的福劳德算法优于二重扫除算法，所以选择推广的福劳德算法作为进一步优化的算法.但推广的福劳德最短路算法存在着自回路现象；同时由于运输网络一般为大型网络，运算次数极为庞大，致使运算速度极为缓慢，使得在实际应用中难以操作，因此需要对现有的算法进行优化.4.1.2问题的描述一个运输网络可以用一个有向图来表示.其中V为顶点集，；为边集，为权集，.假设要求出条最短路，则从点到点的条最短路的距离定义为一向量，，其中的元素表示第条最短路的距离，而距离对应的路径为向量，中的元素排列顺序为到依次经过的点的顺序.此种算法包括了一个特殊的代数运算，称为广义和运算，在这类运算中把向量看成单个数值，参加运算的向量要求维数相同，其元素值允许含，取两个同维向量进行交叉和运算，结果经排序以后得第三向量，其维数相同，而元素取自排序后的最前部分，设广义和的运算符号为×，则广义和的运算为.4.1.3优化后的多条最短路算法的思想50 在推广的福劳德算法中存在着自回路现象，但这种自回路现象不会出现在最短路上，只会出现在大于1的短路上.又因当自回路现象出现时，必定在该条最短路路径中重复出现次其一个或多个点，因此在改进算法中，搜索任意两点第条最短路径所经过的点，然后再进行判断.如果一个点重复出现两次或两次以上，即为自回路现象，则不对最短路距离和最短路路径进行更新，这样就避免了自回路现象.同时在对运算次数较大的优化中，采用分解算法，把网络分为两个互相叠和的子网络(也可分为多个子网络，多个子网络的算法同两个子网络的算法类似，由于多个子网络的算法叙述较为复杂，这里就不再赘述).如把网络分为两个子网络、，其中、网络分别为如图1所示：图1分解算法示意图图中，子网络间相邻的点集为最小点割集，即网络中删除及其相邻的边以后，网络就分解为两个子网络，且不存在的子集能使网络不连通.即：，，，，其相应的距离距阵，可以分块如下形式：式中：，其余类推.50 这样分解后，在计算最短路的路径和最短路的距离时，首先计算第一个子网内部的最短路的路径和最短路的距离(其中最短路径中包含的点只有网络中的点)，然后再计算第2个子网内任意两个点间的最短路的路径和最短路的距离(其中最短路径中包含的点为整个网络中的点)；再计算第一个子网内部的最短路的路径和最短路的距离(其中最短路径中包含的点为整个网络中的点)；最后计算两个子网、间的最短路的路径和最短路的距离.至此得到最后结果.以上分解算法在计算第二步以后的各点间的最短路的距离和最短路的路径时，用到了前一步已算出的最短路的距离和最短路的路径，大大减少了运算次数，加快了运算速度.4.1.4优化后的多条最短路算法的步骤第一步，把网络分为两个(或以上)互相叠和的子网络.第二步，初始化每一个子网络的条最短路的距离及条最短路的路径.若两点间没有通路，则设置为一个无穷大的数.第三步，确定第一个子网的条最短路的路径及其距离.既在中就下列距阵元素执行三角运算(三角运算即进行加法和比较大小的运算，也即下述运算)：其具体步骤又可分为下列几步：(1)在一个子网中，求出从顶点到顶点的条最短路，其中只允许前个顶点即顶点1.2.3.……作为中间点(初始值)；50 (2)从顶点到顶点的条最短路，其中只容许前个顶点即顶点1.2.3.…作为中间点(初始值j=1)；(3)分别判断从到的条和从到的条最短路的路径中有无重复点，即和二向量中的元素有无重复元素，若有，则最短路经中不包含点，也不对进行计算，并转向(1)，若无重复点，则进行下一步；(4)计算(5)比较，中的元素，并求出最短的个距离；(6)根据(5)步所选出的最短的个距离，确定K条最短路的路径；本步运算终止后可得、、、.第四步，在第二个子网中就下列距阵元素执行三角运算：即重复第三步中的6步，本步运算终止后可得，，，第五步，在第一个子网NA中就下列距阵元素再执行三角运算：本步运算终止后可得.50 第六步，计算二个子网、间任意二点间的条最短路的距离及条最短路的路径，根据如下公式：其中：、、…为向量，运算符+为广义和运算.至此，距阵中所有元素均得最短路距离：4.1.５结语本文首先对各种最短路算法进行了优选，在选出了推广的福劳德算法后，又对它进行了优化.其优化后的算法已在计算机中实现，并取得了较满意的结果.但由于选取的网络节点较少，所以对节点较多的网络还应进一步加以调试.4.2GIS网络分析功能的实现随着计算机的普及以及地理信息科学的发展，GIS因其强大的功能得到日益广泛和深入的应用.网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用，而网络分析中最基本最关键的问题是最短路径问题.最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等.相应地，最短路径问题就成为最快路径问题、最低费用问题等.由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统等（如110报警、119火警以及医疗救护系统），这些系统一般要求计算出到出事地点的最佳路线的时间应该在1s～350 s内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的.其实，无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法.经典的最短路径算法——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对Dijkstra算法采用了不同的实现方法.4.2.1经典Dijkstra算法的主要思想Dijkstra算法的基本思路是：假设每个点都有一对标号，其中是从起源点到点的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；则是从到的最短路径中点的前一点.求解从起源点到点的最短路径算法的基本过程如下：1)初始化.起源点设置为：①，为空;②所有其他点:，? ;③标记起源点，记，其他所有点设为未标记的.　　2)检验从所有已标记的点到其直接连接的未标记的点的距离，并设置：式中，是从点到的直接连接距离.　　3)选取下一个点.从所有未标记的结点中，选取中最小的一个：，所有未标记的点］点就被选为最短路径中的一点，并设为已标记的.　　4)找到点的前一点.从已标记的点中找到直接连接到点的点，作为前一点，设置：　　5)标记点.如果所有点已标记，则算法完全推出，否则，记，转到2)再继续.4.2.2　已有的Dijkstra算法的实现50 从上面可以看出，在按标记法实现Dijkstra算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段，即上面所述算法的2)～5)步.这是一个循环比较的过程，如果不采用任何技巧，未标记点将以无序的形式存放在一个链表或数组中.那么要选择一个权值最小的弧段就必须把所有的点都扫描一遍，在大数据量的情况下，这无疑是一个制约计算速度的瓶颈.要解决这个问题，最有效的做法就是将这些要扫描的点按其所在边的权值进行顺序排列，这样每循环一次即可取到符合条件的点，可大大提高算法的执行效率.另外，GIS中的数据(如道路、管网、线路等)要进行最短路径的计算，就必须首先将其按结点和边的关系抽象为图的结构，这在GIS中称为构建网络的拓扑关系(由于这里的计算与面无关，所以拓扑关系中只记录了线与结点的关系而无线与面的关系，是不完备的拓扑关系).如果用一个矩阵来表示这个网络，不但所需空间巨大，而且效率会很低.下面主要就如何用一个简洁高效的结构表示网的拓扑关系以及快速搜索技术的实现进行讨论.网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示.一般而言，无向图可以用邻接矩阵和邻接多重表来表示，而有向图则可以用邻接表和十字链表表示，其优缺点的比较见表1.表1　几种图的存储结构的比较Tab.1　TheComparsionofSeveralGraphforStoringStructures名　称实现方法优　　点缺　　点时间复杂度邻接矩阵二维数组1.易判断两点间的关系占用空间大2.容易求得顶点的度邻接表链表1.节省空间1.不易判断两点间的关系或2.易得到顶点的出度2.不易得到顶点的入度十字链表链表1.空间要求较小结构较复杂同邻接表50 2.易求得顶点的出度和入度邻接多重表链表邻接多重表1.节省空间结构较复杂同邻接表2.易判断两点间的关系目前，对于算法中快速搜索技术的实现，主要有桶结构法、队列法以及堆栈实现法.TQQ、DKA以及DKD在这方面是比较典型的代表.TQQ虽然是基于图增长理论的，但是快速搜索技术同样是其算法实现的关键，它用两个FIFO的队列实现了一个双端队列结构来支持搜索过程［1］.DKA和DKD是采用如图1所示的桶结构来支持这个运算，其算法的命名也来源于此.在DKA算法中，第个桶内装有权值落在范围内的可供扫描的点，其中是视网络中边的权值分布情况而定的一个常数.每一个桶用队列来维护，这样每个点有可能被多次扫描，但最多次数不会超过次.最坏情况下，DKA的时间复杂度将会是，其中，为图中边的最大权值.DKD将点按权值的范围大小分装在两个级别的桶内，高级别的桶保存权值较大的点，相应的权值较小的点都放在低级别的桶内，每次扫描都只针对低级别桶中的点.当然随着点的插入和删除，两个桶内的点是需要动态调整的.在DKA算法中，给每个桶一定的范围以及DKD中使用双桶，在一定程度上都是以空间换时间的做法，需要改进.图1　一个桶结构的示例50 Fig.1　AnExampleoftheBucketDataStructure4.2.3　本文提出的Dijkstra算法实现4.2.3.1　网络拓扑关系的建立上面介绍的各种图的存储结构考虑了图在理论上的各种特征，如有向、无向、带权、出度、入度等.而GIS中的网络一般为各种道路、管网、管线等，这些网络在具有图理论中的基本特征的同时，更具有自己在实际中的一些特点.首先，在GIS中大多数网络都是有向带权图，如道路有单双向问题，电流、水流都有方向（如果是无向图也可归为有向图的特例），且不同的方向可能有不同的权值.更重要的一点是，根据最短路径算法的特性可以知道，顶点的出度是个重要指标，但是其入度在算法里则不必考虑.综合以上4种存储结构的优缺点，笔者采用了两个数组来存储网络图，一个用来存储和弧段相关的数据（Net-ArcList），另一个则存储和顶点相关的数据（Net-NodeIndex）.Net-ArcList用一个数组维护并且以以弧段起点的点号来顺序排列，同一起点的弧段可以任意排序.这个数组类似于邻接矩阵的压缩存储方式，其内容则具有邻接多重表的特点，即一条边以两顶点表示.Net-NodeIndex则相当于一个记录了顶点出度的索引表，通过它可以很容易地得到此顶点的出度以及与它相连的第一条弧段在弧段数组中的位置.此外，属性数据作为GIS不可少的一部分也是必须记录的.这样，计算最佳路径所需的网络信息已经完备了.在顶点已编号的情况下，建立Net-ArcList和Net-NodeIndex两个表以及对Net-ArcList的排序，其时间复杂度共为，否则为.这个结构所需的空间也是必要条件下最小的，记录了个顶点以及条边的相关信息，与邻接多重表是相同的.图2是采用这个结构的示意图.4.2.3.2快速搜索技术的实现无论何种算法，一个基本思想都是将点按权值的大小顺序排列，以节省操作时间.前面已经提到过，这两个算法都是以时间换空间的算法，所以在这里有必要讨论存储空间问题(这部分空间的大小依赖于点的个数及其出度).根据图中顶点和边的个数可以求出顶点的平均出度（为边数，为顶点数），这个数值代表了图的连通程度，一般在GIS的网络图中，.这样，50 如果当前永久标记的点为个，那么，下一步需扫描点的个数就约为～4个.如果采用链表结构，按实际应用中的网络规模大小，所需的总存储空间一般不会超过100K.所以完全没有必要采用以时间换空间的做法，相反以空间换时间的做法是完全可行的.在实现这部分时，笔者采用了一个FIFO队列，相应的操作主要是插入、排序和删除，插入和删除的时间复杂度都是O(1)，所以关键问题在于选择一个合适的排序算法.一般可供选择的排序算法有快速排序、堆排序以及归并排序等，其实现的平均时间都为O(nlgn).经过比较实验，选择了快速排序法.图2　基于最佳路径计算的网络拓扑表示4.3车辆导航系统动态最短路问题车辆导航系统利用计算机，GPS(全球定位系统)GIS(地理信息系统)和通讯技术，向驾驶员提供路径引导信息，使车辆避开拥挤区域，沿最佳路线到达目的地，它是ITS(50 智能运输系统)中受益主体明确、效益显著且见效快的项目，是欧州、美国、日本和中国竟相研究开发的重点.路搜索方法与路径引导策略属车辆导航系统的关键技术，在关于搜索最短路所需的实时流量与路段行程时间的预测方法，导信息影响下的驾驶员反应行为，诱导策略等方面，国内外学者进行了许多研究，为了提高最短径的搜索效率，还研究了DIJKSTRA改进算法、算法、双向搜索、分层搜索、分治搜索、在线搜索等方法.但此类算法皆未考虑车辆行进中路段行程时间动态变化的特性，并且只能搜索出两点间的唯一最短路径，不能满足车辆导航的需要.本文提出了考虑路段行程时间变化因素的动态最短路与动态最短路问题，推导出了车辆通过中途路段所需时间的计算模型，将其融入最短路算法中并结合GIS技术，得到计算动态最短路的改进算法，进而设计了通过替换动态最短路的部分路段以搜索次一动态最短路的合理前趋替换算法，以及递推求解条最短路的方法.驾驶员选择路径考虑的因素很多，不同驾驶员有各自的偏好，但是限于可计量性和数据可获得性，系统只能提供有限的选择准则.一般地，可将选择准则归纳为行程时间、行驶距离、拥挤程度、道路属性和综合费用等6类，其中行程时间是大多数驾驶员选择或关注的焦点.路段行程时间是随时间变化的，但是受交通参数检测技术和预测分析技术的限制，难以找出准确、可用的路段行程时间随时间连续变化的关系式.为此，将系统工作时间划分为若干时段，认为单个时段内交通状态稳定、行程时间固定，但不同时段的行程时间可能不相等.当时段划分得很长时，车辆可能在一个时段内就能完成一次出行，还可能在较长时间内给同一起点的所有车辆推荐同一路线，这实际未考虑行程时间的变化，称这种路径为静态路径.将时段划分适当时，车辆一次出行会跨越若干时段.若仅根据某一时段的路段的行程时间计算最短路，则只有在车辆行驶过程中各路段的行程时间皆为恒定的情况下，求出的最短路才有意义，此类路径称为静态最短路.但是，实际交通状态与行程时间都是变化的，只有以车辆通过各路段所需的实际时间为依据，计算所得最短路才具有真实意义，称这种根据动态行程时间计算所得最短路径为动态最短路.由于预测存在误差，根据预测的行程时间所计算的最短路段未必真实最短，只推荐唯一路线可能引致误导，并且还容易导致车流积聚.可见，性能优良的车辆导航系统应同时计算出次动态最短路、第三动态最短路、…50 、动态最短路等，作为发布路线引导信息的基础.学术上称同时计算若干条最短路的问题为最短路问题，结合路段行程时间的动态特性，称车辆导航系统中同时计算条动态最短路的问题为动态最短路问题.对静态最短路，可采用DIJKSTRA等成熟算法求解;若路段行程时间恒定，对最短路可采用双向扫视算法求解;当路段行程时间变化时，对应的动态最短路与动态最短路皆未有有效算法，需结合交通流系统的特性，研制相应算法.4.3.1动态最短路递推求解方法对动态最短路，两点间的最短路径及路径长度都随计算时刻(车辆呼叫服务时刻)而异.在开始时，中途路段的行程时间为未知条件，需要在计算过程中才能确定到达中途路段的时刻，并由此计算路段行程时间.据此，将确定车辆到达中途路段的时刻与经过路段所需的行程时间纳入最短路算法中，以搜索动态最短路.4.3.2搜索动态最短路的改进算法4.3.2.1车辆通过路段动态行程时间的计算方法以表示导航系统工作开始时刻，将系统工作时间划分为若干时段，以表示一个时段的长度.系统开始工作时刻属于第一个时段，对各时段进行编号(7，称此编号序列为系统工作时段序列;对涉及的路段进行编号.以表示路段第个时段的行程时间，将各路段各时段的行程时间表示为表1.表1路网中路段动态行程时间表路段时段……1234…50 i…某呼叫服务的车辆从起点到目的地可能经过若干条路段，对其所经过的路段按序编号(1，2，3，…，，，，…)以表示车辆经过第路段的时间范围，车辆通过路段行程时间记为，则=L.由于路段为路段的续接路段，可知.车辆通过路段可能跨越若干时段，各时段内路段行程时间分别表示为、、、、...，以表示车辆通过路段起点时刻所属时段在系统工作时段序列中的次序，则且当、路段长度与行程速度有不同取值或不同组合时，可能出现比大、比小、与相等3种情况.当时，表示在一个时段内车辆就能驶过路段，则.当时，表示车辆需要一个以上时段（设为）才能通过该路段，则根据运动学原理，下式成立(1)化简为(2)可采用试算法确定值.由值，并根据运动学原理可计算呼叫服务的车辆通过路段的行程时间50 由此，推出路段行程时间计算公式为，通过价函数描述后续路线的直捷径性.从当前节点到达目标（3）式中：为的解；.4.3.2.2基于GIS搜索动态最短路的改进算法搜索动态最短路涉及到大量动态行程时间的计算，而车辆导航要求路径引导信息具有实时性，因而要求高效率的搜索方法.算法是发展人工智能而产生的计算最短路最有效的启发式搜索方法，该算法到达目标节点即停止搜索.算法中应用了启发式估价函数，用于评价每个生成节点的优先值，该函数使得算法首先搜索最有希望的路径.鉴于网中路径、节点的空间属性，可应用GIS技术获取节点与路径上各点的空间信息，通过价函数描述后续路线的直捷径性、从当前节点到达目标节点的便捷性.据此，对以动态行程时间为路阻的动态最优路径，构造节点的启发式估价函数为式中：为路径行程时间；为从起点到达节点的经过的所有路段的动态行程时间总和；为路段的动态行程时间；估计项反映当前节点后续路线的直捷径性与到达目标节点的便捷性，为节点和目标节点之间的空间距离除以估计的最高车速，空间距离根据从GIS中获得的节点50 和目标节点的坐标计算.根据动态路径的特点，将车辆到达某路段起点时刻对应时段在系统工作时段序列中的次序和通过路段的行程时间纳入最优路径搜索过程，对算法进行改进，计算步骤为：（1）设初始的OPEN表仅包含原节点，其费用值为0，即值为0.令CLOSED为空表，设其他节点的费用为.（2）若OPEN表为空，则宣告失败；否则，选取OPEN表中有最小值的节点，并叫做最佳节点BEST，把BEST从OPEN表移至CLOSED表，判断此BEST是否是目标节点，若BEST为目标节点，转步骤（3），若BEST不是目标节点，则对本节点的每一个后继节点进行下列过程1）计算节点的费用.根据式（1）计算到达BEST时对应的；根据式（3）计算BEST到节点的行程时间；=BEST+从BEST到的行程时间.2）如果与OPEN表上的任一节点相同，判断是否有最低的值，若具有最低的值，用的费用代替OPEN表中相同的节点费用，且将匹配节点的后向指针指向BEST.3）如果在CLOSED表中与一节点相匹配，检查节点H是否具有最小的值，如果节点具有最小的值，则用的费用代替匹配节点的费用，并把匹配节点的后向指针指向BEST，并把该匹配节点移到OPEN表.4）如果不在OPEN表上，也不在CLOSED表上，则把的后向指针指向BEST，并把放入OPEN中，计算节点的估价函数重复第（2）步.（3）从BEST节点回溯，即从BEST的后向指针一直到原节点的遍历节点，最后报告解路径.4.3.3搜索次一动态最短路的合理前趋替换算法以动态最短路为依据，替换动态最短路的部分路段，可得到比最短路距离稍长的合理路径.对起点到终点的动态最短路，其中间节点与终点组成点集50 ，在点的邻接节点中，若某点满足，，且在最短路径中不是的后继（即从起点到的动态最短路未经过），则称点为点的合理前趋.当某点已成为点的合理前趋，则该节点不能再成为其它点（）的合理前趋.称从起点沿最短路到，经沿最短路到终点的路径为较短路.按从到2次序，求出中各点（）的所有合理前趋及相应较短路，并由小到大对各较短路排序，则排位第一者为次短路.同理，以次短路为基础计算第三最短路；依次递推，计算其余条路径.以动态最短路作为当前路径，以表示最短路的编号，令，递推搜索次一最短路，计算步骤如下：（1）根据当前动态最短路的解路径，找出对应的点集.（2），找出的所有合理前趋，并对每一合理前趋进行下列过程；1）根据式（1）计算到达点时刻对应的；2）根据式（3）计算与之间的行程时间.（3）以点作为临时起点，按改进算法计算到终点的最短路.（4），当，返回步骤（2）.（5）对各较短路按由小到大的次序排序，排位第一者为次一最短路，对该路径终点开始回溯，根据各节点的后向指针，一直到临时起点遍历节点，则由起点出发沿原最短路到，经沿新最短路到终点形成第最短路.（6）令，若，则令第最短路为当前最短路，返回步骤（1）；否则，停止运算.4.3.4结语静态型最短路与实际最短路径存在较大差异，以动态行程时间作为路阻计算的动态最短路具有真实意义.50 根据交通流系统的特点，将计算车辆到达中途路段的时刻和通过路段所需行程时间融入算法，得到计算动态最短路的改进算法；在已计算出的动态最短路中，将终点或中间节点的前趋替换为合理前趋，能得到比最短路距离稍长的合理较短路，通过比较各较短路径长度确定次一条最短路；同理递推搜索出其余路径.合理前趋替换算法能以较少的运算次数成功地求出条动态最短路，使建立性能优良的车辆导航系统成为可能.文中方法适合于搜索某一起、终点间条动态最短路，对多端动态最短路的搜索方法、路段动态行程时间预测方法等尚需深入研究.4.4最短路问题举例例1某邮递员负责某区的邮件分发.图6.1.1表示必须经过的街道网络.问邮递员应如何走才能使总路线最短？显然，这个邮递员最好能不重复地一次走完规定街道（图6.1.1实线）.如果在距离最短的两点间加一条重复路线（如图中虚线EF），则可沿路线ABEFADGCEFG走，除EF重复一次外，其余都是不重复地一次走完，所以这是一条最短的邮递路线.例 2某新建住宅小区铺设供水管道，要求水源与各点相通（图6.1.2），而且各点到水源间的路径最短.显然油管铺设问题、通信网架设问题和这一例子是类似的.50    图6.1.2在网络规划问题中称为有向图.最短路问题的可以简要叙述为：设为一个有向图.其中，表示结点集，是结点.表示弧集，每一条弧相应有一长度.表示从到没有弧，即没有路.，表示在点停留. 设始点为，终点，从到经过各点，则路的总长度为，.最短路问题就是在所有从到的路中寻找总长度最小的路，称为从到的最短路.最短路问题有两类：1．到终点的最短路，最后所得是从始点到各点的最短路.   2．从任何一点到任意一点的所有最短路.4.4.1、求始点到终点的最短路求始点到终点的，所有弧长的最短路，目前公认的较好的算法是标号法，首先是由E.W.Dijkstra提出的，故称为Dijkstra标号算法.下面结合图6.1.2给出的例子来说明.设 图6.1.2的网络中，定义弧长（广义长度）矩阵如下：50 矩阵中第行第列的元素是弧长，例如第1行第3列的元素是弧长=22Dijkstra算法是，从始点开始，给每点一个数，或称为标号.分标号与标号两种.为试探性标号，为永久性标号.给点标号时，表示从到的最短路长.给点一个标号时，表示从到的估计最短路长.凡是没有标上标号的点，标以标号，以便用来进一步计算该点的标号.已得到标号的点不再改变标号.一旦终点得到标号，算法停止.图6.1.2的最短路算法如下：1、将标上标号0，即，表示从到的距离为0.给其他点（～）标上标号，即2、分析还没有标号的各点（），比较和，为到的弧长.将的新标号取较小者，即.如果，则用代替作为点的新的标号.50 点V2的T标号的数最小，令P(2)=16.3、以点（刚得到标号的点）作为比较基础，重复上述过程，即比较与取较小的数作为的新的标号.显见，点的标号数由59变为57，其余未改动.比较、、、、=22为最小，将点的标号改为标号：=22.4、再重复上述过程，以点为比较基础.点的标号由57变为53，其余未动.～，其中=30为最小，令=30.  5、下一步以点为比较基础.   ，的标号均未变，=41为最小，令=41.50 6、最后一步以点为比较基础.令=53.终点已标上标号，程序到此结束.前已指出，表示始点到的最短路长.例如点到的最短路长为22，点到的最短路长为41，而点到终点的最短路长为=53.如果只须要知道从到的最短路，则一旦点标了标号，算法就可终止.50 参考文献:1运筹学东北电力学院张杰周硕武文华编著50'