基于Dijkstra 算法的路徑選擇策略研究
——以“穿越沙漠”游戲軟件為例

蘇禧媛

（陜西科技大學(xué)文理學(xué)院，陜西 西安 710021）

穿越沙漠是一種典型的生存游戲，此游戲需遵守一些游戲規(guī)則，例如：負重不能超過上限，購買物資時需考慮資金是否足夠，在規(guī)定時間內(nèi)到達終點。本文要解決的問題是考在遵守游戲規(guī)則的情況下，考慮一定的風險性幫玩家找到最優(yōu)策略，實現(xiàn)剩余資金量最多這一目標。

1 問題分析

針對“玩家必須在截止日期或之前到達終點”這一游戲規(guī)則，本文采用圖論Dijkstra 的方法求得起點到村莊、起點到礦山、村莊到礦山、村莊到終點、礦山到終點的最短距離，同時利用Kruskal 算法（避圈法）對模型進行優(yōu)化。

針對這是多位玩家參與尋求最優(yōu)策略的問題。在游戲規(guī)則改變后，需要分多種情況來討論。最終的目的都是需要走最少的路獲得最大的利，盡量不同時走相同路線。針對于此，本文涉及利用極端情況進行討論，并同時設(shè)置風險界限a，將多目標規(guī)劃變成一個目標的線性規(guī)劃[1-3]。最后分別按情況進行討論，并利用博弈論分析玩家心理，求出最優(yōu)行走路徑。

2 模型建立與求解

2.1 Dijkstra 與Kruskal 算法運用

起點→礦山→終點最短路徑如圖1 所示，可以看出，此地圖是一個不規(guī)則的多邊形圖，為了將它進行簡化，我們利用Dijkstra 算法分別求得起點到村莊，起點到礦山，村莊到礦山，村莊到終點，礦山到終點的最短距離，分別記為：T1，T2，T3，T4，T5，通過求解得出：T1=6，T2=8，T3=2，T4=3，T5=5，于是可以建立最短路徑圖，同時利用Kruskal 算法（避圈法）對圖進行優(yōu)化。

圖1 起點→礦山→終點最短路徑

在確定了起點和終點的最短路徑后，只需對村莊和礦山之間的往返情況進行分析，爭取在起點購買充足的物資，減少往返路程和時間，保證收取資源的時間盡可能多，以期獲得較多的收益，剩余資金數(shù)最大。

經(jīng)過對比，得出玩家行動的最優(yōu)策略：玩家一號從起點出發(fā)去往村莊，其具體路徑為1→25→24→23→21→9→15，在村莊花費2940 元購買水104 箱，購買食物96 箱。從村莊前往礦山，其具體路徑為15→13→12，在礦山挖礦六天，遇到17、18 號風暴天氣不挖礦等待兩天。19 號出發(fā)前往村莊，具體路徑為12→13→15，在村莊花費210 元購買水21 箱。從村莊出發(fā)前往終點，其具體路徑為15→9→21→27，到達終點剩余食物9 箱，折現(xiàn)為45 元，最終剩余資金數(shù)為9295 元。

2.2 多元線性規(guī)劃模型建立

若玩家只知道當天的天氣狀況，但已知一個月內(nèi)較少出現(xiàn)沙暴天氣，故而可以得出在這一個月內(nèi)出現(xiàn)沙暴天氣的概率較少，出現(xiàn)沙暴天氣的事件為小概率事件，概率為3%～5%，即在這一個月中可能出現(xiàn)沙暴天氣的天數(shù)為0 或1 天。

這是一個多元線性規(guī)劃的問題，我們擁有天氣狀況，礦山，村莊等多個因素需要考慮，每一種天氣所要承受的風險不同。

（1）總體風險用所投資的Si中最大的一個風險來衡量，即：

（2）購買Si所付交易費是一個分段函數(shù)，即：

其中，Si（i=1，2，3）分別表示晴朗、高溫、沙暴3 種天氣，ri，pi，qi分別表示Si的平均收益率，風險損失率，交易費率，xi為投資Si的投資資金，ui為投資Si的投入總資金。

假設(shè)在起點購買負重上限（1200kg）的水和食物，在按時到達終點的情況下，易求得最多能在礦山挖礦的天數(shù)為17 天。根據(jù)實際行走的情況，分別求得：

