程 凱 邵義聰 何 欽

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

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

1 問題分析

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

2 模型的建立與求解

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

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

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

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

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

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

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

最終路線

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

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

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

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

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

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

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

3 結(jié)論

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

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