面向多最優(yōu)解組合優(yōu)化問題的決策求解算法

胡振震，袁唯淋，羅俊仁，鄒明我，陳 璟

(國防科技大學(xué) 智能科學(xué)學(xué)院, 湖南 長沙 410073)

最優(yōu)化是應(yīng)用很廣的一個(gè)數(shù)學(xué)分支，很多問題都可以看成是某種形式的最優(yōu)化問題。最優(yōu)化問題根據(jù)變量是否連續(xù)分為兩類，其中離散變量的優(yōu)化問題稱為組合優(yōu)化問題。組合優(yōu)化通常是在一定的約束條件下，根據(jù)目標(biāo)函數(shù)要求，從一個(gè)有限的集合里尋找一個(gè)最優(yōu)的對象，如一個(gè)數(shù)、一個(gè)集合，或者一個(gè)排列[1-3]。在一定約束條件下求目標(biāo)函數(shù)的極值問題也稱為數(shù)學(xué)規(guī)劃，因此組合優(yōu)化問題也是規(guī)劃問題。組合優(yōu)化的很多理論也基于規(guī)劃，如線性規(guī)劃、動(dòng)態(tài)規(guī)劃、整數(shù)規(guī)劃等[4-6]。

組合優(yōu)化的概念源于計(jì)算科學(xué)，與運(yùn)籌、決策、管理、經(jīng)濟(jì)等學(xué)科緊密相關(guān)，科學(xué)研究和工程應(yīng)用十分廣泛。當(dāng)前組合優(yōu)化已經(jīng)發(fā)展成一個(gè)涵蓋許多規(guī)劃問題的學(xué)科，比如：旅行商問題、背包問題、劃分問題、指派問題、最短路徑問題、網(wǎng)絡(luò)最大流問題、最小費(fèi)用流問題、最小頂點(diǎn)覆蓋問題、最小支配集問題、最小生成樹問題、斯坦納最小樹問題等。盡管組合優(yōu)化研究已經(jīng)取得了豐碩的成果，但因?yàn)楝F(xiàn)實(shí)問題的復(fù)雜性，仍然還有很多問題需要研究：一是針對新應(yīng)用問題的模型和方法研究，比如線性約束下的平行機(jī)排序問題[7]、“新高改”高中“走班”排課問題[8]、連續(xù)背包問題[9]、矩形背包問題[10]等；二是針對已有問題的新方法研究，比如尋路問題的規(guī)范排序 A 星算法[11]、圖匹配問題的深度強(qiáng)化學(xué)習(xí)方法[12]、旅行商問題的圖卷積網(wǎng)絡(luò)方法[13]、背包問題的強(qiáng)化學(xué)習(xí)方法[14]、二次背包問題的剪枝算法[15]等。

本文是針對一類新問題開展研究?，F(xiàn)實(shí)中很多組合優(yōu)化問題只有一個(gè)最優(yōu)解，只要找到它就可完成求解，但也存在一些特殊的問題具有多個(gè)最優(yōu)解，而且決策者必須獲取全部最優(yōu)解才能據(jù)此適時(shí)做出決策，比如財(cái)務(wù)預(yù)算要在預(yù)算總值固定情況下得到所有的可能分配方案。這類問題具有兩個(gè)顯著特征：一是最優(yōu)解是多個(gè)且需全部求出；二是目標(biāo)物品或數(shù)值的總和是固定的。兩個(gè)特征使該類問題有別于單最優(yōu)解問題，可稱之為多最優(yōu)解組合優(yōu)化問題。目前專門針對多最優(yōu)解組合優(yōu)化問題的研究少有報(bào)道，本文將其作為研究對象并以固定總和實(shí)數(shù)子集問題和費(fèi)城中國餐館購買雞翅問題為例開展建模和分析。

1 相關(guān)工作

組合優(yōu)化是離散變量的最優(yōu)化問題，往往可以寫成線性規(guī)劃的形式。一個(gè)求最小目標(biāo)的問題可用如下數(shù)學(xué)模型描述：

(1)

其中，x為決策變量，D表示問題或者決策變量的定義域(有限個(gè)值組成的集合)，F(xiàn)為目標(biāo)函數(shù)，G(x)≤0為約束條件。當(dāng)求解的變量是整數(shù)時(shí)，轉(zhuǎn)變?yōu)檎麛?shù)規(guī)劃問題。

