臧 洋 師 艷 景港澳 陳萌琪 趙 怡

（1、蘭州理工大學(xué)土木工程學(xué)院，甘肅 蘭州730050 2、蘭州理工大學(xué)理學(xué)院，甘肅 蘭州730050 3、蘭州理工大學(xué)材料科學(xué)與工程學(xué)院，甘肅 蘭州730050 4、湖北汽車(chē)工業(yè)學(xué)院，湖北 十堰442000）

玩家憑借一張地圖，利用初始資金購(gòu)買(mǎi)一定數(shù)量的水和食物（包括食品和其他日常用品），從起點(diǎn)出發(fā)，在沙漠中行走。途中會(huì)遇到不同的天氣，也可在礦山、村莊補(bǔ)充資金或資源，目標(biāo)是在規(guī)定時(shí)間內(nèi)到達(dá)終點(diǎn)，并保留盡可能多的資金。游戲開(kāi)始的時(shí)間為第0 天，玩家位于起點(diǎn)。玩家必須在截止日期或之前到達(dá)終點(diǎn)，到達(dá)終點(diǎn)后該玩家的戲結(jié)束。穿越沙漠需水和食物兩種資源，每天玩家擁有的水和食物質(zhì)量之和不能超過(guò)負(fù)重上限。玩家在礦山停留時(shí)，可通過(guò)挖礦獲得資金，挖礦一天獲得的資金量稱為基礎(chǔ)收益。玩家經(jīng)過(guò)或在村莊停留時(shí)可用剩余的初始資金或挖礦獲得的資金隨時(shí)購(gòu)買(mǎi)水和食物，若未到達(dá)終點(diǎn)而水或食物已耗盡，視為游戲失敗。

1 問(wèn)題分析

假設(shè)只有一名玩家，在整個(gè)游戲時(shí)段內(nèi)每天天氣狀況事先全部已知，第一關(guān)和第二關(guān)路線全部分設(shè)定為經(jīng)過(guò)礦山和村莊以及不經(jīng)過(guò)礦山和村莊這兩種路線進(jìn)行建模，兩者結(jié)合更加科學(xué)合理的幫助玩家穿越沙漠以及得到最大資金，規(guī)劃以最短流程經(jīng)過(guò)礦山和村莊以及停留礦山最久時(shí)間，所達(dá)到資金最大化，同時(shí)又保證食物充足以及在30 天內(nèi)完成。我們分別從玩家路線一致且經(jīng)過(guò)礦山的情況和不經(jīng)過(guò)礦山的情況以及玩家路線不一致經(jīng)過(guò)或不經(jīng)過(guò)礦山的情況進(jìn)行對(duì)比分析，最終確定兩名玩家路線不一致時(shí)，且不經(jīng)過(guò)礦山，該路線是最優(yōu)策略。我們基于所計(jì)算的最短路線的基礎(chǔ)上分別考慮了晴朗天氣和高溫天氣的所有情況，最終得到在不經(jīng)過(guò)礦山的最短路線為，且全是晴天的情況下，達(dá)到終點(diǎn)的最佳收益最高為9670 元，該路線為最優(yōu)策略。

2 模型的建立與求解

我們通過(guò)對(duì)路線實(shí)際情況的分析，把兩種情況路線全部分為經(jīng)過(guò)礦山和村莊以及不經(jīng)過(guò)礦山和村莊兩種路線進(jìn)行建模，兩者結(jié)合進(jìn)行比較更加科學(xué)合理的確定玩家穿模沙漠的最佳策略。初始化：將除源點(diǎn)外的所有頂點(diǎn)的最優(yōu)距離估計(jì)值：d[v]←+∞，d[s]←0。分布式迭代求解:反復(fù)對(duì)邊集E 中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集V 中的每個(gè)頂點(diǎn)v 的最優(yōu)距離估計(jì)值逐步接近其最優(yōu)距離（運(yùn)行v-1 次）。檢驗(yàn)負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個(gè)端點(diǎn)是否收斂。如果存在未收斂的頂點(diǎn)，則算法返回false，表明問(wèn)題無(wú)解；否則算法返回true，并且從源點(diǎn)可達(dá)的頂點(diǎn)v 的最優(yōu)距離保存在d[v]中。[2]我們先假設(shè)不經(jīng)過(guò)礦山和村莊，最短時(shí)間到達(dá)終點(diǎn)時(shí)在穿越沙漠中水和食物最小消耗量以及剩余的的資金總和，利用Matlab 建立模型并繪圖。

