狀態(tài)離散的確定性多階段群體滿(mǎn)意決策最優(yōu)的算法

張艷娟

（三峽大學(xué)理學(xué)院，湖北宜昌 443002）

群體決策問(wèn)題是一類(lèi)受到普遍重視和研究的決策科學(xué)問(wèn)題，它廣泛應(yīng)用于社會(huì)政治經(jīng)濟(jì)，生活各個(gè)領(lǐng)域.群體決策由兩個(gè)以上的決策者所構(gòu)成，是決策群體對(duì)一集備選方案進(jìn)行評(píng)價(jià)排序后選擇某方案使得群體效用最大的決策活動(dòng).有關(guān)群體決策問(wèn)題的研究已經(jīng)取得了豐富的研究成果.文獻(xiàn)［1］研究了一類(lèi)動(dòng)態(tài)多指標(biāo)決策問(wèn)題，應(yīng)用數(shù)學(xué)理論知識(shí)建立多目標(biāo)多階段動(dòng)態(tài)決策模型.通過(guò)引入一種效用函數(shù)，并據(jù)此將具有不同量綱、不同物理含義、不同指標(biāo)類(lèi)型的決策矩陣歸一化轉(zhuǎn)換到相應(yīng)的效用矩陣，提高了分辨精度，物理概念更加清晰.文獻(xiàn)［2］針對(duì)狀態(tài)離散的確定性多階段群體決策問(wèn)題，建立多階段群體決策模型，通過(guò)引入偏好關(guān)系，得到了各階段的子過(guò)程群體滿(mǎn)意策略以及全過(guò)程群體滿(mǎn)意策略，提出了一種多階段群體決策問(wèn)題的逆向遞推算法.文獻(xiàn)［3］討論了多階段群體滿(mǎn)意決策問(wèn)題，提出了一種多階段群體滿(mǎn)意策略問(wèn)題的最優(yōu)算法，該算法的主要思想是應(yīng)用圖論知識(shí)將此問(wèn)題轉(zhuǎn)化為在多部有向賦權(quán)圖中求一條權(quán)和最長(zhǎng)的路.這些文章為群體決策問(wèn)題的研究提供了很多有用的方法和理論.

本文將針對(duì)狀態(tài)離散的確定性多階段群體決策問(wèn)題，利用圖論的知識(shí)，將群體決策問(wèn)題的多階段與圖的邊集、點(diǎn)集對(duì)應(yīng)起來(lái)，建立群體決策問(wèn)題的模型一多部賦權(quán)圖，定義權(quán)w 為決策者對(duì)決策的評(píng)價(jià)值或效用值，路P 的長(zhǎng)度為P 中各邊的權(quán)和，將多階段群體滿(mǎn)意決策問(wèn)題轉(zhuǎn)換成在多部賦權(quán)圖中找一條最長(zhǎng)路徑的問(wèn)題.依據(jù)一條最長(zhǎng)路徑上的任意兩個(gè)不相鄰的頂點(diǎn)之間是不可以被由不在這一條路徑上的兩個(gè)頂點(diǎn)組成的更長(zhǎng)的路所替代這一事實(shí)，提出了一種多部賦權(quán)圖最長(zhǎng)路徑的算法.

1 多階段群體決策模型

定義1 設(shè)G＝（V（G），E（G），w（G））一個(gè)賦權(quán)圖，其中V（G）是頂點(diǎn)集，E（G）是邊集，w（G）是權(quán)集，如果G 滿(mǎn)足以下條件：

對(duì)于在連通圖中尋找最長(zhǎng)路徑的問(wèn)題，國(guó)內(nèi)外許多學(xué)者已經(jīng)做了比較多的研究.文獻(xiàn)［4］介紹了一種比較簡(jiǎn)單通用的尋找近似最長(zhǎng)路徑的算法.文獻(xiàn)［5］討論了現(xiàn)有求解最長(zhǎng)路徑問(wèn)題的幾種算法，包括近似算法、參數(shù)化算法和特殊圖的多項(xiàng)式時(shí)間算法，著重分析和比較了參數(shù)化算法中利用著色、分治和代數(shù)法研究κ－Path問(wèn)題的最新結(jié)果，并提出了該問(wèn)題的進(jìn)一步研究方向.文獻(xiàn)［6］通過(guò)定義一種有向圖，提出了一種有向圖從始點(diǎn)到其它任一頂點(diǎn)之間最長(zhǎng)路的算法.文獻(xiàn)［7］研究了無(wú)向連通圖指定起點(diǎn)和終點(diǎn)的條件下，通過(guò)對(duì)深度優(yōu)先生成樹(shù)的某條路徑不斷地進(jìn)行頂點(diǎn)插入的策略來(lái)獲得一條近似最長(zhǎng)路徑.本文在總結(jié)和借鑒已有算法的基礎(chǔ)上，依據(jù)一條最長(zhǎng)路徑上的任意兩個(gè)不相鄰的頂點(diǎn)之間不可以被由不在這一條路徑上的兩個(gè)頂點(diǎn)組成的更長(zhǎng)路所替代這一事實(shí)，提出了一種多部賦權(quán)圖中尋求最長(zhǎng)路徑的算法.

