陈明浩 吴耀峰 刘博

摘要：本文是针对穿越沙漠游戏的规划，考虑消耗与收益，逐步优化得到规划方案。本文运用Dijkstra算法，分成三类讨论建立终点最大资本的目标函数，使用基于蚁群系统的地图全遍历算法，使得出第一关和第二关到达终点时剩余资金的最大值分别为10470元，12730元。在处理沙漠地区近10年天气的基础上，将天气情况转为为已知，做出最优路线规划问题，可得到到达终点时资本最大值的区间为[8650，9625]。

关键词：邻接矩阵  Dijkstra算法  蚁群系统的全遍历算法  线性规划

1 研究背景

穿越沙漠是基于互联网时代推出的一款策略游戏。现有一张游戏地图，我们以规定时间内到达终点且获得最大资金为目标，在进行游戏过程中，需考虑诸多因素，如在途中遇到不同的天气，在矿山的资金收益和在村庄的资源的补充，根据题目，在不同的天气基本消耗和村庄与起点购买资源金额均不同。

2 模型的建立与求解

2.1问题一的模型建立

第一关给出了30天的天气状况，每一个玩家都可以向临界的区域移动或者选择停留原地，在风暴日必须停留原地。而根据附件介绍第一关和第二关其差别主要是在地图上。处理地图上移动问题，对地图进行优化简化处理，来进行选择路线。

对第一关用Dijkstra算法找出最短路径，然后进行优化处理。可以分为三种情况：

（1） 不经过矿山和村庄直接到达终点。

（2） 经过村庄不经过矿山直接到达终点。

（3） 经过村庄和矿山到达终点。

对于以上三种情况的分析，分别算出三大类的最后收益。……