基于偏好的有向圖的路徑搜索問題的研究

趙曉東　陳思宇　方歡

摘要：目前，路徑搜索問題在生活中的很多領(lǐng)域都能得到應(yīng)用。生活中存在很多可轉(zhuǎn)化為如下表述的實(shí)際問題：有向圖圖中邊的權(quán)值是一個(gè)區(qū)間[a，b]，其中a表示最小代價(jià)b表示最大代價(jià)，根據(jù)個(gè)人偏好給出各邊的偏好因子和一個(gè)目標(biāo)值F，找出從源點(diǎn)到匯點(diǎn)的所有路徑中，滿足邊的偏好權(quán)重值之和

關(guān)鍵詞：有向圖；偏好；路徑搜索；深度優(yōu)先；路徑優(yōu)化

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）07-0192-03

1背景

路徑搜索問題在很多領(lǐng)域都有其研究的價(jià)值，很多問題最終都可以轉(zhuǎn)化為圖的路徑搜索問題。常見的路徑搜索算法有：Dijkstra算法、BSF算法、A*算法等。Dijkstra算法是通過中心為起點(diǎn)，以輻射狀不斷向中心外搜索（每次取距離起點(diǎn)最近的點(diǎn)），一圈一圈向外擴(kuò)張，直到逼近目標(biāo)點(diǎn)，完成路徑搜索，它較能適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?、性能較穩(wěn)定等；BSF算法每次擴(kuò)張節(jié)點(diǎn)，都是通過啟發(fā)函數(shù)選擇最接近目標(biāo)的節(jié)點(diǎn)，最終完成搜索；A*算法兼具Dijkstra準(zhǔn)確和BSF的快速，在搜索路徑時(shí)，通過啟發(fā)式函數(shù)計(jì)算當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離，而起始點(diǎn)到當(dāng)前點(diǎn)距離已知，則每次選擇初始點(diǎn)到目標(biāo)點(diǎn)的代價(jià)估計(jì)最小的節(jié)點(diǎn)，A*算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問題的有效算法。A*算法中的距離估算值與實(shí)際值越接近，最終搜索速度越快。以上算法都是用來求解最短路徑搜索問題，大多數(shù)研究者也都是對(duì)最短路徑搜索問題在不同領(lǐng)域進(jìn)行研究。

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

2改進(jìn)的深度優(yōu)先路徑搜索方法

2.1深度優(yōu)先搜索{DFS}

假設(shè)給定圖G的初態(tài)是所有頂點(diǎn)均未曾訪問過。在G中任選一頂點(diǎn)v為初始出發(fā)點(diǎn)（源點(diǎn)），則深度優(yōu)先搜索可定義如下；首先訪問出發(fā)點(diǎn)v，并將其標(biāo)記為已訪問過；然后依次從v出發(fā)搜索v的每個(gè)鄰接點(diǎn)w。若w未曾訪問過，則以w為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)（亦稱為從源點(diǎn)可達(dá)的頂點(diǎn)）均已被訪問為止。若此時(shí)圖中仍有未訪問的頂點(diǎn)，則另選一個(gè)尚未訪問的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過程，直至圖中所有頂點(diǎn)均已被訪問為止。算法流程如圖1所示。

2.2改進(jìn)的深度優(yōu)先搜索及具體求解過程

由于采用深度優(yōu)先搜索只能得到一條路徑，為了解決上述問題得到所有滿足條件的路徑，于是對(duì)深度優(yōu)先搜索做如下修改。

