“穿越沙漠”策略研究

唐杰烽

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

1 問題重述

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

2 模型假設

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

3 定義與符號說明

表1

4 模型的建立與求解

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

4.1.1 模型的建立

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

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

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

計算公式為:

remainMoney=principal-cost

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

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

remainMoney=principal- cost+earnings

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

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

cost=costVillage+costStart

其中:

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

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

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

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

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

4.1.2 問題1 模型的求解

對于第一關,

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

圖1 經過簡化后的第一關地圖

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

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

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

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

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

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

圖2 第二關路線圖

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

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

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

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

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

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

4.2.1 問題2 模型的建立

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

以第三關為例,經簡化后的地圖如圖3 所示。

圖3 簡化后的第三關地圖

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

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

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

Step4.將是否前往礦山采礦或到村莊進行物資補給納入考慮。由于本題的天氣未知,玩家只能知道當天的天氣情況作出抉擇。所以注意到不同天氣情況下基礎收益和采礦消耗之間的關系,以下為涉及到采礦時的基礎模型。basicEarning為基礎收益(單位:元/天),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)

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

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

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

4.2.2 問題2 模型的求解

對于第三關,

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

圖4 簡化后的第三關地圖

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

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

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

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

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

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

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

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

假設1:前四天都是晴朗,利用

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

可得兩種方案的cost 相同。

剩余資金為:

remainMoney=principal-cost=10000-cost

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

經計算,可知考慮天氣的行走決策方案的優點為在前8 天中高溫天氣時間少于4 天,且前4 天中出現高溫天氣所產生的cost 要比不考慮天氣時所產生的cost 低。

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

對于第四關,

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

圖5 簡化后的第四關地圖

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

解得路徑為:

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

圖6 第四關路線圖

問題3 的解答:

根據問題2 第三關得出唯一最短路徑為

5 結論

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