穿越沙漠游戲最短路徑策略研究

田欣宇

河北工程大學(xué) 河北邯鄲 056002

1 問題分析

一名玩家知道游戲時(shí)間段內(nèi)30天內(nèi)的全部天氣情況[1]，則可以根據(jù)高溫、晴朗和沙暴天氣不同的基礎(chǔ)消耗量來決定初始攜帶的最大資源數(shù)量。由于在村莊的資源價(jià)格高于較高，因此為保證成功完成穿越沙漠則是否在此購買資源需要結(jié)合路線進(jìn)行具體分析。根據(jù)基準(zhǔn)價(jià)格、基礎(chǔ)消耗量的條件，列出相對應(yīng)的關(guān)系式，并結(jié)合負(fù)重上限、初始資金得出約束條件，得到線性規(guī)劃的模型。首先對地圖應(yīng)用圖論模型和迪杰斯特拉算法[2]，求解出不同方案下的最短路徑。再結(jié)合天氣情況對具體的路線的資源消耗以及收益進(jìn)行計(jì)算，進(jìn)而確定初始購買資源數(shù)量和最終到達(dá)終點(diǎn)時(shí)的資金。最后用靈敏度分析對第一關(guān)和第二關(guān)的具體問題進(jìn)行檢驗(yàn)，驗(yàn)證問題的答案是否具有合理性。

2 模型的建立與求解

假設(shè)在晴朗天氣和高溫天氣時(shí)玩家不原地停留，向相鄰區(qū)域前進(jìn)。目標(biāo)是在規(guī)定時(shí)間內(nèi)到達(dá)終點(diǎn)，并保留盡可能多的資金。需要考慮1。初始的水和食物的購買量2。再不超過負(fù)重的基礎(chǔ)上水和食物的占比3。所消耗的天數(shù)其中包括了受沙暴天氣影響的天數(shù)[5]和受不同地區(qū)[6]所消耗的天數(shù)。所以列出未知數(shù)函數(shù)方程，使最終收益最大來求解方程。針對最短天數(shù)到達(dá)終點(diǎn)或最短天數(shù)到達(dá)礦場兩種情況，采用最短路徑方案，并基于最短路徑下的最大收益模型,得到最大收益要使購買消耗品的資金盡可能少。設(shè)在出發(fā)地購買水質(zhì)量為箱，購買食物重量為箱，花費(fèi)為，則：

并考慮到食物的價(jià)值大于水的價(jià)值且水的質(zhì)量大于食物的質(zhì)量采用0-1背包模型，在基于最短路徑下到達(dá)村莊補(bǔ)充食物和水至少需要98箱水和98箱食物即補(bǔ)充約束條件為：

狀態(tài)加選擇，定義為裝載重量為W的背包和N個物品，每個物品有重量和價(jià)值兩個屬性，其中第i個物品的重量為wt[i],價(jià)值為val[i]。代入W=1200，N=2，價(jià)值分別為5和10，重量分別為3和2。設(shè)在村莊購買的水質(zhì)量為箱，購買食物重量為箱，花費(fèi)為，則：

設(shè)玩家到達(dá)終點(diǎn)之后的總資金為Y，則：

要盡可能使得Y最大，基礎(chǔ)收益最大，基礎(chǔ)消耗最小，同時(shí)使得得到終點(diǎn)的水和食物盡可能小。即：

得到線性規(guī)劃模型如下：

3 結(jié)語

由以上敘述可知此玩家在第一關(guān)最佳優(yōu)化策略分為不經(jīng)過礦山和經(jīng)過礦山兩種決策方案，此兩種決策方案分別對應(yīng)一種最短路徑。對第一關(guān)情況進(jìn)行圖論分析[3]，通過應(yīng)用迪杰斯特拉算法，得到如圖1所示不經(jīng)過礦山的最短路徑情況圖，不經(jīng)過礦山的最短路線為1→25→26→27，此路線僅需考慮天氣因素和食物與水的消耗，不許考慮其他因素。

則可得以下結(jié)論：針對本路線假設(shè)玩家購買的水和食物剛好到達(dá)終點(diǎn)，即剩余資源為零。所以=50+80×2+140+120×2=590在第四天到終點(diǎn)，且剩余資金為9410元。對第一關(guān)情況進(jìn)行圖論分析，通過應(yīng)用迪杰斯特拉算法,分析可得經(jīng)過礦場的最短路線為1→25→24→23→21→9→10→11→12→11→10→9→21→27。為獲得途中的補(bǔ)充資源，采取經(jīng)過村莊的路線，即1→25→24→23→21→9→15→13→12→13→15→9→21→27。計(jì)算得到初始購買98箱水和453箱食物即=453，結(jié)合天數(shù)到達(dá)村莊為第八天經(jīng)歷了兩天沙暴，三天晴朗，三天高溫到達(dá)村莊剛好水耗盡繼而購買163箱水不購買食物，沿著區(qū)域14，進(jìn)入礦區(qū)12，進(jìn)行挖礦到十四天然后返回村莊進(jìn)行購買223箱水，再次趕回礦區(qū)進(jìn)行挖礦在26號出發(fā)到村莊購買11箱食物，然后出發(fā)至終點(diǎn)實(shí)現(xiàn)零剩余。最終資金剩余9900。