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

付芷睿 李雪純 李興睿

摘 要 在“穿越沙漠”的游戲中，玩家需要規(guī)劃路線在規(guī)定時(shí)間內(nèi)到達(dá)終點(diǎn)，并保留盡可能多的資金。利用動(dòng)態(tài)規(guī)劃等數(shù)學(xué)工具可以針對(duì)不同的關(guān)卡設(shè)置尋找玩家的最優(yōu)路線。

第一問中，只有一名玩家且該玩家已知全程天氣。首先以到達(dá)終點(diǎn)時(shí)剩余資金最大為目標(biāo)函數(shù)，以游戲規(guī)則為約束條件，以玩家的策略為決策變量，建立單目標(biāo)規(guī)劃模型。接著將全路程分為三個(gè)階段：從起點(diǎn)到礦山、在礦山與村莊活動(dòng)、從礦山到終點(diǎn)。在一、三階段利用Dijkstra算法求出最短路徑，對(duì)于第二階段設(shè)計(jì)循環(huán)算法求解。

第二問中，只有一名玩家且僅知道當(dāng)天天氣。首先對(duì)時(shí)間離散化，將本問轉(zhuǎn)化為多階段決策問題，而后建立動(dòng)態(tài)規(guī)劃模型。求解過程分為兩步：

（1）借助貪心算法的思想，構(gòu)造符合約束條件的玩家策略;

（2）將采用該策略求解的路徑與第一問中的算法求解的路徑進(jìn)行比較，優(yōu)化該玩家策略，使其逼近最優(yōu)解。

第三問中，推廣到多名玩家與有順序游戲模式。為簡化問題，僅考慮玩家A的最優(yōu)策略。此時(shí)A需要綜合考慮其前面的i-1位玩家的策略以及后n-1位玩家的策略給出最終策略。

關(guān)鍵詞 Dijkstra算法 單目標(biāo)規(guī)劃模型 多階段決策 動(dòng)態(tài)規(guī)劃模型

中圖分類號(hào)：U491.2 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-0745（2021）01-0052-04

1 模型假設(shè)

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

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

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

2 模型準(zhǔn)備

2.1 地圖的要素提取及簡化

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

2.2 最短路徑

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

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

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

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

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

2.4 停留

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

（1）沙暴時(shí)必須在原地，不能移動(dòng);

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

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ū)域的序號(hào)的集合。特別地，當(dāng)玩家在第n天到達(dá)終點(diǎn)后，我們約定玩家位置始終位于終點(diǎn);

（2）玩家在第i天是否位于村莊，對(duì)此引入0-1變量vi;

（3）玩家在第i天是否挖礦，對(duì)此引入0-1變量ui;

（4）玩家在第i天購買的物資數(shù)量，ai表示水的數(shù)量，bi表示食物的數(shù)量。特別地，i=0時(shí)表示第0天玩家在起點(diǎn)處購買的物資數(shù)量，并且需要注意玩家不位于村莊時(shí)無法購買物資，因此ai和bi均取值為0。

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

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

設(shè)玩家在第n天抵達(dá)終點(diǎn)，為使抵達(dá)終點(diǎn)時(shí)剩余的資金yn盡可能多，目標(biāo)函數(shù)為：max yn。其中：

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

3.1.3 約束條件

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

條件二：第i天購買物資所耗費(fèi)的資金Si應(yīng)當(dāng)小于等于當(dāng)天剩余資金yi;

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

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

條件五：當(dāng)且僅當(dāng)?shù)趇天玩家位于起點(diǎn)或村莊時(shí)，才可以購買物資。即玩家不位于起點(diǎn)或村莊時(shí)，購買物資數(shù)量為0。

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

3.2 求解模型得出一般策略

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

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

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

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

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

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

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

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

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

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

1.挖礦天數(shù)

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

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

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

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

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

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

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

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

step1：采用Dijkstra算法計(jì)算從起點(diǎn)到礦山的日期;

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

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

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

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

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

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

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

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

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

狀態(tài)轉(zhuǎn)移方程：在確定性過程中，一旦某階段的狀態(tài)和決策已知，下階段的狀態(tài)便完全確定。用狀態(tài)轉(zhuǎn)移方程表示這種演變規(guī)律，即通過玩家目前位置xi和決策變量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)天可能挖礦的收益與消耗資金之差，記為Vi，n。

最優(yōu)值函數(shù)：在玩家位置xi給定時(shí)指標(biāo)函數(shù)Vi，n對(duì)策略的最優(yōu)值稱為最優(yōu)值函數(shù)，記為gi（xi），即：

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

4.2 求解模型得出一般策略

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

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

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

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

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

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

包內(nèi)食物的數(shù)量小于該數(shù)值，那么玩家進(jìn)行補(bǔ)給，否則不補(bǔ)給。

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

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

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

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

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

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

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

step2：采用第一問的算法計(jì)算玩家采用的策略Z0以及對(duì)應(yīng)的路徑K0;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 模型評(píng)價(jià)

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

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

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

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

6.2 模型缺點(diǎn)

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

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

6.3 模型推廣

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

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

參考文獻(xiàn)：

[1] 韋化，龍丹麗，黎靜華.求解大規(guī)模機(jī)組組合問題的策略迭代近似動(dòng)態(tài)規(guī)劃[J].中國電機(jī)工程學(xué)報(bào)，2014，34（25）： 4420-4429.

[2] 司守奎，孫兆亮.數(shù)學(xué)建模算法與應(yīng)用[M]（第2版）.北京：國防工業(yè)出版社，2016.

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