王天龍

【摘 要】本文主要針對穿越沙漠問題進行了相關(guān)研究，利用鄰接矩陣法制定了不同地圖不同天氣變化條件下游戲玩家的最優(yōu)策略。首先利用鄰接矩陣先對第一關(guān)和第二關(guān)分別情況討論，通過分析得出最優(yōu)路徑。其次第三關(guān)的天氣變化情況不同通過分析得出最優(yōu)路徑。最后對第五關(guān)和第六關(guān)進行求解第五關(guān)中每天的天氣已知，但兩名玩家的路線只能當(dāng)天確定，為使得他們獲得的總資金最大，他們的路線應(yīng)盡可能的不同，第六關(guān)天氣與第四關(guān)一樣未知，且地圖與第四關(guān)相同，因此三名玩家的路線盡可能不重復(fù)，且最終所獲得的總資金最高。

引言

本文介紹了穿越沙漠小游戲，玩家用地圖購買一定數(shù)量的水和食物（包括日常必需品），然后從沙漠步行，行走時會有不同的天氣（晴天、高溫、沙塵暴），當(dāng)經(jīng)過礦山和村莊時可以補充資金和資源。游戲開始時間為第0天，游戲者再出發(fā)前必須在最后期限之前達到終點線，如果沒有達到終點，水或食物耗盡，這被認為游戲失敗，如果到達終點線后，玩家可以歸還剩下的水和食物。

1、問題分析

在游戲規(guī)定的條件下，建立數(shù)學(xué)模型，在整個游戲時段內(nèi)每天天氣狀況事先全部已知，試給出一般情況下玩家的最優(yōu)策略。首先先求解“第一關(guān)”和“第二關(guān)”，并將相應(yīng)結(jié)果分別填入Result.xlsx中，其次玩家僅知道當(dāng)天的天氣狀況，可據(jù)此決定當(dāng)天的行動方案，并對“第三關(guān)”和“第四關(guān)”進行具體討論。

最后對第六關(guān)求解，假設(shè)有n名玩家，求當(dāng)n=2時，兩位玩家的最優(yōu)化路線，當(dāng)n=3時，三位玩家的最優(yōu)化路線。

2、模型的建立與求

首先采用鄰接矩陣 [5]表示沙漠中任意兩點之間可行走路線，鄰接矩陣平方是表示頂bai點之間相鄰關(guān)系的矩陣的平方。先對第一關(guān)和第二關(guān)分別情況討論，在只有一名玩家，且知道每天的天氣變化情況下，要求在30天之內(nèi)從起點到達終點。需要對玩家行走的路線進行分類，通過最短路徑分析出最優(yōu)的幾條路線[2]。在不違背游戲規(guī)則情況下，分別對第一關(guān)和第二關(guān)進行求解。

針對第一關(guān)分三種情況：

（1）從1（起點）-27（終點）;

（2）1（起點）-12（礦山）-27（終點）;

（3）1（起點）-15（村莊）-12（礦山）-27（終點）。

在起始點購買物資消耗的錢小于初始資金：ω1<=η，從起始點到終點天數(shù)的約束：

其中，β=nd，η=10000，ω=ω1 +ω2，d= 1000，a=190，b=104，c=150，最后得到起點a1-村莊a15（經(jīng)過且停留一天）-礦山a12（挖礦）-終點a27的最短路徑為1-25-24-23-22-9-15-13-12-14-15-9-21。得出即從起點出發(fā)經(jīng)過村莊并停留一天購買物資，然后到達礦山，挖八天的礦物，賺取資金，最后返回終點的過程獲得的資金為 13130 元。

針對第二關(guān)同樣也分三種情況：

（1）1（起點）-64（終點）;

（2）1（起點）-30（礦山）-39（村莊）-64（終點）;

（3）1（起點）-30—（礦山）-64（終點）。

對比三種情況，選出所剩資金最多的一種情況。由于第二關(guān)的與第一關(guān)的條件相同，僅地圖不同。由1（起點）-64（終點）;由起點-上礦場-村莊購買物資-下礦場-村莊（/無）-終點。

最后得到路線從起點直接出發(fā)到終點，僅消耗資金，沒有任何收益，到達55（礦山）后挖礦7天，去62（村莊）購買所需物資后回到終點，累計資金最大，為9635元。

