蘇禧媛

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

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

1 問題分析

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

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

2 模型建立與求解

2.1 Dijkstra 與Kruskal 算法運(yùn)用

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

圖1 起點(diǎn)→礦山→終點(diǎn)最短路徑

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

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

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

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

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

（1）總體風(fēng)險(xiǎn)用所投資的Si中最大的一個(gè)風(fēng)險(xiǎn)來衡量，即：

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

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

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

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

2.3 考慮多玩家

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

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)策略為：當(dāng)兩名玩家一名經(jīng)過礦山在晴天的天氣情況下挖一天礦，另一名不經(jīng)過礦山直接到達(dá)終點(diǎn)時(shí)，在這種情況耗費(fèi)的金額較少，剩余資金較多。

3 模型的求解

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

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

由題意得，30 天內(nèi)較少出現(xiàn)沙暴天氣，假設(shè)30 天內(nèi)出現(xiàn)沙暴天氣的概率為0%→5%，那么只有0→1 天是沙暴天氣。分析設(shè)計(jì)路線及策略如下：假設(shè)將三名玩家編號A、B、C，首先ABC三名玩家在起點(diǎn)處分別購買210 箱水和280 食物，138 箱水和184 箱食物，48 箱水和64 箱食物。A、B 號玩家在第一天同時(shí)從區(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 直接到終點(diǎn)，之后A 玩家在礦山挖礦，B 玩家則在原地等待，當(dāng)A 玩家挖礦到23 天，A 沿18→23→24→25 回到終點(diǎn)，B 則在A 出發(fā)的第二天到礦山挖礦，挖到第27 天，沿18→23→24→25 回到終點(diǎn)。

4 結(jié)論

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