穿越沙漠的小游戏策略

张 敏 张 力 王雪锋 孟慧慧 邵光祖

（ 1、黄河交通学院数学教研室，河南 焦作454002 2、黄河交通学院智能工程学院，河南 焦作454002）

玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，在游戏设定的规则下，规定的时间内到达终点，并保留尽可能多的资金。

1 问题分析

根据地形使用广度优先遍历[1]找出任意两区域的最优路径。最优路径的选择从是否挖矿考虑：如果挖矿，则根据动态规划模型求解挖矿天数，从而规划在起点时所需储备的资源；如果不挖矿，根据求得的起点到终点的最短距离以及储备所需资源，并依据所选的最优路径求解剩余资金。比较两种情况下不同线路的剩余资金，选择剩余资金最大的线路填写“第一关”和“第二关”的结果表。

2 模型的建立与求解

2.1 游戏第一关的分析与求解

游戏中只有一名玩家，并且在整个游戏时段内每天的天气状况事先全部已知，寻找一般情况下玩家的最优策略，即寻找从起点到终点的最优路径。

使用广度优先搜索遍历方法，遍历的步骤如下：

（1）从起点1 出发，访问1 区域。

（2）依次访问1 的各个未曾访问过的相邻区域2，25。

（3）分别从这些相邻的区域出发依次访问该区域的相邻区域，并使“先被访问区域的相邻区域”先于“后被访问区域的相邻区域”被访问。

（4）重复步骤（3），直至地图中所有已被访问的区域的相邻区域都被访问到。

一般情况下，玩家的最优策略确定原则从是否挖矿方面考虑，可以分为两种方案。

表1“第一关”最优策略的部分结果表

方案一：从起点走最短路径直接到终点（不考虑挖矿）。

要想在规定时间内到达终点并尽大可能保留最多资金，则需要减少在路途上的消耗，所以需要用最短的时间从起点到达终点。从起点到终点花费最短时间的行动方案为：1（起点）→25→26→27（终点）。

为了使得玩家在到达终点时减少物资的剩余量，降低玩家到达终点后退回的剩余物资总量，从而避免在起点购买太多的物资造成资金浪费的目标，所以需要确定在起点时路程上需要的物资总量。使用Matlab 软件计算在该行动方案中路程上物资的消耗量，通过逆推求解出需要在起点购买水21 箱，食物19箱，负重101 千克，到终点时剩余资金9705 元。

方案二：从起点到终点的路径考虑去矿山挖矿。

将起点到村庄分为第一阶段，村庄到矿山再返回村庄为第二阶段，村庄到终点分为第三阶段。使用广度优先遍历方法，得出第一阶段的最优路径为1（起点）→25→24→23→22→9→15（村庄）。

根据第一阶段的最优路径和附件中给出的天气状况，得到第一阶段的行程为：第零天在1 区域（起点），第一天行走到25区域，第二天行走到24 区域，第三天行走到23 区域。由于第四天是沙暴天气，所以需要原地停留，故第四天仍旧是停留在23区域。第五天行走到22 区域，第六天行走到9 区域，由于第七天是沙暴天气，所以需要原地停留，故第七天仍旧是停留在9 区域。第八天行走到15 区域。

第二阶段为从村庄到矿山再到村庄，使用广度优先遍历的方法得到该阶段最短的路径有两条分别为：15（村庄）→13→12（矿山）→14→15（村庄）和15（村庄）→14→12（矿山）→13→15（村庄）。为了使玩家在到达终点时剩余最多的资金，所以在该阶段考虑通过挖矿来获取外来资金。由于挖矿需要考虑天气状况，所以根据该阶段的最短路线和附件中的天气要分析沙暴日是否挖矿。最坏情况为挖矿需要的资源全部到村庄购买。因为最坏情况下挖矿一天消耗的资金小于基础收益，所以沙暴天气需要挖矿。因为晴朗和高温天气比沙暴天气条件下的基础消耗量少，所以晴朗和高温天气更需要挖矿。

根据第二阶段的行程求解第二阶段所需要的总物资。根据附件中给出的天气情况列出不同天气条件下行走或停留时所需物资量。

晴朗天气行走一天消耗物资质量是58 千克，晴朗天气停留一天消耗物资质量是29 千克，高温天气行走一天消耗物资质量是72 千克，高温天气停留一天消耗物资质量是36 千克，沙暴天气挖矿时一天消耗物资质量是150 千克，沙暴天气不挖矿时每天消耗物资质量是50 千克。

附件给出的信息得到玩家的负重上限为1200 千克，所以在第二阶段物资需求量不超过1200 千克的情况下应该挖选择挖矿天数最多的路径，通过计算挖矿最大天数为7 天。根据挖矿的最大天数和第二阶段在其他区域的需求量，计算得到第二阶段需要水245 箱，食物221 箱。考虑在村庄购买物资比较贵，所以要在起点购买足够量的物资。因为食物的基准价格是水的两倍，所以使用定量的初始资金时要以食物优先（只需备足一定量的水）。使用Matlab 软件求得：在起点时，需要购买水180 箱，食物330 箱，负重总量1200 千克，剩余初始资金5800 元。

