基于动态规划的沙漠行走问题决策分析

姚铭波 黄品文 张婉春 陆 瑶

（浙江水利水电学院，浙江 杭州310018）

针对问题一的求解，第一关：首先将地图转换成无向图进行预处理，其次根据已知条件写出动态规划模型，决策变量为：路径、是否挖矿、是否沿途买水和食物、初始出发时的资金，目标函数为：玩家到达终点时留存的总资金最大，约束条件为：到达终点的截止日期不能超过30 天、负载量不能超过1200 千克、资金、水、食物负重以及当天金币的状态的建模约束。在已知全部天气状况的情况下，再根据无向图写出邻接矩阵，用Floyd 算法得到27 个点两两之间任意的最短路径，然后用C 语言进行求解，最佳结果在第23 天返回终点，总金额为10430 元；第二关：在第一关的基础上，只改变了最短路径，其余条件不变，最佳结果在第30 天返回终点，总金额为12710 元。

1 问题的背景与重述

游戏已经成为人们休闲娱乐的调味品，玩家可以在游戏世界中通过完成任务，领取更高的奖励。现如今有一款穿越沙漠的游戏，玩家凭借着地图在沙漠中行走，根据地图的难度不同，游戏的策略也呈现出不同的效果。如何根据地图难度的不同，在遵守游戏规则的情况下，解决资金资源问题，尽可能留有多的资金，成为游戏攻略的一大难题。

2 问题的分析

问题一要求在一个人出发时得知接下来所有天气状况后求出第一关和第二关的最优解，我们先通过题目和游戏规则整理出目标函数、决策变量和全面准确的相关约束条件，建立问题一的动态规划模型，最后建立模型用C 语言求出最优解，如果难以求解就先通过建立邻接矩阵然后用floyd 算法求出最短路径，再通过优化路径法化简模型，贪心算法求出不同方案的近似解。

3 对问题一模型的建立与求解

3.1 模型的准备

图1

3.2 第一关模型的建立

3.2.1 决策变量

3.2.1.1 沙漠行走游戏中判断是否挖矿，可以采用0-1 变量，用wij 表示如下：

3.2.1.2 沙漠行走游戏中判断是否行动，可以采用0-1 规划，用bij 表示如下：

3.2.2 目标函数

3.2.2.1 在游戏过程中挖矿的收益A 表示的是挖矿的总收益；k 表示的是第k 天到达终点；q 在这里表示区域总数q=27；wij 表示当天是否要挖矿；根据只有一个矿山的情况，这里j 为固定值区域12。

3.2.2.2 以玩家到达终点时留存的总资金最大为目标，根据上述相关决策，可以得到目标函数中e1 表示的是水的基准价格；f1 表示的是食物的基准价格；Xij，Yij 表示的是在第i 天在第j 地买的水和食物的数量，这里用X01，Y01 来表示，并带入数值进行计算Sij，Cij 表示第i 天在j 地剩余的水和食物的数量，这里i=k,j=27。

3.2.3 约束条件

3.2.3.1 ji表示第i 天的金币数。而第i 天的金币数是通过第i-1 天金币数影响因素的影响进行迭代获得的,其中游戏中的金币数不能小于0。

3.2.3.2 由于在游戏中，第i 天只在一个地点行动一次，且冒险者到达终点时用的天数要小于30 天。

3.2.3.3 Zi-1：表示第i 天所在的地点,而游戏中第i 天所在的地点也是由第i-1 所在的地点通过影响因素的影响进行迭代而出的。

3.2.3.4 对购买物资数量的约束。根据题目可知，玩家在初始起点时，所买的水和食物重量不能超过负重，价钱不能超出预算。

3.2.3.5 对剩余物资数量消耗情况的约束。在玩家游戏过程中，活动会存在三种情况：第一种为继续行走，第二种为原地不动，第三种为进行挖矿。无论哪一种情况都会进行物资消耗，一天活动下来后剩余的物资数量由当天活动以及前一天剩余物资数量决定。这里的S 表示的是一天活动之后所拥有的剩余水的数量；SSij 表示当天刚开始时所拥有的水的数量；TSij 表示的是第i 天水的消耗情况。

这里的C 表示的是一天活动之后所拥有的剩余食物的数量；SCij 表示当天刚开始时所拥有的食物的数量；HSij 表示的是第i 天食物的消耗情况。

这里的aij 表示玩家在第i 天在j 地的活动方式；由于剩余物资的重量还是不能够超出负重，所以对负重的约束条件为：3S+2C≤1200。

综上所述，综合以上有关于优化模型中目标函数以及约束条件的分析，可以得到玩家到终点时总资金最大化模型的建立：

3.3 第一关模型的求解

以下方案一、方案二的模型求解方式为暴力枚举，方案三为优化模型后的求解方案。

3.3.1 方案一模型的建立与求解

根据Floyd 算法，用Matlab 软件进行编程，求得起点到终点的最短路径为3。根据每一路径消耗一天为单位，可以根据最短路径得出起点到终点的最短行动时间为3 天。前三天的天气为高温、高温、晴朗，所以在初始起点进行补给的时候购买满足三天的水和食物。通过对附件里第一关的表格计算，水和食物总共买了590 元，还剩下9410 元作为到达终点的总资金。

3.3.2 方案二模型的建立与求解

可以根据Floyd 算法求出两个目标区域之间的最短路径，然后结合附件中所给出的天气状况，制定30 天的行动路线：（1）第1-8：从起点到村庄，（2）第9-10：从村庄到矿山，（3）第11-12天：挖两天矿，（4）第13 天-14 天从矿山到村庄，（5）第15-16 天再从村庄，（6）第17-22 天再从矿山返回村庄，（7）第23-25 天：到村庄后因沙暴停留一天，（8）第26-28 天:从村庄返回终点然后结束。

3.3.3 方案三模型的建立与求解

3.3.3.1 建立方案路线活动内容

（1）从起点出发，所带水的负重为540kg，所带食物的负重为660kg，购买物资支出总金额为4200 元，总负重为1200kg；

（2）由Floyd 算法求得的起点到村庄的最短路径为8，第八天到达村庄后剩余的水的负重为464kg，食物的负重为246kg，需要将剩余的负重进行水的数量的补充，共补充489kg 的水，购买物资的总支出为1630 元，总负重为1199kg；

（3）到矿场时，选择停1 天，挖7 天，然后去村庄进行补给。共消耗水的负重为735kg，消耗食物的负重为422kg，剩下32kg的食物和0kg 的水；

（4）在村庄进行物资的补给，购买水的质量为108kg，购买食物的质量为48kg，这里购买物资需要消费840 元；

（5）从村庄到达终点最短路径为3 天，通过计算，时间和水全部消耗完。

3.3.3.2 求得最优解，通过C 语言软件对模型进行求解，可以得到全局最优解，在终点时得到的总资金最大为10430 元。

3.3.3.3 总结三个方案进行数据比较，得出方案三的结果为最优。因此，最优方案的最大总资金数为10430 元。