張 敏 張 力 王雪鋒 孟慧慧 邵光祖

（ 1、黃河交通學(xué)院數(shù)學(xué)教研室，河南 焦作454002 2、黃河交通學(xué)院智能工程學(xué)院，河南 焦作454002）

玩家憑借一張地圖，利用初始資金購(gòu)買(mǎi)一定數(shù)量的水和食物（包括食品和其他日常用品），從起點(diǎn)出發(fā)，在沙漠中行走。途中會(huì)遇到不同的天氣，也可在礦山、村莊補(bǔ)充資金或資源，在游戲設(shè)定的規(guī)則下，規(guī)定的時(shí)間內(nèi)到達(dá)終點(diǎn)，并保留盡可能多的資金。

1 問(wèn)題分析

根據(jù)地形使用廣度優(yōu)先遍歷[1]找出任意兩區(qū)域的最優(yōu)路徑。最優(yōu)路徑的選擇從是否挖礦考慮：如果挖礦，則根據(jù)動(dòng)態(tài)規(guī)劃模型求解挖礦天數(shù)，從而規(guī)劃在起點(diǎn)時(shí)所需儲(chǔ)備的資源；如果不挖礦，根據(jù)求得的起點(diǎn)到終點(diǎn)的最短距離以及儲(chǔ)備所需資源，并依據(jù)所選的最優(yōu)路徑求解剩余資金。比較兩種情況下不同線(xiàn)路的剩余資金，選擇剩余資金最大的線(xiàn)路填寫(xiě)“第一關(guān)”和“第二關(guān)”的結(jié)果表。

2 模型的建立與求解

2.1 游戲第一關(guān)的分析與求解

游戲中只有一名玩家，并且在整個(gè)游戲時(shí)段內(nèi)每天的天氣狀況事先全部已知，尋找一般情況下玩家的最優(yōu)策略，即尋找從起點(diǎn)到終點(diǎn)的最優(yōu)路徑。

使用廣度優(yōu)先搜索遍歷方法，遍歷的步驟如下：

（1）從起點(diǎn)1 出發(fā)，訪(fǎng)問(wèn)1 區(qū)域。

（2）依次訪(fǎng)問(wèn)1 的各個(gè)未曾訪(fǎng)問(wèn)過(guò)的相鄰區(qū)域2，25。

（3）分別從這些相鄰的區(qū)域出發(fā)依次訪(fǎng)問(wèn)該區(qū)域的相鄰區(qū)域，并使“先被訪(fǎng)問(wèn)區(qū)域的相鄰區(qū)域”先于“后被訪(fǎng)問(wèn)區(qū)域的相鄰區(qū)域”被訪(fǎng)問(wèn)。

（4）重復(fù)步驟（3），直至地圖中所有已被訪(fǎng)問(wèn)的區(qū)域的相鄰區(qū)域都被訪(fǎng)問(wèn)到。

一般情況下，玩家的最優(yōu)策略確定原則從是否挖礦方面考慮，可以分為兩種方案。

表1“第一關(guān)”最優(yōu)策略的部分結(jié)果表

方案一：從起點(diǎn)走最短路徑直接到終點(diǎn)（不考慮挖礦）。

要想在規(guī)定時(shí)間內(nèi)到達(dá)終點(diǎn)并盡大可能保留最多資金，則需要減少在路途上的消耗，所以需要用最短的時(shí)間從起點(diǎn)到達(dá)終點(diǎn)。從起點(diǎn)到終點(diǎn)花費(fèi)最短時(shí)間的行動(dòng)方案為：1（起點(diǎn)）→25→26→27（終點(diǎn)）。

