基于動態(tài)規(guī)劃的沙漠行走問題決策分析

姚銘波 黃品文 張婉春 陸 瑤

（浙江水利水電學(xué)院，浙江 杭州310018）

針對問題一的求解，第一關(guān)：首先將地圖轉(zhuǎn)換成無向圖進(jìn)行預(yù)處理，其次根據(jù)已知條件寫出動態(tài)規(guī)劃模型，決策變量為：路徑、是否挖礦、是否沿途買水和食物、初始出發(fā)時的資金，目標(biāo)函數(shù)為：玩家到達(dá)終點時留存的總資金最大，約束條件為：到達(dá)終點的截止日期不能超過30 天、負(fù)載量不能超過1200 千克、資金、水、食物負(fù)重以及當(dāng)天金幣的狀態(tài)的建模約束。在已知全部天氣狀況的情況下，再根據(jù)無向圖寫出鄰接矩陣，用Floyd 算法得到27 個點兩兩之間任意的最短路徑，然后用C 語言進(jìn)行求解，最佳結(jié)果在第23 天返回終點，總金額為10430 元；第二關(guān)：在第一關(guān)的基礎(chǔ)上，只改變了最短路徑，其余條件不變，最佳結(jié)果在第30 天返回終點，總金額為12710 元。

1 問題的背景與重述

游戲已經(jīng)成為人們休閑娛樂的調(diào)味品，玩家可以在游戲世界中通過完成任務(wù)，領(lǐng)取更高的獎勵?，F(xiàn)如今有一款穿越沙漠的游戲，玩家憑借著地圖在沙漠中行走，根據(jù)地圖的難度不同，游戲的策略也呈現(xiàn)出不同的效果。如何根據(jù)地圖難度的不同，在遵守游戲規(guī)則的情況下，解決資金資源問題，盡可能留有多的資金，成為游戲攻略的一大難題。

2 問題的分析

問題一要求在一個人出發(fā)時得知接下來所有天氣狀況后求出第一關(guān)和第二關(guān)的最優(yōu)解，我們先通過題目和游戲規(guī)則整理出目標(biāo)函數(shù)、決策變量和全面準(zhǔn)確的相關(guān)約束條件，建立問題一的動態(tài)規(guī)劃模型，最后建立模型用C 語言求出最優(yōu)解，如果難以求解就先通過建立鄰接矩陣然后用floyd 算法求出最短路徑，再通過優(yōu)化路徑法化簡模型，貪心算法求出不同方案的近似解。

3 對問題一模型的建立與求解

3.1 模型的準(zhǔn)備

圖1

3.2 第一關(guān)模型的建立

3.2.1 決策變量

3.2.1.1 沙漠行走游戲中判斷是否挖礦，可以采用0-1 變量，用wij 表示如下：

3.2.1.2 沙漠行走游戲中判斷是否行動，可以采用0-1 規(guī)劃，用bij 表示如下：

3.2.2 目標(biāo)函數(shù)

3.2.2.1 在游戲過程中挖礦的收益A 表示的是挖礦的總收益；k 表示的是第k 天到達(dá)終點；q 在這里表示區(qū)域總數(shù)q=27；wij 表示當(dāng)天是否要挖礦；根據(jù)只有一個礦山的情況，這里j 為固定值區(qū)域12。

3.2.2.2 以玩家到達(dá)終點時留存的總資金最大為目標(biāo)，根據(jù)上述相關(guān)決策，可以得到目標(biāo)函數(shù)中e1 表示的是水的基準(zhǔn)價格；f1 表示的是食物的基準(zhǔn)價格；Xij，Yij 表示的是在第i 天在第j 地買的水和食物的數(shù)量，這里用X01，Y01 來表示，并帶入數(shù)值進(jìn)行計算Sij，Cij 表示第i 天在j 地剩余的水和食物的數(shù)量，這里i=k,j=27。

3.2.3 約束條件

3.2.3.1 ji表示第i 天的金幣數(shù)。而第i 天的金幣數(shù)是通過第i-1 天金幣數(shù)影響因素的影響進(jìn)行迭代獲得的,其中游戲中的金幣數(shù)不能小于0。

3.2.3.2 由于在游戲中，第i 天只在一個地點行動一次，且冒險者到達(dá)終點時用的天數(shù)要小于30 天。

3.2.3.3 Zi-1：表示第i 天所在的地點,而游戲中第i 天所在的地點也是由第i-1 所在的地點通過影響因素的影響進(jìn)行迭代而出的。

