分布优化模型下穿越沙漠游戏攻略

摘要：穿越沙漠游戏非常有趣，受资金、水、食物及天气的限制，成功完成游戏有一定的困难。本论文根据游戏的不同设定，建立穿越沙漠游戏的数学模型，得到行动路线最优策略。对于第一关，首先，以剩余资金为目标函数，以水、食物及天气为约束条件，分别建立不经过矿山到达终点和途径矿山到达终点的最优策略模型。然后，通过比较剩余资金，得到最优路线为1→5→6→13或1→4→6→13，且在初始起点备54箱水和食物。对于第二关，首先，根据沙暴出现的概率，建立路线分步优化模型，利用决策树算法，得到不同沙暴出现次数的最优策略。最后，给出一般情况下玩家的最佳策略（见表1）。

关键词：穿越沙漠；分步优化模型；Dijkstra算法；最短路径算法

1模型建立与求解

1.1针对第一关

首先将地图转化为点和线组成的无向图[1]，如图1所示。其中，“1”为起点，“13”为终点。接着利用Dijkstra算法[2，3]对从起点到矿山、矿山到终点和起点到终点的最短路径求解。观察分析可得出起点到矿山和起点到终点的最短路径都是需行走三天，因为前三天整个地图的天气一样，所以从起点去矿山或者直接去终点所消耗的资源一样。因此只需要计算方案二到达矿山后挖矿赚取的收益与从矿山到达终点消耗资源金额的对比，从而确定最优策略。假设方案二到矿山后的7天全部为晴朗，计算所得的收益与消耗之间的关系如下：其中Bw1为行走时所消耗的水；Bf1为行走时所消耗的食物；Bw2为在矿山所消耗的水；Bf2为在矿山所消耗的食物；ω为花费金额。

1.2针对第二关

首先，从起点到村庄，走其最短路径。通过计算发现在前四步跨区域的行程中，无论经历的沙暴是0天还是9天，都要回村庄补给完毕后再去挖矿所得经济效益最高。所以无论沙暴出现在哪一天，从起点出发的第一步都是都是前往村庄。在到达村庄前，最坏的情况为遭遇9天沙暴且行进时为高温天气，所以在起点要备足经历9天沙暴和5天高温行程的水和食物，又要保证在村庄补给所花费的资金最少，因此带到的村庄的极限水量，剩余容量全部带食物，以尽量减少食物在村庄的购买，即在起点所购资源为180箱水和330箱食物。然后，对第二关的地图进行无权重、无方向的抽象表达（如图2），其中“1”为起点，“25”为终点。观察发现其为矩形的路线图，到达目的地有多种路线。于是我们在最短的路径中任意选择一条路线进行标记（如图3）。在众多路径当中会出现影响决策的路径，称为关键路径。假设天气最坏的情况发生在每一段关键路径上，作为决策判断的依据。连续几天集中发生沙暴为最坏的天气情况，以最坏的结果作为依据，在关键点统计沙暴出现的结果对列举的几种情况进行匹配，按照符合的情况对购买水和食物和挖矿天数进行决策。具体出现连续沙暴天气的情况：情况一：出现在第一阶段（图3中1→2→3→8→12→村庄14）：解决策略1：到达村庄时在起点准备的水刚好到极限，因为不同天气对水和食物消耗均接近1:1，所以后续补充水和食物以1：1的比例补充至背包承重的上限，即240箱水、240箱食物。因为9次沙暴在第一阶段全部发生过，后续的天气按照高温计算，后续会出现两次抉择的地方，通过计算比较选出最优方案，如图3所示，从起点→村庄（离开时备足240箱水和240箱食物）→矿山（工作6天）→终点为最优方案。情况二：出现在第二阶段（图3中村庄14→19）的村庄。沙暴出现在村庄上可以随时补充食物和水即出发时可以带足够的水和食物，240箱食物，240箱水。对后续的路程进行比较和选择，确定出最佳路线，与第一种解决策略相同。情况三：出现在第二阶段（图3中村庄14→19）的19号区域。解决策略2：那么就面临两大抉择：回村补给还是直接去矿山，两个抉择又面临着不同的选择。穷举不同的方案选择出最优的方案，即起点→村庄（补充水为225箱，食物不增加）→19号区域（因沙暴阻碍行动9天）→矿山（工作两天）→终点。情况四：出现在第二阶段（图3中19→矿山18）的矿山上。解决策略3：面临两大抉择是回村补给还是直接去矿山，两个抉择的后面又有不同的选择，穷举不同的方案选择出最优的方案，最优的方案为起点→村庄（补充水到240箱）→矿山（工作三天休息六天）→村庄（水补充到225箱，食物补充到225箱）→矿山（工作五天）→终点。情况五：出现在第三阶段（图3中矿山18→19）的19号区域。解决策略4：最优的行进路线为起点→村庄（补充水到240箱）→矿山（工作两天）→19号区域（阻碍行进9天）→村庄（水补充到225箱，食物补充到225箱）→矿山（工作5天）→终点。情况六：出现在第四阶段（图3中19→矿山14）的村庄。解决策略5：最优的行进路线为起点→村庄（补充水到240箱）→矿山（工作六天）→村庄（水补充到54箱，食物补充到54箱）→终点。情况七：出现在第五阶段（图3中村庄14→15→20→终点25）的路径。解决策略6：最优的行进路线为起点→村庄（补充水到240箱）→矿山（工作六天）→村庄（水补充到144箱，食物补充到144箱）→在路径被阻碍9天→终点。情况八：出现在第六阶段（图3中矿山18→23→24→终点25）的矿山。解决策略7：最优的行进路线为起点→村庄（补充水到240箱）→矿山（工作六天）→村庄（补充水到240箱，食物补充到240箱）→矿山（工作三天休息六天）→终点。情况九：出现在第六阶段（图3中矿山18→23→24→终点25）的从矿山出来到终点的行径。解决策略8：最优的行进路线为起点→村庄（补充水到240箱）→矿山（工作六天）→村庄（补充水到207箱，食物补充到207箱）→矿山（工作一天）→在路径被阻碍9天→终点。

2求解结果

对于第一关，因为ωp>ωs，所以即使在7天全部是晴朗的最好的天气情况下挖矿资源的消耗和跨区域移动消耗的物资的价值也大于挖矿的收益，所以最优的游戏策略就是走最短路径直接返回终点即。资源的分配为：带足三天遇到最差天气（三天高温）所用的物资，即54箱水和54箱食物。对于第二关，可能连续出现9天沙暴和其余天气为高温的情况进行分类匹配，具体的结果见表1。

参考文献

[1]司守奎,孙兆亮.数学建模算法与应用[M].北京：国防工业出版社,2015.

[2]刘洋洋.基于改进Dijkstra算法的自驾游最优路径规划研究[J].科学技术创新,2020(17):75-77.

[3]刘志威,杨莉琼,谢永胜,刘鹏,佘培培.基于改进Dijkstra算法的川藏铁路站房工程物资动态调运研究[J].建筑经济,2020,41(S1):166-170.

[4]赵卫绩,巩占宇,王雯,樊守芳.几种经典的最短路径算法比较分析[J].赤峰学院学报(自然科学版),2018,34(12):47-49.

作者:苏盈文 刘佳园 张向远 单位:兰州理工大学理学院 兰州理工大学机电工程学院 兰州理工大学计算机与通信学院