為了使得玩家在到達(dá)終點(diǎn)時(shí)減少物資的剩余量，降低玩家到達(dá)終點(diǎn)后退回的剩余物資總量，從而避免在起點(diǎn)購(gòu)買(mǎi)太多的物資造成資金浪費(fèi)的目標(biāo)，所以需要確定在起點(diǎn)時(shí)路程上需要的物資總量。使用Matlab 軟件計(jì)算在該行動(dòng)方案中路程上物資的消耗量，通過(guò)逆推求解出需要在起點(diǎn)購(gòu)買(mǎi)水21 箱，食物19箱，負(fù)重101 千克，到終點(diǎn)時(shí)剩余資金9705 元。

方案二：從起點(diǎn)到終點(diǎn)的路徑考慮去礦山挖礦。

將起點(diǎn)到村莊分為第一階段，村莊到礦山再返回村莊為第二階段，村莊到終點(diǎn)分為第三階段。使用廣度優(yōu)先遍歷方法，得出第一階段的最優(yōu)路徑為1（起點(diǎn)）→25→24→23→22→9→15（村莊）。

根據(jù)第一階段的最優(yōu)路徑和附件中給出的天氣狀況，得到第一階段的行程為：第零天在1 區(qū)域（起點(diǎn)），第一天行走到25區(qū)域，第二天行走到24 區(qū)域，第三天行走到23 區(qū)域。由于第四天是沙暴天氣，所以需要原地停留，故第四天仍舊是停留在23區(qū)域。第五天行走到22 區(qū)域，第六天行走到9 區(qū)域，由于第七天是沙暴天氣，所以需要原地停留，故第七天仍舊是停留在9 區(qū)域。第八天行走到15 區(qū)域。

第二階段為從村莊到礦山再到村莊，使用廣度優(yōu)先遍歷的方法得到該階段最短的路徑有兩條分別為：15（村莊）→13→12（礦山）→14→15（村莊）和15（村莊）→14→12（礦山）→13→15（村莊）。為了使玩家在到達(dá)終點(diǎn)時(shí)剩余最多的資金，所以在該階段考慮通過(guò)挖礦來(lái)獲取外來(lái)資金。由于挖礦需要考慮天氣狀況，所以根據(jù)該階段的最短路線(xiàn)和附件中的天氣要分析沙暴日是否挖礦。最壞情況為挖礦需要的資源全部到村莊購(gòu)買(mǎi)。因?yàn)樽顗那闆r下挖礦一天消耗的資金小于基礎(chǔ)收益，所以沙暴天氣需要挖礦。因?yàn)榍缋屎透邷靥鞖獗壬潮┨鞖鈼l件下的基礎(chǔ)消耗量少，所以晴朗和高溫天氣更需要挖礦。

根據(jù)第二階段的行程求解第二階段所需要的總物資。根據(jù)附件中給出的天氣情況列出不同天氣條件下行走或停留時(shí)所需物資量。

晴朗天氣行走一天消耗物資質(zhì)量是58 千克，晴朗天氣停留一天消耗物資質(zhì)量是29 千克，高溫天氣行走一天消耗物資質(zhì)量是72 千克，高溫天氣停留一天消耗物資質(zhì)量是36 千克，沙暴天氣挖礦時(shí)一天消耗物資質(zhì)量是150 千克，沙暴天氣不挖礦時(shí)每天消耗物資質(zhì)量是50 千克。

附件給出的信息得到玩家的負(fù)重上限為1200 千克，所以在第二階段物資需求量不超過(guò)1200 千克的情況下應(yīng)該挖選擇挖礦天數(shù)最多的路徑，通過(guò)計(jì)算挖礦最大天數(shù)為7 天。根據(jù)挖礦的最大天數(shù)和第二階段在其他區(qū)域的需求量，計(jì)算得到第二階段需要水245 箱，食物221 箱?？紤]在村莊購(gòu)買(mǎi)物資比較貴，所以要在起點(diǎn)購(gòu)買(mǎi)足夠量的物資。因?yàn)槭澄锏幕鶞?zhǔn)價(jià)格是水的兩倍，所以使用定量的初始資金時(shí)要以食物優(yōu)先（只需備足一定量的水）。使用Matlab 軟件求得：在起點(diǎn)時(shí)，需要購(gòu)買(mǎi)水180 箱，食物330 箱，負(fù)重總量1200 千克，剩余初始資金5800 元。

