趙曉東+方歡+陳思宇

摘 要：利用Java對基于偏好的有向圖路徑搜索系統(tǒng)進行了分析和設計，用來解決以下實際問題：有向圖中邊的權值是一個區(qū)間[a，b]，其中a表示最小代價，b表示最大代價，根據(jù)個人偏好給出有向圖中邊的偏好因子和一個目標值F，找出從源點到匯點的所有路徑中滿足邊的偏好權重值之和小于F的路徑集合。提出的基于偏好的路徑搜索可在相關優(yōu)化算法中廣泛應用。

關鍵詞：偏好；權值區(qū)間；有向圖；路徑搜索；路徑優(yōu)化

DOIDOI：10.11907/rjdk.171321

中圖分類號：TP319

文獻標識碼：A 文章編號文章編號：1672-7800（2017）008-0108-03

0 引言

路徑搜索問題在很多領域都有其研究價值，很多問題最終都可轉(zhuǎn)化為圖的路徑搜索問題。隨著社會的發(fā)展，有向圖最短路徑搜索研究成果已經(jīng)無法滿足需求。為此，本文設計一套給定條件下基于偏好的有向圖路徑搜索系統(tǒng)。

實際生活中往往會遇到做一件事情的代價在一定范圍內(nèi)波動的問題，將這種問題轉(zhuǎn)化為圖的問題進行解決，引入權重區(qū)間來表示圖中邊的權取值范圍。對于同一件事情有不同的解決方法，由于各種因素導致不同的方法有著不同的傾向，于是將問題轉(zhuǎn)化為圖的問題后引入偏好因子來衡量個人對邊的傾向程度，表示對該邊的傾向占整體的比例。實際問題中由于某些因素的限制，會使得問題處理具有一定的局限性。即便問題的處理有多樣性也需要根據(jù)實際選擇解決方法，將這種問題轉(zhuǎn)化為圖的問題引入偏好權重表示，根據(jù)代價的范圍以及傾向程度決定帶入計算的具體值。為了滿足用戶對圖的邊偏好以及圖中邊權重的波動需求，通過用戶輸入圖的起點、終點、目標值、各邊偏好因子和權重區(qū)間，在有向圖環(huán)境下搜索出所有滿足目標值條件的路徑，很容易得到最短路徑。

1 需求與功能分析

1.1 需求分析

隨著計算機的普及，人們遇到問題時都希望通過計算機技術進行科學合理的解決。諸如房子裝修問題，用戶在一定預算下對不同的房間裝修喜好要求不一，又如用戶需要在一定時間內(nèi)從地方A到地方B，由于路況等因素，對于不同路線的傾向程度不一樣，考慮限速、堵車等因素，不同路段行駛時間預計在一定范圍內(nèi)，類似上述問題都可以轉(zhuǎn)化為給定條件下基于偏好的有向圖路徑搜索。為了解決這類問題，設計開發(fā)了給定條件下基于偏好的有向圖的路徑搜索系統(tǒng)。偏好因子采用兩種不同的表示方式，一種是用戶只知道大致的偏好程度無法具體量化，另一種是根據(jù)各邊的部分偏好占整體偏好的比例計算。用戶通過輸入圖的頂點數(shù)、起始點、終點、目標值、圖中各邊的偏好因子、成本區(qū)間矩陣，經(jīng)過后臺算法計算，得到限制條件下滿足個人偏好的所有路徑[1]。

1.2 功能分析

圖的路徑搜索系統(tǒng)軟件功能如下：①對滿足目標值的所有路徑進行顯示；②對于圖的每條路徑的權重受用戶偏好影響；③用戶的偏好因子采用兩種計算方式，由用戶決定采用哪種；④界面簡單易操作。

偏好的兩種表示方式：

（1）用戶只知道大致的偏好程度無法具體量化。采用A-F選項進行選擇，A-F不同選項代表不同區(qū)間，然后從區(qū)間內(nèi)產(chǎn)生一個隨機數(shù)作為偏好因子[2]，選項代表的區(qū)間具體如下：

