张步昇 田帅军 张艳霞

（1.山西农业大学农业工程学院，山西 晋中 030800；2.山西农业大学动物医学学院，山西 晋中 030800）

1 “穿越沙漠”问题的提出

一名玩家在已知每天天气状况的条件下， 给出30 天之内到达终点的最优路径和资源分配的最佳方案。玩家根据地图提示，从起点出发，利用初始资金购买资源在沙漠中行走。 路途中可能会遇到不同天气，若遇到沙暴天气玩家即可以停留在原地，也可以选择挖矿。 将停留在原地所消耗的资源数为基础消耗量，若在沙暴天气挖矿即为基础消耗量的3 倍，但其可获得基础收益。若玩家资源不充足可用剩余的初始资金或挖矿所得的资金购买，但是每箱价格为基准价格的2 倍。 若到达终点时资源还有剩余可按每箱基准价格的一半退回。目的是在满足上述条件下回到终点尽可能多的保留资金。

题目中提到的地图线路以及相关的各种信息提示，包括每天的天气状况、初始资金、资源的价格和质量、在不同天气不同行为条件下消耗的资源配比和挖矿的收益等信息， 皆出自2020 年全国大学生数学建模竞赛B 题关于“穿越沙漠”问题的探讨，读者可根据所需自行查阅。

2 整体思路的构想

经分析认为， 该问题为最短路径和最优决策问题。 从起点到终点有许多条路径可供选择，先用穷举法确定有限个最优路径方案， 再用Dijkstra 算法求出任意两个区域的最小距离，最后用定量分析购买水和食物数量的最佳方案。 在行走过程中由于天气变化、物资是否充足、挖矿天数和负重上限等因素均会影响最优路径的选择。……