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

王天龍

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

引言

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

1、問題分析

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

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

2、模型的建立與求

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

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

（1）從1（起點(diǎn)）-27（終點(diǎn)）;

（2）1（起點(diǎn)）-12（礦山）-27（終點(diǎn)）;

（3）1（起點(diǎn)）-15（村莊）-12（礦山）-27（終點(diǎn)）。

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

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

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

（1）1（起點(diǎn)）-64（終點(diǎn)）;

（2）1（起點(diǎn)）-30（礦山）-39（村莊）-64（終點(diǎn)）;

（3）1（起點(diǎn)）-30—（礦山）-64（終點(diǎn)）。

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

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

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

（2）1（起點(diǎn)）-9（礦山）-13（終點(diǎn)）。

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

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

（2）1（起點(diǎn)）-18（礦山）-14（村莊）-25（終點(diǎn)）;

（3）1（起點(diǎn)）-18（礦山）-25（終點(diǎn)）。

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

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

（1）玩家一和玩家二都從1（起點(diǎn)）直接到13（終點(diǎn)）;

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

（3）兩個(gè)玩家：1（起點(diǎn)）-9（礦山）-13（終點(diǎn)）。

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

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

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

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

結(jié)論

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

參考文獻(xiàn)：

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

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

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