根據(jù)天氣情況、第二階段的最優(yōu)線(xiàn)路和最大挖礦天數(shù)確定第二階段的行程為：第九天行走到14 區(qū)域，第十天從14 區(qū)域行走到12（礦山），第十一天至第十七天在礦山挖礦（共計(jì)挖礦八天）。由于沙暴天氣第十八天在12（礦山）區(qū)域停留，第十九天從12（礦山）區(qū)域走到14 區(qū)域，第二十天從14 區(qū)域走到15 區(qū)域（村莊）。

由于第三階段是從村莊回到終點(diǎn)，為了減少該階段玩家在行程上資源的消耗，所以該階段的最優(yōu)路徑為最短路徑。運(yùn)用廣度優(yōu)先搜素遍歷方法得到第三階段的最短路徑為：15（村莊）→9→21→27（終點(diǎn)）。

根據(jù)最短路徑確定第三階段的行程為：第二十一天行走到9 區(qū)域，第22 天行走到21 區(qū)域，第23 天行走到27 區(qū)域（終點(diǎn)）。

根據(jù)第三階段行程上的物資消耗情況求解第三階段物資購(gòu)買(mǎi)數(shù)量。使用Matlab 軟件求解出第三階段需要在村莊購(gòu)買(mǎi)水36 箱，食物19 箱，此時(shí)的剩余資金為4170 元。該方案第23 天到達(dá)終點(diǎn)，此時(shí)剩余水量為0 箱，剩余食物量為0 箱，剩余資金數(shù)為10430 元。

比較第一關(guān)的兩種方案，發(fā)現(xiàn)方案二比方案一的剩余資金數(shù)大，據(jù)此得出本關(guān)游戲玩家的最優(yōu)的策略為：1→25→24→23→22→9→15（村莊）→14→12（礦山）→14→15（村莊）→9→21→27（終點(diǎn)）。

利用Matlab 軟件計(jì)算出第一關(guān)玩家每天的結(jié)果。如表1。

2.2 游戲第二關(guān)的分析與求解

第二關(guān)尋找最優(yōu)策略的方案與第一關(guān)相似。觀察第二關(guān)的地圖可以發(fā)現(xiàn)有兩個(gè)村莊和兩個(gè)礦場(chǎng)（其中一個(gè)礦山位于30 區(qū)域，距離起點(diǎn)近）。

為保證單次路線(xiàn)中挖礦天數(shù)最長(zhǎng)，根據(jù)貪心算法得到從起點(diǎn)到終點(diǎn)的最優(yōu)策略是玩家需要先從起點(diǎn)到離礦山區(qū)域最近的村莊購(gòu)買(mǎi)能夠達(dá)到最佳狀態(tài)的物資后再去挖礦。挖礦結(jié)束后要使剩余的物資能夠到達(dá)距離挖礦礦山最近村莊，以便于回到村莊進(jìn)行購(gòu)買(mǎi)物資。根據(jù)廣度優(yōu)先遍歷方法，得出在購(gòu)買(mǎi)物資后，從村莊到礦山再到終點(diǎn)的最短天數(shù)比從村莊直接到達(dá)終點(diǎn)的最短天數(shù)多1 天。使用Matlab 軟件計(jì)算出在礦山區(qū)域挖礦的最大天數(shù)為4 天。

表2“第二關(guān)”最優(yōu)策略的部分結(jié)果表

根據(jù)上述分析和第二關(guān)的地圖，把起點(diǎn)到終點(diǎn)的路線(xiàn)分為三個(gè)階段，第一階段為從起點(diǎn)直接到39 區(qū)域（村莊），第二階段為從39 區(qū)域（村莊）到30 區(qū)域（礦山），在該區(qū)域挖最大天數(shù)的礦后回到39 區(qū)域（村莊），第三階段為從39 區(qū)域（村莊）到55 區(qū)域（礦山）挖礦后直接回到64 區(qū)域（終點(diǎn)）。