設(shè)x是當(dāng)前被訪問頂點(diǎn)，在對(duì)x做過訪問標(biāo)記后，選擇一條從x出發(fā)的未檢測過的邊（x，y）。若發(fā)現(xiàn)頂點(diǎn)y已訪問過，則重新選擇另一條從x出發(fā)的未檢測過的邊，否則沿邊（x，y）到達(dá)未曾訪問過的y，對(duì)y訪問并將其標(biāo)記為已訪問過；然后從y開始搜索，直到搜索完從y出發(fā)的所有路徑，即訪問完所有從y出發(fā)可達(dá)的頂點(diǎn)之后，才回溯到頂點(diǎn)x，并且再選擇一條從x出發(fā)的未檢測過的邊。上述過程直至從x出發(fā)的所有邊都已檢測過為止。此時(shí)，若x不是源點(diǎn)，則回溯到在x之前被訪問過的頂點(diǎn)；否則圖中所有和源點(diǎn)有路徑相通的頂點(diǎn)（即從源點(diǎn)可達(dá)的所有頂點(diǎn)）都已被訪問過，若圖G是連通圖，則遍歷過程結(jié)束，否則繼續(xù)選擇一個(gè)尚未被訪問的頂點(diǎn)作為新源點(diǎn)，進(jìn)行新的搜索過程。

滿足目標(biāo)值的搜索算法的偽代碼如下所示：

訪問頂點(diǎn)V0；visited[V0]=1；

W=頂點(diǎn)V0的第一個(gè)鄰接點(diǎn)；

While（W存在）{

if（W未被訪問and W非棧頂結(jié)點(diǎn)）從頂點(diǎn)W出發(fā)進(jìn)行深度優(yōu)先搜索；

else（W為棧頂結(jié)點(diǎn)）

彈出棧計(jì)算路徑偏好權(quán)重；

if（符合目標(biāo)值）輸出路徑及總代價(jià)

else舍棄路徑

W=頂點(diǎn)V0的下一個(gè)鄰接點(diǎn)；

}

下面將通過一個(gè)具體的例子來說明滿足目標(biāo)值的搜索過程。有向圖相關(guān)數(shù)據(jù)見圖2、表1、表2所示。

根據(jù)各邊的偏好因子以及權(quán)重區(qū)間得到各邊的偏好權(quán)重，如表3所示，偏好權(quán)重的計(jì)算方式如下：

假設(shè)邊的權(quán)重區(qū)間為[a，6]，邊的偏好因子為d，則邊的偏好權(quán)重w為：

當(dāng)偏好因子的取值范圍為0-1時(shí)，偏好權(quán)重取值范圍為a-6。

根據(jù)圖1所示的有向圖以及表1、表2、表3，求解節(jié)點(diǎn)0到節(jié)點(diǎn)5的滿足目標(biāo)值的所有路徑的實(shí)現(xiàn)過程如圖3所示。圖3所有路徑求解的實(shí)現(xiàn)過程圖

3結(jié)果及分析

當(dāng)目標(biāo)值為70時(shí)，利用改進(jìn)的深度優(yōu)先搜索算法根據(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：O

第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 VS-V1：0 V5-V2：0 V5-V3：0 VS-V4：0 VS-V5：0

其中0表示兩個(gè)相鄰頂點(diǎn)之間不存在通路，1表示兩個(gè)相鄰頂點(diǎn)之間存在通路。

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

由上述結(jié)果可知，滿足條件的路徑共有4條，并且很容易得到最短路徑為V0->V1->V3->V5->總代價(jià)為：52.0。重復(fù)上述實(shí)驗(yàn)，隨著目標(biāo)值的增大，滿足條件的路徑數(shù)目也越來越多。

4結(jié)束語

在滿足給定條件下，根據(jù)個(gè)人偏好和目標(biāo)值采用改進(jìn)的深度優(yōu)先搜索方法，實(shí)現(xiàn)了給定條件下帶權(quán)有向圖的路徑搜索。通過各邊的偏好因子和權(quán)重區(qū)間確定偏好權(quán)重，利用棧結(jié)構(gòu)保存從起始頂點(diǎn)到目標(biāo)頂點(diǎn)在限制條件下的路徑頂點(diǎn)，從而完成限制條件下滿足個(gè)人偏好的路徑搜索。在本文的基礎(chǔ)上也很容易將算法推廣到限制條件下滿足個(gè)人偏好的無向圖的路徑搜索。本算法的優(yōu)點(diǎn)是能夠人性化的結(jié)合每個(gè)人的不同偏好，在限定條件下對(duì)有向圖進(jìn)行路徑搜索。本文限制條件下滿足個(gè)人偏好的有向圖的路徑搜索可以用來解決房子裝修問題、交通線路選擇問題等方面。