摘要：空間分析在GIS中扮演著越來(lái)越重要的角色。該文以廈門市數(shù)字城市信息管理系統(tǒng)為研究對(duì)象，該系統(tǒng)在大屏幕監(jiān)督指揮子系統(tǒng)中運(yùn)用了GIS技術(shù)，同時(shí)基于GIS實(shí)際需求使用了改進(jìn)的空間分析算法以便實(shí)現(xiàn)系統(tǒng)功能。改進(jìn)的空間算法以傳統(tǒng)空間分析算法為基礎(chǔ)，針對(duì)空間數(shù)據(jù)量龐大檢索緩慢的問(wèn)題，提出了一種基于方向性的最短路徑搜索方法。

關(guān)鍵詞：空間分析；Dijkstra；最短路徑搜索

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2009)04-0984-02

Space Analyse Technology Use in Digital City Management

LIU Dong-po1， LIU Fa-neng2

(1.Department of Antomation， Xiamen University， Xiamen 361001，China; 2.Xiamen Zhiyu Technology Co.Ltd， Xiamen 361002， China)

Abstract: space analyse tech is play more and more important in GIS. This article bases on XIAMEN digital city management system， this system use GIS tech in her big screen supervise and guide vice system， and use improved arithmetic to achieve system function. The improved arithmetic bases on the original arithmetic and direct to the space large data search slowly， comes out with a method baess on the direction for the shortcut search.

Key words:space analyse; Dijkstra; shortcut search

1 引言

最短路徑算法是計(jì)算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域的研究熱點(diǎn)。它是資源分配、區(qū)位分析、路線設(shè)計(jì)等優(yōu)化問(wèn)題的基礎(chǔ)。很多網(wǎng)絡(luò)相關(guān)問(wèn)題均可納入最短路徑問(wèn)題的范疇之中，如時(shí)間、費(fèi)用、線路容量等。相應(yīng)地，最短路徑問(wèn)題就成為最快路徑問(wèn)題、最低費(fèi)用問(wèn)題等[1]。由于最短路徑問(wèn)題在實(shí)際中常用于汽車導(dǎo)航系統(tǒng)以及各種應(yīng)急系統(tǒng)(如110報(bào)警、119火警以及醫(yī)療救護(hù)系統(tǒng))等，這些系統(tǒng)一般要求計(jì)算出到出事地點(diǎn)的最佳路線的時(shí)間很短，在行車過(guò)程中還需要實(shí)時(shí)計(jì)算出車輛前方的行駛路線，這就決定了最短路徑問(wèn)題的實(shí)現(xiàn)應(yīng)該是高效率的。其實(shí)，無(wú)論是距離最短，時(shí)間最快，還是費(fèi)用最低，它們的核心算法都是最短路徑算法。

經(jīng)典的理論與不斷發(fā)展完善的計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)。經(jīng)典的最短路徑算法[1]——Dijkstra（狄克斯特拉）算法采用的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)方法由于受到當(dāng)時(shí)計(jì)算機(jī)硬件發(fā)展水平的限制，將空間存儲(chǔ)問(wèn)題放到了一個(gè)很重要的位置，以犧牲適當(dāng)?shù)臅r(shí)間效率來(lái)?yè)Q取空間節(jié)省。目前，空間存儲(chǔ)問(wèn)題已不是要考慮的主要問(wèn)題，因此有必要對(duì)已有的算法重新進(jìn)行考慮并進(jìn)行改進(jìn)，可以用空間換時(shí)間來(lái)提高最短路徑算法的效率。

2 Dijkstra最優(yōu)路徑算法

設(shè)G=(V，E)是一個(gè)帶權(quán)有向圖，如何求出從G的某個(gè)源點(diǎn)V到其余每一個(gè)頂點(diǎn)的最短路徑，狄克斯特拉于1959年提出了解決此問(wèn)題的一般算法，其基本思想是：

把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過(guò)程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度，U中的頂點(diǎn)的距離從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。

