“穿越沙漠”最优策略研究

刘博韬 张萌

山东协和学院 山东济南 250107

摘要；本文借助马尔可夫决策模型、蒙特卡罗算法、迪杰斯特拉算法对2020年数学建模竞B题“穿越沙漠”问题进行研究，在不同关卡设定下，通过动态规划给出规定时间到达目的地并尽可能多获得资金的最优策略。

关键词： 马尔可夫决策 迪杰斯特拉 蒙特卡罗 博弈论 动态规划

一、问题重述

玩家用初始资金购买一定的必需资源，在天气多变（晴朗、高温、沙暴）的沙漠从起点出发，途中可以在矿山或村庄补充资金和资源。游戏目标是在规定时间到达终点的同时保留尽可能多的资金。

游戏规则如下：

(1)基本时间单位为天，玩家位于起点时为第0天且必须在规定时间内到达终点才能结束该玩家的比赛。

(2)以箱作为必需资源的最小计量单位，玩家每天的资源质量不能超过最高负重，一旦在到达终点前耗尽资源则游戏失败。在起点以基准价格购买必需资源且只能购买一次，在游戏中玩家可以选择返回起点或在起点停留一段时间。在到达终点时，玩家可以以基准价格的一半退回剩余资源。

(3)每天玩家可以原地停留也可以行走到邻近的区域内，整顿一天消耗资源数为基础消耗量；行走需消耗资源，消耗数量为基础消耗量的两倍。当遇到沙暴时必须在原地整顿。

(4)如果玩家到达矿山时，可以选择挖矿赚取资金，沙暴天气也可挖矿，但到达的第一天不可挖矿。挖矿每天消耗的资源为基础消耗量的三倍，每天的赚得的资金为基础收益；不挖矿时资源消耗量为基础消耗量。玩家在村庄可以用现有资金补充资源，资源价格为基准价格的两倍。

需解决的问题：

问题一：已知每天天气状况，假设只有一名玩家参与游戏，给出该玩家的最优游戏策略。并对第一关、第二关进行求解，将结果填入Result.xlsx。

问题二：假设只有一名玩家参与，玩家仅当天天气状况，以此决定每天行动策略。给出该玩家应采取的最优策略，针对第三关、第四关进行具体分析。

问题三：现有拥有相同的初始资金的 名玩家同时从起点出发，若某天有 名玩家从同一区域进入另一相同区域，则这 名玩家的资源消耗量均为基础消耗量的 倍；若某天有 名玩家在同一矿山挖矿，则该 名玩家的资源消耗量均为基础消耗量的三倍且每天的收益均为基础收益的 ；若某天有 名玩家在同一村庄补充资源，则资源价格为基准价格的4倍。其他情况下资源的价格和消耗量不变。

(1)假设每天天气情况均已知，各玩家的方案在起点确定且不可更改，给出玩家应采取的行动策略，针对第五关进行具体分析。

(2)假设仅知道当天的天气情况，从第一天开始，在每天结束后玩家均可知道其他玩家当天的策略和剩余资源，并确定第二天的策略。给出玩家采取的行动策略，针对第六关进行具体分析。

二、问题假设

1、假设沙漠中除题目给定天气情况外无其他突发自然灾害。

2、假设每名玩家的身体情况相同且无突发疾病。

3、假设第四关中仅出现一次沙暴天气。

4、假设第六关中忽略沙暴天气的影响。

三、模型的建立与求解

游戏目标是为了到达终点时使资金最大化，以此为出发点对玩家的资金来源进行。

3.1 已知每天天气的最优策略

不管选择哪种方式都是通过最短路径到达目的地，可以通过将题目所给地图转化为邻接矩阵后使用迪杰斯特拉算法^[2]即可求出两点之间的最短路径

3.1.1 起点-终点路线

该路线表示不选择进入矿山挖矿赚取资金。在赶路时玩家可以选择在某一点“等待”便于以“合理时机”进入系统。从而使选择该路线的资金最大化。

3.1.2 起点-矿山-终点路线

选择该路线表示玩家想在赶路的同时通过挖矿来增加资金金额。

该路线有两种策略可选择：

1.在起点处购买恰好足够玩家挖矿、赶路和最后到达终点需要的资源数。

2.在起点处先购买恰好足够玩家从起点到矿山、挖矿和从矿山到达村庄的资源，在村庄再补充恰好足够玩家回矿山挖矿一段时间的资源（可能多次补充），最后一次补充恰好足够玩家最后到达终点所需要的资源。

