分布優化模型下穿越沙漠游戲攻略

前言：想要寫出一篇引人入勝的文章？我們特意為您整理了分布優化模型下穿越沙漠游戲攻略范文，希望能給你帶來靈感和參考，敬請閱讀。

摘要：穿越沙漠游戲非常有趣，受資金、水、食物及天氣的限制，成功完成游戲有一定的困難。本論文根據游戲的不同設定，建立穿越沙漠游戲的數學模型，得到行動路線最優策略。對于第一關，首先，以剩余資金為目標函數，以水、食物及天氣為約束條件，分別建立不經過礦山到達終點和途徑礦山到達終點的最優策略模型。然后，通過比較剩余資金，得到最優路線為1→5→6→13或1→4→6→13，且在初始起點備54箱水和食物。對于第二關，首先，根據沙暴出現的概率，建立路線分步優化模型，利用決策樹算法，得到不同沙暴出現次數的最優策略。最后，給出一般情況下玩家的最佳策略（見表1）。

關鍵詞：穿越沙漠；分步優化模型；Dijkstra算法；最短路徑算法

1模型建立與求解

1.1針對第一關

首先將地圖轉化為點和線組成的無向圖[1]，如圖1所示。其中，“1”為起點，“13”為終點。接著利用Dijkstra算法[2，3]對從起點到礦山、礦山到終點和起點到終點的最短路徑求解。觀察分析可得出起點到礦山和起點到終點的最短路徑都是需行走三天，因為前三天整個地圖的天氣一樣，所以從起點去礦山或者直接去終點所消耗的資源一樣。因此只需要計算方案二到達礦山后挖礦賺取的收益與從礦山到達終點消耗資源金額的對比，從而確定最優策略。假設方案二到礦山后的7天全部為晴朗，計算所得的收益與消耗之間的關系如下：其中Bw1為行走時所消耗的水；Bf1為行走時所消耗的食物；Bw2為在礦山所消耗的水；Bf2為在礦山所消耗的食物；ω為花費金額。

1.2針對第二關

