“穿越沙漠”游戲最短路徑研究

程 凱 邵義聰 何 欽

（華東理工大學信息科學與工程學院，上海200000）

在沙漠的地理環(huán)境下進行穿越活動需要考慮到相關(guān)地理、水文及食物等條件的制約，極大的限制著相關(guān)人員在沙漠地區(qū)活動路線的選擇。沙漠占據(jù)地球陸地面積的1/4，沙漠天氣和氣候?qū)θ蛏鷳B(tài)、環(huán)境及氣候等的影響一直都受到社會各界極大關(guān)注[1]。在游戲背景中針對不同的地圖，設(shè)有不同地區(qū)，例如礦山和村莊會有相應(yīng)的材料補充，同樣也會投入一些物品。在沙漠途中不同的天氣條件、不同的路線選擇可能會加劇食物的消費也可能會得到相關(guān)食物補充的機會。因此，不同的路線選擇方案以及初始點攜帶物品的數(shù)量及比例將會決定能否按時到達終點以及極大的影響到達終點所剩的資金數(shù)量。

1 問題分析

游戲開始時為第0 天，須在規(guī)定時間內(nèi)到達終點，且每日路線選擇只能在相鄰地區(qū)進行。根據(jù)初始資金購買水和食物，原地停留有基礎(chǔ)消耗且行走一天消耗加倍，且到達終點前不能消耗至0。到達終點后如有剩余食物和水退回基準價格的一半。共有三種可能的天氣情況：“晴朗”、“高溫”、“沙暴”。沙暴日必須原地停留一日。在礦山挖礦一天可獲得基礎(chǔ)收益，消耗資源數(shù)為基礎(chǔ)消耗的3 倍，且到達礦山當天不能挖礦。沙暴日可挖礦，在村莊時可購買水和食物，價格為基準價格的2 倍。在已知天氣的情況下，首先需要針對路線進行分析得到能夠節(jié)省最多花費的路線。其次，在只知道當天天氣條件下，如何選擇能使一名玩家在達到終點時獲得最多的資金。針對所有天氣狀況已知的情況下，兩名玩家需要在第0 天規(guī)劃好所有行程，但兩人同行或同時挖礦會造成消耗的增加及收益的減少，同樣在多人同行時會增大消耗并降低挖礦收益，且只能獲取當天的天氣狀況。知曉其他玩家的資源剩余數(shù)量。

2 模型的建立與求解

首先假設(shè)所有游戲規(guī)定的天數(shù)下均沒有沙暴天氣，分別計算出起點、村莊、礦山以及終點之間的最短的天數(shù)。為了在終點獲得更多的資金總額，分別計算出：起點一終點；起點一礦山（多次）-T 終點兩條路線的總花費，同時計算出沿途需要的食物和水的質(zhì)量并考慮攜帶的質(zhì)量限制。如若沿途任意時間點的食物和水不足以支撐當天的消耗，則需更改路徑，考慮去村莊補充食物及水。選擇起點至終點最短路徑可以消耗較少的食物和水因而獲得較多的剩余資金。然而，途徑礦山采礦在部分天氣條件下可以掙的額外的收入，可以獲取額外收入因此考慮先以最短路徑前往礦山進行挖礦。需要注意的是：在起點時購買物資需要考慮攜帶物資重量的同時觀察到食物的價格比水的價格高且質(zhì)量較輕。

因此可以考慮在起點時相對多購買食物少購買水，并在村莊進行相對較多的飲用水補給，降低在村莊的食物補給。而在第二條選擇當中，需要考慮到挖礦過程中天氣狀況，由于挖礦過程中的消耗為基礎(chǔ)消耗的3 倍，且高溫天氣和沙暴天氣相比，因此需要權(quán)衡挖礦的天數(shù)和挖礦的時間在暴雨或高溫天氣時可能依據(jù)之后的天氣狀況暫停挖礦。如公式所示為在沙暴天氣條件下的挖礦實際獲得資金數(shù)：

闡述了在沙暴天氣條件次下，挖礦一天獲得的凈收益，事實上由于挖礦的巨大消耗，在凈收益的計算當中引入了在商店購買水和食物的價格，即：

Stormmoney=1000-30·10-30·20=100

事實上除了挖礦一天的資金凈收入，由于特殊天氣狀況會出現(xiàn)高溫、沙暴天氣的連續(xù)出現(xiàn)，經(jīng)常需要計算評估在到達礦山后為了減少高溫或沙暴天食物和水的消耗而停留一天，再進行挖礦作業(yè)的資金凈收入，因此列出在礦山停留一天的凈收入：