線性規(guī)劃問題常用的求解算法主要是單純形法及其相關(guān)擴(kuò)展算法。整數(shù)規(guī)劃中的兩種主要算法——分枝限界法和割平面法與線性規(guī)劃的算法具有密切聯(lián)系[5]。對于變量取值是0或1的整數(shù)規(guī)劃問題(稱為0-1整數(shù)規(guī)劃問題)，有兩種更為直觀的求解方法：一是枚舉法，即枚舉所有變量等于0或1的所有組合，然后判斷所有組合是否滿足約束條件并使目標(biāo)函數(shù)最優(yōu); 第二種是隱枚舉法，同樣是枚舉所有的組合，但引入一些過濾條件，過濾掉局部不滿足約束或目標(biāo)函數(shù)值非優(yōu)的組合，從而減少計(jì)算量[16]。0-1整數(shù)規(guī)劃問題，也可以看作是多階段決策問題，從這一角度建模可以運(yùn)用動(dòng)態(tài)規(guī)劃的方法求解。動(dòng)態(tài)規(guī)劃不是一種特殊的算法，而是一種考察問題的途徑和思路。針對不同的問題，往往需要建立針對性的模型進(jìn)行求解[5,17]。

除了確定性算法外，組合優(yōu)化問題還可采用啟發(fā)式算法。無論是人為的構(gòu)造啟發(fā)式，還是基于一些最優(yōu)化方法(如禁忌搜索、模擬退火、遺傳算法等)設(shè)計(jì)啟發(fā)式，主要目的是解決大規(guī)模問題中確定性算法無法在有限時(shí)間內(nèi)求得精確解的問題，即利用啟發(fā)式算法在有限時(shí)間內(nèi)獲得可接受的解(如近似解)。啟發(fā)式往往依賴于問題的性質(zhì)，需要針對不同類型的問題修改，所以通常情況下啟發(fā)式設(shè)計(jì)并不容易。近年來深度強(qiáng)化學(xué)習(xí)被發(fā)現(xiàn)具有一定的潛力用來求解組合優(yōu)化問題，可以通過學(xué)習(xí)來獲得好的啟發(fā)式[18-22]。但這些方法主要是針對單最優(yōu)問題。從需要獲得多最優(yōu)解的角度看，上述方法中枚舉法、隱枚舉法、基于動(dòng)態(tài)規(guī)劃原理的算法最具有獲得問題的全部解的潛力，所以本文的研究主要集中于此。

2 問題定義與求解

2.1 問題形式化描述

多最優(yōu)解組合優(yōu)化問題可以定義為：從一個(gè)有限集合中尋找多個(gè)對象、數(shù)、集合或排列，使目標(biāo)達(dá)到最優(yōu)。它要求將多個(gè)最優(yōu)解全部求出，且約束為等式。在數(shù)學(xué)形式上可以表示為：

(2)

固定總和實(shí)數(shù)子集問題和費(fèi)城中國餐館購買雞翅問題是兩個(gè)典型示例。固定總和實(shí)數(shù)子集問題源于實(shí)際預(yù)算問題：數(shù)據(jù)集X包含一系列數(shù)據(jù){8.05, 6.98, 6.19, 5, 22.96, 4.71, 4.74, 4.25, 6.34, 2.77, 7.31, 3.59, 18.28, 19.55}，希望從中找到多組數(shù)(多個(gè)子集)使其累加總數(shù)為84.03。如果把問題的求解變量看作是取值為{0,1}的變量，即把問題看作是在數(shù)據(jù)集X中對每個(gè)數(shù)據(jù)做挑選的決策，選中則變量取為1，不選中則取為0，如式(3)所示：

(3)

購買雞翅問題源于一家位于美國費(fèi)城的中餐館，其雞翅菜單與眾不同，不標(biāo)注雞翅單價(jià)而是標(biāo)注不同數(shù)量雞翅組合的價(jià)格，如表1所示。問題是求解購買指定數(shù)量雞翅時(shí)的全部最優(yōu)惠購買方案。類似地，可以把問題建模為0-1整數(shù)規(guī)劃問題(0-1決策問題)，如式(4)所示：

Find allx=arg(min(vx))

(4)

其中，b為要購買的雞翅總數(shù)。

表1 雞翅菜單

嚴(yán)格地說，固定總和實(shí)數(shù)子集問題是一個(gè)多最優(yōu)解的約束滿足問題，但也可以轉(zhuǎn)換為最優(yōu)化問題；購買雞翅問題則是一個(gè)標(biāo)準(zhǔn)的優(yōu)化問題，要求購買固定數(shù)量雞翅的同時(shí)使得花費(fèi)的代價(jià)最小。

