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

1、    基于偏好的有向圖的路徑搜索問題的研究    趙曉東陳思宇方歡摘要：目前，路徑搜索問題在生活中的很多領(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)重值之和< p>關(guān)鍵詞：有向圖；偏好；路徑搜索；深度優(yōu)先；路徑優(yōu)化：tp311 ：a ：1009-3044（2017）07-0192-031背景路徑搜索問題在很多領(lǐng)域都有其研究的價(jià)值，很多問題最終都可以轉(zhuǎn)化為圖的路徑搜索問

2、題。常見的路徑搜索算法有：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*算

3、法中的距離估算值與實(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ì)使得問題的處理具有一定的局限性，即便問題的處理具有多樣性，但是還是需

4、要根據(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有路徑相通的

5、頂點(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ā)的所有路徑，即訪問完所有從

6、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；visitedv0=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)值）輸

7、出路徑及總代價(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)值

8、為：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-

9、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.0v0>v1>v3>v5總代價(jià)為：52.0v0>v1>v4>v5總代價(jià)為；55.0v0>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è)人