以經(jīng)過(guò)礦山和村莊建立模型，規(guī)劃以最短路徑經(jīng)過(guò)礦山和村莊以及停留礦山最久時(shí)間，所達(dá)到資金的最大化，同時(shí)又保證食物充足以及在截止日期30 天內(nèi)完成，根據(jù)Bellman-Ford算法得出從起點(diǎn)到達(dá)礦山的最近距離，以及得到從礦山出發(fā)到達(dá)終點(diǎn)的最短路線，找到最小損耗路線。

通過(guò)建立目標(biāo)函數(shù)和約束條件，得出線性規(guī)劃問(wèn)題，最終通過(guò)求解線性規(guī)劃問(wèn)題，得到每種情況的最優(yōu)策略。線性規(guī)劃的目標(biāo)函數(shù)可以是求最大值，也可以是求最小值，約束條件可以是不等式也可以是等式，變量可以有非負(fù)要求也可以沒(méi)有非負(fù)要求。為了避免這種由于形式多樣性而帶來(lái)的不便，規(guī)定線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為[3]：

線性規(guī)劃的標(biāo)準(zhǔn)形式要求目標(biāo)函數(shù)最小化，約束條件取等式，變量非負(fù)。由于題目所給玩家數(shù)量確定，所以該問(wèn)題間接轉(zhuǎn)化成定量分析討論，其規(guī)則是若某天其中的任意k（2燮k燮n）名玩家均從區(qū)域A 行走到區(qū)域B（B≠A），則他們中的任一位消耗的資源數(shù)量均為基礎(chǔ)消耗量的2k 倍；n=2，則有2 名玩家，由題意可知2 人是一同行動(dòng)的。所以他們每人平均基礎(chǔ)消耗量為一人（單獨(dú)行動(dòng)）的2 倍。在兩種方案的條件下進(jìn)行路線規(guī)劃，分別分為：從起點(diǎn)出發(fā)到達(dá)礦山，然后從礦山到達(dá)終點(diǎn)的最短路徑（此時(shí)不考慮在礦山的停留時(shí)間）；從起點(diǎn)出發(fā)不經(jīng)過(guò)礦山直達(dá)終點(diǎn)的最短路徑。在最短路線的基礎(chǔ)上考慮天氣狀況和玩家路線是否重合，從而確定最佳收益路線。對(duì)于天氣狀況已知，排除考慮，我們分別從玩家路線一致且經(jīng)過(guò)礦山的情況和不經(jīng)過(guò)礦山的情況以及玩家路線不一致經(jīng)過(guò)或不經(jīng)過(guò)礦山的情況進(jìn)行對(duì)比分析，最終確定兩名玩家路線不一致時(shí)，且不經(jīng)過(guò)礦山，該路線是最優(yōu)策略。由于每名玩家僅知道當(dāng)天的天氣狀況，因此我們考慮建立時(shí)間序列模型，做出三十天的天氣預(yù)測(cè)，并結(jié)合Bellman-Ford 算法與不同方案進(jìn)行迭代，得到最優(yōu)路線策略。經(jīng)典的時(shí)間序列模型包括移動(dòng)平均模型、自回歸模型、自回歸移動(dòng)平均模型。假設(shè)xt表示t 時(shí)刻的時(shí)間序列的值，q 表示時(shí)間窗的大小，εt表示t 時(shí)刻的白噪聲，