2.2 枚舉和隱枚舉法

枚舉和隱枚舉法是多最優(yōu)解組合優(yōu)化問題的直觀解法。以固定總和實(shí)數(shù)子集問題為例，引入一對相反的不等式，式(3)的約束問題就能轉(zhuǎn)換為一個(gè)優(yōu)化問題，如式(5)所示。這是典型的整數(shù)規(guī)劃形式，可以理解為n=14個(gè)變量(階段)的0-1整數(shù)規(guī)劃(決策)問題。

(5)

首先考慮枚舉法，由于數(shù)據(jù)集中總共包含14個(gè)數(shù)據(jù)，對應(yīng)于14個(gè)變量，因此任意數(shù)量(1～14)的數(shù)據(jù)都可以進(jìn)行組合，枚舉組合總數(shù)為214-1。枚舉過程可以利用字典序循環(huán)實(shí)現(xiàn)。由于目標(biāo)函數(shù)是所選數(shù)據(jù)的和，所以每個(gè)組合都需要累加計(jì)算，運(yùn)算量接近14乘以枚舉組合數(shù)。因此，對于數(shù)據(jù)集規(guī)模為n的問題，枚舉方法的時(shí)間復(fù)雜度約為O(n2n)；枚舉過程不額外增加存儲(chǔ)空間，所以空間復(fù)雜度為O(n)。顯然時(shí)間復(fù)雜度的指數(shù)級增長源自枚舉組合數(shù)隨數(shù)據(jù)集規(guī)模增大產(chǎn)生的指數(shù)級增長。

隱枚舉法思想有些類似于分支定界法，基本思路是：當(dāng)檢測到某些分支組合不符合約束要求，則避免進(jìn)一步往下分支，從而減少總的計(jì)算量。隱枚舉過程可以理解為搜索樹的擴(kuò)展，數(shù)據(jù)集中的每一個(gè)數(shù)作為一層的決策，以選擇和不選擇兩種情況擴(kuò)展分支，因此搜索樹是一個(gè)不斷擴(kuò)展的二叉樹，如圖1所示。圖中“×”表示當(dāng)前節(jié)點(diǎn)已經(jīng)不滿足約束條件，因此可以剪掉。如果不考慮剪枝，那么隱枚舉法的決策樹從根節(jié)點(diǎn)到第14層的葉子節(jié)點(diǎn)是完整的，葉子節(jié)點(diǎn)數(shù)量為214，因此時(shí)間復(fù)雜度為O(n2n)，與枚舉法相同。若考慮剪枝則可以使其計(jì)算復(fù)雜度與枚舉法相比有明顯的下降，但下降的程度與問題的求解特征和方式相關(guān)，也與剪枝約束條件相關(guān)，不是一個(gè)固定值。

2.3 基于動(dòng)態(tài)規(guī)劃的方法

若將問題看作多階段決策問題，可以自然地運(yùn)用動(dòng)態(tài)規(guī)劃原理來建模求解。對于一個(gè)n階段的決策問題sk+1=f(sk,xk),k=1,…,n，其中sk是第k階段的系統(tǒng)狀態(tài)，xk是第k階段的決策變量，優(yōu)化問題可以看作求決策向量x1,x2,…,xn使得目標(biāo)函數(shù)(指標(biāo))達(dá)到極值：

(6)

式中，Vk為各階段的目標(biāo)函數(shù)。 根據(jù)動(dòng)態(tài)規(guī)劃的最優(yōu)性定理，可以將求指標(biāo)極值問題轉(zhuǎn)換為分階段的遞推過程：

(7)

或者：

(8)

式(7)和式(8)分別稱為逆序和順序的動(dòng)態(tài)規(guī)劃方程[4]。由此多階段的決策問題可以分解為在各個(gè)階段的狀態(tài)和目標(biāo)函數(shù)遞推過程中做出最優(yōu)的決策。

為解決固定總和實(shí)數(shù)子集問題，首先用一個(gè)簡單的示例來考察動(dòng)態(tài)規(guī)劃的求解結(jié)構(gòu)。問題是從數(shù)據(jù)集[1,2,3,4]中選擇數(shù)據(jù)子集使其和為7。這是一個(gè)完全類似的問題，可表示為整數(shù)規(guī)劃的形式，并轉(zhuǎn)換為多階段決策問題：

