基于Bellman- Ford 算法的穿越沙漠策略研究

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

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

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

1 問題分析

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

2 模型的建立與求解

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

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

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

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

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

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

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

3 結(jié)論

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