3.1.3 起点-村庄-矿山-村庄-终点路线

此路线玩家有两种策略供选择：

1.在保留恰好到达村庄所需资源的情况下，补充到终点的最短路径下所需的资源。

2.返回村庄补充能够使玩家回矿山挖矿一段时间和最后到达终点所需的资源。

3.1.4 针对第一关、第二关的求解

1、起点-终点省钱路线

根据两关分别的最短路径本文采用线性规划^[2]的对不同关卡的最终资金进行求解：

第一关的线性规划方程：

第二关的线性规划方程：

最终得到两关最终资金

2、矿山赚钱路线

由于起点-矿山-终点路线的收益与起点-村庄-矿山-村庄-终点路线的收益可比性太低，所以这里仅对后者进行具体分析。

第二关矿山与村庄相邻，所以对挖矿结束去村庄补充资源后返回矿山继续挖矿的两种策略作不同分析。

3.2 仅知每天天气的最优策略

穿越沙漠的策略一共有两种：

1.以省钱为目的直接在合理时机下以最短路径从起点到终点来达到资金最大化。

2.经过合理时机进出矿山通过赚钱的方式来达到资金最大化。

两种方式在仅知当天天气的情况下，要对未来天气进行预测。为了简化运算，本文只针对每种路线的最短路径的天气进行蒙特卡罗^[2]模拟（选择最短路径是确保规定时间内到达终点剩余更多资金）。用模拟出的天气情况可以得出资金的期望值，将其均值化，再将每种路线进行比较，最终即可得到所有天气中的最优策略为 ，可作为比较的基本方程。

3.2.1针对省钱方式的策略

消耗资金数：

最终资金期望：

3.2.2针对挖矿方式的策略

1、起点-矿山-终点

在矿山中消耗资源数

平均消耗量：

所以挖矿天数的计算公式为：

最终资金期望：

2、起点-矿山-村庄-终点

挖矿时长的求解公式：

最终资金期望为：

3.3 名玩家的游戏策略

3.3.1 两名玩家在起点确定的游戏策略

该问题可以由博弈论中的囚徒困境来进行模拟，为得到最优策略，两者为达到全局最优解必须做出让步，找出起点-终点的所有路径，在其中选出两条除最短路径之外的路径中最优的路径。

3.3.2三名玩家在行动前一天确定的游戏策略

本题将状态空间分为起点-矿山，矿山-终点两种。针对起点-矿山、矿山-终点的路线，使用马尔可夫决策模型^[4]中的惩罚函数进行路线决策，同时利用蒙特卡罗对各路线天气进行预测。

马尔可夫决策模型中：

1. 状态空间 
   状态空间包括玩家活动区域内动态实体的所有可能描述信息，本文将状态空间定义周围其它玩家的空间存在状态。

2、完结条件
行为决策过程中，迭代过程的结束需要一个终止状态来判断，本文选取下述情况作为结束标志：

当到达终点时为结束，马尔可夫过程不再进行迭代。

3、惩罚函数
玩家相遇：造成资源浪费。故玩家路线重叠时，作为惩罚函数。
玩家避免相遇而选择绕路：造成资源浪费。故作为惩罚函数

4、运动动作
由题意可知，玩家进行下一步的运动时，目的是到达终点，在二维化的地图中，起点与矿山、矿山与终点均在特定矩形的主对角线上，故运动动作只三种情况：
向下 不动 向右。

5、动作值函数 
动作值函数是一个递归函数，首先检测当前状态是否到达终止状态，若未达到递归结束条件，则执行状态转移方程，若达到则结束递归，然后判断当前迭代次数是否达到 T，若达到则结束递归，否则对所有可能的动作进行循环计算。
经过以上迭代之后，得到的路线即为在一般情况下玩家要选择的一般策略。

参考文献

[1]嵇冉,王健.生活中的“囚徒困境”[J].中国统计,2019,(10):44-46.

[2]司守奎,孙兆亮.数学建模算法与应用[M].北京:国防工业出版社;2015.

[3]司守奎等.数学建模算法与应用习题解答[M].北京:国防工业出版社;2015.

[4]MDP及PROLOG在自动驾驶中的应用.班兵,杨志刚,杨航[J].智能网车,2019,(24):37-40.

2