(9)

先考慮順序遞推的方法，定義狀態(tài)為決策(選擇該階段決策變量數(shù)據(jù))前的數(shù)據(jù)總和。實(shí)際狀態(tài)的轉(zhuǎn)移和指標(biāo)的遞推為：

(10)

根據(jù)各階段的狀態(tài)轉(zhuǎn)移式(10)可知，求決策變量需要從最后一個(gè)階段開始，若f4的所有可能值已知，則使f5最優(yōu)可以將x4求出，進(jìn)而知道f4的最優(yōu)值，進(jìn)一步將x3求出來，不斷遞推直到求出所有階段的決策變量。對于這樣一個(gè)求解過程，可以考慮兩種結(jié)構(gòu)：一種是循環(huán)，一種是遞歸。循環(huán)的結(jié)構(gòu)是先將k-1階段的所有狀態(tài)s和指標(biāo)f求出，再求k階段的狀態(tài)和指標(biāo)，直到最后一個(gè)階段，然后再求解決策變量。通俗講就是向前建表(遞推狀態(tài)和指標(biāo))，向后查表(求決策變量)。而遞歸的結(jié)構(gòu)是以遞歸的方式從最后一個(gè)階段的狀態(tài)開始遞歸，當(dāng)存在前一階段的未知狀態(tài)和指標(biāo)時(shí)，則遞歸地進(jìn)入前一個(gè)階段的計(jì)算中，直至第一個(gè)階段的狀態(tài)和指標(biāo)計(jì)算完成，這樣等價(jià)于完成了建表的過程，接著通過查表可以求解決策變量。

圖2給出了順序遞推形式下利用循環(huán)方法構(gòu)造的求解結(jié)構(gòu)。圖中的曲線表示遞推的過程。從狀態(tài)s1和指標(biāo)f1開始遞推到s5和f5，根據(jù)式(10)可知f5=7為最優(yōu)的目標(biāo)。根據(jù)遞推的過程可以計(jì)算得到x4=1,s4=3，根據(jù)s4=3狀態(tài)可以知道有兩條遞推路徑到它。如果是只有一個(gè)解，那么查詢過程只要找到一條解路徑即可，但對于多最優(yōu)解問題，必須獲取全部路徑，可以發(fā)現(xiàn)x4=1,x3=1,x2=0,x1=0和x4=1,x3=0,x2=1,x1=1是兩個(gè)最優(yōu)解，圖中兩條藍(lán)色的路徑就是最優(yōu)解的路徑。

圖3給出了順序遞推形式下利用遞歸方法構(gòu)造的求解結(jié)構(gòu)。圖中的曲線表示遞歸調(diào)用時(shí)的過程。根據(jù)約束條件狀態(tài)s5=7已知，但f5是未知的，要求f5則需遞歸的求f4，接著f3，直到f1。因?yàn)闋顟B(tài)s定義為決策前的和，因此f1只有一個(gè)值為0，其他狀態(tài)下的f值都定義為負(fù)無窮。那么遞歸完畢同樣得到所需的f值后，也可以根據(jù)查表得到解。

圖2 順序遞推循環(huán)求解結(jié)構(gòu)Fig.2 Loop solving structure for sequential recursion

圖3 順序遞推遞歸求解結(jié)構(gòu)Fig.3 Recursive solving structure for sequential recursion

從上述分析可知，順序遞推形式下，通過循環(huán)或者遞歸都能得到解。類似地，逆序遞推形式同樣也可以使用循環(huán)和遞歸兩種求解結(jié)構(gòu)，因此一個(gè)動(dòng)態(tài)規(guī)劃問題求解在實(shí)現(xiàn)上可以有四種結(jié)構(gòu)，而且可以用圖證明逆序循環(huán)的結(jié)構(gòu)和順序遞歸的結(jié)構(gòu)是一致的，而逆序遞歸和順序循環(huán)的結(jié)構(gòu)是一致的。總的來說，順序和逆序形式與指標(biāo)推導(dǎo)式相關(guān)，順序遞推是指標(biāo)從前往后推，決策變量從后往前計(jì)算；逆序遞推是指標(biāo)從后往前推，決策變量從前往后計(jì)算。循環(huán)和遞歸則與指標(biāo)遞推式的具體實(shí)現(xiàn)相關(guān)，循環(huán)是先計(jì)算指標(biāo)推導(dǎo)式的等號右側(cè)項(xiàng)，而遞歸是先調(diào)用指標(biāo)推導(dǎo)式的等號左側(cè)項(xiàng)。另外狀態(tài)的定義也不是固定的，也可以定義為各階段決策完成后的狀態(tài)，對應(yīng)的則需修改遞推式的下標(biāo)形式。

