基于鄰接矩陣法的穿越沙漠路線研究

王天龍

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

引言

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

1、問題分析

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

最后對第六關求解，假設有n名玩家，求當n=2時，兩位玩家的最優化路線，當n=3時，三位玩家的最優化路線。

2、模型的建立與求

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

針對第一關分三種情況：

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

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

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

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

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

針對第二關同樣也分三種情況：

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

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

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

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

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

第三關：（1）1（起點）-13（終點）;

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

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

針對第四關：（1）1（起點）-25（終點）;

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

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

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

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

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

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

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

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

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

玩家一的行走路線為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元。

結論

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

參考文獻：

[1]任洛漪. 基于協同過濾推薦系統優化地圖軟件路線推薦[J].計算機產品與流通，2020，（09）：133.

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

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