穿越沙漠的小游戲策略

張 敏 張 力 王雪鋒 孟慧慧 邵光祖

（ 1、黃河交通學院數學教研室，河南 焦作454002 2、黃河交通學院智能工程學院，河南 焦作454002）

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

1 問題分析

根據地形使用廣度優(yōu)先遍歷[1]找出任意兩區(qū)域的最優(yōu)路徑。最優(yōu)路徑的選擇從是否挖礦考慮：如果挖礦，則根據動態(tài)規(guī)劃模型求解挖礦天數，從而規(guī)劃在起點時所需儲備的資源；如果不挖礦，根據求得的起點到終點的最短距離以及儲備所需資源，并依據所選的最優(yōu)路徑求解剩余資金。比較兩種情況下不同線路的剩余資金，選擇剩余資金最大的線路填寫“第一關”和“第二關”的結果表。

2 模型的建立與求解

2.1 游戲第一關的分析與求解

游戲中只有一名玩家，并且在整個游戲時段內每天的天氣狀況事先全部已知，尋找一般情況下玩家的最優(yōu)策略，即尋找從起點到終點的最優(yōu)路徑。

使用廣度優(yōu)先搜索遍歷方法，遍歷的步驟如下：

（1）從起點1 出發(fā)，訪問1 區(qū)域。

（2）依次訪問1 的各個未曾訪問過的相鄰區(qū)域2，25。

（3）分別從這些相鄰的區(qū)域出發(fā)依次訪問該區(qū)域的相鄰區(qū)域，并使“先被訪問區(qū)域的相鄰區(qū)域”先于“后被訪問區(qū)域的相鄰區(qū)域”被訪問。

（4）重復步驟（3），直至地圖中所有已被訪問的區(qū)域的相鄰區(qū)域都被訪問到。

一般情況下，玩家的最優(yōu)策略確定原則從是否挖礦方面考慮，可以分為兩種方案。

表1“第一關”最優(yōu)策略的部分結果表

方案一：從起點走最短路徑直接到終點（不考慮挖礦）。

要想在規(guī)定時間內到達終點并盡大可能保留最多資金，則需要減少在路途上的消耗，所以需要用最短的時間從起點到達終點。從起點到終點花費最短時間的行動方案為：1（起點）→25→26→27（終點）。

為了使得玩家在到達終點時減少物資的剩余量，降低玩家到達終點后退回的剩余物資總量，從而避免在起點購買太多的物資造成資金浪費的目標，所以需要確定在起點時路程上需要的物資總量。使用Matlab 軟件計算在該行動方案中路程上物資的消耗量，通過逆推求解出需要在起點購買水21 箱，食物19箱，負重101 千克，到終點時剩余資金9705 元。

方案二：從起點到終點的路徑考慮去礦山挖礦。

將起點到村莊分為第一階段，村莊到礦山再返回村莊為第二階段，村莊到終點分為第三階段。使用廣度優(yōu)先遍歷方法，得出第一階段的最優(yōu)路徑為1（起點）→25→24→23→22→9→15（村莊）。

根據第一階段的最優(yōu)路徑和附件中給出的天氣狀況，得到第一階段的行程為：第零天在1 區(qū)域（起點），第一天行走到25區(qū)域，第二天行走到24 區(qū)域，第三天行走到23 區(qū)域。由于第四天是沙暴天氣，所以需要原地停留，故第四天仍舊是停留在23區(qū)域。第五天行走到22 區(qū)域，第六天行走到9 區(qū)域，由于第七天是沙暴天氣，所以需要原地停留，故第七天仍舊是停留在9 區(qū)域。第八天行走到15 區(qū)域。

第二階段為從村莊到礦山再到村莊，使用廣度優(yōu)先遍歷的方法得到該階段最短的路徑有兩條分別為：15（村莊）→13→12（礦山）→14→15（村莊）和15（村莊）→14→12（礦山）→13→15（村莊）。為了使玩家在到達終點時剩余最多的資金，所以在該階段考慮通過挖礦來獲取外來資金。由于挖礦需要考慮天氣狀況，所以根據該階段的最短路線和附件中的天氣要分析沙暴日是否挖礦。最壞情況為挖礦需要的資源全部到村莊購買。因為最壞情況下挖礦一天消耗的資金小于基礎收益，所以沙暴天氣需要挖礦。因為晴朗和高溫天氣比沙暴天氣條件下的基礎消耗量少，所以晴朗和高溫天氣更需要挖礦。

根據第二階段的行程求解第二階段所需要的總物資。根據附件中給出的天氣情況列出不同天氣條件下行走或停留時所需物資量。

晴朗天氣行走一天消耗物資質量是58 千克，晴朗天氣停留一天消耗物資質量是29 千克，高溫天氣行走一天消耗物資質量是72 千克，高溫天氣停留一天消耗物資質量是36 千克，沙暴天氣挖礦時一天消耗物資質量是150 千克，沙暴天氣不挖礦時每天消耗物資質量是50 千克。

附件給出的信息得到玩家的負重上限為1200 千克，所以在第二階段物資需求量不超過1200 千克的情況下應該挖選擇挖礦天數最多的路徑，通過計算挖礦最大天數為7 天。根據挖礦的最大天數和第二階段在其他區(qū)域的需求量，計算得到第二階段需要水245 箱，食物221 箱?？紤]在村莊購買物資比較貴，所以要在起點購買足夠量的物資。因為食物的基準價格是水的兩倍，所以使用定量的初始資金時要以食物優(yōu)先（只需備足一定量的水）。使用Matlab 軟件求得：在起點時，需要購買水180 箱，食物330 箱，負重總量1200 千克，剩余初始資金5800 元。