將所求得的結(jié)果代入目標求解，算出此種情況下所獲得的最大收益?？梢钥闯?，在風險界限a=0.155 附近有一個轉(zhuǎn)折點，在這一點左邊，風險增加很少時，利潤增長很快。在這一點右邊，風險增加很大時，利潤增長很緩慢，以對于風險和收益沒有特殊偏好的投資者來說，應(yīng)該選擇曲線的拐點作為最優(yōu)投資組合，大約是a=12.5%，Q=178.9%，所對應(yīng)投資方案為：風險度a=12.5%，收益Q=178.9%。

2.3 考慮多玩家

同時分別考慮兩人都不經(jīng)過礦山，都經(jīng)過礦山，以及一人經(jīng)過礦山，一人不經(jīng)過礦山三種情況，并分別求其消耗資金。對于一人經(jīng)過一人不經(jīng)過礦山，為了使資金剩余量最大，應(yīng)避免相遇（根據(jù)游戲規(guī)則若相遇玩家必須扣除一定資金）。所以為避免相遇，我們考慮在都走最小路的情況下，有一名玩家停在原地一天，避免和另一位玩家相遇。假設(shè)玩家A 挖一天（耗資少，獲取利潤較少），玩家B（到達礦山之前停一天）挖兩天，耗資多，賺取的利潤多。在這種情況下，兩名玩家耗費的資金分別為：

2*3*55+55*3-200+2*2*55=515（元）

2*55+55+55*2+55*2*3-400+2*135*2=745（元）

綜上所述，所有出現(xiàn)的情況如表1 所示，由非合作博弈均衡可求得：

表1 非合作博弈均衡

可以看出最優(yōu)策略為：當兩名玩家一名經(jīng)過礦山在晴天的天氣情況下挖一天礦，另一名不經(jīng)過礦山直接到達終點時，在這種情況耗費的金額較少，剩余資金較多。

3 模型的求解

當有k 名玩家同時從區(qū)域A 走到區(qū)域B 時，其資源消耗量為基礎(chǔ)消耗量的2k 倍。（1）如果按資源消耗量最少的晴朗天氣，只有兩名玩家同時從A 區(qū)域到B 區(qū)域，那么每人消耗資金是220 元。（2）只有兩名玩家同時挖礦，每人資源消耗量為165 元，獲得資金數(shù)為500 元，凈賺335 元；三名玩家同時挖礦，每人凈賺135 元。（3）如果有k 名玩家在村莊買東西，那么每箱水價格變?yōu)?0 元，每箱食物價格變?yōu)?0 元。（4）如果按資源消耗量最大的沙暴天氣計算，每名玩家停留在原地的資源消耗量為150元。

由以上分析可得，應(yīng)盡量避免兩名或兩名以上玩家同時從A 區(qū)域到B 區(qū)域或一同在村莊購買東西或三名玩家在礦山挖礦。

由題意得，30 天內(nèi)較少出現(xiàn)沙暴天氣，假設(shè)30 天內(nèi)出現(xiàn)沙暴天氣的概率為0%→5%，那么只有0→1 天是沙暴天氣。分析設(shè)計路線及策略如下：假設(shè)將三名玩家編號A、B、C，首先ABC三名玩家在起點處分別購買210 箱水和280 食物，138 箱水和184 箱食物，48 箱水和64 箱食物。A、B 號玩家在第一天同時從區(qū)域1 出發(fā)，A 沿1→2→3→8→13→18，B 沿1→6→11→16→17，C 玩家則在AB 出發(fā)的第二天沿1→6→11→16→21→22→23→24→25 直接到終點，之后A 玩家在礦山挖礦，B 玩家則在原地等待，當A 玩家挖礦到23 天，A 沿18→23→24→25 回到終點，B 則在A 出發(fā)的第二天到礦山挖礦，挖到第27 天，沿18→23→24→25 回到終點。

4 結(jié)論

本文通過利用Dijkstra 與Kruskal 算法能夠清晰得到從起點到終點的最短路徑長，為玩家進行了一定的路線規(guī)劃。同時對具體的關(guān)卡基于沙暴天氣的考慮，因為題目中沒有確切地給出具體一個月內(nèi)有多少沙暴天氣，故而設(shè)定風險界限，進行了風險因素的分析，由此將多目標線性規(guī)劃轉(zhuǎn)為單目標線性規(guī)劃，使得結(jié)果更為精確。同時，用編程對此類問題進行求解，可以全面考慮約束條件對其造成的影響，使得結(jié)果更加全面、精確。