基于動態規劃模型的穿越沙漠路程優化問題

付芷睿 李雪純 李興睿

（武漢大學，湖北 武漢 430000）

1 模型假設

1.假設玩家都是理性的，追求的目標僅是到達終點時獲取的總利益最大；

2.假設區域可以抽象成一個點；

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

2 模型準備

2.1 地圖的要素提取及簡化

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

2.2 最短路徑

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

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

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

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

在只知道當天天氣的情況下，玩家應對此后的天氣進行最壞的打算，計算出消耗上限與收益下限，權衡下一步的行動。

2.4 停留

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

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

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

3 基于單目標規劃模型的最優策略求解

3.1 單目標規劃模型的建立

3.1.1 決策變量的確定

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

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

3.1.2 目標函數的確定

其中：

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

3.1.3 約束條件

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

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

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

綜上，建立單目標規劃模型即可。

3.2 求解模型得出一般策略

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

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

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

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

階段1：起點-礦山

1.起點物資量

由于村莊中物資的價格為基準價格的2倍，因此為了節約資金，玩家應在起點處購買盡可能多的物資。

2.到達礦山的路徑及日期

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

階段2：礦山挖礦，中途去村莊補給

1.挖礦天數

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

2.去村莊補給的日期

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

3.購買補給的數量

應滿足補給后的物資足夠玩家維持到下一次補給。

階段3：礦山-終點

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

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

Step1：采用Dijkstra算法計算從起點到礦山的日期；

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

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

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

4 基于動態規劃的最優決策求解

4.1 多階段決策過程的動態規劃模型

本問題中，玩家不知道全程的天氣，此時不便利用第一問中分3個階段的方法，而是應該每天根據當前的狀態進行下一步行動的決策，因此我們建立動態規劃模型如下：

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

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

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

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

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

在上述動態規劃模型的基礎上增加第一問中的約束條件，即為第二問的總模型。

4.2 求解模型得出一般策略

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

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

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

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

（1）當玩家位于起點時，假如玩家經過礦山的時間超過天數上限，則直接前往終點；否則，時間充足，可以經過礦山。

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

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

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

（5）當玩家位于終點時，游戲結束。

4.2.2 通過比較Z*對策略Z1進行修正

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

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

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

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

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

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

5 多玩家參與情況下的最優策略求解

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

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

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

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

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

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

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

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

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

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

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

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

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

6 模型評價

6.1 模型優點

（1）綜合考慮各種因素，建立路徑決策的單目標規劃模型，模型可遷移性強；

（2）建立動態規劃模型，詳細考慮玩家在各個情況下的決策，模型完備；

（3）采用拆分的思想對模型進行求解，求解迅速且結果較準確。

6.2 模型缺點

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

（2）算法普適性有待提高，對于不同的關卡，運行程序得到的結果需要進行一定步數的手動調整，結果才能更準確。

6.3 模型推廣

（1）可以嘗試手動調整得到更復雜的算法，允許算法運行更長時間得到更優的結果；

（2）可以嘗試采用強化學習的方法學習得到的游戲策略與本文中算法求得的策略進行對比，并疊加強化學習的狀態轉移等要素改進本文算法，得到更好的結果。