“穿越沙漠”策略研究

唐杰烽

(五邑大學 智能制造學部,廣東 江門 529020)

1 問題重述

玩家憑借一張地圖,利用初始資金購買一定數(shù)量的水和食物(包括食品和其他日常用品),從起點出發(fā),在沙漠中行走。途中會遇到不同的天氣,也可在礦山、村莊補充資金或資源,目標是在規(guī)定時間內(nèi)到達終點,并保留盡可能多的資金。

2 模型假設(shè)

(1)假設(shè)題目所給的數(shù)據(jù)真實可靠；(2)假設(shè)晴朗,高溫,沙暴出現(xiàn)的概率分別為P(Sunny),P(Hot)、P(Sand)；(3)假設(shè)第四關(guān)的沙暴天氣不會出現(xiàn)在玩家最后前往終點的路上,導(dǎo)致玩家中途游戲失?。?4)假設(shè)兩個玩家都以游戲勝利為目標,即最多剩余資金為目標進行活動且不會出現(xiàn)回退的情況。

3 定義與符號說明

表1

4 模型的建立與求解

4.1 問題1 的模型建立與求解

4.1.1 模型的建立

Step1.將附件中的地圖進行簡化,構(gòu)建一個只存在起點、終點、礦山、村莊的無向圖。

Step2. 使用Dijkstra 算法在簡化后的地圖中選取物理最近的路徑,結(jié)合天氣情況和負重計算購買的物資數(shù)量從而得出剩余資金。

根據(jù)天氣情況將每天所要花費的食物和水的箱數(shù)存入二維矩陣needEat 中,其中第一行為水的數(shù)量(單位:箱),第二行為食物的數(shù)量(單位:箱)。remainMoney用以表示剩余資金,principal 表示初始資金,cost 表示用于購買水和食物所花費的資金。

計算公式為:

remainMoney=principal-cost

其中cost 是每天所購買的水和食物所花費的資金的總和。waterprice 和foodprice 分別表示水的基準價格(單位:元/箱)和食物的基準價格(單位:元/箱)。needEat[1][i]表示根據(jù)當天天氣情況所確定的水的消耗量(單位:箱),needEat[2][i]表示根據(jù)當天天氣情況所確定的食物的消耗量(單位:箱)。LoadMax=1200kg.

Step3.將是否前往礦山采礦或到村莊進行物資補給納入考慮。basicEarning為基礎(chǔ)收益(單位:元/天),earnings 表示玩家采礦所得的總收益,則剩余資金remainMoney 的計算公式如下:

remainMoney=principal- cost+earnings

由于加入了在村莊購買物資的費用和在礦山采礦時提升的費用成本,故將總花費cost 分解成村莊花費(costVillage)、起點購買物資的花費(costStart)。

此時,總花費cost 的計算公式如下:

cost=costVillage+costStart

其中:

因為村莊購買物資的成本為基準價格的2 倍,因此村莊花費如下:

村莊花費costVillage =2(costMining+costWalking)

利用時間節(jié)點來區(qū)分起點花費和村莊花費,即利用在村莊采購的日期flag 來標記,可知日期1 至flag 日期為起點花費；flag日期至結(jié)束日期為村莊花費。

earnings 是玩家采礦所得的總收益,用date[earning]來記錄開始采礦的時間,則earnings 的計算公式如下:

Step4.比較上述兩種模式(物理遠近和前往礦山采礦)的剩余資金remainMoney,取所剩余資金較多的方案為目標方案。

4.1.2 問題1 模型的求解

對于第一關(guān),

Step1.將不規(guī)則的路徑進行數(shù)字化處理,即利用矩陣存儲,并通過Dijkstra 算法對路徑進行簡化,得出一幅只有起點、終點、礦山和村莊為頂點的無向圖,如圖1 所示。

圖1 經(jīng)過簡化后的第一關(guān)地圖

由costStart 的第二個計算公式可得根據(jù)物理遠近從起點到終點所耗費的資金為cost=590(元)。剩余資金remainMoney=principal-cost=10000-590=9410(元)。

由costStart 和cost 的計算公式可解得cost=7805(元),挖礦天數(shù)為 MineDay1+MineDay2=8+3 (天)=11 (天),故earnings=11000(元)。

則前往礦山采礦的方案剩余資金為remainMoney=1 2195(元 )

對于第二關(guān),將不規(guī)則的路徑進行數(shù)字化處理,即利用矩陣存儲,并通過Dijkstra 算法對路徑進行簡化,由第二關(guān)的地圖可知,礦山30 到村莊62 的距離相較于村莊39 遠,而礦山55 到村莊39 比到村莊62 的路程更遠,且與通向終點的路徑相背。則由最短路徑優(yōu)化思想將上述兩條較遠的路線剔除。