根據天氣情況、第二階段的最優(yōu)線路和最大挖礦天數確定第二階段的行程為：第九天行走到14 區(qū)域，第十天從14 區(qū)域行走到12（礦山），第十一天至第十七天在礦山挖礦（共計挖礦八天）。由于沙暴天氣第十八天在12（礦山）區(qū)域停留，第十九天從12（礦山）區(qū)域走到14 區(qū)域，第二十天從14 區(qū)域走到15 區(qū)域（村莊）。

由于第三階段是從村莊回到終點，為了減少該階段玩家在行程上資源的消耗，所以該階段的最優(yōu)路徑為最短路徑。運用廣度優(yōu)先搜素遍歷方法得到第三階段的最短路徑為：15（村莊）→9→21→27（終點）。

根據最短路徑確定第三階段的行程為：第二十一天行走到9 區(qū)域，第22 天行走到21 區(qū)域，第23 天行走到27 區(qū)域（終點）。

根據第三階段行程上的物資消耗情況求解第三階段物資購買數量。使用Matlab 軟件求解出第三階段需要在村莊購買水36 箱，食物19 箱，此時的剩余資金為4170 元。該方案第23 天到達終點，此時剩余水量為0 箱，剩余食物量為0 箱，剩余資金數為10430 元。

比較第一關的兩種方案，發(fā)現方案二比方案一的剩余資金數大，據此得出本關游戲玩家的最優(yōu)的策略為：1→25→24→23→22→9→15（村莊）→14→12（礦山）→14→15（村莊）→9→21→27（終點）。

利用Matlab 軟件計算出第一關玩家每天的結果。如表1。

2.2 游戲第二關的分析與求解

第二關尋找最優(yōu)策略的方案與第一關相似。觀察第二關的地圖可以發(fā)現有兩個村莊和兩個礦場（其中一個礦山位于30 區(qū)域，距離起點近）。

為保證單次路線中挖礦天數最長，根據貪心算法得到從起點到終點的最優(yōu)策略是玩家需要先從起點到離礦山區(qū)域最近的村莊購買能夠達到最佳狀態(tài)的物資后再去挖礦。挖礦結束后要使剩余的物資能夠到達距離挖礦礦山最近村莊，以便于回到村莊進行購買物資。根據廣度優(yōu)先遍歷方法，得出在購買物資后，從村莊到礦山再到終點的最短天數比從村莊直接到達終點的最短天數多1 天。使用Matlab 軟件計算出在礦山區(qū)域挖礦的最大天數為4 天。

表2“第二關”最優(yōu)策略的部分結果表

根據上述分析和第二關的地圖，把起點到終點的路線分為三個階段，第一階段為從起點直接到39 區(qū)域（村莊），第二階段為從39 區(qū)域（村莊）到30 區(qū)域（礦山），在該區(qū)域挖最大天數的礦后回到39 區(qū)域（村莊），第三階段為從39 區(qū)域（村莊）到55 區(qū)域（礦山）挖礦后直接回到64 區(qū)域（終點）。

使用廣度優(yōu)先遍歷方法，從起點到30 區(qū)域的礦山區(qū)的最短路徑為7 步，分別為：

第一條路徑為：1（起點）→2→10→19→27→28→29→30（礦山）

第二條路徑為：1（起點）→2→3→4→5→13→22→30（礦山）

第三條路徑為：1（起點）→2→10→19→20→28→29→30（礦山）

從30 區(qū)域（礦山）到39 區(qū)域（村莊）最短路徑為1 步，根據廣度優(yōu)先搜索遍歷得到從1（區(qū)域）起點到39 區(qū)域（村莊）的最短路徑就是最優(yōu)路徑。分析求解發(fā)現第一階段的最短路徑線路不唯一，但都是七步，所以無論選擇哪一條路徑行走物資的消耗量都是相等的。

由附件給出的信息得到負重上限為1200 千克。所以在第二階段物資需求量不超過1200 千克的情況下應該挖最大天數的礦，通過計算挖礦的最大天數為7 天。根據挖礦的最大天數和第二階段在其他區(qū)域的需求量，計算得到第二階段需要首先在村莊購買水195 箱，食物0 箱?？紤]在村莊購買物資比較貴，所以要在起點購買足夠量的物資。因為食物的基準價格是水的兩倍，所以使用定量的初始資金時要以食物優(yōu)先（只需備足一定量的水）。使用Matlab 軟件求得：在起點時，需要購買水166 箱，食物350 箱，負重總量1198 千克，剩余初始資金5670 元。

先去30 區(qū)域（礦山）挖礦，直到消耗后所剩的物資和水僅支持從30 區(qū)域（礦山）轉移到39 區(qū)域（村莊）。根據第三階段玩家在路上的物資消耗量確定回到村莊時需要第二次購買水157箱，食物140 箱，剩余初始資金7350 元。

分析第三階段從39 區(qū)域（村莊）出發(fā)直接到達終點時的線路，根據地圖得出該階段的最短線路不唯一，但是最短線路上玩家的消耗量是相同的。到達終點時剩余水量0 箱，食物0 箱，剩余資金數12350 元。

使用Matlab 軟件計算出玩家在一般情況下第二關的最優(yōu)策略的結果。結果如表2。

該方案顯示玩家在第30 天到達終點時，此時剩余水量為0箱，剩余食物量為0 箱，剩余資金數為12350 元。

3 結論

從是否挖礦角度出發(fā)，如果挖礦，則根據動態(tài)規(guī)劃模型求解挖礦天數，從而規(guī)劃在起點時所需儲備的資源；如果不挖礦，根據求得的起點到終點的最短距離以及儲備所需資源，依據所選的最優(yōu)方案計算剩余資金。