基于区域限定模型的最短路径算法研究

第２９卷第６期　计算机仿真　２０１２年６月　文章编号：１００６—９３４８（２０１２）０６—０２１４—０４　

基于区域限定模型的最短路径算法研究　

关涌涛，李勇　（安阳师范学院，河南安阳４５５０００）　摘要：研究地理信息系统中最短路径问题，提高最短路径的搜索速率。针对地理信息系统ＧＩＳ中最短路径是根据路径权值　最小原则选取的，需要逐个遍历系统中所有路径，传统的Ｄｉ　ｊｋｓｔｒａ算法逐个比较所有路径的权值计算量大，不能快速找出最　短路径的问题。提出一种基于区域限定模型的算法选取最短路径，采用区域限定模型减少参与计算的路径信息数目，并在　此基础上使用启发式搜索策略快速找到最短路径，这样就避免了对系统中所有路径信息遍历带来的计算量大、搜索速率不　高的问题。实验证明，改进方法能够快速将最短路径搜索出来，满足地理信息系统实时性的要求，取得了满意的结果。　关键词：地理信息系统；最短路径；路径权值　中图分类号：ＴＰ２０２　．７　文献标识码：Ｂ　

Ｒｅｓｅａｒｃｈ　ｏｎ　Ｓｈｏｒｔｅｓｔ　Ｐａｔｈ　Ｂａｓｅｄ　ｏｎ　Ｒｅｇｉｏｎａｌ　Ｌｉｍｉｔ　Ｍｏｄｅｌ　

ＧＵＡＮ　Ｙｏｎｇ—ｔａｏ，ＬＩ　Ｙｏｎｇ　（Ａｎｙａｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ａｎｙａｎｇ　Ｈｅｎａｎ　４５５０００，Ｃｈｉｎａ）　ＡＢＳＴＲＡＣＴ：Ｒｅｓｅａｒｃｈ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｐａｔｈ　ｉｎ　ｇｅｏｇｒａｐｈｉｃ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍ　ｔｏ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｓｅａｒｃｈｉｎｇ　ｒａｔｅ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｄ　ａ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｒｅｇｉｏｎａｌ　ｌｉｍｉｔ　ｍｏｄｅｌ　ｔｏ　ｓｅｌｅｃｔ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｐａｔｈ．Ｕｓｉｎｇ　ｔｈｅ　ｒｅｇｉｏｎａｌ　ｌｉｍｉｔ　ｍｏｄｅｌ　ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ｐａｔｈ　ｉｎｆｏｒｍａｔｉｏｎ　ｔｈａｔ　ｎｅｅｄｓ　ｃａｌｃｕｌａｔｉｏｎ，ａｎｄ　ｏｎ　ｔｈｉｓ　ｂａｓｉｓ　ｈｅｕｒｉｓｔｉｃ　ｓｅａｒｃｈ　ｓｔｒａｔｅｇｙ　ｗａｓ　ｕｓｅｄ　ｔｏ　ｑｕｉｃｋｌｙ　ｆｉｎｄ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｐａｔｈ，ｔｈｕｓ　ｐｒｅｖｅｎｔｉｎｇ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｌｏｔ　ｏｆ　ｃａｌｃｕｌａｔｉｏｎ　ａｎｄ　ｌｏｗ　ｓｅａｒｃｈ　ｒａｔｅ　ｃａｕｓｅｄ　ｂｙ　ｔｒａｖｅｒｓｉｎｇ　ａｌｌ　ｔｈｅ　ｐａｔｈ　ｉｎｆｏｒｍａｔｉｏｎ．Ｅｘｐｅｒｉｍｅｎｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｍｅｔｈｏｄ　ｃａｎ　ｑｕｉｃｋｌｙ　ｆｉｎｄ　ｏｕｔ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｐａｔｈ，ｆｕｌｌ　ｆｉｌｌ　ｔｈｅ　ｒｅａｌ—ｔｉｍｅ　ｒｅ—　ｑｕｉｒｅｍｅｎｔ，ａｎｄ　ｏｂｔａｉｎ　ｔｈｅ　ｓａｔｉｓｆａｃｔｏｒｙ　ｒｅｓｕｈｓ．　ＫＥＹＷＯＲＤＳ：Ｇｅｏｇｒａｐｈｉｃ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍ（ＧＩＳ）；Ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｐａｔｈ；Ｐａｔｈ　ｗｅｉｇｈｔｓ　

