穿越沙漠游戲最短路徑策略研究

田欣宇

河北工程大學 河北邯鄲 056002

1 問題分析

一名玩家知道游戲時間段內30天內的全部天氣情況[1]，則可以根據高溫、晴朗和沙暴天氣不同的基礎消耗量來決定初始攜帶的最大資源數量。由于在村莊的資源價格高于較高，因此為保證成功完成穿越沙漠則是否在此購買資源需要結合路線進行具體分析。根據基準價格、基礎消耗量的條件，列出相對應的關系式，并結合負重上限、初始資金得出約束條件，得到線性規劃的模型。首先對地圖應用圖論模型和迪杰斯特拉算法[2]，求解出不同方案下的最短路徑。再結合天氣情況對具體的路線的資源消耗以及收益進行計算，進而確定初始購買資源數量和最終到達終點時的資金。最后用靈敏度分析對第一關和第二關的具體問題進行檢驗，驗證問題的答案是否具有合理性。

2 模型的建立與求解

假設在晴朗天氣和高溫天氣時玩家不原地停留，向相鄰區域前進。目標是在規定時間內到達終點，并保留盡可能多的資金。需要考慮1。初始的水和食物的購買量2。再不超過負重的基礎上水和食物的占比3。所消耗的天數其中包括了受沙暴天氣影響的天數[5]和受不同地區[6]所消耗的天數。所以列出未知數函數方程，使最終收益最大來求解方程。針對最短天數到達終點或最短天數到達礦場兩種情況，采用最短路徑方案，并基于最短路徑下的最大收益模型,得到最大收益要使購買消耗品的資金盡可能少。設在出發地購買水質量為箱，購買食物重量為箱，花費為，則：

并考慮到食物的價值大于水的價值且水的質量大于食物的質量采用0-1背包模型，在基于最短路徑下到達村莊補充食物和水至少需要98箱水和98箱食物即補充約束條件為：

狀態加選擇，定義為裝載重量為W的背包和N個物品，每個物品有重量和價值兩個屬性，其中第i個物品的重量為wt[i],價值為val[i]。代入W=1200，N=2，價值分別為5和10，重量分別為3和2。設在村莊購買的水質量為箱，購買食物重量為箱，花費為，則：

設玩家到達終點之后的總資金為Y，則：

要盡可能使得Y最大，基礎收益最大，基礎消耗最小，同時使得得到終點的水和食物盡可能小。即：

得到線性規劃模型如下：

3 結語

由以上敘述可知此玩家在第一關最佳優化策略分為不經過礦山和經過礦山兩種決策方案，此兩種決策方案分別對應一種最短路徑。對第一關情況進行圖論分析[3]，通過應用迪杰斯特拉算法，得到如圖1所示不經過礦山的最短路徑情況圖，不經過礦山的最短路線為1→25→26→27，此路線僅需考慮天氣因素和食物與水的消耗，不許考慮其他因素。

則可得以下結論：針對本路線假設玩家購買的水和食物剛好到達終點，即剩余資源為零。所以=50+80×2+140+120×2=590在第四天到終點，且剩余資金為9410元。對第一關情況進行圖論分析，通過應用迪杰斯特拉算法,分析可得經過礦場的最短路線為1→25→24→23→21→9→10→11→12→11→10→9→21→27。為獲得途中的補充資源，采取經過村莊的路線，即1→25→24→23→21→9→15→13→12→13→15→9→21→27。計算得到初始購買98箱水和453箱食物即=453，結合天數到達村莊為第八天經歷了兩天沙暴，三天晴朗，三天高溫到達村莊剛好水耗盡繼而購買163箱水不購買食物，沿著區域14，進入礦區12，進行挖礦到十四天然后返回村莊進行購買223箱水，再次趕回礦區進行挖礦在26號出發到村莊購買11箱食物，然后出發至終點實現零剩余。最終資金剩余9900。