礦山停留一天的凈收入由兩部分表示：沙暴天氣下停留一天的消耗，晴朗天挖礦工作一天的消耗，即：

如此選擇停留一天，實則多積贊了30 元資金，但與此同時需要多消耗一天時間且需要特殊的天氣條件。依據(jù)此原則，遍歷所有可能的即可得到最優(yōu)路徑及最終的金額總數(shù)。通過Matlab 程序即可得到最優(yōu)線路，如下圖所示：

最終路線

其中在23 號區(qū)域停留兩天，9 號區(qū)域停留兩天，12 號礦山區(qū)域共停留9 天，其中挖礦7 天。由于在終點水和食物的換算價格僅為起始點的一半，故在到達終點時要盡可能使得剩余食物和水消耗完畢，Matlab 程序最終給出的剩余總資金為10430 元，在23 號到達終點。

此線路的最終結(jié)論顯然優(yōu)于直觀的從起點走至終點的9705 元。玩家判斷自己離開礦山時間的判斷機制：考慮反向問題，滿足如下兩個條件即可留在礦山：身上的物資足夠自己再進行挖礦一天并且回到村莊，即物資>行動2 天消耗+挖礦一天消耗。消耗計算見判斷機制時間很充裕，不用立刻啟程去終點，即時間>6 天。

若不滿足上述條件，則必須離開礦山。玩家在村莊中，需要購買物資數(shù)量的判斷機制：判斷方法是預(yù)測玩家直到下一次購買物資之前需要消耗多少物資。離開村莊之后可以直接去礦山，也可以去終點，預(yù)測方法為根據(jù)路上消耗一天的食物、路上消耗一天的水、挖礦消耗一天的食物和挖礦消耗一天的水這四個量來評估消耗物資的數(shù)量。若去礦山則消耗物資為：挖礦n天消耗+路程4 天消耗。

其中n（n>2）天與剩余時間有關(guān)若去終點，則消耗物資為：路程3 天消耗從村莊出來后，若時間相對充裕則去礦山挖礦，反之則直接前往終點。

由單人玩家增加為了多人玩家，根據(jù)規(guī)則若多人同時從A區(qū)域遷移到B 區(qū)域（A^B），每個玩家的消耗與同行人數(shù)成正比，且挖礦收益與同行人成反比，同時在村莊購買物資時的價格隨著人數(shù)的多少而翻倍，極大的提高了在村莊消費的成本。

同時還涉及到了天氣已知和天氣未知兩種情況，需要綜合考慮各方影響因素得出可能的路線，假設(shè)多人游戲針對團體的目標為多人集體的剩余資金，僅知道當天的天氣狀況以及當天其他玩家的資源剩余狀況，同時多人同行也會面臨一樣的高消費、低收益問題。[2]

根據(jù)闡述食物和水都需要在村莊進行一定的二倍價格補充，并且最終補充的數(shù)量大約等于獲得的數(shù)量。因此食物平均價格約為15 元，水平均價格約為7.5 元可以計算得出，當高溫天與沙暴天總和較多時，輪流工作反而虧損金錢。由于計算中還沒有考慮沙暴天氣的影響，如果沙暴天氣出現(xiàn)在路程中，相比單人工作時，會額外虧損金錢，因此輪流工作大部分情況下不如單人工作，故舍棄輪流挖礦的計劃。

3 結(jié)論

對于天氣未知的情況，顯然無法保證總是取到最優(yōu)的方案，因此應(yīng)當對天氣未知時模型可能出現(xiàn)的誤判作分析，誤差來源于兩個方面：停留時間引起的誤差。如果在高溫天試圖等待晴朗天以方便挖礦或者行動，但若未來不出現(xiàn)晴朗天，就浪費了等待的時間，這就是停留時間錯誤。每額外停留一天，會增加消耗135 元。

但是根據(jù)函數(shù)可以得知，在不出現(xiàn)極端天氣情況下（如連續(xù)15 個晴朗之后出現(xiàn)連續(xù)15 個高溫）通常只會等待1-2 天，因此額外消耗的金錢是有限的。物資購買引起的誤差。當預(yù)計消耗的物資大于實際消耗的物資時，就會出現(xiàn)物資購買過多的情況，如果出現(xiàn)額外購買，額外購買的物資數(shù)量大約等于一天的消耗，即100 元左右。