基于動態(tài)規(guī)劃模型的穿越沙漠路程優(yōu)化問題

付芷睿 李雪純 李興睿

（武漢大學(xué)，湖北 武漢 430000）

1 模型假設(shè)

1.假設(shè)玩家都是理性的，追求的目標(biāo)僅是到達(dá)終點(diǎn)時獲取的總利益最大；

2.假設(shè)區(qū)域可以抽象成一個點(diǎn)；

3.假設(shè)以下的初始值是不變的：負(fù)重上限恒為1200kg，初始資金恒為10000元，每箱水的質(zhì)量為3kg，食物的質(zhì)量為2kg，每箱水的基準(zhǔn)價格為5元/箱，食物的基準(zhǔn)價格為10元/箱。

2 模型準(zhǔn)備

2.1 地圖的要素提取及簡化

首先，對于形狀不規(guī)則的地圖進(jìn)行抽象處理，提取出起點(diǎn)、終點(diǎn)、村莊和礦山四個要素，其余點(diǎn)均視為普通點(diǎn)。

2.2 最短路徑

為了使得到達(dá)終點(diǎn)時剩余資金最大，玩家應(yīng)盡量減少行走過程中的消耗，因此玩家在起點(diǎn)出發(fā)后，會立即以最短路徑前往村莊、礦山或終點(diǎn)其中之一。

2.3 定義消耗上限與收益下限

消耗上限：假設(shè)全程30天均為沙暴天氣，計算出玩家的物資消耗量，稱作消耗上限。

收益下限：假設(shè)挖礦時均遇到沙暴天氣，計算出此時的挖礦收益，稱作收益下限。

在只知道當(dāng)天天氣的情況下，玩家應(yīng)對此后的天氣進(jìn)行最壞的打算，計算出消耗上限與收益下限，權(quán)衡下一步的行動。

2.4 停留

初步分析可知，停留的條件有兩種：

（1）沙暴時必須在原地，不能移動；

（2）到達(dá)礦山后，由于挖礦的消耗為基礎(chǔ)消耗量的三倍，并且高溫天氣與沙暴天氣相對于晴朗天氣的基礎(chǔ)消耗量都顯著提高，所以為了挖礦期間的消耗盡可能少，可能會根據(jù)需要在沙暴天或高溫天不挖礦，通過簡單演算，我們規(guī)定每一關(guān)卡除沙暴天以外，其余總的停留時間不超過兩天。

3 基于單目標(biāo)規(guī)劃模型的最優(yōu)策略求解

3.1 單目標(biāo)規(guī)劃模型的建立

3.1.1 決策變量的確定

（1）玩家在第i天的位置xi，i=0,…,N，xi∈A。其中，N表示游戲的截止日期，A表示地圖上所有區(qū)域的序號的集合。特別地，當(dāng)玩家在第n天到達(dá)終點(diǎn)后，我們約定玩家位置始終位于終點(diǎn)；

綜合上述變量，決策變量可統(tǒng)一表示為向量Xi=(xi,vi,ui,ai,bi)，。

3.1.2 目標(biāo)函數(shù)的確定

其中：

S0表示挖礦的基礎(chǔ)收益，ai和bi分別表示玩家在第i天購買的水和食物的數(shù)量，wi為第i天的天氣狀況：

3.1.3 約束條件

條件一：任意第i天包內(nèi)都有剩余物資且總負(fù)重mi不超過負(fù)重上限1200kg；

條件三：當(dāng)天氣狀況為沙暴時，玩家必須在原地停留一天，即第i+1天和第i天位置相同；

條件四：玩家每天只能從目前區(qū)域到達(dá)與之相鄰的區(qū)域，或在目前區(qū)域停留一天；

綜上，建立單目標(biāo)規(guī)劃模型即可。

3.2 求解模型得出一般策略

3.2.1 求解一般策略的思維過程

由于直接求解上述優(yōu)化問題時間和電腦儲存空間開銷較大，因此我們首先根據(jù)不同類型的地圖所含要素進(jìn)行分類討論，將全程路線分為挖礦與不挖礦兩種路線。

路線一：不經(jīng)過村莊或礦山。通過選擇最短路徑，計算出玩家最快到達(dá)終點(diǎn)的日期n，可得最終剩余資金為：

路線二：經(jīng)過村莊和礦山。當(dāng)玩家采取挖礦的路線時，我們又將全程分為從起點(diǎn)到礦山、挖礦過程和從礦山到終點(diǎn)三個階段處理，并且給出每個階段玩家應(yīng)采取的策略，最后給出整體算法。

階段1：起點(diǎn)-礦山

1.起點(diǎn)物資量

由于村莊中物資的價格為基準(zhǔn)價格的2倍，因此為了節(jié)約資金，玩家應(yīng)在起點(diǎn)處購買盡可能多的物資。

2.到達(dá)礦山的路徑及日期

為了減少行走的消耗，玩家應(yīng)當(dāng)盡快前往礦山，僅在沙暴天氣停留。通過選擇最短路徑，可以得到玩家最快到達(dá)礦山的路徑及日期。

