基于Dijkstra算法的沙漠路徑規劃研究

陳明浩 吳耀峰 劉博

摘要：本文是針對穿越沙漠游戲的規劃，考慮消耗與收益，逐步優化得到規劃方案。本文運用Dijkstra算法，分成三類討論建立終點最大資本的目標函數，使用基于蟻群系統的地圖全遍歷算法，使得出第一關和第二關到達終點時剩余資金的最大值分別為10470元，12730元。在處理沙漠地區近10年天氣的基礎上，將天氣情況轉為為已知，做出最優路線規劃問題，可得到到達終點時資本最大值的區間為[8650，9625]。

關鍵詞：鄰接矩陣 ?Dijkstra算法 ?蟻群系統的全遍歷算法 ?線性規劃

1 研究背景

穿越沙漠是基于互聯網時代推出的一款策略游戲。現有一張游戲地圖，我們以規定時間內到達終點且獲得最大資金為目標，在進行游戲過程中，需考慮諸多因素，如在途中遇到不同的天氣，在礦山的資金收益和在村莊的資源的補充，根據題目，在不同的天氣基本消耗和村莊與起點購買資源金額均不同。

2 模型的建立與求解

2.1問題一的模型建立

第一關給出了30天的天氣狀況，每一個玩家都可以向臨界的區域移動或者選擇停留原地，在風暴日必須停留原地。而根據附件介紹第一關和第二關其差別主要是在地圖上。處理地圖上移動問題，對地圖進行優化簡化處理，來進行選擇路線。

對第一關用Dijkstra算法找出最短路徑，然后進行優化處理。可以分為三種情況：

（1） 不經過礦山和村莊直接到達終點。

（2） 經過村莊不經過礦山直接到達終點。

（3） 經過村莊和礦山到達終點。

對于以上三種情況的分析，分別算出三大類的最后收益。對游戲過程進行分析，看得出三種情況的動態規劃函數。

3 模型評價

3.1 模型優點

1）在各個求最短路徑過程中，我們采用的DP算法可以快速算出兩點之間最短距離，為各個關卡提供基礎。

2）在求解過程中，我們采用樹狀搜索的蒙特卡洛隨機模擬的方法，可以通過大量的隨機模擬，推算出一個最優的收益路線，這是出于MCTS最佳的搜索技術，可以最快的找出最優的路徑決策。

3）我們基于已有的算法模型，進行模塊分析，逐步求出最優解。

3.2 模型缺點

1） 運算規模較大，不夠簡化。

2） 我們在一般情況概率設定考慮因素并不全面，題中所含天氣只有三種用所建立的模型求解十分簡單，但是若天氣狀況復雜多變，所建立的模型就十分難以實現，不能直接應用在現實生活中。

參考文獻

[1] 閆登福.基于距離可達矩陣的自架游路線優化研究[D].東北大學，2012.

[2] 吳張家善.基于改進蟻群算法的物流配送車輛路徑優化研究[D].遼寧工程技術大學，2014.

[3] 譚明金.基于邊界相鄰三點的區域遍歷算法[J].中國圖象圖形學報，2003年，第8卷（A版），第3期，2003.

[4] 何所俱.人工智能在游戲中的應用[D].北京郵電大學，2010.

[5] 高瑞苑，張寒凝.基于博弈論的多人游戲設計研究.大眾美學，美術與設計.

作者簡介

陳明浩 2000年6月 男 漢 山東省濟寧市 學生 本科（在讀）飛行器動力工程