2.4 基于0-1決策動(dòng)態(tài)規(guī)劃多最優(yōu)解算法

根據(jù)前述分析，在動(dòng)態(tài)規(guī)劃遞推建表過程中，多個(gè)最優(yōu)解能夠用遞推路徑表示，與單最優(yōu)解問題的差異主要體現(xiàn)在查表求決策變量過程中。一般的簡單遞推式查表，只能得到一條最優(yōu)解路徑，但是多最優(yōu)解問題必須得到多條最優(yōu)解路徑。

以順序遞推循環(huán)求解結(jié)構(gòu)為例，單個(gè)最優(yōu)解問題可以用一個(gè)很簡單的邏輯進(jìn)行求解：從最后一個(gè)階段開始，最優(yōu)的fn已知，如果fn!=fn-1，那么必有xn=1，如果fn==fn-1，那么必有xn=0，然后根據(jù)最優(yōu)的fn-1在前一個(gè)階段繼續(xù)求解。但若要得到多條解路徑則不同。

一種直觀解決思路是考慮建表過程中，當(dāng)遞推某階段出現(xiàn)多種不同決策可以得到相同指標(biāo)時(shí)，記錄多個(gè)決策，并在查表時(shí)根據(jù)這一信息向后搜索。然而這種方式會(huì)帶來內(nèi)存空間的增大，因此若不希望增大內(nèi)存空間，那么只能在建表的信息里實(shí)現(xiàn)對路徑搜索。觀察圖2中第3和第4階段，目標(biāo)狀態(tài)f4=3可以從f3=0和f3=3得到，這是兩條路徑。不同于單最優(yōu)解的邏輯，在查表過程中已知最優(yōu)fn情況下，應(yīng)判斷fn==fn-1+cn-1xn和fn==fn-1兩種情況，當(dāng)都滿足條件時(shí)則采用分支的形式繼續(xù)下一階段。由于已經(jīng)在建表過程中確認(rèn)解的存在，因此完全可以采用深度優(yōu)先搜索的方式得到不同路徑的解，而且搜索分支不用深入第1階段，只要達(dá)到fn==0(狀態(tài)也等于0)就可以終止分支，如算法1所示。

算法1 整數(shù)狀態(tài)的多最優(yōu)解動(dòng)態(tài)規(guī)劃算法

分析算法的結(jié)構(gòu)可知，在狀態(tài)是整數(shù)的情況下，利用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)狀態(tài)遞推，可以方便地利用數(shù)組(或列表)數(shù)據(jù)結(jié)構(gòu)來記錄指標(biāo)(目標(biāo)函數(shù))信息，并可同時(shí)利用數(shù)組的索引信息來表示階段和狀態(tài)。但是對于如式(3)這樣的實(shí)數(shù)問題，階段是整數(shù)可方便表示，但狀態(tài)卻是實(shí)數(shù)的，不便于表示。因此基于動(dòng)態(tài)規(guī)劃的基本原理，考慮順序遞推的循環(huán)結(jié)構(gòu)，針對性地提出一種狀態(tài)實(shí)數(shù)表示的算法，即采用列表加字典的數(shù)據(jù)結(jié)構(gòu)算法，核心是利用實(shí)數(shù)表示的狀態(tài)作為字典的key值，如算法2所示。

算法2 實(shí)數(shù)狀態(tài)的多最優(yōu)解動(dòng)態(tài)規(guī)劃算法