在算法實(shí)現(xiàn)過(guò)程中，核心步驟就是從U中選擇一個(gè)權(quán)值最小的結(jié)點(diǎn)，加入到S中。這是一個(gè)循環(huán)比較的過(guò)程，如果不采用任何技巧，U中的頂點(diǎn)將以無(wú)序的形式存放在一個(gè)鏈表或數(shù)組中。那么要選擇一個(gè)權(quán)值最小的弧段就必須把所有的點(diǎn)都掃描一遍，在大數(shù)據(jù)量的情況下，這無(wú)疑是一個(gè)制約計(jì)算速度的瓶頸。另外，對(duì)GIS中的道路數(shù)據(jù)進(jìn)行最短路徑計(jì)算，首先必須將其按結(jié)點(diǎn)和邊的關(guān)系抽象為圖的結(jié)構(gòu)，這在GIS中稱為構(gòu)建網(wǎng)絡(luò)的拓?fù)潢P(guān)系。如果用一個(gè)矩陣來(lái)表示這個(gè)網(wǎng)絡(luò)，不但所需空間巨大，而且效率會(huì)很低。下面將對(duì)以上問(wèn)題提出解決辦法。

3 基于方向性的最短路徑搜索方法

最短路徑算法產(chǎn)生于計(jì)算機(jī)科學(xué)及運(yùn)籌學(xué)，因只考慮網(wǎng)絡(luò)的拓?fù)涮卣骰螂A段特征，而忽略了網(wǎng)絡(luò)的空間分布特征，導(dǎo)致其搜索過(guò)程缺乏方向性，得到的是一棵以源點(diǎn)為根的最短路徑樹(shù)。即使構(gòu)造此路徑樹(shù)的過(guò)程在到達(dá)終止結(jié)點(diǎn)后即結(jié)束，此方法依然有大量計(jì)算是冗余的。為了解決Dijkstra算法效率的這個(gè)瓶頸問(wèn)題，可以通過(guò)減少臨時(shí)標(biāo)記結(jié)點(diǎn)數(shù)量的方法使算法得到優(yōu)化。基于此，提出了采用方向性限制搜索的方法，通過(guò)減少臨時(shí)標(biāo)記點(diǎn)數(shù)量來(lái)提高計(jì)算效率。

3.1 優(yōu)化搜索實(shí)現(xiàn)過(guò)程

具體實(shí)現(xiàn)過(guò)程為，從永久標(biāo)記點(diǎn)Vk開(kāi)始，尋找與其直接連接的所有結(jié)點(diǎn)。此時(shí)將Vk點(diǎn)作為直角坐標(biāo)系下的原點(diǎn)，以Vk點(diǎn)與終點(diǎn)Vt的連線方向作為直角坐標(biāo)系的X軸方向，由此就可以確定一個(gè)與永久標(biāo)記點(diǎn)Vk和終點(diǎn)Vt有關(guān)的有向二維空間。如圖1所示。

在圖1中，與永久標(biāo)記點(diǎn)Vk直接連接的結(jié)點(diǎn)有四個(gè)，將其編號(hào)為(1)～(4)，根據(jù)永久標(biāo)記點(diǎn)Vk和終點(diǎn)Vt的位置關(guān)系，我們把二維空間分為四個(gè)象限。由于在定義數(shù)據(jù)結(jié)構(gòu)時(shí)，己經(jīng)存儲(chǔ)了每個(gè)結(jié)點(diǎn)的坐標(biāo)信息，因此，在這里就可以直接使用這些數(shù)據(jù)。