注意到對(duì)于ARMA 模型，當(dāng)權(quán)重系數(shù)β1，…，βq全為0時(shí)，其可以被看作一個(gè)AR 模型[4]。因?yàn)镸A，AR 和ARMA 都具有弱平穩(wěn)性，其均值和協(xié)方差都不取決于t，即：E（Xt）=μ，cov（Xt，Xt+k）=E（Xt-u）（Xt+k-u）=γk，k∈Z 分別做出了四種情況下的最短路線：第一種情況是在不經(jīng)過(guò)礦山情況下最短路徑為路線11（此時(shí)視為兩名玩家路線一致），第二種情況是經(jīng)過(guò)礦山的最短路徑是路線12（此時(shí)視為兩名玩家路線一致），第三種情況是兩名玩家路線均不一致經(jīng)過(guò)礦山到達(dá)終點(diǎn)最短路徑13，第四種情況是兩名玩家路線均不一致不經(jīng)過(guò)礦山到達(dá)終點(diǎn)最短路徑是14。

根據(jù)建立的模型，分別假設(shè)經(jīng)過(guò)礦山和村莊及不經(jīng)過(guò)礦山和村莊這兩種不同的假設(shè)確定兩條最短路線（不考慮停留情況），在這兩條的最短路線的基礎(chǔ)上同時(shí)考慮天氣情況和挖礦停留時(shí)間。因?yàn)橥婕覂H知道當(dāng)天的天氣狀況，只能據(jù)此決定當(dāng)天的行動(dòng)方案。游戲條件不考慮沙暴，我們基于所計(jì)算的最短路線的基礎(chǔ)上分別考慮了晴朗天氣和高溫天氣的所有情況，最終得到在不經(jīng)過(guò)礦山的最短路線為，且全是晴天的情況下，達(dá)到終點(diǎn)的最佳收益最高為9670 元，該路線為最優(yōu)策略?？紤]到沙暴天氣的取值介于0～9 之間，通過(guò)建立目標(biāo)函數(shù)和約束條件，得出線性規(guī)劃問(wèn)題模型，最終通過(guò)求解線性規(guī)劃問(wèn)題，得到每種情況的最優(yōu)策略。在最短路線的基礎(chǔ)上考慮天氣狀況和玩家路線是否重合，從而確定最佳收益路線。對(duì)于天氣狀況已知，故排除考慮，我們分別從玩家路線一致且經(jīng)過(guò)礦山的情況和不經(jīng)過(guò)礦山的情況以及玩家路線不一致經(jīng)過(guò)或不經(jīng)過(guò)礦山的情況進(jìn)行對(duì)比分析，最終確定兩名玩家路線不一致時(shí)，且不經(jīng)過(guò)礦山，該路線是最優(yōu)策略。

由于每名玩家僅知道當(dāng)天的天氣狀況，因此我們考慮建立時(shí)間序列分析模型，做出三十天的天氣預(yù)測(cè)，并結(jié)合Bellman-Ford 算法與不同方案進(jìn)行迭代，得到最優(yōu)路線策略2人共同挖礦，另一個(gè)人以最短路線經(jīng)過(guò)所得資金最多，為57760元。最后對(duì)模型的優(yōu)缺點(diǎn)進(jìn)行了討論，主要分析了未考慮到折返情況及特殊情況下天氣對(duì)整個(gè)路線規(guī)劃的影響。

3 結(jié)論

首先兩種方案的條件下進(jìn)行路線規(guī)劃，分別從起點(diǎn)出發(fā)到達(dá)礦山，然后從礦山到達(dá)終點(diǎn)的最短路徑，從起點(diǎn)出發(fā)不經(jīng)過(guò)礦山直達(dá)終點(diǎn)的最短路徑，在最短路線的基礎(chǔ)上考慮天氣狀況和玩家路線是否重合，從而確定最佳收益路線。當(dāng)天氣狀況已知，排除考慮，我們分別從玩家路線一致且經(jīng)過(guò)礦山的情況和不經(jīng)過(guò)礦山的情況以及玩家路線不一致經(jīng)過(guò)或不經(jīng)過(guò)礦山的情況進(jìn)行對(duì)比分析，最終確定兩名玩家路線不一致時(shí)，且不經(jīng)過(guò)礦山，該路線是最優(yōu)策略。對(duì)于每名玩家僅知道當(dāng)天的天氣狀況，因此我們考慮建立時(shí)間序列模型，做出三十天的天氣預(yù)測(cè)，并結(jié)合Bellman-Ford 算法與不同方案進(jìn)行迭代，得到最優(yōu)路線策略。