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

蘇盈文 劉佳園 張向遠(yuǎn)

（1、蘭州理工大學(xué)理學(xué)院，甘肅 蘭州 730050 2、蘭州理工大學(xué)機(jī)電工程學(xué)院，甘肅 蘭州 730050 3、蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院，甘肅 蘭州 730050）

1 模型建立與求解

1.1 針對第一關(guān)

首先將地圖轉(zhuǎn)化為點(diǎn)和線組成的無向圖[1]，如圖1 所示。其中，“1”為起點(diǎn)，“13”為終點(diǎn)。接著利用Dijkstra 算法[2，3]對從起點(diǎn)到礦山、礦山到終點(diǎn)和起點(diǎn)到終點(diǎn)的最短路徑求解。

圖1 第一關(guān)路徑無向圖

觀察分析可得出起點(diǎn)到礦山和起點(diǎn)到終點(diǎn)的最短路徑都是需行走三天，因?yàn)榍叭煺麄€(gè)地圖的天氣一樣，所以從起點(diǎn)去礦山或者直接去終點(diǎn)所消耗的資源一樣。因此只需要計(jì)算方案二到達(dá)礦山后挖礦賺取的收益與從礦山到達(dá)終點(diǎn)消耗資源金額的對比，從而確定最優(yōu)策略。

假設(shè)方案二到礦山后的7 天全部為晴朗，計(jì)算所得的收益與消耗之間的關(guān)系如下：

其中Bw1為行走時(shí)所消耗的水；Bf1為行走時(shí)所消耗的食物；Bw2為在礦山所消耗的水；Bf2為在礦山所消耗的食物；ω 為花費(fèi)金額。

1.2 針對第二關(guān)

首先，從起點(diǎn)到村莊，走其最短路徑。通過計(jì)算發(fā)現(xiàn)在前四步跨區(qū)域的行程中，無論經(jīng)歷的沙暴是0 天還是9 天，都要回村莊補(bǔ)給完畢后再去挖礦所得經(jīng)濟(jì)效益最高。所以無論沙暴出現(xiàn)在哪一天，從起點(diǎn)出發(fā)的第一步都是都是前往村莊。在到達(dá)村莊前，最壞的情況為遭遇9 天沙暴且行進(jìn)時(shí)為高溫天氣，所以在起點(diǎn)要備足經(jīng)歷9 天沙暴和5 天高溫行程的水和食物，又要保證在村莊補(bǔ)給所花費(fèi)的資金最少，因此帶到的村莊的極限水量，剩余容量全部帶食物，以盡量減少食物在村莊的購買，即在起點(diǎn)所購資源為180 箱水和330 箱食物。

然后，對第二關(guān)的地圖進(jìn)行無權(quán)重、無方向的抽象表達(dá)（如圖2），其中“1”為起點(diǎn)，“25”為終點(diǎn)。觀察發(fā)現(xiàn)其為矩形的路線圖，到達(dá)目的地有多種路線。于是我們在最短的路徑中任意選擇一條路線進(jìn)行標(biāo)記（如圖3）。

圖2 第二關(guān)路徑無向圖

圖3 第二關(guān)路徑圖

在眾多路徑當(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é)果對列舉的幾種情況進(jìn)行匹配，按照符合的情況對購買水和食物和挖礦天數(shù)進(jìn)行決策。

具體出現(xiàn)連續(xù)沙暴天氣的情況：

情況一：出現(xiàn)在第一階段（圖3 中1→2→3→8→12→村莊14）：

解決策略1：到達(dá)村莊時(shí)在起點(diǎn)準(zhǔn)備的水剛好到極限，因?yàn)椴煌鞖鈱λ褪澄锵木咏?:1，所以后續(xù)補(bǔ)充水和食物以1：1 的比例補(bǔ)充至背包承重的上限，即240 箱水、240 箱食物。因?yàn)? 次沙暴在第一階段全部發(fā)生過，后續(xù)的天氣按照高溫計(jì)算，后續(xù)會(huì)出現(xiàn)兩次抉擇的地方，通過計(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 箱水。對后續(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）的從礦山出來到終點(diǎn)的行徑。

解決策略8：最優(yōu)的行進(jìn)路線為起點(diǎn)→村莊（補(bǔ)充水到240箱）→礦山（工作六天）→村莊（補(bǔ)充水到207 箱，食物補(bǔ)充到207 箱）→礦山（工作一天）→在路徑被阻礙9 天→終點(diǎn)。

2 求解結(jié)果

對于第一關(guān)，因?yàn)棣豴＞ωs，所以即使在7 天全部是晴朗的最好的天氣情況下挖礦資源的消耗和跨區(qū)域移動(dòng)消耗的物資的價(jià)值也大于挖礦的收益，所以最優(yōu)的游戲策略就是走最短路徑直接返回終點(diǎn)即。資源的分配為：帶足三天遇到最差天氣（三天高溫）所用的物資，即54 箱水和54 箱食物。

對于第二關(guān)，可能連續(xù)出現(xiàn)9 天沙暴和其余天氣為高溫的情況進(jìn)行分類匹配，具體的結(jié)果見表1。

表1 第二關(guān)不同情況下的解決策略