首先，從起點到村莊，走其最短路徑。通過計算發現在前四步跨區域的行程中，無論經歷的沙暴是0天還是9天，都要回村莊補給完畢后再去挖礦所得經濟效益最高。所以無論沙暴出現在哪一天，從起點出發的第一步都是都是前往村莊。在到達村莊前，最壞的情況為遭遇9天沙暴且行進時為高溫天氣，所以在起點要備足經歷9天沙暴和5天高溫行程的水和食物，又要保證在村莊補給所花費的資金最少，因此帶到的村莊的極限水量，剩余容量全部帶食物，以盡量減少食物在村莊的購買，即在起點所購資源為180箱水和330箱食物。然后，對第二關的地圖進行無權重、無方向的抽象表達（如圖2），其中“1”為起點，“25”為終點。觀察發現其為矩形的路線圖，到達目的地有多種路線。于是我們在最短的路徑中任意選擇一條路線進行標記（如圖3）。在眾多路徑當中會出現影響決策的路徑，稱為關鍵路徑。假設天氣最壞的情況發生在每一段關鍵路徑上，作為決策判斷的依據。連續幾天集中發生沙暴為最壞的天氣情況，以最壞的結果作為依據，在關鍵點統計沙暴出現的結果對列舉的幾種情況進行匹配，按照符合的情況對購買水和食物和挖礦天數進行決策。具體出現連續沙暴天氣的情況：情況一：出現在第一階段（圖3中1→2→3→8→12→村莊14）：解決策略1：到達村莊時在起點準備的水剛好到極限，因為不同天氣對水和食物消耗均接近1:1，所以后續補充水和食物以1：1的比例補充至背包承重的上限，即240箱水、240箱食物。因為9次沙暴在第一階段全部發生過，后續的天氣按照高溫計算，后續會出現兩次抉擇的地方，通過計算比較選出最優方案，如圖3所示，從起點→村莊（離開時備足240箱水和240箱食物）→礦山（工作6天）→終點為最優方案。情況二：出現在第二階段（圖3中村莊14→19）的村莊。沙暴出現在村莊上可以隨時補充食物和水即出發時可以帶足夠的水和食物，240箱食物，240箱水。對后續的路程進行比較和選擇，確定出最佳路線，與第一種解決策略相同。情況三：出現在第二階段（圖3中村莊14→19）的19號區域。解決策略2：那么就面臨兩大抉擇：回村補給還是直接去礦山，兩個抉擇又面臨著不同的選擇。窮舉不同的方案選擇出最優的方案，即起點→村莊（補充水為225箱，食物不增加）→19號區域（因沙暴阻礙行動9天）→礦山（工作兩天）→終點。情況四：出現在第二階段（圖3中19→礦山18）的礦山上。解決策略3：面臨兩大抉擇是回村補給還是直接去礦山，兩個抉擇的后面又有不同的選擇，窮舉不同的方案選擇出最優的方案，最優的方案為起點→村莊（補充水到240箱）→礦山（工作三天休息六天）→村莊（水補充到225箱，食物補充到225箱）→礦山（工作五天）→終點。情況五：出現在第三階段（圖3中礦山18→19）的19號區域。解決策略4：最優的行進路線為起點→村莊（補充水到240箱）→礦山（工作兩天）→19號區域（阻礙行進9天）→村莊（水補充到225箱，食物補充到225箱）→礦山（工作5天）→終點。情況六：出現在第四階段（圖3中19→礦山14）的村莊。解決策略5：最優的行進路線為起點→村莊（補充水到240箱）→礦山（工作六天）→村莊（水補充到54箱，食物補充到54箱）→終點。情況七：出現在第五階段（圖3中村莊14→15→20→終點25）的路徑。解決策略6：最優的行進路線為起點→村莊（補充水到240箱）→礦山（工作六天）→村莊（水補充到144箱，食物補充到144箱）→在路徑被阻礙9天→終點。情況八：出現在第六階段（圖3中礦山18→23→24→終點25）的礦山。解決策略7：最優的行進路線為起點→村莊（補充水到240箱）→礦山（工作六天）→村莊（補充水到240箱，食物補充到240箱）→礦山（工作三天休息六天）→終點。情況九：出現在第六階段（圖3中礦山18→23→24→終點25）的從礦山出來到終點的行徑。解決策略8：最優的行進路線為起點→村莊（補充水到240箱）→礦山（工作六天）→村莊（補充水到207箱，食物補充到207箱）→礦山（工作一天）→在路徑被阻礙9天→終點。

2求解結果

對于第一關，因為ωp>ωs，所以即使在7天全部是晴朗的最好的天氣情況下挖礦資源的消耗和跨區域移動消耗的物資的價值也大于挖礦的收益，所以最優的游戲策略就是走最短路徑直接返回終點即。資源的分配為：帶足三天遇到最差天氣（三天高溫）所用的物資，即54箱水和54箱食物。對于第二關，可能連續出現9天沙暴和其余天氣為高溫的情況進行分類匹配，具體的結果見表1。

參考文獻

[1]司守奎,孫兆亮.數學建模算法與應用[M].北京：國防工業出版社,2015.

[2]劉洋洋.基于改進Dijkstra算法的自駕游最優路徑規劃研究[J].科學技術創新,2020(17):75-77.

[3]劉志威,楊莉瓊,謝永勝,劉鵬,佘培培.基于改進Dijkstra算法的川藏鐵路站房工程物資動態調運研究[J].建筑經濟,2020,41(S1):166-170.

[4]趙衛績,鞏占宇,王雯,樊守芳.幾種經典的最短路徑算法比較分析[J].赤峰學院學報(自然科學版),2018,34(12):47-49.

作者:蘇盈文 劉佳園 張向遠 單位:蘭州理工大學理學院 蘭州理工大學機電工程學院 蘭州理工大學計算機與通信學院