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

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

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

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

1 問題分析

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

2 模型的建立與求解

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

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

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

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

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

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

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

3 結論

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