基于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月 男 汉 山东省济宁市 学生 本科（在读）飞行器动力工程