付芷睿 李雪纯 李兴睿

摘 要 在“穿越沙漠”的游戏中，玩家需要规划路线在规定时间内到达终点，并保留尽可能多的资金。利用动态规划等数学工具可以针对不同的关卡设置寻找玩家的最优路线。

第一问中，只有一名玩家且该玩家已知全程天气。首先以到达终点时剩余资金最大为目标函数，以游戏规则为约束条件，以玩家的策略为决策变量，建立单目标规划模型。接着将全路程分为三个阶段：从起点到矿山、在矿山与村庄活动、从矿山到终点。在一、三阶段利用Dijkstra算法求出最短路径，对于第二阶段设计循环算法求解。

第二问中，只有一名玩家且仅知道当天天气。首先对时间离散化，将本问转化为多阶段决策问题，而后建立动态规划模型。求解过程分为两步：

（1）借助贪心算法的思想，构造符合约束条件的玩家策略;

（2）将采用该策略求解的路径与第一问中的算法求解的路径进行比较，优化该玩家策略，使其逼近最優解。

第三问中，推广到多名玩家与有顺序游戏模式。为简化问题，仅考虑玩家A的最优策略。此时A需要综合考虑其前面的i-1位玩家的策略以及后n-1位玩家的策略给出最终策略。

关键词 Dijkstra算法 单目标规划模型 多阶段决策 动态规划模型

中图分类号：U491.2 文献标识码：A 文章编号：1007-0745（2021）01-0052-04

1 模型假设

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

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

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