１　引言　随着科技的飞速发展，网络技术、通讯技术和计算机技　术已经广泛应用到人们生活的各个领域。计算机技术的迅　速普及和网络信息的发展，应用计算机网络来辅助实现电子　导航、城市规划、交通旅游等通讯管线、网络设计布局的地理　信息系统（Ｇｅｏｇｒａｐｈｉｃ　ｈｆｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍ，简称ＧＩＳ）应运而　生，得到了深入的研究和广泛的应用　。尤其在城市交通网　络分析中，地理信息系统发挥了重要的作用，特别１１０报警、　１１９火警等救急系统。其中，在地理信息系统中最关键的核　心部分是最短路径算法。最短路径不是普通意义上的距离　达到最短，而是解决最快、费用最低的问题。随着经济的发　展，企业需要利用获得的路径信息来规划配送的路径，以期　选择最短路径来降低运输成本、满足客户的需要、提高企业　的综合竞争力，使企业在竞争中立于不败之地　。因此，最　收稿日期：２０１１—０７—２０　—２１４一　短路径算法成为人们研究的热点问题。　然而传统的最短路径选取算法是基于Ｄｉ　ｊｋｓｔｒａ的算法。　此算法是将待搜索的所有路径组成一个网络，将各条路径作　为网络中的结点，计算路径的长度、路径运费、路径运输耗时　等参数得到各个路径的权值，最后根据权值最小的原则选取　出最短路径　Ｊ。但是，这种传统的Ｄｉ　ｊｋｓｔｒａ算法需要从起始　结点出发，遍历并比较网络中所有结点的权值，最终比较得　出最短路径。这样遍历网络中所有结点计算量大，造成了最　短路径搜索时间过长，不能满足人们对最短路径搜索速率的　要求。　针对传统的Ｄｉ　ｊｋｓｔｒａ算法计算量大、搜索速率不高的缺　陷，本文提出一种基于区域限定模型的改进Ｄｉ　ｊｋｓｔｒａ算法。　采用区域限定模型减少参与计算的路径信息数目，并在此基　础上使用启发式搜索策略快速找到最短路径，这样就避免了　对系统中所有路径信息遍历带来的计算量大、搜索速率不高　的问题，提高了搜索效率，满足了人们对最短路径搜索的实　时性要求。　２最短路径搜索原理　最短路径搜索是通过利用计算机网络技术，对地理信息　系统进行搜索，找到满足人们要求的最优路径，其在交通网　络中的应用最为广泛。由于现在车辆的增多，经常出现交通　拥堵问题，浪费了人们大量的出行时间，成为人们普遍被困　扰的问题之一。因此，最短路径搜索通过搜索算法找出最短　路径，引导车辆的行驶，就能大大减少人们行驶的时间，保证　整个交通网络的畅通，改善日益突出的交通拥堵问题。由于　实际应用的需要，最短路径的搜索必须具有搜索效率高、搜　索时间短的特点来满足人们对系统的实时性要求。　但是，传统的Ｄｉ　ｊｋｓｔｒａ算法是通过计算各个路径的权　值，然后遍历网络中所有结点选取路径权值最小的路径来找　到最短路径的。算法设定所有路径组成一个网络，每个路径　就是网络中的一个结点，每个结点用标号（ｄ　，Ｐｊ）表示，其中　的ｄ　表示的是从起始结点ｑ出发，到达最终结点　的最短路　径长度，Ｐｊ表示的是从起始结点出发，到达结点　的前一个结　点　Ｊ。具体的算法是：　１）初始时，设定起始结点信息为ｄ。＝０，Ｐ。＝　，并将起始　结点ｑ标记并加入标记结点集ｓ中，而其他的所有结点都没　有被标记；　２）计算当前的已被标记的结点ｋ到达所有与其直接相　连的没有被标记的结点　之间的距离，设定此距离为：　＝ｄ　＋　（１）　其中，ｆ　提结点ｋ到达结点　的路径权值。然后选取所有距　离中最短的距离作为下一个标记结点，即ｃｆ　＝ｍｉｎｄｊ，并将此　结点放入标记结点集Ｓ中；　３）从未标记的结点中选择距离最短的结点，并将此结点　标记加入标记集合５中；　４）查看是否所有的结点被遍历，如果遍历结束，则完成　最短路径的搜索，标记集合中的结点就是最短路径的结点。　由以上的运算过程可以看出，需要循环执行步骤２）、　３），对网络中的所有结点进行遍历，这样就造成了计算量大　的问题，最终导致了最短路径搜索耗时过长，不满足人们对　最短路径搜索的实时性要求　。最短路径搜索算法的效率　由算法复杂度和遍历耗时决定：　（２）　×１００％　（３）　式中，ｔ是搜索的总耗时，ｔ　是每个结点的搜索耗时，ｆ　是结点　的权值，Ⅳ是算法遍历的结点的数目，　是系统中所有结点　的数目，Ｏ（　）是算法的复杂度。从公式可以看出，算法遍历　的结点数目越多其搜索耗时越长，又由于搜索耗时与算法的　效率成反比，所以传统的Ｄｉ　ｊｋｓｔｒａ算法遍历网络中所有结点　造成搜索耗时长，搜索效率不高的问题。因此，需要找到新　的算法，减少需要遍历的结点的数目，提高算法的效率，满足　人们实时性要求。　针对传统的Ｄｉ　ｊｋｓｔｒａ算法计算量大、搜索速率不高的缺　陷，本文提出一种基于区域限定模型的改进Ｄｉ　ｊｋｓｔｒａ算法。　首先采用区域限定模型对系统网络结点进行限定，以减少参　与计算的路径信息数目，并在此基础上使用启发式搜索策略　快速找到最短路径，这样就避免了对系统中所有路径信息遍　历带来的计算量大、搜索速率不高的问题，大大提高了搜索　效率，满足了人们对最短路径搜索的实时性要求。　

