基于偏好的有向圖路徑搜索系統設計與實現

趙曉東+方歡+陳思宇

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

關鍵詞：偏好；權值區間；有向圖；路徑搜索；路徑優化

DOIDOI：10.11907/rjdk.171321

中圖分類號：TP319

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

0 引言

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

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

1 需求與功能分析

1.1 需求分析

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

1.2 功能分析

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

偏好的兩種表示方式：

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

A選項對應區間為[-1.0，-0.6]，B選項對應區間為[-0.6，-0.3]，C選項對應區間為[-0.3，0]，D選項對應區間為[0，+0.3]，E選項對應區間為[+0.3，+0.6]，F選項對應區間為[+0.6，+1.0]。

該方式下偏好權重W為：

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

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

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

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

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

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

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

2 系統設計

2.1 功能設計

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

2.2 系統界面設計

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

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

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

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

2.3 軟件測試

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

根據上述數據運行結果如下：

當前的頂點個數：6

目標值：70

第V0個節點：V0-V0：0 V0-V1：1 V0-V2：1 V0-V3：0 V0-V4：0 V0-V5：0

第V1個節點：V1-V0：0 V1-V1：0 V1-V2：1 V1-V3：1 V1-V4：1 V1-V5：0

第V2個節點：V2-V0：0 V2-V1：0 V2-V2：0 V2-V3：0 V2-V4：1 V2-V5：0

第V3個節點：V3-V0：0 V3-V1：0 V3-V2：1 V3-V3：0 V3-V4：1 V3-V5：1

第V4個節點：V4-V0：0 V4-V1：0 V4-V2：0 V4-V3：0 V4-V4：0 V4-V5：1

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

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

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

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

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

經檢驗，上述結果正確。

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

3 結語

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

參考文獻：

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

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

[3] 李興華.Java開發實戰經典[M].北京：清華大學出版社，2009.

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

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