2 算 法

設(shè)P＝x0x1…xN是多部賦權(quán)連通圖G 中連接點(diǎn)x0和xN的路，其中x0∈V0，x1∈V1，…，xN∈VN.設(shè)G1，G2，…，（Gm）（m≥0）為由不在路P 上的頂點(diǎn)組成的圖G 的連通子圖.

定義3 路P 中的任意兩個(gè)不相鄰頂點(diǎn)xk和xt同時(shí)分別與任意一個(gè)連通子圖Gl中的頂點(diǎn)xp和xq（xp和xq為Gl中的點(diǎn)）相連接.在P 中頂點(diǎn)xk和xl之間路P1的長(zhǎng)度為L(zhǎng)（P1），在Gl中頂點(diǎn)xp和xq之間最長(zhǎng)路P2的長(zhǎng)度為L(zhǎng)（P2），如果L（P2）＋w（xk，xp）＋w（xt＋xq）＜L（P1），即在路P 中任意不相鄰兩個(gè)頂點(diǎn)之間的路不可被由不在路P 上頂點(diǎn)組成的更長(zhǎng)路所代替，則稱(chēng)滿(mǎn)足這個(gè)條件的路為不可替代路.

定理1 如果路P 上的任意兩個(gè)不相鄰的頂點(diǎn)之間的路均為不可替代路，則路P 就是最長(zhǎng)路徑.

顯然，如果路P 不滿(mǎn)足上面的性質(zhì)，則路P 不是最長(zhǎng)路徑.對(duì)于任意一條路P＝x0x1…xN，設(shè)點(diǎn)xk和xt是路P 上任意兩個(gè)不相鄰的頂點(diǎn)，連接點(diǎn)xk和xl之間路P1的長(zhǎng)度為L(zhǎng)（P1）.Gl為某個(gè)由不在路P 上的頂點(diǎn)所構(gòu)成的圖G 的極大連通子圖，設(shè)xp和xq為Gl中的點(diǎn)，且邊（xk，xp）∈E（G），（xt，xq）∈E（G）.Gl中頂點(diǎn)xp和xq之間最長(zhǎng)路P2的長(zhǎng)度為L(zhǎng)（P2），如果L（P2）＋w（xk，xp）＋w（xt，xq）＞L（P1），則在路P上用頂點(diǎn)xp和xq之間的路徑替代頂點(diǎn)xk＋1和xt－1之間的路徑.因此在多部有向賦權(quán)圖中尋找最長(zhǎng)路徑問(wèn)題的關(guān)鍵是要尋找不可替代路.

步驟4：若可被替代的點(diǎn)的列表為空，轉(zhuǎn)步驟8，否則取出可被替代的點(diǎn)的列表中的點(diǎn)，完成一次操作以后，如果可被替代的點(diǎn)的列表中的點(diǎn)沒(méi)有被替代，將其保留.否則將其刪除.

步驟5：若可替代的點(diǎn)列表為空，轉(zhuǎn)步驟8，否則遍歷可以替代的點(diǎn)的列表，查找可替代點(diǎn)列表中的點(diǎn)，若找到可替代點(diǎn)列表中的點(diǎn)，執(zhí)行步驟6，否則轉(zhuǎn)步驟4.

步驟6：用可替代的點(diǎn)的列表中的點(diǎn)替代可被替代的點(diǎn)的列表中的點(diǎn)，可以得到一條新的路徑，如果新路徑的長(zhǎng)度大于原來(lái)路徑的長(zhǎng)度，則可被替代的點(diǎn)的列表中的點(diǎn)將會(huì)被可替代的點(diǎn)的列表中的點(diǎn)所替代，執(zhí)行步驟7.否則可被替代的點(diǎn)的列表中的點(diǎn)將不會(huì)被替代，轉(zhuǎn)步驟4.

