求解模糊最短路問題的動態(tài)規(guī)劃法

李 紅 霞

(隴東學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 慶陽 745000)

求解模糊最短路問題的動態(tài)規(guī)劃法

李 紅 霞

(隴東學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 慶陽 745000)

提出動態(tài)規(guī)劃法求解模糊最短路問題。對于給定起點(diǎn)和終點(diǎn)的有向模糊圖，可以從終點(diǎn)出發(fā)，逆向追溯分階段探尋最短路，同時(shí)刪去非最短路。而對于每個(gè)階段的最短路問題，給出了求解最短路長度和最短路的方法，即利用模糊最小算子求最短路長度，并根據(jù)每條路與最短路長度的貼近度來確定最短路。最后通過例子說明此種方法的可行性和有效性。

模糊數(shù)；最短路；動態(tài)規(guī)劃

Abstract： The dynamic programming method for solving fuzzy shortest path problem is given.For the fuzzy graph with a given starting point and end point,we can reversely explore the most short circuit from the end point in stages,and delete non shortest path.For the shortest path problem in each stage,a method to calculate the shortest path length and the shortest path is presented to solve the shortest path length by using the fuzzy minimum operator and to determine the shortest path according to the closeness of each road with the shortest length.Finally the validity and feasibility of this method is illustrated through an example.

Keywords： fuzzy number;the shortest path;dynamic programming

最短路問題是經(jīng)典的網(wǎng)絡(luò)優(yōu)化問題。在經(jīng)典網(wǎng)絡(luò)圖中,兩點(diǎn)之間的邊不僅表示距離,而且還表示時(shí)間,運(yùn)費(fèi)等,而這些涉及到路況、庫存等許多因素的量一般都是不確定的,因而用模糊數(shù)表示不失為一種有效方法。對于由有限個(gè)頂點(diǎn)和有向邊構(gòu)成的網(wǎng)絡(luò),假定每兩個(gè)點(diǎn)之間都存在有向邊,邊的權(quán)重都表示為模糊數(shù),于是路的長度即為組成路的邊權(quán)之和,找到長度最短的路即為模糊最短路問題。Dubois和Prade[1]首先進(jìn)行模糊最短路問題的研究,其算法是推廣了經(jīng)典的Floyd和Ford-Moore-Bellman算法。Okada和Gen[2,3]等推廣了Kjikstra算法。Takaoka[4]通過信息共享改進(jìn)了一類特殊圖最短路問題的計(jì)算復(fù)雜度。Dou[5]給出了最優(yōu),最劣的模糊理想路,比較所有路與模糊理想路的相似度,從而得到最優(yōu)路。Cheng[6]給出了約束條件的最短路問題,其邊為獨(dú)立的正態(tài)分布,并提出了分支定界算法。關(guān)于最短路問題的研究可參閱文獻(xiàn)[7-10]。然而我們考慮到,在尋找最優(yōu)，最劣路的過程中，如果從頂點(diǎn)到終點(diǎn)的所有路中去考察,計(jì)算量會很大，同時(shí)還可能遺漏掉某些路,因此這個(gè)過程異常復(fù)雜。。由于最短路的子路應(yīng)該是最短路，如果分階段進(jìn)行并且刪去子路的非優(yōu)路將會減少計(jì)算量。因此本文給出了基于模糊理想路的動態(tài)規(guī)劃方法，從目標(biāo)點(diǎn)出發(fā)逆向搜索最短路，同時(shí)刪去非最優(yōu)路，而對于每個(gè)階段的最短路問題，給出了求解最短路長度和最短路的方法，即利用模糊最小算子求最短路長度，并根據(jù)每條路與最短路長度的貼近度來確定最短路。最后通過例子說明此種方法的可行性和有效性。

1 基礎(chǔ)知識

其中α,β分別為左右擴(kuò)張。

下面給出模糊數(shù)的加法運(yùn)算和序關(guān)系:

此定義較不適合計(jì)算，我們給出下面的等價(jià)定義1.6，利用模糊數(shù)的α水平集表示，更加符合人們的直覺。