根據(jù)三角形余弦定理，a2= b2＋c2－2bc×cosθ，其中a、b、c分別為三角形三個(gè)邊的長(zhǎng)度，θ為邊長(zhǎng)為b和c的兩個(gè)邊的夾角。我們令b為與永久標(biāo)記點(diǎn)Vk直接連接的線段的長(zhǎng)度，令c為永久標(biāo)記點(diǎn)Vk與終點(diǎn)Vt的連線長(zhǎng)度，θ角為這兩條線之間的夾角。在圖1中，以1號(hào)點(diǎn)為例，它是一個(gè)與永久標(biāo)記點(diǎn)Vk直接連接的點(diǎn)，對(duì)應(yīng)的a， b， c三條邊和θ角的均為圖中標(biāo)識(shí)所示。首先，根據(jù)邊的權(quán)值直接得到b的值，再根據(jù)地圖屬性表中SpointX， SpointY和EpointX，EpointY四個(gè)域的域值，得到三角形三個(gè)頂點(diǎn)的坐標(biāo)值，進(jìn)而求得a和c的值，最后利用余弦定理就可以解出θ。對(duì)方向性的要求，也就是要求臨時(shí)標(biāo)記點(diǎn)要位于直角坐標(biāo)系的第一象限和第四象限，即θ值小于或等于90度。在所有的與永久標(biāo)記結(jié)點(diǎn)直接連接的點(diǎn)中，我們只選擇符合方向性要求的點(diǎn)作為臨時(shí)標(biāo)記點(diǎn)。顯然在圖1中我們只選擇(1)、(2)兩個(gè)點(diǎn)標(biāo)一記為臨時(shí)標(biāo)一記結(jié)點(diǎn)，排除了(3)，(4)兩點(diǎn)。

3.2 優(yōu)化搜索算法流程

圖2為改進(jìn)算法的流程圖，其中包括了直接插入排序過(guò)程和方向性搜索過(guò)程。在實(shí)際應(yīng)用中，還包括根據(jù)己有的GIS數(shù)據(jù)，按定義的數(shù)據(jù)結(jié)構(gòu)建立相應(yīng)的數(shù)據(jù)拓?fù)潢P(guān)系，然后根據(jù)己有的拓?fù)浣Y(jié)構(gòu)實(shí)現(xiàn)最短路徑的算法。

4 系統(tǒng)應(yīng)用實(shí)例界面

根據(jù)上面提出的改進(jìn)后的Dijkstra優(yōu)化算法，系統(tǒng)在空間移動(dòng)信息服務(wù)系統(tǒng)中實(shí)現(xiàn)了城市交通道路規(guī)劃功能。此功能的實(shí)現(xiàn)過(guò)程為，當(dāng)用戶需要最佳路徑時(shí)，首先在地圖上確定起點(diǎn)和終點(diǎn)的位置，并查找起點(diǎn)和終點(diǎn)對(duì)應(yīng)位置的結(jié)點(diǎn)編號(hào)，繼而向GIS服務(wù)器發(fā)出路徑規(guī)劃請(qǐng)求，服務(wù)器接到用戶請(qǐng)求后，利用優(yōu)化搜索算法計(jì)算出最短路徑，再將規(guī)劃結(jié)果返回到客戶端，客戶端根據(jù)得到的數(shù)據(jù)在地圖中顯示出規(guī)劃結(jié)果，如圖4所示。

■

圖3 最優(yōu)路徑查詢交互界面圖4 最佳路徑實(shí)現(xiàn)示意圖

5 結(jié)束語(yǔ)

本文主要描述了傳統(tǒng)空間分析技術(shù)及數(shù)字城管系統(tǒng)中所應(yīng)用的改進(jìn)型的空間分析技術(shù)。針對(duì)傳統(tǒng)空間分析技術(shù)中關(guān)于搜索過(guò)程缺乏方向性的問(wèn)題，為了降低算法復(fù)雜度，提高算法效率，我們提出了基于方向性的最短路徑搜索方法，該算法非常易于編程實(shí)現(xiàn)。這些算法最后都成功地應(yīng)用于廈門市數(shù)字城市信息管理系統(tǒng)。

致謝：在此感謝廈門智?？萍加邢薰镜念I(lǐng)導(dǎo)及公司的同事們，謝謝他們?cè)谡麄€(gè)項(xiàng)目開(kāi)展過(guò)程中的支持和鼓勵(lì)。

參考文獻(xiàn):

[1] 張宏，溫永寧，劉愛(ài)利，等.地理信息系統(tǒng)算法基礎(chǔ)[D].北京：科學(xué)出版社，2006.06.