基于最优解算法的穿越沙漠游戏解决策略 .pdfVIP

2021年第16期百家争鸣

基于最优解算法的穿越沙漠游戏解决策略

唐晨洋张瀚文刘松泽

青海大学，青海西宁810016

摘要：本文通过建立图论模型、最优动态路径规划模型、最大收益模型对穿越沙漠游戏进行了研究和分析，同时还采用了贪

婪算法、枚举算法、蚁群算法和神经网络算法进行计算，得到玩家在消耗最少物资的条件下获得的最大收益。

关键词：最优解算法；沙漠游戏；解决策略

一、问题的重述买的补给以及赶路的时间，而解决这类问题可以更有效地帮助

考虑如下的小游戏：玩家凭借一张地图，利用初始资金购现实生活中公司的决策与运筹。

买一定数量的水和食物（包括食品和其他日常用品），从起点（二）问题一的分析

出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、对于问题一，首先要考虑的一点是在村庄购买水和食物是

村庄补充资金或资源，目标是在规定时间内到达终点，并保留起点购买的两倍。这里我们把水在原点的价格作为基础量，也

尽可能多的资金。就是说在村庄购买水是两倍的基础量，食物是四倍的基础量。

游戏的基本规则如下：我们如果想获得收益，首先一定要经过矿山，那里是唯一可以

（1）以天为基本时间单位，游戏的开始时间为第0天，玩获得收益的地方。而且我们如果要到达矿山，可以有好多条最

家位于起点。玩家必须在截止日期或之前到达终点，到达终点短路径，但是我们要注意的一点是在路上也会消耗食物和水，

后该玩家的游戏结束。玩家所携带的水和食物是有上限的，既在起点买的食物和水的

（2）穿越沙漠需水和食物两种资源，它们的最小计量单位量是有上限的。因此我们在到达矿山的时候必定不是一个良好

均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。的状态，如果想要有一个良好的状态，必须选择经过村庄的那

若未到达终点而水或食物已耗尽，视为游戏失败。条路在路过村庄的时候购买一定的物资，然后到达矿山。在矿

（3）每天的天气为“晴朗”、“高温”、“沙暴”三种状山里尽可能选择晴朗天气和高温天气进行工作，沙暴日可以休

况之一，沙漠中所有区域的天气相同。息，也可以开矿。必须留有足够的食物和水来返回村庄或者终点，

（4）每天玩家可从地图中的某个区域到达与之相邻的另一这里根据返程的时候的天气情况而定。从矿山返回终点的时候，

个区域，也可在原地停留。沙暴日必须在原地停留。也有若干条路径长度相同的路线，但是选择经过村庄的那条路

（5）玩家在原地停留一天消耗的资源数量称为基础消耗量，会更好一些，因为可以更好地利用第一次到达矿山的时候携带

行走一天消耗的资源数量为基础消耗量的倍。的物资，而且，只需要根据天气留有两天的物资到达村庄进行

（6）玩家第0天可在起点处用初始资金以基准价格购买水补给即可。

和食物。玩家可在起点停留或回到起点，但不能多次在起点购（三）问题二的分析

买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价对于问题二，与问题一最大的区别在于不知道以后的天气，

格为基准价格的一半。只知道当天的天气，并且基础收益大幅下降，高温天气成本有

（7）玩家在矿山停留时，可通过挖矿获得资金，挖矿一天了一定程度上的增加。通过C++编程计算可知，在高温天气开

获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基矿一定是赔钱的，而在晴朗天气开矿的话是挣钱的，可挣35元

础消耗量的倍；如果不挖矿，消耗的