2 模糊圖及模糊最短路

在有向圖中，給定起點(diǎn)和終點(diǎn)的所有路有n條，其模糊長度為Li(i=1,2,…,n)，我們給出求最短路長度的步驟如下：

第一步：置L=L1，令i=2。

第二步：根據(jù)公式計(jì)算L=min(L,Li)。

第三步：i=i+1，重復(fù)第二步到第三步，直到i=n+1。

上述過程可以用下面例子來說明：

假定有四條路，其對應(yīng)的模糊長度用梯形模糊數(shù)表示為：L1=(30,40,10,5),L2=(25,45,6,8),L3=(25,33,3,2),L4=(33,38,6,5)。

第一步：置L=L1=(30,40,10,5),令i=2。

第二步：計(jì)算L=min(L,Li)=min(L,L2)=(25,40,6,8)。

第三步：i=i+1，重復(fù)第二步到第三步，直到i=5。由此我們得到L=(25,33,6,2)。

為了求出模糊最短路,我們求每條路與最短路長度的貼近度，與最短路長度最貼近的即為最短路。關(guān)于模糊貼近度的研究也比較多,其定義如下：

3 用動態(tài)規(guī)劃法求模糊最短路

對于有始點(diǎn)和終點(diǎn)的有向模糊圖，我們可以從終點(diǎn)出發(fā)，逆向溯源，分階段尋找最短路，刪掉顯然的非最短路，同時(shí)可以簡化運(yùn)算量。對于有向模糊圖，根據(jù)模糊路的長度的計(jì)算，模糊最短路有下面的定理:

定理3.1 設(shè)G(V,A)為有向模糊圖,路pst={s,(s,v1),v1,…,vi-1,(vi-1,vi),vi,…，(vn,t),t}為頂點(diǎn)s到t的路，則pst為最短路當(dāng)且僅當(dāng)從頂點(diǎn)s到任意中間點(diǎn)vi的子路psvi為s到vi的最短路。

設(shè)有向圖G(V,A)由有限個(gè)頂點(diǎn)V={1,2,…,n}和m條有向邊A?V×V構(gòu)成,對于從始點(diǎn)1到終點(diǎn)n的模糊最短路問題，我們給出如下動態(tài)規(guī)劃法算法：

第三步：對每個(gè)頂點(diǎn)i,使得(i,j)∈A，執(zhí)行下面(1)到(3)。

第四步：找出從頂點(diǎn)1到n的最短路。

下面我們借用文[12]中的例子來介紹動態(tài)規(guī)劃法。

圖1

圖1中兩點(diǎn)i和j之間的有向弧長度分別用梯形模糊數(shù)lij來表示，l12=(20,20,10,10),l13=(62,65,10,5),l23=(38,40,3,5),l25=(55,60,3,5),l34=(13,17,3,3),l35=(9,9,1,1),l46=(75,85,5,12),l56=(70,80,20,20),我們要利用動態(tài)規(guī)劃法計(jì)算從頂點(diǎn)1到6的最短路。

這可被看作三階段動態(tài)規(guī)劃問題。第一階段從頂點(diǎn)5開始，因?yàn)閺捻旤c(diǎn)5到6只有一條路，其模糊長度為(70,80,20,20),則路5-6為輸入點(diǎn)為5的最短路。同時(shí)，從頂點(diǎn)4到6只有唯一的路4-6，其模糊長度為(75,85,5,12),也是輸入點(diǎn)為4的最短路。

表2 第一階段

第二階段從頂點(diǎn)3開始，有兩條路3-4-6和3-5-6，其模糊長度分別為(88,102,8,15),(79,89,21,21),根據(jù)第二節(jié)的算法，3-5-6為從頂點(diǎn)3輸入的模糊最短路，刪去3-4-6。對于頂點(diǎn)2，有2-3與2-5兩條路，通過計(jì)算，2-3-5-6為頂點(diǎn)2輸入的模糊最短路，刪去2-5-6。