實(shí)數(shù)狀態(tài)的多最優(yōu)解算法與整數(shù)狀態(tài)的算法基本結(jié)構(gòu)一致，差異主要由使用實(shí)數(shù)作為字典的key而產(chǎn)生。要注意由于實(shí)數(shù)在計(jì)算機(jī)中只是高精度的近似表示，所以在作為key以及運(yùn)算時(shí)可能產(chǎn)生的問題可以使用固定模式的實(shí)數(shù)表達(dá)來解決。當(dāng)然如果從另外一個(gè)角度看，實(shí)數(shù)狀態(tài)的問題也可以直接轉(zhuǎn)換為整數(shù)狀態(tài)的問題來解決，比如：式(5)可以將c和b同乘以100，那么整個(gè)問題變?yōu)檎麛?shù)問題，而且解是相同的。分析算法1可以知道，基于0-1決策的動(dòng)態(tài)規(guī)劃法的空間復(fù)雜度主要由指標(biāo)f的矩陣決定，為O(nb)，b為整數(shù)表示的狀態(tài)總數(shù)(對于上述實(shí)數(shù)問題，b=84.03×100=8 403)。對于時(shí)間復(fù)雜度，計(jì)算主要體現(xiàn)在建表和查表過程中，建表過程中計(jì)算的區(qū)域約為nb/2，加上一些比較運(yùn)算，可以認(rèn)為在O(nb)量級。而查表過程由解的數(shù)量m和表的階段數(shù)n決定，最小的情況是nm，而最極端的情況是mn，因此時(shí)間復(fù)雜度在O(nb+nm)和O(nb+mn)之間的范圍內(nèi)。

比較算法2與隱枚舉算法，建表過程中的s≤b判斷可以看作隱枚舉法的剪枝約束，而動(dòng)態(tài)規(guī)劃相比隱枚舉法的主要優(yōu)勢在于建表過程中對狀態(tài)的規(guī)約，相同的狀態(tài)合并到一起考慮，而隱枚舉法一直都是以叉樹的形式在擴(kuò)展。基于動(dòng)態(tài)規(guī)劃的算法正是在對狀態(tài)的不斷規(guī)約中使得其分支數(shù)不斷地縮減從而減小計(jì)算量。

3 兩種改進(jìn)的多最優(yōu)解算法

前面提出的基于0-1決策的算法有效解決了本文多最優(yōu)解問題的兩個(gè)特征帶來的問題。固定物品(數(shù)值)總和的問題通過固定目標(biāo)終狀態(tài)解決，多最優(yōu)解的問題通過考慮多條解路徑查找來解決。同時(shí)由于狀態(tài)的壓縮使其相比枚舉和隱枚舉算法在計(jì)算復(fù)雜度上具有明顯的優(yōu)勢。

購買雞翅問題，要求購買目標(biāo)數(shù)量的物品，求代價(jià)最小的多個(gè)最優(yōu)購買方案，仍采用前述方法開展分析。最直觀的求解思路仍然是采用枚舉，枚舉所有的購買方案組合，從中得到全部的最優(yōu)惠方案。枚舉時(shí)需要考慮不同數(shù)量組合的雞翅可以購買多次的問題，比如要購買12只雞翅，可以購買3次4只，或2次6只，或1次4只1次8只等。因此購買b(>200)只雞翅，需要在b/4+b/5+…+b/200=n個(gè)數(shù)據(jù)的組合中尋找，比如購買256只雞翅，需要在587個(gè)數(shù)據(jù)中尋找最優(yōu)組合，那么枚舉總數(shù)為2587-1，顯然這種規(guī)模已無法有效求解?？煽紤]用隱枚舉法和動(dòng)態(tài)規(guī)劃法，即將問題轉(zhuǎn)換為n個(gè)階段的0-1決策問題。然而，隱枚舉法在購買數(shù)量上升到一定的程度后計(jì)算時(shí)間也變得不可接受，圖4表明采用隱枚舉法在購買數(shù)量為28時(shí)計(jì)算時(shí)間已經(jīng)呈現(xiàn)指數(shù)級上升。

圖4 最優(yōu)解數(shù)量較少情況下的計(jì)算時(shí)間Fig.4 Computation time of cases with small number of optimal solutions

基于0-1決策的多最優(yōu)解動(dòng)態(tài)規(guī)劃算法結(jié)果如圖4中紅色虛線所示，圖4中藍(lán)色實(shí)線是根據(jù)量級O(nb)估計(jì)的計(jì)算時(shí)間。結(jié)果表明在多數(shù)情況下計(jì)算時(shí)間會(huì)接近正比于O(nb)，但在某些特殊情況下，比如圖中購買120和216只雞翅的情況，計(jì)算時(shí)間有跳躍式的上升，而這正是最優(yōu)解數(shù)量較多的情況。由于圖4只是為說明問題，所以只選取了有限情況(曲線上星號標(biāo)記)進(jìn)行計(jì)算。

3.1 基于相同決策路徑合并的改進(jìn)算法

