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

2021-06-24付芷睿李雪纯李兴睿

科海故事博览 2021年2期

关键词：挖矿消耗矿山

付芷睿李雪纯李兴睿

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

1 模型假设

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

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

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

2 模型准备

2.1 地图的要素提取及简化

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

2.2 最短路径

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

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

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

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

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

2.4 停留

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

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

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

3 基于单目标规划模型的最优策略求解

3.1 单目标规划模型的建立

3.1.1 决策变量的确定

（1）玩家在第i天的位置xi，i=0,…,N，xi∈A。其中，N表示游戏的截止日期，A表示地图上所有区域的序号的集合。特别地，当玩家在第n天到达终点后，我们约定玩家位置始终位于终点；

综合上述变量，决策变量可统一表示为向量Xi=(xi,vi,ui,ai,bi)，。

3.1.2 目标函数的确定

其中：

S0表示挖矿的基础收益，ai和bi分别表示玩家在第i天购买的水和食物的数量，wi为第i天的天气状况：

3.1.3 约束条件

条件一：任意第i天包内都有剩余物资且总负重mi不超过负重上限1200kg；

条件三：当天气状况为沙暴时，玩家必须在原地停留一天，即第i+1天和第i天位置相同；

条件四：玩家每天只能从目前区域到达与之相邻的区域，或在目前区域停留一天；

综上，建立单目标规划模型即可。

3.2 求解模型得出一般策略

3.2.1 求解一般策略的思维过程

由于直接求解上述优化问题时间和电脑储存空间开销较大，因此我们首先根据不同类型的地图所含要素进行分类讨论，将全程路线分为挖矿与不挖矿两种路线。

路线一：不经过村庄或矿山。通过选择最短路径，计算出玩家最快到达终点的日期n，可得最终剩余资金为：

路线二：经过村庄和矿山。当玩家采取挖矿的路线时，我们又将全程分为从起点到矿山、挖矿过程和从矿山到终点三个阶段处理，并且给出每个阶段玩家应采取的策略，最后给出整体算法。

阶段1：起点-矿山

1.起点物资量

由于村庄中物资的价格为基准价格的2倍，因此为了节约资金，玩家应在起点处购买尽可能多的物资。

2.到达矿山的路径及日期

为了减少行走的消耗，玩家应当尽快前往矿山，仅在沙暴天气停留。通过选择最短路径，可以得到玩家最快到达矿山的路径及日期。

阶段2：矿山挖矿，中途去村庄补给

1.挖矿天数

根据阶段1和阶段2计算的到达与离开矿山的日期，可得玩家挖矿的天数。

2.去村庄补给的日期

在物资即将不足但是恰好能维持玩家抵达村庄时，离开矿山前往村庄。根据往返矿山和村庄之间需要花费的时间，计算出最多可以前往村庄的次数。

3.购买补给的数量

应满足补给后的物资足够玩家维持到下一次补给。

阶段3：矿山-终点

离开矿山的日期。为了使收益最大，玩家应当用尽可能多的天数挖矿，通过选择最短路径并且考虑食物和水的约束可以得到玩家最晚离开矿山的日期。

3.2.2 求解一般过程的整体算法

Step1：采用Dijkstra算法计算从起点到矿山的日期；

Step2：根据食物和水的余量的初步计算从矿山离开到终点的日期范围，而后采用Dijkstra算法计算从矿山离开到终点的确切日期；

Step3：遍历玩家离开矿山到达村庄进行补给的日期，对于多种可能的路线，分别计算出终点时玩家的资金剩余量，求出最大资金剩余量所在路线，则该路线即为所求玩家最佳策略；

step4：综合前四步，得到全过程的策略。

4 基于动态规划的最优决策求解

4.1 多阶段决策过程的动态规划模型

本问题中，玩家不知道全程的天气，此时不便利用第一问中分3个阶段的方法，而是应该每天根据当前的状态进行下一步行动的决策，因此我们建立动态规划模型如下：

划分阶段：以天为单位，假设游戏的截止日期为第n天，则全程分为n-1个阶段。

状态变量：Xi=(xi,vi,ui,ai,bi)，，其中i表示第i天，xi表示玩家所在位置，vi表示玩家是否在村庄，ui表示玩家是否挖矿，ai表示购买水的数量，bi表示购买食物的数量[1]。

决策变量：当一个阶段的状态确定后，玩家需要做出选择从而演变到下一阶段的某个状态，这种选择手段称为决策，描述决策的变量称为决策变量。设玩家在位置xi的决策变量为fi(xi)。

状态转移方程：在确定性过程中，一旦某阶段的状态和决策已知，下阶段的状态便完全确定。用状态转移方程表示这种演变规律，即通过玩家目前位置和决策变量fi(xi)来确定下一步的位置xi+1的方程，设为xi+1=Ti(xi,fi)。

指标函数：是衡量过程优劣的数量指标。由于玩家的目标是使剩余的资金最大，因此选择每一天的净收益作为指标函数，净收益即玩家当天可能挖矿的收益与消耗资金之差，记为。

在上述动态规划模型的基础上增加第一问中的约束条件，即为第二问的总模型。

4.2 求解模型得出一般策略

通过该动态规划模型，我们希望求解出全过程的最优策略S*={f1(x1)*，f2(x2)*，…，fn(xn)*}，即玩家在每一天的决策fi(xi)*的集合。但是，由于该动态规划模型的时间复杂度是O(n3)，直接采用逆序求解法的消耗巨大，无法在满意的时间内求得最优解。因此我们采用拆分的思想，将求解过程拆分成两步[2]：

（1）首先利用贪心算法的思想制定出某一特定的策略S0，作为初值；

（2）接着通过与最优策略的比较，不断修改该策略S0，得到最终的一般策略S*，S*就是上述动态规划问题的近似最优解。

4.2.1 基于贪心算法的特定策略S1

（1）当玩家位于起点时，假如玩家经过矿山的时间超过天数上限，则直接前往终点；否则，时间充足，可以经过矿山。

（2）当玩家在第i天位于村庄时，我们利用贪心算法，使得玩家始终做出利益最大化的选择。即，先计算从当前日期到最后一天的消耗上限，若此时包内水的数量或者包内食物的数量小于该数值，那么玩家进行补给，否则不补给。

（3）当玩家位于矿山时，利用贪心算法，使得玩家始终做出利益最大化的选择。即，先将水和食物的消耗上限按照村庄的价格折算成资金，再与挖矿收益进行比较。若，那么玩家不挖矿，否则挖矿。

（4）当玩家位于其他位置时，由于约束条件过于复杂，无法确定应该前往终点、矿山还是村庄。此时我们首先计算出所有可能的移动路线的消耗上限，当包内水的数量和食物的数量均大于消耗上限时，在这些路线中，我们约定玩家等可能选择其中一条。

（5）当玩家位于终点时，游戏结束。

4.2.2 通过比较Z*对策略Z1进行修正

1.定义两条路径的差别εij。在该问题中，定义向量，εij中的元素为两条路径xi和路径yj中每个位置的差，用于衡量两条路线的相似程度。其中，εij的零位越多，两条路径越相似。

2.根据ε0k修正一般策略Z1的算法。

Step1：编写程序模拟玩家采用一般策略Z1后走的路径K1；