1. 赛题回顾与核心挑战解析2020年高教社杯全国大学生数学建模竞赛的B题题目是“穿越沙漠”。这道题在当时甚至在赛后很长一段时间里都成为了一个经典案例被无数参赛者和指导老师反复咀嚼、分析。它之所以经典不在于其数学模型有多么高深莫测而在于它极其巧妙地在一个看似简单的游戏规则下埋藏了决策优化、动态规划、博弈论乃至风险管理的多重内核对参赛者的综合建模能力、编程实现功底和策略思维提出了全方位的挑战。简单回顾一下题目背景你和你的团队驾驶一辆吉普车在一张网格化的沙漠地图上从起点出发目标是抵达终点。地图上散布着若干天气已知的“矿山”和“村庄”。你的车有初始资金、载重上限和基础能耗。每天你需要根据已知的天气晴天、高温、沙暴决定当天的行动移动、采矿、购买物资或停留。不同的行动在不同天气下消耗的物资水和食物不同沙暴天则强制停留。矿山可以采矿获得资金村庄可以用资金购买水和食物。最终的目标是在规定时间内抵达终点并最大化剩余资金。初看之下这像一个资源管理版的“大富翁”游戏。但它的核心挑战立刻浮现出来这是一个多阶段、多状态、带随机性天气已知但路径选择带来状态分支爆炸的序贯决策问题。你的每一个决策——今天去哪、挖不挖矿、买不买物资——都会影响后续所有天的物资状态、资金状态和位置状态进而影响最终能否存活到终点以及剩下多少钱。这绝不是一道简单的线性规划能解决的问题它需要一套系统的求解框架。2. 解题思路的演进从直觉到模型面对这样一道题团队的解题思路通常会经历几个阶段的演进。很多队伍一开始会陷入“手算”或“局部贪心”的误区比如觉得某个矿看起来很近就直奔而去结果可能因为中途物资计算失误而失败。成熟的建模过程应该遵循以下路径。2.1 问题抽象与状态定义这是建模的第一步也是决定后续算法复杂度的关键。我们必须把游戏规则转化为数学语言。首先需要定义“状态”。一个完整的状态至少需要描述在特定“时间点”第几天的以下信息位置车辆所在的网格坐标 (x, y)。物资库存当前拥有的水数量、食物数量。这直接关系到生存。资金当前拥有的金钱数量。这决定了在村庄的购买能力。载重当前车辆的总负重物资重量基础重量。不能超过上限。那么在时间t一个状态可以表示为S_t (x_t, y_t, water_t, food_t, money_t, load_t)。我们的所有决策就是从一个状态S_t根据行动A_t移动方向、采矿、购买等转移到下一个状态S_{t1}的过程同时伴随着物资消耗、资金增减和负重变化。为什么状态定义如此重要因为它是动态规划类算法的基础。后续无论是用经典动态规划DP、启发式搜索还是强化学习都需要清晰的状态空间。一个常见的失误是忽略了“载重”这个状态认为它可以从物资量推算出来。但在购买决策时你需要实时知道剩余载重是否能容纳想买的物资否则决策无效。因此载重必须作为一个独立的状态变量参与决策计算。2.2 核心模型建立马尔可夫决策过程框架一旦状态和行动定义清楚这个问题就天然地适配马尔可夫决策过程Markov Decision Process, MDP的框架。MDP是处理序贯决策问题的标准模型其五要素恰好对应本题状态集合 S就是我们上面定义的所有可能的状态(x, y, water, food, money, load)。注意这是一个巨大的离散空间。行动集合 A在任意非沙暴天行动包括向相邻四个方向移动、停留、采矿如果在矿山、购买如果在村庄。沙暴天则只有“停留”。状态转移概率 P本题的“随机性”仅来源于天气而天气是预先完全已知的。因此状态转移是确定性的。给定当前状态S_t和行动A_t下一个状态S_{t1}是唯一确定的由消耗规则、购买价格、采矿收益等计算得出。这大大简化了问题从随机MDP退化为确定性动态规划。奖励函数 R在MDP中我们通常最大化累积奖励。在本问题中除了最终到达终点时的剩余资金过程中的资金增减采矿得钱、购买花钱可以视为即时奖励。更直接的建模方式是将最终剩余资金作为目标函数过程决策都是为了优化这个终点值。因此可以设定每日行动的即时奖励为0而将终点状态的价值函数定义为剩余资金。折扣因子 γ由于是有限期问题最长30天且无风险折扣需求通常设为1。建立MDP模型的意义在于它为我们指明了理论上的最优解法求解最优价值函数V*(s)即从状态s出发采取最优策略能获得的最大最终剩余资金。然后通过价值函数导出最优策略π*(s)即在该状态下应该采取什么行动。2.3 算法选择与面临的“维数灾难”理论上对于确定性有限期MDP可以通过逆序动态规划Backward DP从终点倒推求解最优价值函数。但这就是本题最大的实践难点状态空间爆炸。让我们粗略估算一下状态数量。地图大小约50502500个格点时间最多30天。水和食物数量即使按最粗略的离散化比如0-200间隔为1也有20020040000种组合。资金和载重也需要离散化。这样总状态数轻松达到2500 * 30 * 40000 * ...这是一个天文数字任何计算机都无法直接存储和计算完整的价值函数表。因此直接应用标准DP是不可行的。参赛队伍必须采用各种方法来压缩状态空间或改变求解策略。这直接区分了不同层次的解决方案。3. 主流求解策略与实现细节拆解在实际比赛中顶尖队伍通常采用以下几种策略或它们的混合。每种策略背后都有其深刻的优化思想。3.1 策略一基于Dijkstra或A*搜索的路径规划与资源核查这是许多队伍首先想到的思路。既然目标是到终点那么先找一条从起点到终点的最短路径时间最短或基础消耗最小。然后在这条路径上考虑沿途的矿山和村庄进行物资补充和采矿的规划。具体步骤地图建模为图每个网格点作为节点相邻点之间的移动消耗根据基础天气假设如全程晴天作为边的权重。运行最短路径算法使用Dijkstra或A*算法计算起点到终点、起点到各矿山、矿山到矿山、矿山到村庄、村庄到终点等关键点之间的最短路径天数和基础消耗。生成关键点序列得到一个类似“起点 - 矿山A - 村庄B - 终点”的访问序列。资源模拟与调整沿着这个序列按天模拟物资消耗和资金变化。在村庄点根据模拟结果决定购买数量在矿山点决定采矿天数。如果模拟中发现物资不足则需要回溯调整访问顺序比如先去更近的村庄或者在中途增加去村庄的“补给支线”。优点直观易于理解和实现。能将复杂的全局优化问题分解为“路径规划”和“资源调度”两个相对独立的子问题。缺点与坑点局部最优陷阱最短路径不一定是全局最优路径。为了去一个高收益矿山绕远路可能最终总收益更高。天气差异处理算法第一步用的基础天气权重与实际每天变化的天气不符。实际消耗可能更大导致模拟结果过于乐观最终执行时物资不足。决策耦合性弱这种方法将“去哪”和“干什么”分开了。但实际上在某个点购买多少物资强烈依赖于后续要去哪、天气如何。这种解耦可能导致决策不是全局最优的。实操心得采用这种策略的队伍务必在资源模拟环节加入“安全冗余”。例如不是按照模拟的精确值购买物资而是多买10%-20%以应对实际路径与理想路径的偏差以及天气组合带来的风险。同时不要只生成一条路径最好生成2-3条候选路径如最短时间路径、经过最多矿山的路径、经过村庄最方便的路径分别进行模拟对比最终收益。3.2 策略二有限状态动态规划与剪枝这是更接近理论最优解的方法核心思想是聪明地遍历状态空间通过剪枝去掉大量明显劣质的策略从而在可接受的时间内找到近似最优解。核心操作状态离散化对水和食物进行粗粒度离散化。例如以“箱”为单位1箱水箱重1箱食物箱重而不是以“份”为单位。这样可以大幅减少状态数。资金也可以按一定间隔离散化。前向递推DP从第0天起点状态开始遍历所有可能的状态。对于第t天的每个状态S_t枚举所有合法的行动A_t计算出第t1天可能到达的所有状态S_{t1}并记录到达该状态时的剩余资金。状态剪枝这是算法的关键。在递推过程中如果对于同一个网格点、同一天出现了两个状态S1和S2我们需要判断是否可以舍弃其中一个。经典的剪枝规则是“支配关系”如果S1在物资、资金、载重所有方面都不差于S2即水不少于、食物不少于、钱不少于、负重不高于且至少有一项严格更好那么S2就是被S1“支配”的劣质状态。因为从S2出发能到达的终点从S1出发一定能以不差的方式到达。因此我们可以安全地丢弃S2只保留S1。迭代至终点重复递推和剪枝直到第30天或所有有效状态到达终点。最后比较所有终点状态的剩余资金最大值即为最优解并可通过回溯找到行动序列。优点理论上能得到全局最优解在离散化精度内。方法系统不易遗漏好策略。缺点与坑点离散化精度与计算量的权衡离散化太粗可能错过最优解离散化太细状态爆炸算不完。这需要反复调试。剪枝算法的正确性与效率实现“支配关系”判断需要谨慎。一个状态可能在水和食物上优于另一个但资金少这就不是严格支配。更精细的剪枝策略是“帕累托最优前沿”维护对于同一位置同一天保留所有互不支配的状态即帕累托最优解集。这比单一支配规则保留的状态更多但更精确。内存与时间管理即使剪枝中后期状态数也可能庞大。需要使用高效的数据结构如哈希表存储状态集合和编程技巧如使用整数位运算编码状态。实操心得实现DP剪枝时建议先使用较粗的离散化如水和食物以5份或1箱为单位快速跑通流程得到一个基准解和大致的时间消耗。然后逐步细化离散化精度观察解的质量提升和耗时增长在比赛时间内选择一个平衡点。另外天气预处理很重要提前计算出从任何位置到任何位置在已知天气序列下最短需要多少天、最少消耗多少物资。这可以作为DP过程中的一个“启发式动作”直接跳到下一个关键点而不是笨拙地一天天移动能极大提升效率。3.3 策略三蒙特卡洛树搜索与启发式策略这是当时一些强队采用的“降维打击”式方法借鉴了AlphaGo在围棋中的思想。MCTS非常适合这种分支繁多、难以直接评估的序贯决策问题。基本框架模拟从当前状态根节点开始随机选择行动直到游戏结束到达终点或死亡得到一次模拟的最终收益剩余资金。扩展与评估不是完全随机模拟而是用一棵树来记录访问过的状态节点。对于树内的节点使用上置信界算法来选择行动平衡“探索”尝试访问少的行动和“利用”选择历史收益高的行动。回溯将一次模拟的收益沿着访问路径回溯更新所有节点的统计信息访问次数、平均收益。迭代重复上述过程成千上万次最终选择根节点下访问次数最多或平均收益最高的行动作为当前决策。执行一步后以新状态为根节点继续搜索。如何融入本题纯粹的随机模拟效率极低。必须加入启发式策略来引导模拟移动策略模拟中移动方向不是完全随机而是有一定概率朝向最近的未访问矿山、村庄或终点。购买/采矿策略在村庄根据当前物资和到下一个关键点的预估消耗决定购买量在矿山根据资金需求和天气决定采矿天数。评估函数对于未到终局的中间状态需要一个快速评估函数来估计其“好坏”用于MCTS中的默认策略。这个函数可以很简单比如当前资金 预估到达终点所需最小消耗节省下来的资金价值。优点不依赖于精细的状态离散化能处理非常庞大的状态空间。通过大量随机模拟来逼近最优解特别适合带有随机性本题是确定性但分支多和复杂评估的问题。缺点与坑点实现复杂度高需要实现完整的MCTS框架、树结构、UCT选择算法等对编程能力要求高。启发式策略设计是关键如果引导模拟的启发式策略太差MCTS就会在低质量区域浪费时间找不到好解。这需要深厚的领域知识即对本题的理解来设计。耗时可能很长要获得稳定解需要大量的模拟次数数万甚至百万级对程序性能是考验。实操心得对于数学建模竞赛采用MCTS是高风险高回报的选择。如果决定用不要试图实现一个通用MCTS一定要紧密结合本题特性进行大量定制。例如可以将“天气”作为决策的一部分因为天气已知模拟时可以完美预知这本身就是最强的启发信息。另外并行化是提升MCTS效率的利器可以利用多线程同时进行多轮模拟这在允许使用多核的比赛中是巨大优势。4. 关键细节、常见陷阱与实战技巧无论采用哪种策略在具体实现中都会遇到一系列共性的细节问题处理不好就会前功尽弃。4.1 物资消耗与负重的精确计算这是所有模型的基础必须做到分毫不差。容易出错的地方包括基础消耗与挖掘消耗的叠加在矿山“采矿”时消耗是“基础消耗”加上“挖掘消耗”。很多人在模拟时只算了挖掘消耗忘了人活着每天就要消耗的基础水粮。沙暴日的消耗沙暴日停留消耗是基础消耗的2倍。并且沙暴日不能进行任何移动或采矿操作这个约束必须在决策逻辑中严格体现。负重计算购买或挖矿后要立即更新负重。判断一个行动是否合法首先要检查执行后的总负重是否超过上限。移动时消耗的是水和食物负重会减轻这个变化也要实时更新。建议单独编写一个simulate_action(state, action, weather)函数输入当前状态、行动和天气输出下一个状态。这个函数要经过反复的单元测试用各种边界情况如负重刚好满、物资刚好用完去验证其正确性。4.2 矿山收益模型的建立题目说“在矿山停留k天需要消耗k倍的基础与挖掘资源同时获得200*k元”。但这并不是简单的线性关系。你需要决策的是在这个矿山挖几天边际收益分析挖第1天收益200元消耗是基础挖掘份物资。挖第2天再得200元再消耗一份。但这里有个关键你多停留一天就晚一天到达终点消耗了额外的时间资源。因此需要计算挖矿的“净收益率”(收益 - 消耗物资的等效资金) / 占用天数。消耗物资的等效资金需要用村庄的物价将其折算成钱。与天气结合高温天气挖掘消耗更大沙暴天不能挖。所以挖矿决策必须结合后续几天的天气预报。如果明天就是沙暴那么今天挖矿可能不如提前离开去下一个点。资金的时间价值早一天拿到钱就可以早一天在村庄购买物资可能影响后续决策。这是一个复杂的动态问题。在简化模型中可以假设挖矿直到“边际收益率为正”就继续否则离开。4.3 村庄购买策略的优化在村庄水和食物的价格是固定的。购买决策的目标是用最少的钱购买足够到达下一个补给点下一个村庄或终点的物资同时考虑负重限制。“够用”原则不是买得越多越好多买的物资会占用负重可能迫使你后续更早去补给或者影响你携带更多矿山收益。需要精确计算到达下一个目标所需的最少物资加上一个安全余量如10%。水食比例水和食物的消耗速度不同基础消耗比例是2:1挖掘消耗是3:1。购买时要注意比例避免一种早早用完而另一种大量剩余造成浪费和负重无效占用。资金约束购买量不能超过当前资金。在DP或MCTS中这是一个硬约束。4.4 天气已知信息的极致利用本题所有天气是预先知道的这是最强的已知条件。高手和普通选手的差距很大程度上体现在对天气信息的利用上。路径规划避开沙暴规划路径时应尽量避免在沙暴天位于野外。理想情况是沙暴天正好停留在村庄或矿山可以购买或挖矿或者至少是在移动消耗较少的路径段上。“天气窗口”概念将连续的晴天或高温天视为一个“窗口”在这个窗口内适合进行长距离移动或高强度挖矿。沙暴天则视为必须停留的“节点”。你的整体行程应该像在搭积木把不同的行动模块移动块、挖矿块塞进不同的天气窗口里。逆向思维从终点倒推回来思考。假设你必须在最后一天到达终点那么倒数第二天你应该在哪根据天气你可以反推出到达终点前最后一段路的最佳出发时间和物资储备。5. 论文写作与结果呈现要点数学建模竞赛模型和算法只占一半另一半是论文表达。对于B题这种决策优化类问题论文写作有特殊要求。模型部分清晰定义状态、决策变量、目标函数和约束条件。即使你用了高级算法这些基本要素也要用数学公式清晰地表达出来。这是评委理解你工作的基础。详细阐述算法流程。无论是DP剪枝还是MCTS都需要用流程图或伪代码说明核心步骤。特别是剪枝规则、启发函数的设计要解释其合理性和有效性。进行复杂度分析。说明你的方法如何应对状态空间爆炸你的离散化策略如何剪枝后状态数减少了多少算法时间复杂度大概是多少。这体现了你对问题规模的认知和工程化处理能力。求解与结果部分提供详细的策略表或行动序列。这是最重要的输出。不能只说“我们得到了最大资金XXXX元”必须给出从第一天到最后一天每一天在什么位置、做什么、剩余多少水和食物、多少资金。通常以表格形式呈现。进行灵敏度分析或稳健性分析。这是拿高分的关键。可以探讨如果初始资金增加/减少10%策略和最终收益如何变化如果水的消耗量增加一些策略是否依然有效这展示了模型的鲁棒性和你的深入思考。可视化绘制行动路径图在地图上用箭头标出每天的移动轨迹用不同标记标出矿山停留和村庄购买点。一张好的路径图胜过千言万语。与简单策略对比可以设计一个“贪婪策略”总是去最近的矿物资快用完才去村作为基准对比你的优化策略在最终收益上的提升突出你模型的优越性。个人体会当年我们队采用的就是有限状态DP加帕累托剪枝的策略。最大的教训是在离散化精度上吃了亏。初期为了求快离散化单位设得很大结果求出的解明显粗糙。后来调整了离散化粒度并加入了“天气窗口跳跃”的优化即预计算两点间最短通行天数在DP中作为一个复合动作才在有限时间内得到了一个质量较高的解。另一个深刻体会是编程调试的时间远超预期。一个细微的逻辑bug比如沙暴日负重更新错误可能导致整个策略崩溃。因此一定要模块化编程并编写大量测试用例从简单场景比如没有矿山、全程晴天开始验证逐步增加复杂度。这道题与其说是数学竞赛不如说是一次对系统工程能力和严谨思维的全方位考验。