顯然前述算法在最優(yōu)解數(shù)量較多的特殊情況下，時(shí)間復(fù)雜度可能會(huì)往差的mn方向發(fā)展。這是因?yàn)楫?dāng)解的數(shù)量很多且階段數(shù)量很大時(shí)，使用遞歸的查表可能會(huì)近似于搜索一個(gè)n層m叉樹問題，這顯然是非常耗時(shí)的，例如：購買188只雞翅時(shí)，最優(yōu)解的數(shù)量為69，利用前述算法計(jì)算時(shí)間為67.1 s；購買192只雞翅時(shí)，最優(yōu)解數(shù)量為300，計(jì)算時(shí)間已達(dá)2 874.7 s，將變得不可接受。

顯然對于要求出全部最優(yōu)解的給定問題，解的數(shù)量m是固定的，那么只能從問題的決策階段上來考慮降低極端條件下的計(jì)算復(fù)雜性。在前面的問題建模中，采用了0-1決策思路，其中一些階段的決策是購買相同數(shù)量的雞翅組合，因此這些階段的作用是相同的。如果能夠?qū)ζ溥M(jìn)行處理和簡化，即將相同作用的決策路徑合并，那么搜索空間將會(huì)大幅度減小?；谶@種相同決策路徑合并的改進(jìn)思路，可采用寬度優(yōu)先搜索實(shí)現(xiàn)，如算法3所示。

算法3核心改進(jìn)在于寬度優(yōu)先搜索節(jié)點(diǎn)擴(kuò)展過程中對相同決策效果的節(jié)點(diǎn)進(jìn)行了刪減。購買相同雞翅數(shù)量情況下的改進(jìn)算法與原算法計(jì)算時(shí)間比較如圖5所示，可以看到改進(jìn)算法相比原來算法具有明顯的改進(jìn)，在最優(yōu)解數(shù)量比較多的情況下也沒有出現(xiàn)與原算法類似的跳躍性增長。

圖6給出了購買4～300只雞翅問題的改進(jìn)算法計(jì)算時(shí)間結(jié)果。很明顯看到，計(jì)算時(shí)間與最優(yōu)解數(shù)量的關(guān)系，計(jì)算時(shí)間總體符合O(nb+nm)的正比估計(jì)(圖中藍(lán)色線為根據(jù)該量級估計(jì)的計(jì)算時(shí)間)，但隨著解數(shù)量的增加有一定的偏離，且解的數(shù)量越多則偏離越大，但總體性能仍可接受。

算法3 相同決策路徑合并的改進(jìn)算法

圖5 改進(jìn)算法與原始算法的計(jì)算時(shí)間比較Fig.5 Computation time comparison between improved algorithm and original algorithm

購買188只雞翅時(shí)，改進(jìn)算法的時(shí)間為2.3 s，是原算法的1/29；購買192只雞翅時(shí)改進(jìn)算法計(jì)算時(shí)間為5.3 s，是原算法的1/542。

圖6 改進(jìn)算法計(jì)算時(shí)間與解數(shù)量的關(guān)系Fig.6 Relation of computation time to solution number for improved algorithm

3.2 基于0-x決策的改進(jìn)算法

對原算法的改進(jìn)除了進(jìn)行相同決策路徑合并的思路外，其實(shí)也可以從建模的角度進(jìn)行改進(jìn)。如果能夠?qū)?-1決策問題轉(zhuǎn)變?yōu)?-x決策問題，那么決策階段數(shù)也可大幅下降，從而降低極端情況下的時(shí)間復(fù)雜度。因此考慮將問題建模為[0,b/cj]決策問題，其中每個(gè)階段求解變量的最大值為b/cj，數(shù)學(xué)模型如式(11)所示。

(11)

這種改進(jìn)思路是利用0-x決策建模減少總的決策階段數(shù)，使得表的整體搜索深度明顯下降，可采用深度優(yōu)先類搜索算法實(shí)現(xiàn)，計(jì)算時(shí)間也將有明顯的改善?；?-x決策的改進(jìn)方法實(shí)現(xiàn)如算法4所示。

算法4 基于0-x決策的改進(jìn)算法

與前述改進(jìn)算法最大差別是，前述算法采用0-1決策，而算法4采用[0,b/cj]決策，在建表過程中同一階段的遞推需要比較b/cj種選擇，在查表過程中的遞歸則由原來的2個(gè)分支變?yōu)閎/cj個(gè)分支，原理是通過階段內(nèi)更多的比較和計(jì)算來換取決策階段數(shù)的下降。

