周 影0

淮北師范大學(xué)計算機科學(xué)與技術(shù)學(xué)院，淮北，235000

?

基于方向啟發(fā)性的路徑查找模型研究

周 影0

淮北師范大學(xué)計算機科學(xué)與技術(shù)學(xué)院，淮北，235000

提出了一種在起點和終點的方向關(guān)系已知的前提下的路徑查找模型。查找過程從起點開始，計算其鄰接點與終點的方向關(guān)系，利用優(yōu)劣評價函數(shù)逐一計算出各經(jīng)歷頂點的最優(yōu)鄰接點，由若干最優(yōu)鄰接點組成的頂點序列就是所找路徑。結(jié)果表明：該模型依托的方向關(guān)系可以有效提高陌生環(huán)境的路徑查找效率，同時模型的穩(wěn)定性和準確率也都較高。

路徑查找；優(yōu)劣評價函數(shù)；方向關(guān)系；模型；鄰接點

1 問題的提出

路徑查找是確定出起點到終點之間的一條路徑，并沿路徑而行的心理過程，它的最終目標是找到由起點到達終點的一條路徑[1]。對于路徑查找，很多國外的學(xué)者和專家提出了多種模型。Moise Busogi等提出一種人類理性行為基礎(chǔ)上的路徑查找建模方法，通過對人的行為評估，在執(zhí)行層面上感知物理環(huán)境[2]。Beatrix Emo提出并強調(diào)空間幾何角色對個人空間決策的重要性，并在城市環(huán)境中實現(xiàn)了路徑查找[3]。但國內(nèi)研究路徑查找模型的較少，齊平、李龍澍提出一種基于信任機制的動態(tài)商拓撲模型，該模型拓撲結(jié)構(gòu)在隨時間變化的情況下，使用貝葉斯方法評估節(jié)點可信度[4]。蘇加強、丁柳云基于遺傳算法，提出了查找最優(yōu)路徑的算法[5]。趙開新、王東署等人提出基于蟻群遺傳算法的移動機器人路徑規(guī)劃算法，旨在改進初期搜索盲目性大等問題[6]。

以上文獻都在實驗中說明方法的有效性，但均未針對方向啟發(fā)信息進行路徑查找。為此，本文提出一種以方向啟發(fā)為前提的路徑查找模型，假設(shè)前提為已知起點和終點的方位，一步步找出起點到終點的最優(yōu)鄰接頂點，這些頂點組成了所找路徑。

2 方向關(guān)系和優(yōu)劣評價函數(shù)解析

此模型中,假設(shè)知道起點(SV)和終點(EV)的方向關(guān)系，從起點出發(fā)，找出起點的鄰接點(AV)，利用鄰接點和終點的方向關(guān)系是否接近于起點和終點的方向，進而確定出最優(yōu)鄰接點。

2.1 方向關(guān)系

模型中的方向關(guān)系有8種，東、南、西、北為4個基本方位，東南、西南、西北、東北為4個輔助方位，其位置關(guān)系如圖1所示。

圖1 方向關(guān)系圖

2.2 優(yōu)劣評價函數(shù)

路徑查找的關(guān)鍵是通過計算找出最優(yōu)鄰接點，最優(yōu)鄰接點可使用優(yōu)劣評價函數(shù)計算得出。函數(shù)的定義：如果起點與當前點(CV)的方向關(guān)系等于起點與終點的關(guān)系，那么該當前點的評價函數(shù)值最大；如果起點與當前點的方向關(guān)系和起點與終點的方向關(guān)系是相關(guān)的，它的評價函數(shù)值取中間值；如果起點與當前點的方向關(guān)系和起點與終點的關(guān)系是無關(guān)的，那么它的評價函數(shù)值就是最小的。這里所說的相關(guān)，應(yīng)理解為相近，比如起點與終點的方向關(guān)系是東南，起點與當前點的方向關(guān)系是東或南，那么就認為它們是相關(guān)的；相反，比如起點與終點的方向關(guān)系是正東，起點與當前點的方向關(guān)系是東北或東南，此時也認為它們是相關(guān)的。

Fun (SV,CV) {

If (Relation(SV,CV))∩(Relation(SV,EV))= Relation(SV,EV)) return max;

If (Relation(SV,CV))∩(Relation(SV,EV))∈Relation(SV,EV)) return middle;

If (Relation(SV,CV))∩(Relation(SV,EV))=?return min;

}；

如果起點與當前點的方向關(guān)系和起點與終點的方向關(guān)系是一致的，且符合條件的當前點不止一個頂點時，就按存儲時第一個存儲的當前點作為最優(yōu)鄰接點。

2.3 假設(shè)場景解析

圖2為假設(shè)場景，場景中A是起點，B是終點，A1、A2、A3、A4是起點A的鄰接點，Relation(A,B)=WS。

圖2 假設(shè)場景

(1)分別計算三個鄰接點與A的方向關(guān)系：

Relation(A,A1)=WS, Relation(A,A2)=S, Relation(A,A3)=ES；

(2)計算三個鄰接點與起點的方向關(guān)系的評價函數(shù)：

