基于动态规划模型的穿越沙漠路程优化问题

付芷睿 李雪纯 李兴睿

（武汉大学，湖北 武汉 430000）

1 模型假设

1.假设玩家都是理性的，追求的目标仅是到达终点时获取的总利益最大；

2.假设区域可以抽象成一个点；

3.假设以下的初始值是不变的：负重上限恒为1200kg，初始资金恒为10000元，每箱水的质量为3kg，食物的质量为2kg，每箱水的基准价格为5元/箱，食物的基准价格为10元/箱。

2 模型准备

2.1 地图的要素提取及简化

首先，对于形状不规则的地图进行抽象处理，提取出起点、终点、村庄和矿山四个要素，其余点均视为普通点。

2.2 最短路径

为了使得到达终点时剩余资金最大，玩家应尽量减少行走过程中的消耗，因此玩家在起点出发后，会立即以最短路径前往村庄、矿山或终点其中之一。

2.3 定义消耗上限与收益下限

消耗上限：假设全程30天均为沙暴天气，计算出玩家的物资消耗量，称作消耗上限。

收益下限：假设挖矿时均遇到沙暴天气，计算出此时的挖矿收益，称作收益下限。

在只知道当天天气的情况下，玩家应对此后的天气进行最坏的打算，计算出消耗上限与收益下限，权衡下一步的行动。

2.4 停留

初步分析可知，停留的条件有两种：

（1）沙暴时必须在原地，不能移动；

（2）到达矿山后，由于挖矿的消耗为基础消耗量的三倍，并且高温天气与沙暴天气相对于晴朗天气的基础消耗量都显著提高，所以为了挖矿期间的消耗尽可能少，可能会根据需要在沙暴天或高温天不挖矿，通过简单演算，我们规定每一关卡除沙暴天以外，其余总的停留时间不超过两天。……