根据天气情况、第二阶段的最优线路和最大挖矿天数确定第二阶段的行程为：第九天行走到14 区域，第十天从14 区域行走到12（矿山），第十一天至第十七天在矿山挖矿（共计挖矿八天）。由于沙暴天气第十八天在12（矿山）区域停留，第十九天从12（矿山）区域走到14 区域，第二十天从14 区域走到15 区域（村庄）。

由于第三阶段是从村庄回到终点，为了减少该阶段玩家在行程上资源的消耗，所以该阶段的最优路径为最短路径。运用广度优先搜素遍历方法得到第三阶段的最短路径为：15（村庄）→9→21→27（终点）。

根据最短路径确定第三阶段的行程为：第二十一天行走到9 区域，第22 天行走到21 区域，第23 天行走到27 区域（终点）。

根据第三阶段行程上的物资消耗情况求解第三阶段物资购买数量。使用Matlab 软件求解出第三阶段需要在村庄购买水36 箱，食物19 箱，此时的剩余资金为4170 元。该方案第23 天到达终点，此时剩余水量为0 箱，剩余食物量为0 箱，剩余资金数为10430 元。

比较第一关的两种方案，发现方案二比方案一的剩余资金数大，据此得出本关游戏玩家的最优的策略为：1→25→24→23→22→9→15（村庄）→14→12（矿山）→14→15（村庄）→9→21→27（终点）。

利用Matlab 软件计算出第一关玩家每天的结果。如表1。

2.2 游戏第二关的分析与求解

第二关寻找最优策略的方案与第一关相似。观察第二关的地图可以发现有两个村庄和两个矿场（其中一个矿山位于30 区域，距离起点近）。

为保证单次路线中挖矿天数最长，根据贪心算法得到从起点到终点的最优策略是玩家需要先从起点到离矿山区域最近的村庄购买能够达到最佳状态的物资后再去挖矿。挖矿结束后要使剩余的物资能够到达距离挖矿矿山最近村庄，以便于回到村庄进行购买物资。根据广度优先遍历方法，得出在购买物资后，从村庄到矿山再到终点的最短天数比从村庄直接到达终点的最短天数多1 天。使用Matlab 软件计算出在矿山区域挖矿的最大天数为4 天。

表2“第二关”最优策略的部分结果表

根据上述分析和第二关的地图，把起点到终点的路线分为三个阶段，第一阶段为从起点直接到39 区域（村庄），第二阶段为从39 区域（村庄）到30 区域（矿山），在该区域挖最大天数的矿后回到39 区域（村庄），第三阶段为从39 区域（村庄）到55 区域（矿山）挖矿后直接回到64 区域（终点）。

使用广度优先遍历方法，从起点到30 区域的矿山区的最短路径为7 步，分别为：

第一条路径为：1（起点）→2→10→19→27→28→29→30（矿山）

第二条路径为：1（起点）→2→3→4→5→13→22→30（矿山）

第三条路径为：1（起点）→2→10→19→20→28→29→30（矿山）

从30 区域（矿山）到39 区域（村庄）最短路径为1 步，根据广度优先搜索遍历得到从1（区域）起点到39 区域（村庄）的最短路径就是最优路径。分析求解发现第一阶段的最短路径线路不唯一，但都是七步，所以无论选择哪一条路径行走物资的消耗量都是相等的。

由附件给出的信息得到负重上限为1200 千克。所以在第二阶段物资需求量不超过1200 千克的情况下应该挖最大天数的矿，通过计算挖矿的最大天数为7 天。根据挖矿的最大天数和第二阶段在其他区域的需求量，计算得到第二阶段需要首先在村庄购买水195 箱，食物0 箱。考虑在村庄购买物资比较贵，所以要在起点购买足够量的物资。因为食物的基准价格是水的两倍，所以使用定量的初始资金时要以食物优先（只需备足一定量的水）。使用Matlab 软件求得：在起点时，需要购买水166 箱，食物350 箱，负重总量1198 千克，剩余初始资金5670 元。

先去30 区域（矿山）挖矿，直到消耗后所剩的物资和水仅支持从30 区域（矿山）转移到39 区域（村庄）。根据第三阶段玩家在路上的物资消耗量确定回到村庄时需要第二次购买水157箱，食物140 箱，剩余初始资金7350 元。

分析第三阶段从39 区域（村庄）出发直接到达终点时的线路，根据地图得出该阶段的最短线路不唯一，但是最短线路上玩家的消耗量是相同的。到达终点时剩余水量0 箱，食物0 箱，剩余资金数12350 元。

使用Matlab 软件计算出玩家在一般情况下第二关的最优策略的结果。结果如表2。

该方案显示玩家在第30 天到达终点时，此时剩余水量为0箱，剩余食物量为0 箱，剩余资金数为12350 元。

3 结论

从是否挖矿角度出发，如果挖矿，则根据动态规划模型求解挖矿天数，从而规划在起点时所需储备的资源；如果不挖矿，根据求得的起点到终点的最短距离以及储备所需资源，依据所选的最优方案计算剩余资金。