趙曉東+方歡+陳思宇

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

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

DOIDOI：10.11907/rjdk.171321

中圖分類號：TP319

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：1672-7800（2017）008-0108-03

0 引言

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

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

1 需求與功能分析

1.1 需求分析

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

1.2 功能分析

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

偏好的兩種表示方式：

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

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

該方式下偏好權(quán)重W為：

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

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

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

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

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

這兩種方式下，當(dāng)偏好因子的取值范圍為0～1時，偏好權(quán)重取值范圍為a～b。

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

2 系統(tǒng)設(shè)計

2.1 功能設(shè)計

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

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

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

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

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

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

2.3 軟件測試

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

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

當(dāng)前的頂點(diǎn)個數(shù)：6

目標(biāo)值：70

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

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

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

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

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

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

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

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ù)得到結(jié)果：

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)檢驗，上述結(jié)果正確。

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

3 結(jié)語

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

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].C語言版.北京：清華大學(xué)出版社，2006.

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

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

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

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