基于分布优化模型的穿越沙漠游戏攻略

苏盈文 刘佳园 张向远

（1、兰州理工大学理学院，甘肃 兰州 730050 2、兰州理工大学机电工程学院，甘肃 兰州 730050 3、兰州理工大学计算机与通信学院，甘肃 兰州 730050）

1 模型建立与求解

1.1 针对第一关

首先将地图转化为点和线组成的无向图[1]，如图1 所示。其中，“1”为起点，“13”为终点。接着利用Dijkstra 算法[2，3]对从起点到矿山、矿山到终点和起点到终点的最短路径求解。

图1 第一关路径无向图

观察分析可得出起点到矿山和起点到终点的最短路径都是需行走三天，因为前三天整个地图的天气一样，所以从起点去矿山或者直接去终点所消耗的资源一样。因此只需要计算方案二到达矿山后挖矿赚取的收益与从矿山到达终点消耗资源金额的对比，从而确定最优策略。

假设方案二到矿山后的7 天全部为晴朗，计算所得的收益与消耗之间的关系如下：

其中Bw1为行走时所消耗的水；Bf1为行走时所消耗的食物；Bw2为在矿山所消耗的水；Bf2为在矿山所消耗的食物；ω 为花费金额。

1.2 针对第二关

首先，从起点到村庄，走其最短路径。通过计算发现在前四步跨区域的行程中，无论经历的沙暴是0 天还是9 天，都要回村庄补给完毕后再去挖矿所得经济效益最高。所以无论沙暴出现在哪一天，从起点出发的第一步都是都是前往村庄。在到达村庄前，最坏的情况为遭遇9 天沙暴且行进时为高温天气，所以在起点要备足经历9 天沙暴和5 天高温行程的水和食物，又要保证在村庄补给所花费的资金最少，因此带到的村庄的极限水量，剩余容量全部带食物，以尽量减少食物在村庄的购买，即在起点所购资源为180 箱水和330 箱食物。

然后，对第二关的地图进行无权重、无方向的抽象表达（如图2），其中“1”为起点，“25”为终点。观察发现其为矩形的路线图，到达目的地有多种路线。于是我们在最短的路径中任意选择一条路线进行标记（如图3）。

图2 第二关路径无向图

图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 第二关不同情况下的解决策略