3.2.3.4 對購買物資數(shù)量的約束。根據(jù)題目可知，玩家在初始起點時，所買的水和食物重量不能超過負(fù)重，價錢不能超出預(yù)算。

3.2.3.5 對剩余物資數(shù)量消耗情況的約束。在玩家游戲過程中，活動會存在三種情況：第一種為繼續(xù)行走，第二種為原地不動，第三種為進(jìn)行挖礦。無論哪一種情況都會進(jìn)行物資消耗，一天活動下來后剩余的物資數(shù)量由當(dāng)天活動以及前一天剩余物資數(shù)量決定。這里的S 表示的是一天活動之后所擁有的剩余水的數(shù)量；SSij 表示當(dāng)天剛開始時所擁有的水的數(shù)量；TSij 表示的是第i 天水的消耗情況。

這里的C 表示的是一天活動之后所擁有的剩余食物的數(shù)量；SCij 表示當(dāng)天剛開始時所擁有的食物的數(shù)量；HSij 表示的是第i 天食物的消耗情況。

這里的aij 表示玩家在第i 天在j 地的活動方式；由于剩余物資的重量還是不能夠超出負(fù)重，所以對負(fù)重的約束條件為：3S+2C≤1200。

綜上所述，綜合以上有關(guān)于優(yōu)化模型中目標(biāo)函數(shù)以及約束條件的分析，可以得到玩家到終點時總資金最大化模型的建立：

3.3 第一關(guān)模型的求解

以下方案一、方案二的模型求解方式為暴力枚舉，方案三為優(yōu)化模型后的求解方案。

3.3.1 方案一模型的建立與求解

根據(jù)Floyd 算法，用Matlab 軟件進(jìn)行編程，求得起點到終點的最短路徑為3。根據(jù)每一路徑消耗一天為單位，可以根據(jù)最短路徑得出起點到終點的最短行動時間為3 天。前三天的天氣為高溫、高溫、晴朗，所以在初始起點進(jìn)行補給的時候購買滿足三天的水和食物。通過對附件里第一關(guān)的表格計算，水和食物總共買了590 元，還剩下9410 元作為到達(dá)終點的總資金。

3.3.2 方案二模型的建立與求解

可以根據(jù)Floyd 算法求出兩個目標(biāo)區(qū)域之間的最短路徑，然后結(jié)合附件中所給出的天氣狀況，制定30 天的行動路線：（1）第1-8：從起點到村莊，（2）第9-10：從村莊到礦山，（3）第11-12天：挖兩天礦，（4）第13 天-14 天從礦山到村莊，（5）第15-16 天再從村莊，（6）第17-22 天再從礦山返回村莊，（7）第23-25 天：到村莊后因沙暴停留一天，（8）第26-28 天:從村莊返回終點然后結(jié)束。

3.3.3 方案三模型的建立與求解

3.3.3.1 建立方案路線活動內(nèi)容

（1）從起點出發(fā)，所帶水的負(fù)重為540kg，所帶食物的負(fù)重為660kg，購買物資支出總金額為4200 元，總負(fù)重為1200kg；

（2）由Floyd 算法求得的起點到村莊的最短路徑為8，第八天到達(dá)村莊后剩余的水的負(fù)重為464kg，食物的負(fù)重為246kg，需要將剩余的負(fù)重進(jìn)行水的數(shù)量的補充，共補充489kg 的水，購買物資的總支出為1630 元，總負(fù)重為1199kg；

（3）到礦場時，選擇停1 天，挖7 天，然后去村莊進(jìn)行補給。共消耗水的負(fù)重為735kg，消耗食物的負(fù)重為422kg，剩下32kg的食物和0kg 的水；

（4）在村莊進(jìn)行物資的補給，購買水的質(zhì)量為108kg，購買食物的質(zhì)量為48kg，這里購買物資需要消費840 元；

（5）從村莊到達(dá)終點最短路徑為3 天，通過計算，時間和水全部消耗完。

3.3.3.2 求得最優(yōu)解，通過C 語言軟件對模型進(jìn)行求解，可以得到全局最優(yōu)解，在終點時得到的總資金最大為10430 元。

3.3.3.3 總結(jié)三個方案進(jìn)行數(shù)據(jù)比較，得出方案三的結(jié)果為最優(yōu)。因此，最優(yōu)方案的最大總資金數(shù)為10430 元。