A選項對應區(qū)間為[-1.0，-0.6]，B選項對應區(qū)間為[-0.6，-0.3]，C選項對應區(qū)間為[-0.3，0]，D選項對應區(qū)間為[0，+0.3]，E選項對應區(qū)間為[+0.3，+0.6]，F(xiàn)選項對應區(qū)間為[+0.6，+1.0]。

該方式下偏好權重W為：

W=a+b2+b-a2×d（1）

其中，邊的權重區(qū)間為[a，b]，邊的偏好因子為d。

（2）根據(jù)部分偏好占整體偏好的比例，從起始點到終點的一條路徑上各邊的偏好因子之和為1，該方式下偏好權重W為：

W=a+b2+b-a2×（2×d-1）（2）

其中，邊的權重區(qū)間為[a，b]，邊的偏好因子為d。

這兩種方式下，當偏好因子的取值范圍為0～1時，偏好權重取值范圍為a～b。

系統(tǒng)包括3大模塊：①界面設計模塊。該模塊用以設計各種界面，用來輸入圖的頂點數(shù)、起始點、終點、目標值、圖中各邊的偏好因子、成本區(qū)間矩陣，完成各界面之間的數(shù)據(jù)交互以及最終限制條件下滿足個人偏好的所有路徑結果顯示；②有向圖路徑搜索模塊。根據(jù)界面模塊提供的數(shù)據(jù)，基于深度優(yōu)先算法進行路徑搜索，得到想要的路徑集合；③結果顯示截獲模塊。利用Eclipse進行Java語言設計，把控制臺結果截獲以管道流的形式將輸出結果在界面中的文本框中顯示[3]。模塊間的聯(lián)系如圖1所示。

2 系統(tǒng)設計

2.1 功能設計

為實現(xiàn)用戶與系統(tǒng)的交互功能，考慮實際問題中用戶的偏好問題，由用戶輸入轉(zhuǎn)化后有向圖頂點個數(shù)動態(tài)生成有向圖，輸入起始點、終點、目標值、各邊偏好因子等數(shù)據(jù)完成路徑搜索。由于有些用戶的偏好程度無法量化，系統(tǒng)通過偏好程度選項自動生成衡量偏好程度的數(shù)值指標。系統(tǒng)界面輸入相關數(shù)據(jù)和顯示結果，算法用以求解路徑集合[4]。系統(tǒng)執(zhí)行流程如圖2所示。

2.2 系統(tǒng)界面設計

（1）主界面設計。本界面用于輸入頂點個數(shù)、開始頂點、結束頂點、目標值以及顯示最終結果。單擊輸入成本鄰接矩陣按鈕跳轉(zhuǎn)到成本鄰接矩陣界面，單擊輸入偏好鄰接矩陣（類型一）按鈕跳轉(zhuǎn)到偏好鄰接矩陣（類型一）界面，單擊輸入偏好鄰接矩陣（類型二）按鈕跳轉(zhuǎn)到偏好鄰接矩陣（類型二）界面，單擊顯示滿足條件的路徑（類型一）按鈕，顯示由偏好鄰接矩陣（類型一）界面數(shù)據(jù)得到的結果，單擊顯示滿足條件的路徑（類型二）按鈕，顯示由偏好鄰接矩陣（類型二）界面數(shù)據(jù)得到的結果。主界面設計如圖3所示。

（2）成本鄰接矩陣界面設計。本界面根據(jù)主界面輸入的頂點個數(shù)動態(tài)生成一個輸入矩陣，用于輸入有向圖中各邊權重，即兩個相鄰頂點之間需要的代價[5]。由于矩陣的每個元素是一個數(shù)值區(qū)間，為方便用戶輸入，將矩陣中的每個元素輸入界面設計成圖4樣式。對于矩陣對角線元素默認為[0，0]，頂點之間不連通的則不用輸入。單擊提交按鈕進行提交且關閉界面。endprint

