郭仁安，郭先春

(1.福建省國土測(cè)繪院，福建廈門 361012; 2.東華理工大學(xué)，江西 撫州 344000)

1 引言

地理信息系統(tǒng)(GIS)是一項(xiàng)以計(jì)算機(jī)為基礎(chǔ)的新興技術(shù)，圍繞著這項(xiàng)技術(shù)的研究、開發(fā)和應(yīng)用形成了一門交叉性、邊緣性的學(xué)科，是管理和研究空間數(shù)據(jù)的技術(shù)系統(tǒng)。GIS的發(fā)展在國內(nèi)外的發(fā)展大致可分兩個(gè)階段:早期階段是20世紀(jì)90年代初期主要解決的問題涉及:信息提供、工作發(fā)布及數(shù)據(jù)管理;中期主要是基于圖像導(dǎo)航的多功能3D虛擬現(xiàn)實(shí)［1］國土資源調(diào)查、流域調(diào)查［2］等。這階段的GIS能高效的使外業(yè)人員與GIS中心部門之間傳輸空間數(shù)據(jù)，消除了往返辦公室取“硬地圖”的必要。在這階段國內(nèi)外都有相應(yīng)的產(chǎn)品，特別值得一提的是國內(nèi)武漢大學(xué)的GeoStar、中國地質(zhì)大學(xué)的MapGIS、北京超圖SuperMap平臺(tái)等。然而地圖著色問題一致是人們困擾的問題:究竟只要幾種顏色就能將地圖一一區(qū)分開來是人們研究的熱點(diǎn)。1852年英國人格思里于提出四色猜想，1878年英國數(shù)學(xué)家凱萊重新提出這問題，引起人們關(guān)注，1890年英國人希伍德沿著這方向證明了任何地圖只用5種顏色著色便夠了，取得初步進(jìn)展。1968年挪威數(shù)學(xué)家奧雷等人證明了用4種顏色把不超過40個(gè)國家的地圖著色，推進(jìn)了四色問題的研究。70年代人們通過數(shù)學(xué)歸納法證明四色問題。本文就在此基礎(chǔ)上，結(jié)合數(shù)據(jù)結(jié)構(gòu)的算法，用C語言編程，對(duì)地圖著色問題給予了實(shí)現(xiàn)，現(xiàn)就其實(shí)現(xiàn)過程加以論述。

2 地圖著色問題的數(shù)據(jù)模型

在地圖中兩個(gè)城市之間只可能存在著兩種關(guān)系相離和相交關(guān)系。因此在計(jì)算機(jī)中可用0、1表示這兩種關(guān)系，用0、1分別來表示兩城市之間的相離和相鄰(相鄰是指兩城市之間有公共的邊界)，并人為規(guī)定相同的城市與城市之間的關(guān)系是0。由于一幅圖中城市太多，為使問題簡(jiǎn)化，現(xiàn)就用如下9個(gè)區(qū)域(設(shè)每個(gè)區(qū)域所代表不同的城市)來進(jìn)行模擬，如圖1所示。用0、1將兩者的關(guān)系由矩陣加以表示，如圖2所示，不難看出它們兩兩之間的關(guān)系是鄰接對(duì)稱矩陣。

圖1 9個(gè)區(qū)域模擬圖

圖2 9個(gè)區(qū)域的關(guān)系圖

3 地圖著色的原理及算法

地圖著色的原理是任何平面地圖可以使用4種顏色給每個(gè)不同的城市著色，而保證相鄰的城市著不同的顏色，可采用“貪心算法”來完成。貪心算法［3］是求最優(yōu)解的一種比較不錯(cuò)的算法，其思想為:先用一種顏色給盡可能多的結(jié)點(diǎn)上色，然后用另一種顏色在未著色結(jié)點(diǎn)中給盡可能多的結(jié)點(diǎn)上色，如此反復(fù)直到所有結(jié)點(diǎn)都著色為止。因此可把地圖上的每個(gè)城市抽象為一個(gè)點(diǎn)，并給每個(gè)城市編號(hào)，相鄰的城市之間用直線連接。據(jù)此做出鄰接矩陣，若第i個(gè)城市與第j個(gè)城市相鄰，則 metro［i］［j］=1，否則 metro［i］［j］=0，照編號(hào)從小到大的順序檢查每個(gè)城市，對(duì)每個(gè)城市從1到4使用4種顏色著色，若當(dāng)前顏色可用(即不與相鄰城市顏色相同)，則著色;否則測(cè)試下一種顏色。

地圖著色問題可以轉(zhuǎn)化為圖來處理，假設(shè)要著色的圖為G，集合V1包括圖中所有未被著的結(jié)點(diǎn)，著色開始時(shí)V1是G1所有結(jié)點(diǎn)的集合(用 G.V表示)。NEW表示已確定可以用新顏色著色的結(jié)點(diǎn)的集合。

從V1中找出可用新顏色著色的結(jié)點(diǎn)集的工作可以用下面的程序框架描述:

通過上面的程序框架便可完成。

4 地圖著色問題的實(shí)現(xiàn)

有了上面的數(shù)據(jù)模型、原理、算法及開發(fā)思路以后，可對(duì)圖1的9個(gè)城市區(qū)域加以模擬，選擇C語言作為開發(fā)工具，其主要代碼如下:

5 實(shí)現(xiàn)結(jié)果展示

運(yùn)行上面的程序，即可看到運(yùn)行后的結(jié)果，并將其結(jié)果對(duì)著前面的區(qū)域分別用1、2、3、4進(jìn)行填充和用1、2、3、4 所代表的 red、green、blue、yellow 結(jié)果進(jìn)行填充，得到如圖5展示的結(jié)果圖。

圖3 C語言程序運(yùn)行的界面圖

圖4 用C語言數(shù)字結(jié)果進(jìn)行填充圖

圖5 用C語言顏色進(jìn)行填充圖

6 結(jié)論

本文重點(diǎn)介紹了GIS中地圖著色問題，并將其轉(zhuǎn)化為計(jì)算機(jī)能表達(dá)的數(shù)據(jù)結(jié)構(gòu)，接著介紹了其數(shù)據(jù)結(jié)構(gòu)及其算法，然后用C語言給予了實(shí)現(xiàn)，最后展示了實(shí)現(xiàn)的結(jié)果。本程序也存在著不足，就是如何將其結(jié)果進(jìn)行優(yōu)化的問題，還有待進(jìn)一步的研究。

［1］T CHEN，R SHIBASAKI.A Versatile AR Type 3D Mobile GIS Based on Image Navigation Technology。Systems，Man，and Cybernetica，1999.IEEE SMC’99 Conference Proceedings.1999 IEEE International Conference on 1999，8:1070～1075.

［2］Hardy pundt，Yaser Bishr，Domain On tologies for Data Sharing an Example from Environmental Monitoring Using Fiels GIS［J］.computers and Geosciences，2002，28(1):95 ～102.

［3］Congalton R G，Green K.Assessing the accuracy of remotely sensed data:Principles and practices［M］.New York:Lewis Publishers，1999.

［4］張乃孝.算法與數(shù)據(jù)結(jié)構(gòu)—C語言描述［M］.北京:高等教育出版社，2002.

［5］何宗宜.地圖數(shù)據(jù)處理模型的原理與方法［M］.武漢:武漢大學(xué)出版社，2004.

［6］龔健雅.地理信息系統(tǒng)基礎(chǔ).北京:科學(xué)出版社，2001.