Step2.根據(jù)Step1 所得出的最短路徑,再次利用Dijkstra 算法,求解出從起點到終點的物理上的5 條帶相同權(quán)的路徑,將其中兩條路徑結(jié)合可得出第6 條路徑分別為:

由cost 的計算公式可得可得根據(jù)物理遠近從起點到終點所耗費的資金為 cost=2810 (元)。 剩余資金為remainMoney=principal-cost=10000-2810=7190(元)。

圖2 第二關(guān)路線圖

Step3. 將是否前往礦山采礦或到村莊進行物資補給納入考慮。從起點出發(fā)前往礦山30 采礦5 天,隨后前往離其最近的村莊39,補給后前往礦山55,再次采礦9 天,隨后2 天前往終點。

利用Dijkstra 算法求解出按照路線從起點到終點的最短路徑為

由cost 和costStart 的計算公式可解得cost=7080(元),挖礦天數(shù)為 MineDay1+MineDay2=5+8 (天)=13 (天),故earnings=13000(元)。

則前往礦山采礦的方案剩余資金為remainMoney=1 5920(元 )

Step4. 將上述兩個方案的剩余資金remainMoney 做比較,取大者,則前往礦山采礦的方案作為玩家的最優(yōu)策略。

4.2 問題2 模型的建立與求解

4.2.1 問題2 模型的建立

Step1. 對附件中的第三關(guān)、第四關(guān)地圖進行簡化,利用Dijkstra 算法構(gòu)建幾個特殊端點之間的最短路徑。特殊端點指的是起點、終點、礦山和村莊。從而得到一個只含有特殊端點的無向圖。

以第三關(guān)為例,經(jīng)簡化后的地圖如圖3 所示。

圖3 簡化后的第三關(guān)地圖

Step2.由于天氣未知且玩家可根據(jù)當天天氣來做出當天的行動決策,題目條件中沙暴天氣出現(xiàn)的幾率較低,因此在考慮玩家行動策略時,不考慮沙暴天氣對行動策略的主要影響,而將晴朗行走與高溫行走的物資消耗納入主要決策范圍。

Step3. 使用Dijkstra 算法在簡化后的地圖中選取物理最近的路徑,結(jié)合天氣情況和負重計算購買的物資數(shù)量從而得出剩余資金。

根據(jù)天氣情況將每天所要花費的食物和水的箱數(shù)存入二維矩陣needEat 中,其中第一行為水的數(shù)量,第二行為食物的數(shù)量。remainMoney 用以表示剩余資金,principal 表示初始資金,cost 表示用于購買水和食物所花費的資金。

Step4.將是否前往礦山采礦或到村莊進行物資補給納入考慮。由于本題的天氣未知,玩家只能知道當天的天氣情況作出抉擇。所以注意到不同天氣情況下基礎(chǔ)收益和采礦消耗之間的關(guān)系,以下為涉及到采礦時的基礎(chǔ)模型。basicEarning為基礎(chǔ)收益(單位:元/天),earnings 表示玩家采礦所得的總收益,則剩余資金remainMoney的計算公式如下:

remainMoney=principal- cost+earnings

由于加入了在村莊購買物資的費用和在礦山采礦時提升的費用成本,故將總花費cost 分解成村莊花費(costVillage)、起點購買物資的花費(costStart)。

因為村莊購買物資的成本為基準價格的2 倍,因此村莊花費如下:

村莊花費

costVillage =2(Day*P(Sunny)*C_Walking in Sunny Day+Day*P(Hot)*C_Resting in Hot Day+Day*P(Sand)*C_Resting in Sand Day)

利用時間節(jié)點來區(qū)分起點花費和村莊花費,即利用在村莊采購的日期flag 來標記,可知日期1 至flag 日期為起點花費；flag日期至結(jié)束日期為村莊花費。

earnings 是玩家采礦所得的總收益,用date[earning]來記錄開始采礦的時間。

Step4.比較上述兩種模式(物理遠近和前往礦山采礦)的剩余資金remainMoney,取所剩余資金較多的方案為目標方案。

4.2.2 問題2 模型的求解

對于第三關(guān),

Step1. 將不規(guī)則的路徑進行數(shù)字化處理,即利用矩陣存儲,并通過Dijkstra 算法對特殊端點之間的路徑進行簡化,得出一幅只有特殊端點的無向圖,如圖4 所示。

圖4 簡化后的第三關(guān)地圖

因天氣未知,所以玩家需要通過當天的天氣做出當天的行動策略。題目能唯一確定的是10 天內(nèi)不可能出現(xiàn)沙暴天氣。玩家行走策略的主要評估對象為晴朗天氣下的行走與高溫天氣下的行走和休息之間的消耗關(guān)系。

