基于Dijkstra算法的沙漠路徑規(guī)劃研究

陳明浩 吳耀峰 劉博

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

關(guān)鍵詞：鄰接矩陣 ?Dijkstra算法 ?蟻群系統(tǒng)的全遍歷算法 ?線性規(guī)劃

1 研究背景

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

2 模型的建立與求解

2.1問題一的模型建立

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

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

（1） 不經(jīng)過礦山和村莊直接到達終點。

（2） 經(jīng)過村莊不經(jīng)過礦山直接到達終點。

（3） 經(jīng)過村莊和礦山到達終點。

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

3 模型評價

3.1 模型優(yōu)點

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

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

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

3.2 模型缺點

1） 運算規(guī)模較大，不夠簡化。

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

參考文獻

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

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

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

[4] 何所俱.人工智能在游戲中的應(yīng)用[D].北京郵電大學(xué)，2010.

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

作者簡介

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