# 2020高教社全国大学生数学建模大赛 赛题B 穿越沙漠
水和食物是沙漠中重要的生命资源。由于沙漠复杂多变的天气等因素,对如何合理分配资源和行为决策的研究具有深远的意义。
本文针对穿越沙漠这一游戏,利用多种方法对这个问题进行了探究。
首先,本文利用数学语言对游戏过程加以描述,将地图压缩到只包括起点、终点、矿山、村庄四种特殊点,用Dijkstra算法求出各个特殊点之间的最短距离。将复杂的
游戏过程转化为玩家在几个特殊点之间的移动和其他行为(如购买物资,挖矿等行为),从而降低模型复杂度。
针对问题一,本文根据化简得到的两张地图,分析地图特性,规划出了最优路径的解空间,利用有限空间穷举法和蒙特卡洛模拟法,分别得到10430元和12020元的最终资金,以及对应的最优策略。
针对问题二,本文根据第一、二关的先验知识,估算天气概率,随机生成天气序列。结合地图信息和当天天气情况,给出玩家应采取的动态策略。然后利用蒙特卡洛模拟,分别对第三关、第四关进行求解。结果为第三关应直奔终点,最佳预期资金为9450元左右;第四关预期平均收益趋近于10800元。
针对问题三,本文分别对第五关的两种可能的最优策略进行大量模拟,得到两名玩家在不同策略下的期望收益,根据Nash平衡理论,得到两名玩家达到最佳预期收益的混合策略,即以0.654的概率在高温天停留。对于第六关,本文在每一个状态下采用蒙特卡洛动态评估方法对当前的可能行动进行评分,并执行评分最高的行动,最终给出了在有两名玩家干扰情况下的最优策略。