分布優(yōu)化模型下穿越沙漠游戲攻略
前言：想要寫出一篇引人入勝的文章？我們特意為您整理了分布優(yōu)化模型下穿越沙漠游戲攻略范文，希望能給你帶來靈感和參考，敬請閱讀。
摘要：穿越沙漠游戲非常有趣，受資金、水、食物及天氣的限制，成功完成游戲有一定的困難。本論文根據(jù)游戲的不同設(shè)定，建立穿越沙漠游戲的數(shù)學(xué)模型，得到行動路線最優(yōu)策略。對于第一關(guān)，首先，以剩余資金為目標函數(shù)，以水、食物及天氣為約束條件，分別建立不經(jīng)過礦山到達終點和途徑礦山到達終點的最優(yōu)策略模型。然后，通過比較剩余資金，得到最優(yōu)路線為1→5→6→13或1→4→6→13，且在初始起點備54箱水和食物。對于第二關(guān)，首先，根據(jù)沙暴出現(xiàn)的概率，建立路線分步優(yōu)化模型，利用決策樹算法，得到不同沙暴出現(xiàn)次數(shù)的最優(yōu)策略。最后，給出一般情況下玩家的最佳策略（見表1）。
關(guān)鍵詞：穿越沙漠；分步優(yōu)化模型；Dijkstra算法；最短路徑算法
1模型建立與求解
1.1針對第一關(guān)
首先將地圖轉(zhuǎn)化為點和線組成的無向圖[1]，如圖1所示。其中，“1”為起點，“13”為終點。接著利用Dijkstra算法[2，3]對從起點到礦山、礦山到終點和起點到終點的最短路徑求解。觀察分析可得出起點到礦山和起點到終點的最短路徑都是需行走三天，因為前三天整個地圖的天氣一樣，所以從起點去礦山或者直接去終點所消耗的資源一樣。因此只需要計算方案二到達礦山后挖礦賺取的收益與從礦山到達終點消耗資源金額的對比，從而確定最優(yōu)策略。假設(shè)方案二到礦山后的7天全部為晴朗，計算所得的收益與消耗之間的關(guān)系如下：其中Bw1為行走時所消耗的水；Bf1為行走時所消耗的食物；Bw2為在礦山所消耗的水；Bf2為在礦山所消耗的食物；ω為花費金額。
1.2針對第二關(guān)
首先，從起點到村莊，走其最短路徑。通過計算發(fā)現(xiàn)在前四步跨區(qū)域的行程中，無論經(jīng)歷的沙暴是0天還是9天，都要回村莊補給完畢后再去挖礦所得經(jīng)濟效益最高。所以無論沙暴出現(xiàn)在哪一天，從起點出發(fā)的第一步都是都是前往村莊。在到達村莊前，最壞的情況為遭遇9天沙暴且行進時為高溫天氣，所以在起點要備足經(jīng)歷9天沙暴和5天高溫行程的水和食物，又要保證在村莊補給所花費的資金最少，因此帶到的村莊的極限水量，剩余容量全部帶食物，以盡量減少食物在村莊的購買，即在起點所購資源為180箱水和330箱食物。然后，對第二關(guān)的地圖進行無權(quán)重、無方向的抽象表達（如圖2），其中“1”為起點，“25”為終點。觀察發(fā)現(xiàn)其為矩形的路線圖，到達目的地有多種路線。于是我們在最短的路徑中任意選擇一條路線進行標記（如圖3）。在眾多路徑當(dāng)中會出現(xiàn)影響決策的路徑，稱為關(guān)鍵路徑。假設(shè)天氣最壞的情況發(fā)生在每一段關(guān)鍵路徑上，作為決策判斷的依據(jù)。連續(xù)幾天集中發(fā)生沙暴為最壞的天氣情況，以最壞的結(jié)果作為依據(jù)，在關(guān)鍵點統(tǒng)計沙暴出現(xiàn)的結(jié)果對列舉的幾種情況進行匹配，按照符合的情況對購買水和食物和挖礦天數(shù)進行決策。具體出現(xiàn)連續(xù)沙暴天氣的情況：情況一：出現(xiàn)在第一階段（圖3中1→2→3→8→12→村莊14）：解決策略1：到達村莊時在起點準備的水剛好到極限，因為不同天氣對水和食物消耗均接近1:1，所以后續(xù)補充水和食物以1：1的比例補充至背包承重的上限，即240箱水、240箱食物。因為9次沙暴在第一階段全部發(fā)生過，后續(xù)的天氣按照高溫計算，后續(xù)會出現(xiàn)兩次抉擇的地方，通過計算比較選出最優(yōu)方案，如圖3所示，從起點→村莊（離開時備足240箱水和240箱食物）→礦山（工作6天）→終點為最優(yōu)方案。情況二：出現(xiàn)在第二階段（圖3中村莊14→19）的村莊。沙暴出現(xiàn)在村莊上可以隨時補充食物和水即出發(fā)時可以帶足夠的水和食物，240箱食物，240箱水。對后續(xù)的路程進行比較和選擇，確定出最佳路線，與第一種解決策略相同。情況三：出現(xiàn)在第二階段（圖3中村莊14→19）的19號區(qū)域。解決策略2：那么就面臨兩大抉擇：回村補給還是直接去礦山，兩個抉擇又面臨著不同的選擇。窮舉不同的方案選擇出最優(yōu)的方案，即起點→村莊（補充水為225箱，食物不增加）→19號區(qū)域（因沙暴阻礙行動9天）→礦山（工作兩天）→終點。情況四：出現(xiàn)在第二階段（圖3中19→礦山18）的礦山上。解決策略3：面臨兩大抉擇是回村補給還是直接去礦山，兩個抉擇的后面又有不同的選擇，窮舉不同的方案選擇出最優(yōu)的方案，最優(yōu)的方案為起點→村莊（補充水到240箱）→礦山（工作三天休息六天）→村莊（水補充到225箱，食物補充到225箱）→礦山（工作五天）→終點。情況五：出現(xiàn)在第三階段（圖3中礦山18→19）的19號區(qū)域。解決策略4：最優(yōu)的行進路線為起點→村莊（補充水到240箱）→礦山（工作兩天）→19號區(qū)域（阻礙行進9天）→村莊（水補充到225箱，食物補充到225箱）→礦山（工作5天）→終點。情況六：出現(xiàn)在第四階段（圖3中19→礦山14）的村莊。解決策略5：最優(yōu)的行進路線為起點→村莊（補充水到240箱）→礦山（工作六天）→村莊（水補充到54箱，食物補充到54箱）→終點。情況七：出現(xiàn)在第五階段（圖3中村莊14→15→20→終點25）的路徑。解決策略6：最優(yōu)的行進路線為起點→村莊（補充水到240箱）→礦山（工作六天）→村莊（水補充到144箱，食物補充到144箱）→在路徑被阻礙9天→終點。情況八：出現(xiàn)在第六階段（圖3中礦山18→23→24→終點25）的礦山。解決策略7：最優(yōu)的行進路線為起點→村莊（補充水到240箱）→礦山（工作六天）→村莊（補充水到240箱，食物補充到240箱）→礦山（工作三天休息六天）→終點。情況九：出現(xiàn)在第六階段（圖3中礦山18→23→24→終點25）的從礦山出來到終點的行徑。解決策略8：最優(yōu)的行進路線為起點→村莊（補充水到240箱）→礦山（工作六天）→村莊（補充水到207箱，食物補充到207箱）→礦山（工作一天）→在路徑被阻礙9天→終點。
2求解結(jié)果
對于第一關(guān)，因為ωp>ωs，所以即使在7天全部是晴朗的最好的天氣情況下挖礦資源的消耗和跨區(qū)域移動消耗的物資的價值也大于挖礦的收益，所以最優(yōu)的游戲策略就是走最短路徑直接返回終點即。資源的分配為：帶足三天遇到最差天氣（三天高溫）所用的物資，即54箱水和54箱食物。對于第二關(guān)，可能連續(xù)出現(xiàn)9天沙暴和其余天氣為高溫的情況進行分類匹配，具體的結(jié)果見表1。
參考文獻
[1]司守奎,孫兆亮.數(shù)學(xué)建模算法與應(yīng)用[M].北京：國防工業(yè)出版社,2015.
[2]劉洋洋.基于改進Dijkstra算法的自駕游最優(yōu)路徑規(guī)劃研究[J].科學(xué)技術(shù)創(chuàng)新,2020(17):75-77.
[3]劉志威,楊莉瓊,謝永勝,劉鵬,佘培培.基于改進Dijkstra算法的川藏鐵路站房工程物資動態(tài)調(diào)運研究[J].建筑經(jīng)濟,2020,41(S1):166-170.
[4]趙衛(wèi)績,鞏占宇,王雯,樊守芳.幾種經(jīng)典的最短路徑算法比較分析[J].赤峰學(xué)院學(xué)報(自然科學(xué)版),2018,34(12):47-49.
作者:蘇盈文 劉佳園 張向遠 單位:蘭州理工大學(xué)理學(xué)院 蘭州理工大學(xué)機電工程學(xué)院 蘭州理工大學(xué)計算機與通信學(xué)院