階段2：礦山挖礦，中途去村莊補(bǔ)給

1.挖礦天數(shù)

根據(jù)階段1和階段2計算的到達(dá)與離開礦山的日期，可得玩家挖礦的天數(shù)。

2.去村莊補(bǔ)給的日期

在物資即將不足但是恰好能維持玩家抵達(dá)村莊時，離開礦山前往村莊。根據(jù)往返礦山和村莊之間需要花費(fèi)的時間，計算出最多可以前往村莊的次數(shù)。

3.購買補(bǔ)給的數(shù)量

應(yīng)滿足補(bǔ)給后的物資足夠玩家維持到下一次補(bǔ)給。

階段3：礦山-終點(diǎn)

離開礦山的日期。為了使收益最大，玩家應(yīng)當(dāng)用盡可能多的天數(shù)挖礦，通過選擇最短路徑并且考慮食物和水的約束可以得到玩家最晚離開礦山的日期。

3.2.2 求解一般過程的整體算法

Step1：采用Dijkstra算法計算從起點(diǎn)到礦山的日期；

Step2：根據(jù)食物和水的余量的初步計算從礦山離開到終點(diǎn)的日期范圍，而后采用Dijkstra算法計算從礦山離開到終點(diǎn)的確切日期；

Step3：遍歷玩家離開礦山到達(dá)村莊進(jìn)行補(bǔ)給的日期，對于多種可能的路線，分別計算出終點(diǎn)時玩家的資金剩余量，求出最大資金剩余量所在路線，則該路線即為所求玩家最佳策略；

step4：綜合前四步，得到全過程的策略。

4 基于動態(tài)規(guī)劃的最優(yōu)決策求解

4.1 多階段決策過程的動態(tài)規(guī)劃模型

本問題中，玩家不知道全程的天氣，此時不便利用第一問中分3個階段的方法，而是應(yīng)該每天根據(jù)當(dāng)前的狀態(tài)進(jìn)行下一步行動的決策，因此我們建立動態(tài)規(guī)劃模型如下：

劃分階段：以天為單位，假設(shè)游戲的截止日期為第n天，則全程分為n-1個階段。

狀態(tài)變量：Xi=(xi,vi,ui,ai,bi)，，其中i表示第i天，xi表示玩家所在位置，vi表示玩家是否在村莊，ui表示玩家是否挖礦，ai表示購買水的數(shù)量，bi表示購買食物的數(shù)量[1]。

決策變量：當(dāng)一個階段的狀態(tài)確定后，玩家需要做出選擇從而演變到下一階段的某個狀態(tài)，這種選擇手段稱為決策，描述決策的變量稱為決策變量。設(shè)玩家在位置xi的決策變量為fi(xi)。

狀態(tài)轉(zhuǎn)移方程：在確定性過程中，一旦某階段的狀態(tài)和決策已知，下階段的狀態(tài)便完全確定。用狀態(tài)轉(zhuǎn)移方程表示這種演變規(guī)律，即通過玩家目前位置和決策變量fi(xi)來確定下一步的位置xi+1的方程，設(shè)為xi+1=Ti(xi,fi)。

指標(biāo)函數(shù)：是衡量過程優(yōu)劣的數(shù)量指標(biāo)。由于玩家的目標(biāo)是使剩余的資金最大，因此選擇每一天的凈收益作為指標(biāo)函數(shù)，凈收益即玩家當(dāng)天可能挖礦的收益與消耗資金之差，記為。

在上述動態(tài)規(guī)劃模型的基礎(chǔ)上增加第一問中的約束條件，即為第二問的總模型。

4.2 求解模型得出一般策略

通過該動態(tài)規(guī)劃模型，我們希望求解出全過程的最優(yōu)策略S*={f1(x1)*，f2(x2)*，…，fn(xn)*}，即玩家在每一天的決策fi(xi)*的集合。但是，由于該動態(tài)規(guī)劃模型的時間復(fù)雜度是O(n3)，直接采用逆序求解法的消耗巨大，無法在滿意的時間內(nèi)求得最優(yōu)解。因此我們采用拆分的思想，將求解過程拆分成兩步[2]：

（1）首先利用貪心算法的思想制定出某一特定的策略S0，作為初值；

（2）接著通過與最優(yōu)策略的比較，不斷修改該策略S0，得到最終的一般策略S*，S*就是上述動態(tài)規(guī)劃問題的近似最優(yōu)解。

4.2.1 基于貪心算法的特定策略S1

（1）當(dāng)玩家位于起點(diǎn)時，假如玩家經(jīng)過礦山的時間超過天數(shù)上限，則直接前往終點(diǎn)；否則，時間充足，可以經(jīng)過礦山。

（2）當(dāng)玩家在第i天位于村莊時，我們利用貪心算法，使得玩家始終做出利益最大化的選擇。即，先計算從當(dāng)前日期到最后一天的消耗上限，若此時包內(nèi)水的數(shù)量或者包內(nèi)食物的數(shù)量小于該數(shù)值，那么玩家進(jìn)行補(bǔ)給，否則不補(bǔ)給。