算法4的復(fù)雜度仍然由建表和查表過程決定，表的結(jié)構(gòu)為n行b列，只是n由原來0-1決策的b/4+b/5+…+b/200變?yōu)閏ount(4,…,cj,…,200)。建表過程的時(shí)間復(fù)雜度仍為O(nb)，查表過程沒有重復(fù)分支所以時(shí)間復(fù)雜度為O(nm)。圖7給出了0-x決策查表和0-1決策查表過程的局部差異，其中j階段的0-x決策對應(yīng)了i到i-2階段的0-1決策。對應(yīng)于xj=1，0-1決策有3種情況xi=1或者xi-1=1或者xi-2=1，而這三種情況其實(shí)是一個(gè)相同的決策，只是由于0-1決策結(jié)構(gòu)導(dǎo)致分成3個(gè)階段來決策。所以，0-x決策的建模避免了0-1決策中的很多重復(fù)搜索，前面基于相同決策路徑合并的改進(jìn)算法實(shí)質(zhì)也是解決這一重復(fù)問題。

(a) 0-1決策(a) 0-1 Decision

(b) 0-x決策(b) 0-x Decision圖7 0-1決策和0-x決策的查表路徑差異Fig.7 Searching path difference between 0-1 and 0-x decision

圖8給出了購買4～300只雞翅利用基于0-x決策改進(jìn)算法的運(yùn)行時(shí)間情況，顯然計(jì)算時(shí)間基本符合時(shí)間復(fù)雜度O(nb+nm)的正比估計(jì)。與圖6相比可知，基于0-x決策的改進(jìn)算法的性能相比基于0-1決策相同決策路徑合并的改進(jìn)算法也有明顯的提升，例如最優(yōu)解數(shù)量最多的購買298只雞翅的情況，計(jì)算時(shí)間也僅為0.437 5 s。由此得出結(jié)論，對于存在多次相同決策的問題，更適合建模為0-x決策問題，因?yàn)榧幢悴捎孟嗤瑳Q策路徑合并，基于0-1決策的算法性能也達(dá)不到基于0-x決策算法的水平，而每次決策都不相同的問題，則更適合建模成0-1決策問題。(本文所有實(shí)驗(yàn)代碼見：https://github.com/hushidong/multi-optimal-solution-combinatorial-optimization-problem)

圖8 基于0-x決策改進(jìn)算法計(jì)算時(shí)間與解數(shù)量的關(guān)系Fig.8 Relation of computation time to solution number for improved algorithm based on 0-x decision

4 結(jié)論

本文提出了一類具有固定物品(數(shù)值)總和及多最優(yōu)解特征的組合優(yōu)化問題。該問題不同于一般的單最優(yōu)解組合優(yōu)化問題，必須求解所有最優(yōu)解。以固定總和實(shí)數(shù)子集問題和費(fèi)城中國餐館購買雞翅問題為例，比較分析了枚舉、隱枚舉和動(dòng)態(tài)規(guī)劃三類不同方法。通過動(dòng)態(tài)規(guī)劃求解結(jié)構(gòu)分析，明確了狀態(tài)定義、指標(biāo)遞推、決策變量求解對于算法實(shí)現(xiàn)的影響。提出基于0-1決策的多最優(yōu)解的動(dòng)態(tài)規(guī)劃算法，并針對實(shí)數(shù)狀態(tài)問題提出了基于字典數(shù)據(jù)結(jié)構(gòu)的實(shí)數(shù)狀態(tài)表示求解算法。該算法在最優(yōu)解數(shù)量較少時(shí)能夠獲得較好的性能，但最優(yōu)解數(shù)量較多的情況下，計(jì)算時(shí)間呈現(xiàn)跳躍式上升。基于降低時(shí)間復(fù)雜度考慮，提出了壓縮決策階段的改進(jìn)思路，并實(shí)現(xiàn)了兩種改進(jìn)算法：基于相同決策路徑合并的0-1決策求解算法和基于0-x決策的求解算法。結(jié)果表明通過減小決策的階段數(shù)可使算法性能得到明顯提升，兩種改進(jìn)算法的對比表明具有多次相同決策的問題更適合于建模成0-x決策問題。本文將一類多最優(yōu)解的特殊的組合優(yōu)化問題作為一類獨(dú)立問題專門進(jìn)行研究，能夠幫助解決現(xiàn)實(shí)中一些多最優(yōu)解的決策問題，且對開發(fā)新的建模和求解方法也有促進(jìn)作用，下一步將持續(xù)推進(jìn)算法優(yōu)化和實(shí)際應(yīng)用。