基于分布優化模型的穿越沙漠游戲攻略

蘇盈文 劉佳園 張向遠

（1、蘭州理工大學理學院，甘肅 蘭州 730050 2、蘭州理工大學機電工程學院，甘肅 蘭州 730050 3、蘭州理工大學計算機與通信學院，甘肅 蘭州 730050）

1 模型建立與求解

1.1 針對第一關

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

圖1 第一關路徑無向圖

觀察分析可得出起點到礦山和起點到終點的最短路徑都是需行走三天，因為前三天整個地圖的天氣一樣，所以從起點去礦山或者直接去終點所消耗的資源一樣。因此只需要計算方案二到達礦山后挖礦賺取的收益與從礦山到達終點消耗資源金額的對比，從而確定最優策略。

假設方案二到礦山后的7 天全部為晴朗，計算所得的收益與消耗之間的關系如下：

其中Bw1為行走時所消耗的水；Bf1為行走時所消耗的食物；Bw2為在礦山所消耗的水；Bf2為在礦山所消耗的食物；ω 為花費金額。

1.2 針對第二關

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

然后，對第二關的地圖進行無權重、無方向的抽象表達（如圖2），其中“1”為起點，“25”為終點。觀察發現其為矩形的路線圖，到達目的地有多種路線。于是我們在最短的路徑中任意選擇一條路線進行標記（如圖3）。

圖2 第二關路徑無向圖

圖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 第二關不同情況下的解決策略