（3）當(dāng)玩家位于礦山時，利用貪心算法，使得玩家始終做出利益最大化的選擇。即，先將水和食物的消耗上限按照村莊的價格折算成資金，再與挖礦收益進(jìn)行比較。若，那么玩家不挖礦，否則挖礦。

（4）當(dāng)玩家位于其他位置時，由于約束條件過于復(fù)雜，無法確定應(yīng)該前往終點(diǎn)、礦山還是村莊。此時我們首先計算出所有可能的移動路線的消耗上限，當(dāng)包內(nèi)水的數(shù)量和食物的數(shù)量均大于消耗上限時，在這些路線中，我們約定玩家等可能選擇其中一條。

（5）當(dāng)玩家位于終點(diǎn)時，游戲結(jié)束。

4.2.2 通過比較Z*對策略Z1進(jìn)行修正

1.定義兩條路徑的差別εij。在該問題中，定義向量，εij中的元素為兩條路徑xi和路徑y(tǒng)j中每個位置的差，用于衡量兩條路線的相似程度。其中，εij的零位越多，兩條路徑越相似。

2.根據(jù)ε0k修正一般策略Z1的算法。

Step1：編寫程序模擬玩家采用一般策略Z1后走的路徑K1；

Step2：采用第一問的算法計算玩家采用的策略Z0以及對應(yīng)的路徑K0；

Step3：根據(jù)ε0k修正策略Z1，得到策略Z2，當(dāng)向量ε0k中有超過兩位元素不為零時，繼續(xù)修正策略；

Step4：直到向量ε0k中只有小于等于兩位元素不為零時，可以認(rèn)為兩條路徑足夠接近，此時迭代得到的Zk即為所求Z*。

5 多玩家參與情況下的最優(yōu)策略求解

現(xiàn)在，將第一問和第二問的情況分別推廣到存在n名玩家的情況下。由于不同玩家處于同一區(qū)域時，他們的消耗量會增加為2k倍而挖礦的收益變?yōu)?/k，此時會出現(xiàn)多人博弈的問題，每個玩家的策略會受到環(huán)境和他人決策的共同影響。

由于無順序選擇模式較為簡單，我們假設(shè)游戲模式為有順序模式：n個玩家同一天從起點(diǎn)出發(fā)，但選擇策略有先后順序，即抽到的編號越小，越先選擇策略。

為了簡化模型，我們只考慮玩家A應(yīng)選擇的策略。

5.1 第一小問：已知全部天氣狀況

首先，根據(jù)第一問，確定單名玩家的最佳策略S*，A的策略選擇流程為：

（1）n名玩家在開始游戲前分別獲得其編號，按編號從小到大先后進(jìn)入游戲并確定策略，即抽到第i號的玩家是第i個確定策略的玩家；

（2）玩家A根據(jù)第二問中的一般策略推測前i-1名玩家的策略的集合Pi，并根據(jù)Pi推測出自己的策略；

（3）玩家A根據(jù)第二問中的一般策略推測后n-i名玩家的策略的集合Qi，并根據(jù)Pi和Qi以及自己的策略得出自己的最終收益。

5.2 第二小問：不知道天氣狀況

首先根據(jù)第二問，確定單名玩家的最佳策略S*，A的選擇流程為：

（1）n名玩家在開始游戲前分別獲得其編號，按編號從小到大先后進(jìn)入游戲并確定策略，即抽到第i號的玩家是第i個確定策略的玩家；

（2）玩家A根據(jù)第二問中的一般策略推測前i-1名玩家的策略的集合Pi，并根據(jù)Pi推測出自己的策略；

（3）玩家A根據(jù)第二問中的一般策略推測后n-i名玩家的策略的集合Qi，并根據(jù)Pi和Qi以及自己的策略得出自己的最終收益。

6 模型評價

6.1 模型優(yōu)點(diǎn)

（1）綜合考慮各種因素，建立路徑?jīng)Q策的單目標(biāo)規(guī)劃模型，模型可遷移性強(qiáng)；

（2）建立動態(tài)規(guī)劃模型，詳細(xì)考慮玩家在各個情況下的決策，模型完備；

（3）采用拆分的思想對模型進(jìn)行求解，求解迅速且結(jié)果較準(zhǔn)確。

6.2 模型缺點(diǎn)

（1）第三問求解多名玩家的游戲時，簡化了模型，并未考慮多者博弈的情況；

（2）算法普適性有待提高，對于不同的關(guān)卡，運(yùn)行程序得到的結(jié)果需要進(jìn)行一定步數(shù)的手動調(diào)整，結(jié)果才能更準(zhǔn)確。

6.3 模型推廣

（1）可以嘗試手動調(diào)整得到更復(fù)雜的算法，允許算法運(yùn)行更長時間得到更優(yōu)的結(jié)果；

（2）可以嘗試采用強(qiáng)化學(xué)習(xí)的方法學(xué)習(xí)得到的游戲策略與本文中算法求得的策略進(jìn)行對比，并疊加強(qiáng)化學(xué)習(xí)的狀態(tài)轉(zhuǎn)移等要素改進(jìn)本文算法，得到更好的結(jié)果。