（3）偏好鄰接矩陣（類型一）界面設計。本界面根據(jù)主界面輸入的頂點個數(shù)動態(tài)生成一個輸入矩陣，用于輸入有向圖中各邊的偏好指標。考慮到有些用戶對于偏好程度無法量化，系統(tǒng)通過偏好程度選項（A-F）自動生成衡量偏好程度的數(shù)值指標。

（4）偏好鄰接矩陣（類型二）界面設計。本界面根據(jù)主界面輸入的頂點個數(shù)動態(tài)生成一個輸入矩陣，用于輸入有向圖中各邊的偏好指標。根據(jù)部分偏好占整體偏好的比例進行填寫，填寫范圍為0-1。

2.3 軟件測試

進行功能測試，主要針對系統(tǒng)的輸入、界面跳轉(zhuǎn)、相關數(shù)據(jù)求解路徑集合等進行測試，每種測試都包括正常和非正常兩種情況。測試的相關數(shù)據(jù)如表1、表2、表3、表4所示。

根據(jù)上述數(shù)據(jù)運行結果如下：

當前的頂點個數(shù)：6

目標值：70

第V0個節(jié)點：V0-V0：0 V0-V1：1 V0-V2：1 V0-V3：0 V0-V4：0 V0-V5：0

第V1個節(jié)點：V1-V0：0 V1-V1：0 V1-V2：1 V1-V3：1 V1-V4：1 V1-V5：0

第V2個節(jié)點：V2-V0：0 V2-V1：0 V2-V2：0 V2-V3：0 V2-V4：1 V2-V5：0

第V3個節(jié)點：V3-V0：0 V3-V1：0 V3-V2：1 V3-V3：0 V3-V4：1 V3-V5：1

第V4個節(jié)點：V4-V0：0 V4-V1：0 V4-V2：0 V4-V3：0 V4-V4：0 V4-V5：1

第V5個節(jié)點：V5-V0：0 V5-V1：0 V5-V2：0 V5-V3：0 V5-V4：0 V5-V5：0 其中0表示兩個相鄰頂點之間不存在通路，1表示兩個相鄰頂點之間存在通路。

由偏好鄰接矩陣（類型一）界面數(shù)據(jù)得到結果：

V0→V1→V3→V4→V5 總代價為：69.0

V0→V1→V3→V5 總代價為：61.0

V0→V1→V4→V5 總代價為：60.0

V0→V2→V4→V5 總代價為：64.5

由偏好鄰接矩陣（類型二）界面數(shù)據(jù)得到結果：

V0→V1→V3→V4→V5 總代價為：62.0

V0→V1→V3→V5 總代價為：52.0

V0→V1→V4→V5 總代價為：55.0

V0→V2→V4→V5 總代價為：59.0

經(jīng)檢驗，上述結果正確。

性能測試主要是進行響應時間測試，該測試通過不同數(shù)量的數(shù)據(jù)完成。

3 結語

采用Java語言設計并實現(xiàn)了給定條件下基于偏好的有向圖路徑搜索系統(tǒng)。應用本系統(tǒng)，用戶基于偏好輸入相關數(shù)據(jù)得到最終想要的路徑集合，很容易得到最短路徑。下一步將對系統(tǒng)進行優(yōu)化，更多考慮人性化需求，美化系統(tǒng)操作界面，優(yōu)化路徑搜索算法，提高系統(tǒng)運行速度。

參考文獻：

[1] 嚴蔚敏，吳偉民.數(shù)據(jù)結構[M].C語言版.北京：清華大學出版社，2006.

[2] 方賢文.Java語言程序設計[M].合肥：安徽科學技術出版社，2014.

[3] 李興華.Java開發(fā)實戰(zhàn)經(jīng)典[M].北京：清華大學出版社，2009.

[4] 馬可，艾倫，維斯.數(shù)據(jù)結構與算法分析：Java語言描述[M].第3版.北京：機械工業(yè)出版社，2016.

[5] 李剛.瘋狂Java講義[M].北京：電子工業(yè)出版社，2012.endprint