分布優(yōu)化模型下穿越沙漠游戲攻略

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

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

關(guān)鍵詞：穿越沙漠；分步優(yōu)化模型；Dijkstra算法；最短路徑算法

1模型建立與求解

1.1針對(duì)第一關(guān)

首先將地圖轉(zhuǎn)化為點(diǎn)和線組成的無(wú)向圖[1]，如圖1所示。其中，“1”為起點(diǎn)，“13”為終點(diǎn)。接著利用Dijkstra算法[2，3]對(duì)從起點(diǎn)到礦山、礦山到終點(diǎn)和起點(diǎn)到終點(diǎn)的最短路徑求解。觀察分析可得出起點(diǎn)到礦山和起點(diǎn)到終點(diǎn)的最短路徑都是需行走三天，因?yàn)榍叭煺麄€(gè)地圖的天氣一樣，所以從起點(diǎn)去礦山或者直接去終點(diǎn)所消耗的資源一樣。因此只需要計(jì)算方案二到達(dá)礦山后挖礦賺取的收益與從礦山到達(dá)終點(diǎn)消耗資源金額的對(duì)比，從而確定最優(yōu)策略。假設(shè)方案二到礦山后的7天全部為晴朗，計(jì)算所得的收益與消耗之間的關(guān)系如下：其中Bw1為行走時(shí)所消耗的水；Bf1為行走時(shí)所消耗的食物；Bw2為在礦山所消耗的水；Bf2為在礦山所消耗的食物；ω為花費(fèi)金額。

1.2針對(duì)第二關(guān)

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

2求解結(jié)果

對(duì)于第一關(guān)，因?yàn)棣豴>ωs，所以即使在7天全部是晴朗的最好的天氣情況下挖礦資源的消耗和跨區(qū)域移動(dòng)消耗的物資的價(jià)值也大于挖礦的收益，所以最優(yōu)的游戲策略就是走最短路徑直接返回終點(diǎn)即。資源的分配為：帶足三天遇到最差天氣（三天高溫）所用的物資，即54箱水和54箱食物。對(duì)于第二關(guān)，可能連續(xù)出現(xiàn)9天沙暴和其余天氣為高溫的情況進(jìn)行分類匹配，具體的結(jié)果見(jiàn)表1。

參考文獻(xiàn)

[1]司守奎,孫兆亮.數(shù)學(xué)建模算法與應(yīng)用[M].北京：國(guó)防工業(yè)出版社,2015.

[2]劉洋洋.基于改進(jìn)Dijkstra算法的自駕游最優(yōu)路徑規(guī)劃研究[J].科學(xué)技術(shù)創(chuàng)新,2020(17):75-77.

[3]劉志威,楊莉瓊,謝永勝,劉鵬,佘培培.基于改進(jìn)Dijkstra算法的川藏鐵路站房工程物資動(dòng)態(tài)調(diào)運(yùn)研究[J].建筑經(jīng)濟(jì),2020,41(S1):166-170.

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

作者:蘇盈文 劉佳園 張向遠(yuǎn) 單位:蘭州理工大學(xué)理學(xué)院 蘭州理工大學(xué)機(jī)電工程學(xué)院 蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院