步驟7：將替代到原來(lái)選取的路徑中的點(diǎn)加入到可被替代的點(diǎn)的列表中，返回步驟4，調(diào)整可被替代的點(diǎn)的列表.

例：在圖1中，找一條從頂點(diǎn)x0到x4的長(zhǎng)度最長(zhǎng)的路徑.

圖1 例圖

3 算法應(yīng)用

在群體決策問(wèn)題中，經(jīng)常要對(duì)狀態(tài)離散的確定性多階段決策的群體滿(mǎn)意策略做出判斷，下面的這個(gè)例子就是實(shí)際生活中會(huì)經(jīng)常遇到的.設(shè)由5個(gè)決策者構(gòu)成的決策群體共同參與一個(gè)包含4個(gè)決策階段的狀態(tài)離散的確定性動(dòng)態(tài)決策過(guò)程，多個(gè)決策者的權(quán)重在各個(gè)決策狀態(tài)下是不變的，即決策者的權(quán)重向量為（0.1，0.3，0.3，0.1，0.2），各階段的狀態(tài)轉(zhuǎn)移過(guò)程以及決策者對(duì)方案的評(píng)價(jià)值如圖2所示，求全過(guò)程的群體滿(mǎn)意策略.為了便于表述，將其策略用所經(jīng)過(guò)的多個(gè)狀態(tài)點(diǎn)來(lái)表示.

圖2 狀態(tài)離散的確定性多階段決策的群體問(wèn)題的示例圖

步驟1：建立狀態(tài)離散的確定性多階段決策的群體滿(mǎn)意決策問(wèn)題的模型，利用在多階段群體決策模型中計(jì)算權(quán)的方法詳細(xì)計(jì)算出圖2中每條邊的權(quán).比如w（x0，x）＝3×0.1＋3×0.3＋4×0.3＋7×0.1＋9×0.2＝4.9，依次計(jì)算出所有的權(quán).此時(shí)圖2就可以轉(zhuǎn)化成多部賦權(quán)圖，如圖3所示.

圖3 多部賦權(quán)圖

4 結(jié) 語(yǔ)

近幾年來(lái)，經(jīng)過(guò)研究者們的努力，最長(zhǎng)路徑問(wèn)題的研究取得了重大的進(jìn)展，大量的文獻(xiàn)都在研究該問(wèn)題的參數(shù)化算法.本文針對(duì)生活中常見(jiàn)的狀態(tài)離散的確定性多階段群體滿(mǎn)意策略問(wèn)題，應(yīng)用圖論的知識(shí)建立了多階段群體決策問(wèn)題的模型，并在此基礎(chǔ)上給出了算法，但是，由于該算法采用的是點(diǎn)逐步被替代的方式，因此計(jì)算量較大，有待進(jìn)一步改善.

［1］ 戴文站，鄒立華，王建章.一種基于獎(jiǎng)優(yōu)罰劣原則的多階段多目標(biāo)決策模型［J］.系統(tǒng)工程理論與實(shí)踐，2000，6（1）：32－36.

［2］ 彭 怡，胡 楊.狀態(tài)離散的確定性多階段群決策的滿(mǎn)意策略性［J］.運(yùn)籌學(xué)學(xué)報(bào)案，2006，10（1）：80－86.

［3］ 鄭文婷，劉紅美，余 真.多階段群體滿(mǎn)意決策最優(yōu)算法［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2008，38（16）：44－48.

［4］ Karger D，Motwani R，Ramkmmar G D.On Approximating the Longest Path in a Graph［J］.Algorithmica，1997，18（1）：82－98.

［5］ 王建新，楊志彪，陳建二.最長(zhǎng)路徑研究問(wèn)題進(jìn)展［J］.計(jì)算機(jī)科學(xué)，2009，36（12）：1－4，31.

［6］ 屈芝蓮.一種有向圖最長(zhǎng)路的算法、靈敏度分析及其應(yīng)用［J］.科學(xué)技術(shù)與工程，2011，11（16）：3746－3449.

［7］ 孫承山，何援軍，蔡鴻明.無(wú)向連通圖求約束條件下近似最長(zhǎng)路算法［J］.計(jì)算機(jī)仿真，2004，21（7）：45－47，81.