“穿越沙漠”游戏最短路径研究

程 凯 邵义聪 何 钦

（华东理工大学信息科学与工程学院，上海200000）

在沙漠的地理环境下进行穿越活动需要考虑到相关地理、水文及食物等条件的制约，极大的限制着相关人员在沙漠地区活动路线的选择。沙漠占据地球陆地面积的1/4，沙漠天气和气候对全球生态、环境及气候等的影响一直都受到社会各界极大关注[1]。在游戏背景中针对不同的地图，设有不同地区，例如矿山和村庄会有相应的材料补充，同样也会投入一些物品。在沙漠途中不同的天气条件、不同的路线选择可能会加剧食物的消费也可能会得到相关食物补充的机会。因此，不同的路线选择方案以及初始点携带物品的数量及比例将会决定能否按时到达终点以及极大的影响到达终点所剩的资金数量。

1 问题分析

游戏开始时为第0 天，须在规定时间内到达终点，且每日路线选择只能在相邻地区进行。根据初始资金购买水和食物，原地停留有基础消耗且行走一天消耗加倍，且到达终点前不能消耗至0。到达终点后如有剩余食物和水退回基准价格的一半。共有三种可能的天气情况：“晴朗”、“高温”、“沙暴”。沙暴日必须原地停留一日。在矿山挖矿一天可获得基础收益，消耗资源数为基础消耗的3 倍，且到达矿山当天不能挖矿。沙暴日可挖矿，在村庄时可购买水和食物，价格为基准价格的2 倍。在已知天气的情况下，首先需要针对路线进行分析得到能够节省最多花费的路线。其次，在只知道当天天气条件下，如何选择能使一名玩家在达到终点时获得最多的资金。针对所有天气状况已知的情况下，两名玩家需要在第0 天规划好所有行程，但两人同行或同时挖矿会造成消耗的增加及收益的减少，同样在多人同行时会增大消耗并降低挖矿收益，且只能获取当天的天气状况。知晓其他玩家的资源剩余数量。

2 模型的建立与求解

首先假设所有游戏规定的天数下均没有沙暴天气，分别计算出起点、村庄、矿山以及终点之间的最短的天数。为了在终点获得更多的资金总额，分别计算出：起点一终点；起点一矿山（多次）-T 终点两条路线的总花费，同时计算出沿途需要的食物和水的质量并考虑携带的质量限制。如若沿途任意时间点的食物和水不足以支撑当天的消耗，则需更改路径，考虑去村庄补充食物及水。选择起点至终点最短路径可以消耗较少的食物和水因而获得较多的剩余资金。然而，途径矿山采矿在部分天气条件下可以挣的额外的收入，可以获取额外收入因此考虑先以最短路径前往矿山进行挖矿。需要注意的是：在起点时购买物资需要考虑携带物资重量的同时观察到食物的价格比水的价格高且质量较轻。

因此可以考虑在起点时相对多购买食物少购买水，并在村庄进行相对较多的饮用水补给，降低在村庄的食物补给。而在第二条选择当中，需要考虑到挖矿过程中天气状况，由于挖矿过程中的消耗为基础消耗的3 倍，且高温天气和沙暴天气相比，因此需要权衡挖矿的天数和挖矿的时间在暴雨或高温天气时可能依据之后的天气状况暂停挖矿。如公式所示为在沙暴天气条件下的挖矿实际获得资金数：

阐述了在沙暴天气条件次下，挖矿一天获得的净收益，事实上由于挖矿的巨大消耗，在净收益的计算当中引入了在商店购买水和食物的价格，即：

Stormmoney=1000-30·10-30·20=100

事实上除了挖矿一天的资金净收入，由于特殊天气状况会出现高温、沙暴天气的连续出现，经常需要计算评估在到达矿山后为了减少高温或沙暴天食物和水的消耗而停留一天，再进行挖矿作业的资金净收入，因此列出在矿山停留一天的净收入：

矿山停留一天的净收入由两部分表示：沙暴天气下停留一天的消耗，晴朗天挖矿工作一天的消耗，即：

如此选择停留一天，实则多积赞了30 元资金，但与此同时需要多消耗一天时间且需要特殊的天气条件。依据此原则，遍历所有可能的即可得到最优路径及最终的金额总数。通过Matlab 程序即可得到最优线路，如下图所示：

最终路线

其中在23 号区域停留两天，9 号区域停留两天，12 号矿山区域共停留9 天，其中挖矿7 天。由于在终点水和食物的换算价格仅为起始点的一半，故在到达终点时要尽可能使得剩余食物和水消耗完毕，Matlab 程序最终给出的剩余总资金为10430 元，在23 号到达终点。

此线路的最终结论显然优于直观的从起点走至终点的9705 元。玩家判断自己离开矿山时间的判断机制：考虑反向问题，满足如下两个条件即可留在矿山：身上的物资足够自己再进行挖矿一天并且回到村庄，即物资>行动2 天消耗+挖矿一天消耗。消耗计算见判断机制时间很充裕，不用立刻启程去终点，即时间>6 天。

若不满足上述条件，则必须离开矿山。玩家在村庄中，需要购买物资数量的判断机制：判断方法是预测玩家直到下一次购买物资之前需要消耗多少物资。离开村庄之后可以直接去矿山，也可以去终点，预测方法为根据路上消耗一天的食物、路上消耗一天的水、挖矿消耗一天的食物和挖矿消耗一天的水这四个量来评估消耗物资的数量。若去矿山则消耗物资为：挖矿n天消耗+路程4 天消耗。

其中n（n>2）天与剩余时间有关若去终点，则消耗物资为：路程3 天消耗从村庄出来后，若时间相对充裕则去矿山挖矿，反之则直接前往终点。

由单人玩家增加为了多人玩家，根据规则若多人同时从A区域迁移到B 区域（A^B），每个玩家的消耗与同行人数成正比，且挖矿收益与同行人成反比，同时在村庄购买物资时的价格随着人数的多少而翻倍，极大的提高了在村庄消费的成本。

同时还涉及到了天气已知和天气未知两种情况，需要综合考虑各方影响因素得出可能的路线，假设多人游戏针对团体的目标为多人集体的剩余资金，仅知道当天的天气状况以及当天其他玩家的资源剩余状况，同时多人同行也会面临一样的高消费、低收益问题。[2]

根据阐述食物和水都需要在村庄进行一定的二倍价格补充，并且最终补充的数量大约等于获得的数量。因此食物平均价格约为15 元，水平均价格约为7.5 元可以计算得出，当高温天与沙暴天总和较多时，轮流工作反而亏损金钱。由于计算中还没有考虑沙暴天气的影响，如果沙暴天气出现在路程中，相比单人工作时，会额外亏损金钱，因此轮流工作大部分情况下不如单人工作，故舍弃轮流挖矿的计划。

3 结论

对于天气未知的情况，显然无法保证总是取到最优的方案，因此应当对天气未知时模型可能出现的误判作分析，误差来源于两个方面：停留时间引起的误差。如果在高温天试图等待晴朗天以方便挖矿或者行动，但若未来不出现晴朗天，就浪费了等待的时间，这就是停留时间错误。每额外停留一天，会增加消耗135 元。

但是根据函数可以得知，在不出现极端天气情况下（如连续15 个晴朗之后出现连续15 个高温）通常只会等待1-2 天，因此额外消耗的金钱是有限的。物资购买引起的误差。当预计消耗的物资大于实际消耗的物资时，就会出现物资购买过多的情况，如果出现额外购买，额外购买的物资数量大约等于一天的消耗，即100 元左右。