使用廣度優(yōu)先遍歷方法，從起點(diǎn)到30 區(qū)域的礦山區(qū)的最短路徑為7 步，分別為：

第一條路徑為：1（起點(diǎn)）→2→10→19→27→28→29→30（礦山）

第二條路徑為：1（起點(diǎn)）→2→3→4→5→13→22→30（礦山）

第三條路徑為：1（起點(diǎn)）→2→10→19→20→28→29→30（礦山）

從30 區(qū)域（礦山）到39 區(qū)域（村莊）最短路徑為1 步，根據(jù)廣度優(yōu)先搜索遍歷得到從1（區(qū)域）起點(diǎn)到39 區(qū)域（村莊）的最短路徑就是最優(yōu)路徑。分析求解發(fā)現(xiàn)第一階段的最短路徑線(xiàn)路不唯一，但都是七步，所以無(wú)論選擇哪一條路徑行走物資的消耗量都是相等的。

由附件給出的信息得到負(fù)重上限為1200 千克。所以在第二階段物資需求量不超過(guò)1200 千克的情況下應(yīng)該挖最大天數(shù)的礦，通過(guò)計(jì)算挖礦的最大天數(shù)為7 天。根據(jù)挖礦的最大天數(shù)和第二階段在其他區(qū)域的需求量，計(jì)算得到第二階段需要首先在村莊購(gòu)買(mǎi)水195 箱，食物0 箱?？紤]在村莊購(gòu)買(mǎi)物資比較貴，所以要在起點(diǎn)購(gòu)買(mǎi)足夠量的物資。因?yàn)槭澄锏幕鶞?zhǔn)價(jià)格是水的兩倍，所以使用定量的初始資金時(shí)要以食物優(yōu)先（只需備足一定量的水）。使用Matlab 軟件求得：在起點(diǎn)時(shí)，需要購(gòu)買(mǎi)水166 箱，食物350 箱，負(fù)重總量1198 千克，剩余初始資金5670 元。

先去30 區(qū)域（礦山）挖礦，直到消耗后所剩的物資和水僅支持從30 區(qū)域（礦山）轉(zhuǎn)移到39 區(qū)域（村莊）。根據(jù)第三階段玩家在路上的物資消耗量確定回到村莊時(shí)需要第二次購(gòu)買(mǎi)水157箱，食物140 箱，剩余初始資金7350 元。

分析第三階段從39 區(qū)域（村莊）出發(fā)直接到達(dá)終點(diǎn)時(shí)的線(xiàn)路，根據(jù)地圖得出該階段的最短線(xiàn)路不唯一，但是最短線(xiàn)路上玩家的消耗量是相同的。到達(dá)終點(diǎn)時(shí)剩余水量0 箱，食物0 箱，剩余資金數(shù)12350 元。

使用Matlab 軟件計(jì)算出玩家在一般情況下第二關(guān)的最優(yōu)策略的結(jié)果。結(jié)果如表2。

該方案顯示玩家在第30 天到達(dá)終點(diǎn)時(shí)，此時(shí)剩余水量為0箱，剩余食物量為0 箱，剩余資金數(shù)為12350 元。

3 結(jié)論

從是否挖礦角度出發(fā)，如果挖礦，則根據(jù)動(dòng)態(tài)規(guī)劃模型求解挖礦天數(shù)，從而規(guī)劃在起點(diǎn)時(shí)所需儲(chǔ)備的資源；如果不挖礦，根據(jù)求得的起點(diǎn)到終點(diǎn)的最短距離以及儲(chǔ)備所需資源，依據(jù)所選的最優(yōu)方案計(jì)算剩余資金。