Step2. 通過附件中所附帶的基礎(chǔ)消耗量(箱)可算得

晴朗天氣行走一天的總花費C_WalkinginSunnyDay=1 10(元 )

高溫天氣行走一天的總花費C_WalkinginHotDay= 270( 元)

高溫天氣休息一天的總花費C_restinginHotDay= 135( 元)

玩家從一個區(qū)域移動到與其相鄰的另一區(qū)域,以玩家的耗費的角度來做計算,高溫行走所耗費的資金要大于高溫休息一天后晴天行走所耗費的資金。根據(jù)Step1 所得的簡化地圖可知,在時間為10 天的情況下,完成物理遠近的路線的路徑最短所需時間為4 天,即不考慮用3 天時間完成從一個區(qū)域到另一區(qū)域的移動。由此可得,玩家的基本行走策略為:如果當天為高溫,則不行走,晴朗則行走,且附加約束條件為8 天內(nèi)走完全部路程。

Step3. 使用Dijkstra 算法在簡化后的地圖中選取物理最近

的路徑,解得路徑為:。由于整個游戲時間段中,玩家僅知道當天的天氣情況,故作以下幾種特殊情況的假設(shè),并與不考慮天氣直接完成該路徑的決策作比較。

假設(shè)1:前四天都是晴朗,利用

cost=Day*(P(Sunny)*C_Walking in Sunny Day)+P(Hot)*C_Resting in Hot Day)

可得兩種方案的cost 相同。

剩余資金為:

remainMoney=principal-cost=10000-cost

假設(shè)2:前四天中有兩天是高溫天氣,且前六天中只有兩天高溫,利用如假設(shè)1 相同的公式可算得不考慮天氣的行走決策方案的cost 大于考慮天氣的行走方案決策的cost。

經(jīng)計算,可知考慮天氣的行走決策方案的優(yōu)點為在前8 天中高溫天氣時間少于4 天,且前4 天中出現(xiàn)高溫天氣所產(chǎn)生的cost 要比不考慮天氣時所產(chǎn)生的cost 低。

Step4.將是否前往礦山采礦納入考慮。由于游戲規(guī)則指出玩家的基礎(chǔ)收益僅為200 元/天,而晴朗采礦產(chǎn)生的消耗為135 元/天,高溫天氣消耗為405 元/天,在有基礎(chǔ)收益少于采礦消耗的可能性下,途徑礦山再到終點的最短路徑要比物理最短路徑多出一天的路程。可算得至少要在晴朗采礦3 天才可減小與物理最短路徑之間的差距。但該條件出現(xiàn)的要求較為苛刻,即大概率情況下,前往礦山都將造成過多的支出,難以達到前往礦山采礦獲得收益的目的。故在第三關(guān)中,不考慮玩家前往礦山進行采礦。

對于第四關(guān),

Step1. 將不規(guī)則的路徑進行數(shù)字化處理,即利用矩陣存儲,并通過Dijkstra 算法對特殊端點之間的路徑進行簡化,得出一幅只有特殊端點的無向圖,如圖5 所示。

圖5 簡化后的第四關(guān)地圖

Step2. 使用Dijkstra 算法在簡化后的地圖中選取物理最近的路徑,由于題目表述“30 天內(nèi)極少出現(xiàn)沙暴”,故本文不考慮玩家在最后一段前往終點的路途中遭遇沙暴天氣導(dǎo)致到達不了終點的情況。

解得路徑為:

Step3.考慮礦山采礦或村莊補給物資的情況。(圖6)

圖6 第四關(guān)路線圖

問題3 的解答:

根據(jù)問題2 第三關(guān)得出唯一最短路徑為

5 結(jié)論

本文所提出的模型較為簡潔、簡單易懂,故可在日常生活中方便應(yīng)用；模型的求解較為簡單、方便；模型的普適性較強,推廣度更大。不足之處在于文章解答的環(huán)境均處于較為理想的狀態(tài),故需考慮的因素還有待發(fā)掘；模型的求解需要較高的編程基礎(chǔ),涉及到強化學習。模型可以進一步推廣作為一些生存游戲的觀察設(shè)計的基準,因涉及到許多的生存參數(shù),例如:食物與水的重量分配、在游戲設(shè)計中,可以在此處添加更多的相關(guān)參數(shù),例如:攻擊、防御等；可以作為功能型機器人的路徑選擇指標。相關(guān)的生存參數(shù)可推廣為機器人的各項功能指標；3.模型上涉及到大量的概率統(tǒng)計知識,可用于機器學習。