第三關(guān)：（1）1（起點）-13（終點）;

（2）1（起點）-9（礦山）-13（終點）。

對比兩種情況，選出所剩資金最多的一種情況，從起點到礦山挖礦掙取資金，最后回到終點。其次途中一直行走不停留，由于起點到礦山，礦山到終點的最短路徑已經(jīng)確定，且不存在沙暴天氣，因此可以得到在路上行走消耗的天數(shù)是固定的五天，由于挖礦天數(shù)越多，獲得的收益也越多，在起點購買的物資，最大只能支持行走五天和五天的挖礦時間消耗，若高溫條件下不停留，在起點購買的物資，最多可以支持五天挖礦的消耗。

針對第四關(guān)：（1）1（起點）-25（終點）;

（2）1（起點）-18（礦山）-14（村莊）-25（終點）;

（3）1（起點）-18（礦山）-25（終點）。

對比三種情況，選出所剩資金最多的一種情況。得出玩家僅知道當(dāng)天的天氣狀況，最短路得到從起點直接到終點的最短途徑為1-6-11-16-21-22-23-24-25路線。在該路線下，八天晴朗的天氣情況下，獲得最大收益為9120元。

將游戲規(guī)則復(fù)雜化，隨著玩家數(shù)目的變化，挖礦收益和資源消耗也隨著發(fā)生變化。在不違背游戲規(guī)則情況下，針對不同的天氣變化情況分別對第五關(guān)和第六關(guān)進行分情況討論。針對第五關(guān)：

（1）玩家一和玩家二都從1（起點）直接到13（終點）;

（2）玩家一從：1（起點）-13（終點），玩家二從：1（起點）-9（礦山）-13（終點）;

（3）兩個玩家：1（起點）-9（礦山）-13（終點）。

選出所剩資金最多的一種情況：由兩個玩家同時從起點走向終點，兩個玩家一同行走，消耗的物資是一般情況下的二倍，因此為了減少不必要的消耗，盡可能的使得兩個人分開走，一個玩家走礦山，一個玩家且不走礦山，最終得出起點直接到終點的最短路徑為：1-5-6-13（經(jīng)過三個區(qū)域）. 其次為1-4-7-12（或11）-13（經(jīng)過四個區(qū)域）。因此，兩人最終剩余金錢總和為18965元，重量總和為333kg，遠遠小于重量限制。

針對第六關(guān)由第四關(guān)可知，直接從起點直接到礦山最后回到終點，是一個玩家獲得資金最大的時刻，24150元。且從起點到達礦山，以及從礦山回到終點的最短路線有多條，從起點到礦山，任選三條路線，至少有2個區(qū)域是相重合的。（原因：從起點出發(fā)只有兩條路，3 個人必有兩個人一起出發(fā);從最后一個區(qū)域到達礦山，同起點出發(fā)）。從礦山到終點，無論三個人如何選擇，必有一個人，至少與其他兩個人的路線有重合。

玩家一的行走路線為1（起點）-2-3-8-13-18（礦山）-19-20-25（終點）;

玩家二的行走路線為1（起點）-6-11-16-17-18（礦山）-23-24-25（礦山）;玩家三的行走路線為1（起點）-2-7-12-17-18（礦山）-19-20-25（終點）。最后收益為求得三人的總收益為11370元。

結(jié)論

關(guān)卡1和關(guān)卡2都已知天氣條件，因此考慮行走路線及是否在村莊買物資和挖礦時間的變化，對于不同行走路線分別考慮挖礦時間，得到最終結(jié)果。第四關(guān)忽略了較少出現(xiàn)的沙暴天氣，只討論了在晴朗和高溫兩種天氣變化情況。第六關(guān)只討論以最大的挖礦時間十六天獲得的收益，沒有詳細討論兩人其它挖礦時間變化。

參考文獻：

[1]任洛漪. 基于協(xié)同過濾推薦系統(tǒng)優(yōu)化地圖軟件路線推薦[J].計算機產(chǎn)品與流通，2020，（09）：133.

[2]徐波，張玉敏.計及惡劣氣象條件的系統(tǒng)狀態(tài)檢修決策模型[J].廣東電力，2019，32（06）：61-69.

（作者單位：河北工程大學(xué)材料科學(xué)與工程學(xué)院）