第三階段從頂點(diǎn)1開始，類似地，得到1-2-3-5-6為模糊最短路，其長度為(137,149，34,36)。這個(gè)結(jié)果與文[12]中的應(yīng)用標(biāo)簽法計(jì)算的結(jié)果相同,由此前面的動態(tài)規(guī)劃法計(jì)算模糊最短路問題不失為一種有效的算法。

第二階段(刪去3-4，2-5)

第三階段(刪去1-3)

4 小結(jié)

模糊最短路問題的廣泛應(yīng)用已引起許多學(xué)者的關(guān)注。對于決策者來說，模糊最短路長度和相應(yīng)的模糊最短路是重要的信息。這篇文章試圖找到模糊最短路長度和模糊最短路。首先給出了求解模糊最短路長度和模糊最短路的方法，對于n條路，利用模糊最小和貼近度找到模糊最短路長度和模糊最短路。其次，在給定始點(diǎn)和終點(diǎn)的模糊有向圖中，從終點(diǎn)出發(fā)，我們給出了逆向追溯的動態(tài)規(guī)劃方法，在非最優(yōu)路的刪除過程中，計(jì)算量將會減少。因而，對于較復(fù)雜的網(wǎng)絡(luò)圖來說，所提出的方法不失為一種有效方法。

[1]D.Dubois,H.Prade.Fuzzy Sets and Systems:Theory and Applications[M].New York:Academic Press,1980,144(3):370-374.

[2]S.Okada,M.Gen.Order relation between intervals and its applications to shortest path problem[C],in:Proc.15th Annu.Conf.on Computers and Industrial Engineering,Vol.25,1993.

[3]S.Okada,M.Gen.Fuzzy shortest path problem[C],in: Proc.16th Ann.Conf.on Computers and Industrial Engineering,Vol.27,1994.

[4]T.Takaoka.Sharing information for the all pairs shortest path problem[J].Theoretical Computer Science,2014(520):43-50.

[5]Y.L.Dou,L.C.Zhu,H.S.Wang.Solving the fuzzy shortest path problem using multi-criteria decision method based on vague similarity measure[J].Applied soft computing,2012(12):1621-1631.

[6]J.Q.Cheng,A.Lisser.Maximum probability shortest path problem[J].Discrete Applied Mathematics,2015(192):40-48.

[7]D.Cantone,S.Faro.Fast shortest paths algorithms in the presence of few destinations of negative weight arcs[J].Journal of dscrete algorithms,2014(24):12-25.

[8]楊曉凌.最短路及最小支撐樹的靈敏度分析[D].長沙：國防科學(xué)技術(shù)大學(xué)，2007:5-8.

[9]Shinkoh Okada.Fuzzy shortest path problems incorporating interactivity among paths[J],Fuzzy sets and Systems,2004(142),335-357.

[10]F.Hernandes,M.T.Lamata,J.L.Verdegay,A.Yanakami.The shortest path problem on networks with fuzzy parameters[J].Fuzzy Sets and Systems,2007(158):1561-1570.

[11]吳從炘,馬明.模糊分析學(xué)基礎(chǔ)[M].北京：國防工業(yè)出版社,1991:56-60.

[12]S.Okada,T.Soper.A shortest path problem on a network with fuzzy arc lengths[J].Fuzzy Sests and Systems,2000(109):129-140.

【責(zé)任編輯朱世廣】

TheDynamicProgrammingMethodforSolvingtheFuzzyShortestPathProblem

LI Hong-xia

(CollegeofMathematicsandStatistics,LongDongUniversity,Qingyang745000,Gansu)

O159

A

1674-1730(2017)05-0001-04

2016-11-12

甘肅省高等學(xué)?？蒲许?xiàng)目《模糊圖在網(wǎng)絡(luò)優(yōu)化中的應(yīng)用研究》(2015A-144)；2016年度甘肅省“十三五”教育科學(xué)規(guī)劃課題《地方高校師范專業(yè)教師職業(yè)技能嵌入式培養(yǎng)的應(yīng)用研究》(GS[2016]GHB1255)

李紅霞(1970—)，女，甘肅慶陽人，副教授，碩士，主要從事模糊分析與模糊圖的研究。