基于偏好的有向圖路徑搜索系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

趙曉東+方歡+陳思宇

摘 要：利用Java對(duì)基于偏好的有向圖路徑搜索系統(tǒng)進(jìn)行了分析和設(shè)計(jì)，用來(lái)解決以下實(shí)際問(wèn)題：有向圖中邊的權(quán)值是一個(gè)區(qū)間[a，b]，其中a表示最小代價(jià)，b表示最大代價(jià)，根據(jù)個(gè)人偏好給出有向圖中邊的偏好因子和一個(gè)目標(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

中圖分類號(hào)：TP319

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

0 引言

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

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

1 需求與功能分析

1.1 需求分析

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

1.2 功能分析

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

偏好的兩種表示方式：

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

A選項(xiàng)對(duì)應(yīng)區(qū)間為[-1.0，-0.6]，B選項(xiàng)對(duì)應(yīng)區(qū)間為[-0.6，-0.3]，C選項(xiàng)對(duì)應(yīng)區(qū)間為[-0.3，0]，D選項(xiàng)對(duì)應(yīng)區(qū)間為[0，+0.3]，E選項(xiàng)對(duì)應(yīng)區(qū)間為[+0.3，+0.6]，F(xiàn)選項(xiàng)對(duì)應(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時(shí)，偏好權(quán)重取值范圍為a～b。

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

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

2.1 功能設(shè)計(jì)

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

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

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

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

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

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

2.3 軟件測(cè)試

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

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

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

目標(biāo)值：70

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

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

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

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

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

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

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

V0→V1→V3→V4→V5 總代價(jià)為：69.0

V0→V1→V3→V5 總代價(jià)為：61.0

V0→V1→V4→V5 總代價(jià)為：60.0

V0→V2→V4→V5 總代價(jià)為：64.5

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

V0→V1→V3→V4→V5 總代價(jià)為：62.0

V0→V1→V3→V5 總代價(jià)為：52.0

V0→V1→V4→V5 總代價(jià)為：55.0

V0→V2→V4→V5 總代價(jià)為：59.0

經(jīng)檢驗(yàn)，上述結(jié)果正確。

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

3 結(jié)語(yǔ)

采用Java語(yǔ)言設(shè)計(jì)并實(shí)現(xiàn)了給定條件下基于偏好的有向圖路徑搜索系統(tǒng)。應(yīng)用本系統(tǒng)，用戶基于偏好輸入相關(guān)數(shù)據(jù)得到最終想要的路徑集合，很容易得到最短路徑。下一步將對(duì)系統(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語(yǔ)言版.北京：清華大學(xué)出版社，2006.

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

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

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

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