３基于区域限定模型的最短路径搜索算法　由于传统的Ｄｉ　ｊｋｓｔｒａ算法需要遍历网络中所有结点，这　样计算量很大，造成最短路径搜索的耗时长，由搜索效率的　计算公式知道长耗时导致了搜索效率低下，显然传统的Ｄｉ　ｊｋｓｔｒａ算法搜索最短路径不能满足人们对最短路径搜索时实　时性的要求。如果构建限定模型，将网络中的结点按照一定　规则筛选，去除无效的结点，这样就减少了网络中需要遍历　的结点的数目，就能大大降低搜索耗时，提高搜索效率。　３．１构建区域限定模型　在地理信息系统网络中，搜索最短路径的起始结点和目　的结点一般都是已知的，并且一旦起始和终止结点确定，其　大致的走向也就随之确定，在走向范围内的结点属于最短路　径的可能性较大，而有些不在走向范围内的结点被选作最短　路径的可能性很小，甚至为零，因此可以大胆地将这些无效　结点删除，这样既能保证最短路径的搜索又能降低搜索的耗　时，提高搜索的效率。　由实践经验知道，起始结点和终止结点确定的走向所包　含的结点大致是在一个椭圆范围内。因此，本文设定一个椭　圆区域来限制遍历结点的数目，假设网络中一个结点ｎ与起　始结点ｇ和终止结点　之间的垂直距离为ｄ　和ｄ　，那么可　将限制条件写为：　ｄ　＋ｄ　＜Ｄ　（４）　式中，Ｄ是一个设定的定值，用来约束调节限定区域的大小　变化。这样就构成了一个以起始结点ｑ和终止结点　为中　心，以Ｄ的值为长轴的椭圆区域。所以需要将待遍历的所有　网络结点进行限定区域删选，在限定区域内的结点进行遍　历，对不在限定区域内的结点直接略过不进行遍历。符合限　定区域结点的筛选公式如式（５）所示。　ｆｄ　＋ｄ　＜Ｄ结点ｎ保留　…　【ｄ　＋ｄ　≥Ｄ结点ｎ删除　其中，Ｄ是限定区域的控制参数，Ｄ取值越大则算法搜索的　区域越大，Ｄ取值越ｔＪ，Ｎ算法搜索的区域越小。如果Ｄ取值　过小会导致不能搜索出最短路径，因此需要根据实际网络状　况设定合适的Ｄ值。　这样通过限定区域模型对网络中所有结点筛选后就减　少了算法遍历的结点数目，能够大大缩短算法耗时、提高搜　索效率。　

一２】５一