Fun(A,A1)=max,Fun(A,A2)=middle,Fun(A,A3)=min;

(3)比較三個評價函數(shù)的大小，選取評價函數(shù)值大的點作為下一步需要訪問的頂點，因為Fun(A,A1)>Fun(A,A2)>Fun(A,A3),所以A1的評價函數(shù)值最大，故A1是最優(yōu)鄰接點。

A1為起點之后的計算得到下一個的頂點，然后再以A1作為新的起點，計算A1的鄰接點中的最優(yōu)者，一步步執(zhí)行，直到頂點和終點相同結(jié)束。

3 基于方向啟發(fā)式的路徑查找模型

3.1 模型的實現(xiàn)步驟

模型的實現(xiàn)依托一個相對完整的環(huán)境，把環(huán)境轉(zhuǎn)換為道路圖，圖中有頂點集、邊集、圖層，算法步驟如下：

Step1 定義頂點Vertex的數(shù)據(jù)類型，定義與頂點類型相同的隊列，用于存儲路徑查找過程中的諸多最優(yōu)鄰接頂點；

Step2 初始化道路圖中所有頂點個數(shù)N(int N≥2)；

Step3 輸入起點SV和終點EV，和兩者的位置關(guān)系Relation (SV,EV)；

Step4 如果N=2,輸出SV→EV那條路徑；如果N>2，轉(zhuǎn)向Step5；

Step5 利用優(yōu)劣評價函數(shù)計算起點的每個鄰接點的函數(shù)值，從中選出最優(yōu)鄰接點作為下一個訪問對象AV′，同時將此鄰接點存入隊列中；

Step6 如果AV′=EV,輸出隊列里的所有頂點，頂點序列就是所求的路徑；如果AV′!=EV,把AV′作為新的頂點，轉(zhuǎn)向Step5。

3.2 實驗結(jié)果與分析

MapXtreme是MapInfo公司開發(fā)的基于網(wǎng)絡(luò)的應(yīng)用服務(wù)器，它具有強大的地圖化功能，包括地圖編輯、地圖顯示、圖層控制等[7-8]。以下使用MapXtreme作為界面工具，以淮北師范大學(xué)校園為模擬環(huán)境。將校園平面圖構(gòu)造成由頂點和直線路徑組成的實驗用圖，為了直觀，把各建筑物用類實物圖顯示。實驗中，以學(xué)校大門(存儲名為node1)為起點，學(xué)生第二食堂(存儲名為node62)為終點，輸入兩者的方位關(guān)系為西南方向(WS),執(zhí)行界面如圖3所示，粗虛線即為所求路徑。

圖3 基于方向啟發(fā)的路徑查找模型實驗圖

4 結(jié) 論

在起點和終點的方向關(guān)系已知的基礎(chǔ)上，從起點開始，利用最優(yōu)評價函數(shù)計算出最優(yōu)鄰接點，直到找出到終點的路徑位置。該模型的實現(xiàn)是在學(xué)校環(huán)境里，經(jīng)過多次比較和測試，該模型在時間上是高效的，同時穩(wěn)定性和準確率也都較高。從問題的系統(tǒng)性上考慮，在今后的研究工作中可考慮增加頂點的信息存儲量、道路權(quán)值等信息，可提高問題的精準度。

[1]David M Mark,Christian Freksa,Stephen C.Hirtle,et al.Cognitive models of geographical space[J].International Journal of Geographical Information Science,1999,13(8):747-774

[2]Moise Busog,Namhun Kim,Dongmin Shin,et al.Bayesian Affordance-Based Agent Model for Wayfinding Behaviors in Evacuation Problems[C].Berlin：4th International Conference of HCI International,2013:297-306

[3]Beatrix Emo.Wayfinding in Real Cities:Experiments at Street Corners[C].Berlin：International Conference of Spatial Cognition,2012:461-477

[4]齊平,李龍澍.動態(tài)商拓撲模型及其在路徑查找中的應(yīng)用[J].模式識別與人工智能,2014,24(7):337-344

[5]蘇加強,丁柳云.基于遺傳算法的GIS輔助最優(yōu)路徑查找算法[J].遼寧科技學(xué)院學(xué)報,2012,14(4):23-25

[6]趙開新,王東署,徐立新.蟻群遺傳算法在移動機器人路徑規(guī)劃中的綜合應(yīng)用研究，制造業(yè)自動化，2014,36(9):70-72,84

[7]孫龍,曹菡.基于MapXtreme的候機樓導(dǎo)航和監(jiān)控系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機科學(xué)與發(fā)展,2011,21(5):183-186

[8]吳開興,范周艷.MapXtreme下WebGIS的優(yōu)化研究[J].測繪通報,2015,(7):109-112

(責(zé)任編輯：汪材印)

10.3969/j.issn.1673-2006.2017.04.032

2017-02-01

安徽省教育廳高校自然科學(xué)研究重點項目“安全協(xié)議的形式化分析方法研究”( KJ2017A848)。

周影(1981-)，女，安徽淮北人，碩士，講師，研究方向：GIS，信息安全。

TP301.6

A

1673-2006(2017)04-0115-03