简介本资源是2020年全国大学生数学建模竞赛B题‘穿越沙漠’的参赛作品合集面向数学建模初学者、竞赛备赛学生及高校指导教师聚焦路径优化、资源约束建模与多阶段决策等典型问题。压缩包共28个文件含10个Python源码如Dijktra.py、Map*_MC.py等实现动态规划与蒙特卡洛模拟、6个文本配置与地图数据文件、2个PDF含论文thesis.pdf与提交规范submit.pdf、1个Excel成果汇总result.xlsx及MATLAB整数规划脚本intprogram_map5.m等整体仅2.51MB轻量易用。已有180人学习下载内容覆盖模型构建全过程从地图建模、变量定义、算法设计到结果可视化与验证分析代码结构清晰、注释完整配套文档明确说明提交格式与实验逻辑便于对照复现与思路迁移。 周末把2020年国赛B题“穿越沙漠”的参赛作品重新翻了一遍三十多份论文摆在桌面上从校级优秀到落选论文都有。越看越觉得这道题称得上近几年里“上手容易做深难”的典型。题目表面是找一条从起点到终点的沙漠路线背后却把资源分配、随机决策、信息利用这些硬核问题全部串了起来。这次整理出来的合集里有思路清晰、拿奖概率很高的做法也有让我印象深刻的典型错误。这篇就把这些作品里的主流解法、常见坑、以及真正得分的地方逐条拆开给以后想参加建模竞赛的队伍留一份能直接参考的复盘笔记。不管你是第一次接触这道题还是今年准备冲刺国奖都能从里面找到自己需要的东西。1. 题目到底在算一笔什么账1.1 先还原一下穿越沙漠的背景设定2020年B题的核心场景并不复杂一名玩家从起点出发背着有限的物资穿越沙漠最终到达终点。区域里分布着村庄和矿山。在村庄可以购买水和食物在矿山则可以挖矿换钱但挖矿本身也要消耗水、食物和时间。游戏按天推进每天天气不同晴天、高温、沙暴、暴风雨对体力与物资消耗影响很大。玩家每天要做一次行动决策是继续前进、就地休整、进村补货还是留在矿山多挖一天。目标是在所有约束都满足的前提下让最终收益最大化。约束主要有四类资金约束、携带容量上限约束、天数约束和天气约束。资金约束决定你能买多少补给容量约束决定你能带多少走天气约束决定每天消耗得快还是慢。这些要素直接戳中了建模竞赛最核心的考点多约束条件下的序贯决策。玩家每次行动都会改变后续的状态之前买多买少都会影响后面几天的生存概率。所以很多队伍看到题目第一反应是“这不是图论题吗”实际上它根本不是单纯的图论问题而是一个带资源流的状态转移问题。地图只是外壳资源和决策才是真正的内核。谁能早一步看透这一点谁就能在后面的建模中少走弯路。1.2 从参赛作品看命题组的真实意图我整理了这批作品之后明显感受到命题组想选拔的不是“路径搜索员”而是“决策建模者”。从作品反馈来看第一问大多数队伍都能写满因为确定性天气下可以用枚举、搜索、动态规划硬算。第二问加入随机天气后系统复杂度立刻提升。第三问引入每日天气信息的动态更新很多队伍直接放弃或者只给一个拍脑袋的决策规则。这说明命题组在层层递进地考察三件事一能不能在确定条件下做精细化最优决策二能不能在不确定条件下定义并优化期望目标三能不能利用新增信息动态调整策略。得分高低基本就取决于这三层做到了哪一层。用一句不太客气的话说能完整做完三个小问的队伍哪怕模型规模不大也在建模思路和算法实现上超过了大多数参赛者。而只能写出第一问的论文哪怕内容写得再华丽也很难进入高分区。2. 合集里出现的四条主流技术路线2.1 动态规划最稳妥的主力解法在收集到的作品里动态规划是出现频率最高的方法不算花哨但做扎实了就是稳定拿分的路线。核心思路是把每一天的决策看成一次状态转移状态定义为“当前在第几天、在哪个位置、手里剩多少水和多少食物”。行动就是转移的开关不同的行动会产生不同的消耗、收益和位置更新。用状态递推就能算出从起点到终点的最大收益。这条路线最大的优点是逻辑直观容易向评委解释也方便做灵敏度分析。缺点也很明显状态维度一多就会爆炸。我看到的几份高分作品基本都做了一件事就是利用约束条件剪枝。比如水或者食物已经不够支撑走到下一个补给节点时状态直接抛弃不再参与后续递推。还有队伍在状态里去掉了冗余维度把食物和水合并为“剩余存活天数”大大压缩了状态空间。这种在实现层面的细节往往比用一个高级算法更能拉开差距。2.2 网络流与最短路第一问的极简解法另一类作品把第一问抽象成了网络流或者最短路问题。思路也不复杂把地图上的节点和节点之间的耗水耗粮关系转化成边的权重然后用Dijkstra或者最小费用最大流寻找最优路径。这个做法的优势是求解效率高代码量也小非常适合第一问这种确定性的场景。但它的问题在于不好扩展。第二问加入随机天气之后边的权重不再是确定值最短路模型就需要变成随机最短路复杂度直线上升。第三问要处理动态信息更不是静态网络流能覆盖的。所以在合集里选择这种路线的队伍如果第二问和第三问没有及时切换建模思路后面两个小问往往就写得很浅。如果第一问用网络流求一个下界后两问换用动态规划倒是一种合理的组合策略也有作品因此拿到不错的分数。2.3 蒙特卡洛模拟随机场景下的兜底方案面对第二问的随机天气不少队伍选择了蒙特卡洛模拟。操作方法是根据天气分布随机生成大量天气序列在每一条天气序列下运行第一问的确定性最优策略然后对所有结果取平均得到期望收益。这种办法实现门槛低而且能比较直观地给出“在不同运气下可能赚多少”的分布连置信区间都能顺便画出来。看得出来这是很多参赛队伍在时间紧张时的第一直觉。但我在作品里也看到个很明显的短板很多队伍只做了模拟却没有把“应对随机天气的策略”真正设计出来。模拟本身能够评价一个策略的好坏却不能自动生成一个好策略。所以更合理的用法是先假定一套决策规则比如“只要第二天沙暴概率超过50%就提前在村庄补满物资”然后用蒙特卡洛枚举所有天气场景检验这套规则的收益均值是否最优。只有把策略设计、模拟验证和参数寻优结合起来蒙特卡洛这条路线才算走完整。2.4 强化学习、启发式搜索亮点与风险并存还有几份作品用了强化学习方法比如Q-learning或者蒙特卡洛树搜索。这些作品在评委眼里很有新鲜感尤其是把天气随机性看作环境的转移概率把状态价值函数直接学出来思路确实漂亮。问题在于训练参数的稳定性和可解释性普遍不足。有份作品把Q表大小写得很大但完全没有交代收敛条件也没有给出不同学习率下的结果对比评委很难判断这个结果到底靠不靠谱。我的判断是这类方法作为点缀或者对照实验非常出彩但作为主要解题方法要承担较大风险。建模竞赛最终提交的是论文而不是代码评委更希望看到能读懂的模型结构和对结果的深入分析。算法花哨但讲不清楚反而会拉低整体评价。如果你所在的队伍恰好有大佬能把这套方法讲透那可以尝试否则建议把强化学习放在附录里作为扩展实验正文还是以能完整自圆其说的模型为主。技术路线适用小问最大优势最大风险动态规划第一、二、三问逻辑清晰、可解释性强状态维度爆炸网络流/最短路第一问求解快代码量小难以扩展随机与信息蒙特卡洛模拟第二问实现简单、可出分布只评价策略不生成策略强化学习第二、三问思路新颖、上限高稳定性差、可解释性弱3. 三个小问的拆解与实操记录3.1 第一问确定性天气下的最优决策第一问通常是“在给定未来天气的条件下找出收益最大的穿越方案”。实操上可以先做一个可行性枚举列出所有从起点到终点的可行路径以及每条路径上的停留天数然后在每条路径上再优化购买和挖矿策略。因为地图节点少、天数窗口有限枚举加剪枝完全跑得动。这个思路不少队伍都想到了真正的差异在后面对细节的处理上。下面这个递推结构是我从一份高分作品里提炼出来的很值得参考状态: S (day, pos, water, food) 含义: 第 day 天在 pos 位置剩余 water 单位水、food 单位食物 最优值: F[S] 表示进入该状态时累计资金的最大值 初始: 在起点购买补给后进入第1天F 初始资金 - 购买花费 转移: 停留: water - 当日消耗; food - 当日消耗 行走: 移动到相邻节点额外扣除行走消耗 挖矿: 扣除挖矿消耗; F 挖矿收益 购买: 在村庄用资金换水和食物总量不超过容量上限 答案: 所有到达终点状态中 F 的最大值如果你第一次写这种状态最容易漏掉的是“购买”这个动作。很多队伍默认只有路过村庄时才购买却忽略了可以专门绕路去村庄补货再折返矿山。第一问的收益差异往往就来自这些看似细节的选择。我建议在建模时把“购买”当成一个与位置相关的可选行动而不是一个被动事件。另外挖矿并不是挖越多越好因为每多挖一天就多消耗一天的水和食物还可能错过后面的天气窗口。正确做法是把挖矿天数也纳入优化变量用枚举或搜索方式找到最优值。3.2 第二问随机天气下的期望收益与决策第二问的天气不再提前给定而是以一定概率分布出现。这里最核心的变化是目标函数从“给定序列下的收益”变成了“所有可能天气序列下的期望收益”。如果你只是随机抽几条天气序列取平均那只能叫模拟不能叫优化。真正要做好需要把决策规则作为变量来优化。一种可行方法是先确定一个决策规则的参数化形式比如“当剩余水少于某个阈值且附近有村庄时进村补货”然后用动态规划或搜索去调优这些阈值。另一种更系统的做法是随机动态规划把天气状态加入状态空间用期望值递推计算最优行动。写成公式就是V(day, pos, w, f, m) max_action E_weather[ V(day1, pos, w, f, m) ]这个期望是当天可能是晴、沙暴等不同天气下的加权平均。由于状态维度和天气种类有限完全可以在可接受时间内算出精确解。我在合集里见过用动态规划配合状态压缩完成第二问的队伍他们把所有可能的天气序列按概率加权后直接并行枚举最后画出了收益分布直方图结果非常扎实。不过请注意如果完全按照期望收益最大化来选择策略可能会忽略风险。在现实里玩家更关注的是“保证能活着到终点”的前提下再谈赚多少钱。所以有不少作品会在第二问里加入一个“最低生存概率约束”要求策略必须保证不因缺水断粮而失败的概率低于某个阈值。这种带风险约束的决策模型明显比单纯算期望更有竞争力也更容易写出亮点。3.3 第三问动态信息下的滚动决策第三问把场景变得更贴近现实玩家在每天行动之前能获得新的天气信息比如当天确切天气已经能提前看到未来几天只有概率预报。这种问题本质上是带信息更新的序贯决策求解思路可以从决策树展开。每个节点代表一个状态树的每条分支代表一种可能的新信息在叶节点做完整收益评估后再沿树回传最优决策。但在实际比赛中想完整展开决策树往往不现实所以高分作品更多采用滚动时域优化也叫在线重规划。核心做法是当前时刻只决定今天的行动等明天获得新的天气信息后重新优化剩余的路径和资源分配。这种策略不需要预先算完所有可能场景实现起来逻辑清楚也不容易出错。我甚至见过有队伍把第一问的求解器封装成一个函数在第三问里循环调用代码量很小却非常实用。还有一个加分技巧是引入“信息价值”这个指标。做法是对比“知道当天天气再决策”和“完全不知道天气只能按历史概率决策”两种情况下的期望收益差值就是天气信息的价值。这个量既能在论文里作为评价指标也能让评委看到你对问题本质的理解深度。能从第三问里把“信息”单独拿出来量化的作品整体评价都不会低。3.4 从作品合集看三道题的整体完成度分布把所有作品摊开看三个小问的完成度分布非常不均匀。第一问绝大多数队伍都给出了完整的模型和结果第二问大概只有一半队伍给出了真正在优化策略而非单纯模拟的方案第三问能拿出系统模型的队伍就不到三成了。这也解释了为什么最终评奖梯度拉得特别开。所以给参赛队伍最直接的建议是不要在前面耗费太多篇幅。第一问写得干净利落即可后面两问才是区分度所在。如果时间不够也至少要保证第二问有完整的建模和灵敏度分析第三问给出清晰的算法流程和至少一组对比实验。从评委视角看宁可用简单方法把后面两问做完整也不要拿着复杂模型只做第一问。4. 作品里反复出现的失分点与避坑清单4.1 审题阶段最容易犯的三个错误整理作品时我发现审题阶段的错误比算法错误更可惜因为明明会做却因为理解偏差白白丢分。第一个错误是目标定位偏了把“最大化收益”简化成“最短路径”。题目真正关心的是到达终点后手里有多少钱最短路径不等于最大收益有时候绕路去挖矿反而更赚。第二个错误是遗漏容量约束很多队伍购买物资时只算钱够不够忘了手上的水加上食物不能超过载重上限。第三个错误是混淆“确定性天气”和“已知概率天气”。第一问和第二问的解题思路完全不同但不少作品在第一问里加入期望分析在第二问里却按固定最坏天气设计路线读起来非常别扭。4.2 建模和实现阶段的典型问题在电脑上实际跑出来的问题更五花八门。最常见的是状态爆炸后又没有剪枝程序跑几分钟都不出结果最后只能硬调参数。其次是对采样和随机性的处理不严谨。第二问用蒙特卡洛时有的作品只跑了500次模拟就说“结果趋于稳定”这明显不够。正确做法是画一条模拟次数与收益均值的关系曲线观察到均值进入平稳区间后再说明收敛性。另外保存中间状态时要注意单位统一有的作品水和食物的单位不一致导致转移方程里出现过“每单位水重量3、每单位食物重量5”之类的数字代码虽然能跑通结果却完全失真。这些低级错误最可惜因为只要多花十分钟核对就能避免。4.3 论文表达和结果验证方面的建议论文表达方面我特别想强调图表的重要性。好的作品会画三张图地图结构示意图、状态转移流程图、以及不同策略下的收益对比柱状图。这几张图比大段公式更容易让评委抓住核心思路。验证方面几乎每份优秀作品都会做边界case测试比如假设全程无沙暴、全程沙暴、物资刚好够用等极端场景验证模型在极限条件下依然合理。如果你提交的作品里缺少这类验证评委很难相信你的模型具备普适性。在合集中有一个让我印象很深的队伍他们专门把三种极端天气场景列在同一张表里逐项对比模型给出的路径与资源余量这种严谨性是评委愿意给高分的重要原因。5. 从这批作品里捞出的实战经验5.1 好的参赛作品普遍具备五个特征把优秀作品放在一起横向对比我能找出五个共性特征。第一问题重述不拖泥带水直接提取出状态、行动、约束和目标函数没有任何废话。第二模型的假设清晰且合理对于暂时简化掉的要素都有交代比如“假设天气之间独立”“假设玩家体力不随时间衰减”。第三算法复杂度有预估队伍在提交前就知道程序大概要跑多久不会等到现场跑死了才想办法。第四结果分析包含参数灵敏度至少改变一个关键参数后重新计算一遍观察最优策略是否稳定。第五对模型局限性有反思承认在极端天气或超大场景下可能失效。这五点看起来不难但能同时做到的队伍并不多。5.2 给下一届参赛队伍的操作建议如果你准备参加下一届建模竞赛或者正在训练同类型题目我的建议是从三天时间分配开始倒推。第一天上午只做审题和建立基本模型下午实现一个能跑通第一问的简化版本晚上留给第二问的建模。第二天重点做第二问的随机模型并尽量让结果能稳定复现这个稳定比华丽更重要。第三天上午解决第三问的动态决策下午集中精力写论文、画图表、做灵敏度分析和边界测试。这个节奏对绝大多数队伍都适用也是我在带过的队伍里验证多次的安排。另外在建模和编程分工上我强烈建议建模和编程由不同人负责但两人必须随时沟通状态定义。很多队伍吃亏就吃亏在建模同学写了一个很漂亮的状态转移图编程同学却有自己的一套变量定义最后两边对不上。定好状态变量的命名规则和单位换算表写在显眼的地方能少走很多弯路。这道题特别考验建模和代码的衔接因为状态空间和行动空间都在模型层就决定了后面所有程序都建立在同一套定义上。5.3 我自己重算这道题时用到的两个小技巧最后分享两个我在整理作品时手动重算验证的小技巧。第一个是“反向推演”站在终点往前推判断从某个节点出发最少需要准备多少水和食物才能保证到终点。这个反向值可以作为正向动态规划的下界用来剪枝效果很好。比如某个状态即使所有天气都放晴剩余资源也不足以到达终点那这个状态就可以直接丢掉了。第二个是“逐日滚动验证”拿到一个推荐的策略后不要只看最终收益要按天模拟一遍每天检查水、食物、资金余额是否始终为非负补给动作是否严格遵守了容量上限。很多策略的隐藏bug只有在这种逐日检查中才会暴露出来。这两个技巧不复杂但简单可靠尤其是在比赛时间紧张的时候能帮你快速排除错误的策略把精力留给真正值得优化的部分。以后再遇到穿越沙漠这类资源分配加随机决策的题目记住先把状态和转移画清楚再决定用什么算法顺序千万不能反。这个习惯是我从这次整理作品的过程中体会最深的一点也是那些高分作品共同的教学案例。本文还有配套的精品资源点击获取