简介多阶段决策是运筹优化与算法工程中的核心问题其原理在于将复杂决策过程拆解为一系列相互关联的阶段每个阶段的状态与动作共同影响后续收益。在资源受限、环境动态变化的场景中动态规划通过状态压缩与递推方程高效求解最优策略而最短路模型则将消耗与收益转化为边权为路径优化提供另一种视角。当环境存在不确定性时蒙特卡洛模拟与稳健决策思想能够评估策略的风险与期望收益从而在随机条件下做出可靠选择。这类建模方法不仅适用于数学建模竞赛更广泛用于物流调度、生产排程、库存管理等真实工程问题。本文以2020年全国大学生数学建模竞赛B题《穿越沙漠》为例系统拆解确定性天气下的动态规划建模、随机天气下的决策树与蒙特卡洛验证并给出参赛论文的组织框架与代码实现要点帮助读者掌握从规则分析到模型落地的完整链路。 2020年国赛B题《穿越沙漠》是我近几年在整理参赛作品时最常翻出来重看的一道题。原因是它的规则简单到可以用一个下午讲清楚但建模深度又足够撑起一篇获奖论文。当年这道题一公布各群里的讨论就炸了有人觉得这是模拟题有人觉得这是动态规划题还有人拿着图论最短路直接冲。事实上这些说法都对关键是看你用哪套框架去组织问题。我这次整理了数十份参赛作品合集把不同思路的论文放在一起对比发现很多队伍不是输在算法上而是输在对赛题规则的建模颗粒度上。这篇文章就围绕“穿越沙漠B题到底在考什么、常见解法怎么做、一篇好论文该怎么组织”这三个问题展开希望能给准备打数学建模竞赛的同学一些可以直接落地的思路。1. 赛题规则与考点透视先别急着写代码1.1 核心规则还原很多同学拿到这道题的第一反应是找题目里的“答案”比如求最短路径或者最大收益。但《穿越沙漠》的难点恰恰在于它不是一个单纯的路径优化问题而是一整套资源调度规则下的决策问题。我先把规则梳理一遍后面所有模型都建在这套规则之上。玩家从起点出发在规定的天数内到达终点超时即失败。每天消耗一定量的水和食物消耗量由当天天气晴朗、高温、沙暴以及当天是否挖矿决定。天气按天给出第一问中未来若干天天气是已知的第二问中只有前若干天已知。玩家可以选择移动、停留、挖矿、购买物资。挖矿只能在矿山位置进行每天获得固定收益但当天水、食物消耗翻倍。购买物资只能在起点或村庄进行起点价格便宜村庄价格贵。玩家有负重上限水和食物都有单位重量超出就无法携带。水和食物任一消耗到0还未到达终点判定为游戏失败。规则里最容易被忽略的有两个点。第一个是“沙暴天不能移动”这个约束直接把路径搜索的可行域切断了第二个是“挖矿时消耗翻倍”这意味着矿山不是纯收益节点而是“用物资换资金”的转换节点是否值得挖矿完全取决于当前水、食物储备和后续天气。这两条规则叠加在一起就让“多挖几天矿”变成了一个需要仔细权衡的决策而不是无脑赚钱。为了把问题讲清楚我这里给出一组常见的示例参数各队伍当年使用的官方参数可能略有不同实际以赛题为准。参数示例值说明初始资金1000可用于购买物资负重上限1200 kg水和食物总重量不能超过起点水价3元/份起点购买最便宜起点食物价3元/份起点购买最便宜村庄水价6元/份贵但可应急矿山日收益100元挖矿当天收益固定晴朗/高温/沙暴消耗3/5/8份水和食物同标准消耗这里的消耗数字并不是当年官方赛题的标准值只是我用来说明建模思路的示例。实际比赛时要把官方给的消耗表、收益表原样代入模型。有一点需要注意不同版本的赛题可能在关卡设定上有差异有的关卡把路线分成多段有的关卡把天气概率给了不同的分布所以建模前一定要逐字读题把参数抽出来列成一张表这是后面所有工作的地基。1.2 题目真正想考的能力从出题者的角度看这道题想考查的不是“你会不会贪心”而是四个方面。第一多阶段决策建模能力。玩家每天都要面对“移动/停留/挖矿/购买”的离散决策每个决策都会影响后续所有天的可行性和收益。这不是一道静态题而是一道典型的序贯决策问题。第二约束处理能力。负重、时间、天气、资源耗尽任何一个约束都能让朴素贪心算法直接崩掉。第三不确定性建模能力。第二问把天气从“全知”改成“部分未知”这就从确定性优化跳到了随机决策的范畴。很多队伍在这里掉队因为他们还是拿第一问的思路硬套。第四工程实现与验证能力。模型再漂亮最后都得跑出数字。对动态规划、最短路、蒙特卡洛模拟这些算法的实现细节决定了你能不能在规定时间内交出一份可复现的结果。把这四点想清楚之后再去看各类参赛作品就会发现优秀论文和普通论文的分水岭不在算法炫不炫而在对规则的建模颗粒度和对求解思路的取舍逻辑。比如同样是用动态规划有的队伍把状态定义得又大又散跑都跑不动有的队伍做了状态压缩几秒钟就出结果。这两支队伍在论文里写出来的模型公式可能长得差不多但背后的思考深度完全不一样。2. 第一问确定性天气下用动态规划还是最短路2.1 状态定义是建模的第一步第一问的核心特征是未来所有天的天气已知。也就是说玩家在做任何决策之前整个“环境”是一个完全确定的信息集。这时候问题变成一个确定性、有限阶段的离散优化问题最常见的做法是动态规划。但动态规划第一步——状态定义就卡住了很多人。如果直接定义状态为“第t天、位置i、剩余水w、剩余食物f、剩余资金m”那么这个状态空间是五维的w和f的取值范围还可能达到几百上千组合起来根本没法枚举。所以要做状态压缩。压缩的思路是把“剩余资金”变成由其他状态推导出来的值。因为在规则里资金只通过购买和挖矿两个动作变化而水、食物是实际消耗品。只要记录“当前还剩多少水、多少食物、多少物资总重量”再结合历史路径就能算出资金的使用情况。更进一步的压缩思路是对每个位置、每一天直接定义“到达该节点时剩余资金最大”作为DP值。由于路径和天气确定从上一个节点转移到下一个节点时消耗是确定的所以只需要决策“是否挖矿、是否购买、是否等待”。这个思路有点类似“从终点倒推”的逆推动态规划从最后一天往前递归每一步都保留当前最优资金最后起点处的值就是答案。这里有一个我当年踩过的坑把“剩余水”和“剩余食物”当作两个独立维度放进状态结果状态爆炸程序跑了一个小时都没出结果。后来改成“只保留水和食物的总重量”作为状态再通过贪心策略分配水和食物的携带比例计算量直接降了一个数量级。原因在于水和食物在功能上高度相似而决策时真正约束携带量的是总负重而不是各自的剩余量。但要注意这个压缩思路在“水和食物价格相同、消耗比例固定”的简化条件下才成立。如果赛题把水和食物的基础消耗比例设得完全不同比如水消耗快、食物消耗慢就需要在压缩时额外加一个维度记录当前策略下水和食物的比例是否偏离最优比例否则压缩就会失真。2.2 把每天消耗转成边权把问题看成图论最短路也行而且这是一个很优雅的转化。思路是每个节点表示为“第t天在位置i”。如果第t1天天气允许移动就建一条边从(第t天,位置i)指向(第t1天,位置i1)边的代价是当天的水、食物消耗。如果玩家选择在某个位置停留就建一条自环边消耗当天水、食物。如果玩家在矿山停留并挖矿消耗翻倍但获得固定收益。如果玩家在村庄或起点可以在节点上做“购买”操作相当于在水、食物消耗的代价基础上加一笔价格调整。这样整理出来的图边的权重是“资金”而不是“距离”。因为天气已知每个节点的消耗都能精确计算所以从起点到终点的最短路对应的就是最优决策。但是千万不要直接用任意图最短路模板去跑。这个转化后的图里节点之间的边权并不是独立的它们共享同一个负重限制。换句话说即使最短路算法告诉你“这条路总代价最低”也还要检查这条路径上的物资总重量有没有超出负重上限。否则算法会给你一条理论上资金最优、实际上根本不可行的路径。正确的做法是在DP中把负重上限当作约束条件或者在构建图时把“携带的物资总量”作为路径上的累计状态再做约束检查。我个人更推荐前者因为动态规划天然支持维度扩展而图算法扩展状态维度会比较别扭。还有一个折中的办法是先不管负重上限跑一遍最短路得到一张“最优路径表”再逐段检查负重。如果超了就把超重那几段的物资购买方案拆开看看能不能通过提前购买、分批携带来绕开限制。这个方法虽然不一定能找到全局最优但作为初筛非常快。2.3 边界情况与失败判定第一问的陷阱往往藏在边界条件里不是算法本身。初始阶段资金有限如果起点就把物资买满可能后续资金不够在村庄应急。沙暴天无法移动如果恰好卡在离村庄或矿山很远的位置连续几天沙暴会直接耗尽物资。挖矿虽然赚钱但收益是否覆盖额外消耗需要提前用“收益/额外消耗”的比值判断。我见过不少队伍在论文里把“失败判定”写得很模糊什么“物资耗尽则游戏失败”但代码里却没有严格检查每个中间状态的可行性。评委最喜欢在这种地方扣分。建议在建模时把“水0或食物0”作为硬约束写进递推公式并在数值实验时给出失败路径的示例让读者直观看到边界条件的意义。实际操作中还有一种隐蔽的失败情况是“到达终点但超时”。有些队伍在DP里没有限制至少要在第几天之前到达只在最后输出终点的最优值结果程序为了多挖几天矿选择了超时到达的路径。为了避免这种情况我把“天数”直接放在状态里并且只记录“恰好第t天到达位置i”的最优值这样天然排除了所有超时路径。这个小细节看起来不起眼但能帮你避免一个很尴尬的结果错误。3. 第二问天气未知时从“最优”到“稳健”3.1 决策树与期望收益第二问把天气改成了“前若干天已知后续未知”。这意味着第一问的确定性DP不能直接用了。但好消息是天气虽然是随机的它的取值是有限的晴朗、高温、沙暴三种而且概率分布题目会给出。于是可以把问题建模成决策树树的每一层代表一天树的每个分支代表一种可能的天气状态。在决策树上做“期望资金最大化”思路和第一问的DP一致只是转移函数改为求期望。如果设V(t, i, s)为“第t天在位置i、当前物资状态为s时的最大期望剩余资金”那么转移时对每个可能的天气计算对应的消耗和决策后的资金再按概率加权求和。这个求解框架虽然简单但有一个隐藏问题如果直接在完整决策树上展开30天、每天3种天气会得到3的30次方个叶子节点这显然是不可行的。所以实际要做的是“剪枝”和“近似”。常用做法是在每个决策点只保留有限个候选动作再用蒙特卡洛抽样去评价这些动作的期望收益而不是枚举所有天气组合。我整理过的作品里有队伍用“随机动态规划”来求解状态转移方程写得很漂亮但运行时间极长。后来他们做了一个简化因为每种天气出现的概率是独立的未来10天的天气组合虽然很多但很多组合对应的消耗是一样的比如3个晴天、2个高温、5个沙暴和2个晴天、4个高温、4个沙暴如果只关心总消耗这两组天气的累计效果可能相同。这就能用“合并同类项”的思路大幅压缩状态。这个技巧在第二问里特别适用因为玩家关心的往往不是某一天具体是什么天气而是接下来若干天累计消耗了多少物资。3.2 稳健策略与后悔值分析第二问里很多优秀作品并没有直接追求“期望资金最大”而是引入了风险厌恶用“最大化最坏情况下的收益”或者“最小化最大后悔值”来建模。原因很实际期望最大化的策略可能在某些极端天气下直接失败比如为了多挖几天矿赌后续不会连续沙暴结果一旦连沙暴就资源耗尽。竞赛题目想要看到的是你能不能在不确定性下做出合理决策而不只是算一个期望值。最小最大后悔值的思路是先假设我们知道真实天气序列算出每个天气序列下的“事后最优收益”然后定义“后悔值”为当前策略收益与事后最优收益之差最后选择一个让最大后悔值最小的策略。这个思路在论文里写出来会非常加分因为它体现了你没有把随机性简单地平均化而是考虑了决策的稳健性。评委看到这部分通常会给较高的模型创新分。举一个很直观的例子假设两种策略A策略在90%的情况下收益是500在10%的情况下失败B策略在任何天气下收益都是400。期望收益算下来A更高但如果你把这个游戏重复玩一百次B策略永远不会失败而A策略有十次会直接出局。对于一次性的比赛你愿意赌A还是保B这个选择没有标准答案但你能不能在论文里把两种选择的利弊讲清楚就体现出建模思维成熟度了。3.3 蒙特卡洛模拟评估第二问里蒙特卡洛模拟不应该作为求解主算法而是作为验证工具。做法是按照题目给出的天气概率分布随机生成大量天气序列几千到几万条然后用第一问开发的确定性DP来求解每条天气序列下的最优策略得到收益分布。再把你设计的稳健策略在这些天气序列上跑一遍对比收益分布。这里有一个关键点模拟得到的收益分布直方图非常好用。第一可以直观展示某个策略在大多数情况下收益高不高第二能看出策略是否有“尾部风险”即在极端天气下是否容易翻车。论文里放一张收益直方图比十段文字都管用。我在整理作品时发现凡是拿到高分的队伍几乎都做了某种形式的蒙特卡洛验证。有的队伍还额外做了“在预测天气存在误差时策略的表现”分析这个属于加分项因为他们主动处理了模型对输入误差的敏感性。做蒙特卡洛模拟时一个常见的坑是随机数种子没有固定。结果每次运行程序得到的收益分布都不一样论文里写的数字和代码实际跑出来的数字对不上这在答辩时是致命的。我建议在代码里固定随机种子并且在论文的附录里写清楚“随机种子为2020抽样次数为1000095%置信区间为XXX到XXX”这样整个结果可复现、可验证也能体现你做实验的严谨性。4. 参赛作品的完整组织框架从摘要到灵敏度分析4.1 从摘要到灵敏度分析的布局整理了大量参赛作品之后我发现优秀论文的结构惊人地一致不是因为他们抄袭而是因为数学建模竞赛的评分维度非常稳定。通常一篇完整作品包含摘要、问题分析、模型假设、模型建立与求解、灵敏度分析、模型评价与推广这几大块。摘要300到500字直接决定评委的第一印象。高手会在这段里写清楚“问题是什么、我用了什么模型、得到什么结果”而且会写具体数字比如“在天气全知条件下最优资金为8400元瓶颈约束来自连续沙暴天气下物资储备不足”。避免写“我们采用动态规划求得了较好的结果”这种废话。问题分析部分用自然语言梳理决策链路画出问题拆解图或决策流程图这一步是为了让评委相信你真的理解规则。模型假设把赛题里没有明说但建模时默认的细节列出来比如“忽略购买物资时的时间成本”“水、食物可无限细分”等。模型建立与求解部分按问题拆成小节每个小节给出数学模型、递推公式、算法流程、运行结果。灵敏度分析是变化关键参数如初始资金、天气概率、物资价格观察结果变化。很多队伍把这一节写得像应付差事其实这是拉开分差的地方。模型评价与推广部分简单写优缺点的同时要说明模型思路可以迁移到哪些场景比如库存管理、物流调度、生产排程。4.2 评委视角下的常见丢分点第二问部分已知天气这种题目最容易出现“把随机问题当确定性问题做”的错误。很多队伍在第二问里直接沿用第一问的DP只在前若干天用已知天气后续天气就随便挑一种“最可能”的天气去跑。这种做法理论上不严谨评委一眼就能看出来。还有几个常见丢分点。模型假设过多把赛题核心矛盾假设没了比如假设“沙暴天气不会出现”或者“挖矿收益大于一切”这样后续模型再精巧也没意义。把算法实现了但缺少数学表达式评委需要看到具体的递推公式、约束条件表达式而不是只看到“用Python实现动态规划”一句话。结果没有解释写出“资金为8400”还不够要解释为什么是这个数比如“资金主要消耗在最后三天的连续高温天气”。灵敏度分析是空的只画图不加解释画完参数变化图后至少要说清楚“初始资金每降低100元最优收益下降多少原因是购买物资的边际成本上升”。我翻过的几十份作品里还有一个很普遍的毛病论文里贴了大段源代码。评委根本不会看你的代码他们要的是思路和结果。代码可以放附录但正文只放关键公式、核心算法伪代码和结果图。做这个调整之后论文的观感会提升不少。另外排版规范也是隐性分数公式编号、图表标题、参考文献格式统一这些细节做不好再好的内容也会被打折扣。5. 代码实现与复现从公式到可运行结果5.1 动态规划的Python实现思路写代码之前先定数据结构。我建议定义三个核心数据结构天气表、位置属性和状态记录。天气表是长度为总天数的一维数组位置属性是一个字典key是位置编号value说明这个位置是起点、终点、村庄、矿山还是普通地点状态记录则用多维数组或字典记录(day, pos, water, food, money)或者压缩后的状态。一个典型的确定性DP伪代码如下# 示例伪代码具体参数以官方赛题为准 days len(weather) # dp[t][i][carry] 表示第t天在位置i携带总重量为carry时最大剩余资金 dp [[[-inf] * (MAX_CAPACITY 1) for _ in range(N)] for _ in range(days 1)] dp[0][start][init_weight] init_money for t in range(days): for i in range(N): for carry in range(MAX_CAPACITY 1): if dp[t][i][carry] -inf: continue w_use, f_use consume_by_weather[weather[t]] # 决策1: 移动到下一个位置天气允许时 # 决策2: 停留在当前地点 # 决策3: 挖矿如果在矿山 # 决策4: 购买物资如果在村庄或起点注意这段伪代码里“购买”应该放在转移之后还是之前取决于你对“当天消费顺序”的定义。现实模型中玩家可以在一开始就购买也可以到达村庄当天购买再消费。不同的时序假设会带来不同的结果所以你要在模型假设里明确写清楚。我习惯上把“消费”放在每天的最后也就是先决策移动或挖矿再扣除当天消耗最后才允许购买补给。这样模拟的是“白天赶路或干活一天结束后再补货”的场景。5.2 参数标定与结果验证跑通代码之后不要急着写论文。第一件事是做小规模测试手动构造一个两三天的小沙漠手算最优解再和程序跑出来的结果对比。这样能快速发现时序错误、边界条件错误。我当年测试时发现代码里最常见的bug是“沙暴天仍然允许移动”和“购买后负重超限”这两个条件没有同时检查。这两个bug同时存在时程序会给出一个看似合理但实际不可行的最优策略。你如果不做小规模手动验证这种错误会一直藏到交卷。还有一种情况要特别注意程序求出的“最优路径”里可能会出现走到某个节点时剩余物资刚刚好够走到终点但完全没有预留应对意外天气的余量。在确定性第一问里这没问题因为天气已知不会有意外的沙暴但在第二问里如果还沿用这种“卡着边界走”的策略一旦实际天气和预测概率分布有偏差就很容易翻车。所以做第二问的策略时我建议在代码里人为设置一个“安全库存”比如始终保留至少一天的物资作为缓冲这样虽然期望收益会略微下降但大大降低了失败概率。5.3 可视化与结果呈现论文里放图不要放代码截图。最有用的图有三类最优路径图、资源消耗曲线、天气与决策对齐图。最优路径图是在地图上标出玩家每天的位置和动作颜色区分移动、停留、挖矿。资源消耗曲线画出每天结束时水、食物、资金的变化曲线直观展示资源是否逼近耗尽边界。天气与决策对齐图把天气条和决策条按天对齐显示哪几天因为沙暴被迫停留哪几天因为高温消耗激增。这类图不用画得多花哨用matplotlib画清楚就行。关键是让评委一眼看懂你的策略在关键节点上的取舍。我见过一个作品把“资金曲线”和“物资总量曲线”画在同一张图里并用阴影标出“可安全返回村庄的最晚时间”这个设计非常加分因为它把决策的“死线”可视化了出来。后来我自己做类似的调度问题时也沿用这个画法效果很好。画图的配色和字体也要统一避免出现花里胡哨的颜色毕竟这是学术论文不是海报设计。6. 从穿越沙漠沉淀出的通用建模能力6.1 一套可复用的资源-路径-随机三层框架比赛结束后回头再看这道题会发现它其实是一个通用问题框架的实例。底层是资源层水、食物、资金分别对应库存、消耗品、货币。中层是路径层移动、停留、挖矿、购买对应路径选择、加工、采购。上层是决策层确定性天气和随机天气对应确定性环境和随机环境下的序贯决策。把这三层拆开之后你会发现很多实际场景都能套进这个框架。外卖骑手的送餐路线规划要考虑时间、电量、订单收入“三坐标”平衡工厂的生产排程要处理原料库存、加工时间、机器产能的匹配仓储物流的补货策略要解决库存水位、需求随机、运输成本之间的冲突。这些问题的底层结构都和你在这道题里遇到的“水、食物、资金、天气、时间、负重”非常相似。所以打比赛的价值不只是学一个算法而是学会“把现实问题抽象成可求解的数学模型”。在整理合集的过程中我看到一支队伍用“库存-生产-销售”模型来类比穿越沙漠水、食物是原材料移动是生产过程挖矿是增值加工村庄是补货点终点是交付客户。这个类比看起来简单却能帮助队友快速对齐思路也方便后续把成熟的库存管理模型迁移过来。这也是我建议大家拿到新题以后先做的一件事用自己熟悉的领域去重新描述题目找到问题的“骨架”。6.2 对备赛选手的几点建议最后聊一点更实在的备赛建议。第一前三天不要急着写代码先把题目读三遍把所有规则写成一二三四条再开始建模。第二代码和论文要并行推进不要等模型完全跑通再写论文因为论文里的问题分析部分完全可以提前写。第三重要参数一定要做多组对比一组参数跑出结果就写进论文评委一眼就能看出你没有做系统分析。另外我想分享一个个人感受整理优秀作品集的时候你会发现那些拿国奖的队伍论文里的关键结果几乎都能复现而不是“比赛当天随手跑的运气产物”。他们把每一步推导都写清楚每个数字都能对上每个参数都是有意选择的这种严谨习惯比临时抱佛脚学某个高级算法有用得多。这道“穿越沙漠”看起来是个游戏题但把它的所有决策逻辑串起来之后你锻炼出的恰好是真实世界里的资源配置能力。这几年数学建模竞赛的题目越来越偏向规则复杂、数据量大、环境不确定的真实场景题穿越沙漠B题算是这种趋势的早期代表。如果你能把这道题的原理吃透再去做类似的任务调度、资源优化题目会顺畅很多。本文还有配套的精品资源点击获取
从动态规划到随机决策：国赛穿越沙漠B题全解析
简介多阶段决策是运筹优化与算法工程中的核心问题其原理在于将复杂决策过程拆解为一系列相互关联的阶段每个阶段的状态与动作共同影响后续收益。在资源受限、环境动态变化的场景中动态规划通过状态压缩与递推方程高效求解最优策略而最短路模型则将消耗与收益转化为边权为路径优化提供另一种视角。当环境存在不确定性时蒙特卡洛模拟与稳健决策思想能够评估策略的风险与期望收益从而在随机条件下做出可靠选择。这类建模方法不仅适用于数学建模竞赛更广泛用于物流调度、生产排程、库存管理等真实工程问题。本文以2020年全国大学生数学建模竞赛B题《穿越沙漠》为例系统拆解确定性天气下的动态规划建模、随机天气下的决策树与蒙特卡洛验证并给出参赛论文的组织框架与代码实现要点帮助读者掌握从规则分析到模型落地的完整链路。 2020年国赛B题《穿越沙漠》是我近几年在整理参赛作品时最常翻出来重看的一道题。原因是它的规则简单到可以用一个下午讲清楚但建模深度又足够撑起一篇获奖论文。当年这道题一公布各群里的讨论就炸了有人觉得这是模拟题有人觉得这是动态规划题还有人拿着图论最短路直接冲。事实上这些说法都对关键是看你用哪套框架去组织问题。我这次整理了数十份参赛作品合集把不同思路的论文放在一起对比发现很多队伍不是输在算法上而是输在对赛题规则的建模颗粒度上。这篇文章就围绕“穿越沙漠B题到底在考什么、常见解法怎么做、一篇好论文该怎么组织”这三个问题展开希望能给准备打数学建模竞赛的同学一些可以直接落地的思路。1. 赛题规则与考点透视先别急着写代码1.1 核心规则还原很多同学拿到这道题的第一反应是找题目里的“答案”比如求最短路径或者最大收益。但《穿越沙漠》的难点恰恰在于它不是一个单纯的路径优化问题而是一整套资源调度规则下的决策问题。我先把规则梳理一遍后面所有模型都建在这套规则之上。玩家从起点出发在规定的天数内到达终点超时即失败。每天消耗一定量的水和食物消耗量由当天天气晴朗、高温、沙暴以及当天是否挖矿决定。天气按天给出第一问中未来若干天天气是已知的第二问中只有前若干天已知。玩家可以选择移动、停留、挖矿、购买物资。挖矿只能在矿山位置进行每天获得固定收益但当天水、食物消耗翻倍。购买物资只能在起点或村庄进行起点价格便宜村庄价格贵。玩家有负重上限水和食物都有单位重量超出就无法携带。水和食物任一消耗到0还未到达终点判定为游戏失败。规则里最容易被忽略的有两个点。第一个是“沙暴天不能移动”这个约束直接把路径搜索的可行域切断了第二个是“挖矿时消耗翻倍”这意味着矿山不是纯收益节点而是“用物资换资金”的转换节点是否值得挖矿完全取决于当前水、食物储备和后续天气。这两条规则叠加在一起就让“多挖几天矿”变成了一个需要仔细权衡的决策而不是无脑赚钱。为了把问题讲清楚我这里给出一组常见的示例参数各队伍当年使用的官方参数可能略有不同实际以赛题为准。参数示例值说明初始资金1000可用于购买物资负重上限1200 kg水和食物总重量不能超过起点水价3元/份起点购买最便宜起点食物价3元/份起点购买最便宜村庄水价6元/份贵但可应急矿山日收益100元挖矿当天收益固定晴朗/高温/沙暴消耗3/5/8份水和食物同标准消耗这里的消耗数字并不是当年官方赛题的标准值只是我用来说明建模思路的示例。实际比赛时要把官方给的消耗表、收益表原样代入模型。有一点需要注意不同版本的赛题可能在关卡设定上有差异有的关卡把路线分成多段有的关卡把天气概率给了不同的分布所以建模前一定要逐字读题把参数抽出来列成一张表这是后面所有工作的地基。1.2 题目真正想考的能力从出题者的角度看这道题想考查的不是“你会不会贪心”而是四个方面。第一多阶段决策建模能力。玩家每天都要面对“移动/停留/挖矿/购买”的离散决策每个决策都会影响后续所有天的可行性和收益。这不是一道静态题而是一道典型的序贯决策问题。第二约束处理能力。负重、时间、天气、资源耗尽任何一个约束都能让朴素贪心算法直接崩掉。第三不确定性建模能力。第二问把天气从“全知”改成“部分未知”这就从确定性优化跳到了随机决策的范畴。很多队伍在这里掉队因为他们还是拿第一问的思路硬套。第四工程实现与验证能力。模型再漂亮最后都得跑出数字。对动态规划、最短路、蒙特卡洛模拟这些算法的实现细节决定了你能不能在规定时间内交出一份可复现的结果。把这四点想清楚之后再去看各类参赛作品就会发现优秀论文和普通论文的分水岭不在算法炫不炫而在对规则的建模颗粒度和对求解思路的取舍逻辑。比如同样是用动态规划有的队伍把状态定义得又大又散跑都跑不动有的队伍做了状态压缩几秒钟就出结果。这两支队伍在论文里写出来的模型公式可能长得差不多但背后的思考深度完全不一样。2. 第一问确定性天气下用动态规划还是最短路2.1 状态定义是建模的第一步第一问的核心特征是未来所有天的天气已知。也就是说玩家在做任何决策之前整个“环境”是一个完全确定的信息集。这时候问题变成一个确定性、有限阶段的离散优化问题最常见的做法是动态规划。但动态规划第一步——状态定义就卡住了很多人。如果直接定义状态为“第t天、位置i、剩余水w、剩余食物f、剩余资金m”那么这个状态空间是五维的w和f的取值范围还可能达到几百上千组合起来根本没法枚举。所以要做状态压缩。压缩的思路是把“剩余资金”变成由其他状态推导出来的值。因为在规则里资金只通过购买和挖矿两个动作变化而水、食物是实际消耗品。只要记录“当前还剩多少水、多少食物、多少物资总重量”再结合历史路径就能算出资金的使用情况。更进一步的压缩思路是对每个位置、每一天直接定义“到达该节点时剩余资金最大”作为DP值。由于路径和天气确定从上一个节点转移到下一个节点时消耗是确定的所以只需要决策“是否挖矿、是否购买、是否等待”。这个思路有点类似“从终点倒推”的逆推动态规划从最后一天往前递归每一步都保留当前最优资金最后起点处的值就是答案。这里有一个我当年踩过的坑把“剩余水”和“剩余食物”当作两个独立维度放进状态结果状态爆炸程序跑了一个小时都没出结果。后来改成“只保留水和食物的总重量”作为状态再通过贪心策略分配水和食物的携带比例计算量直接降了一个数量级。原因在于水和食物在功能上高度相似而决策时真正约束携带量的是总负重而不是各自的剩余量。但要注意这个压缩思路在“水和食物价格相同、消耗比例固定”的简化条件下才成立。如果赛题把水和食物的基础消耗比例设得完全不同比如水消耗快、食物消耗慢就需要在压缩时额外加一个维度记录当前策略下水和食物的比例是否偏离最优比例否则压缩就会失真。2.2 把每天消耗转成边权把问题看成图论最短路也行而且这是一个很优雅的转化。思路是每个节点表示为“第t天在位置i”。如果第t1天天气允许移动就建一条边从(第t天,位置i)指向(第t1天,位置i1)边的代价是当天的水、食物消耗。如果玩家选择在某个位置停留就建一条自环边消耗当天水、食物。如果玩家在矿山停留并挖矿消耗翻倍但获得固定收益。如果玩家在村庄或起点可以在节点上做“购买”操作相当于在水、食物消耗的代价基础上加一笔价格调整。这样整理出来的图边的权重是“资金”而不是“距离”。因为天气已知每个节点的消耗都能精确计算所以从起点到终点的最短路对应的就是最优决策。但是千万不要直接用任意图最短路模板去跑。这个转化后的图里节点之间的边权并不是独立的它们共享同一个负重限制。换句话说即使最短路算法告诉你“这条路总代价最低”也还要检查这条路径上的物资总重量有没有超出负重上限。否则算法会给你一条理论上资金最优、实际上根本不可行的路径。正确的做法是在DP中把负重上限当作约束条件或者在构建图时把“携带的物资总量”作为路径上的累计状态再做约束检查。我个人更推荐前者因为动态规划天然支持维度扩展而图算法扩展状态维度会比较别扭。还有一个折中的办法是先不管负重上限跑一遍最短路得到一张“最优路径表”再逐段检查负重。如果超了就把超重那几段的物资购买方案拆开看看能不能通过提前购买、分批携带来绕开限制。这个方法虽然不一定能找到全局最优但作为初筛非常快。2.3 边界情况与失败判定第一问的陷阱往往藏在边界条件里不是算法本身。初始阶段资金有限如果起点就把物资买满可能后续资金不够在村庄应急。沙暴天无法移动如果恰好卡在离村庄或矿山很远的位置连续几天沙暴会直接耗尽物资。挖矿虽然赚钱但收益是否覆盖额外消耗需要提前用“收益/额外消耗”的比值判断。我见过不少队伍在论文里把“失败判定”写得很模糊什么“物资耗尽则游戏失败”但代码里却没有严格检查每个中间状态的可行性。评委最喜欢在这种地方扣分。建议在建模时把“水0或食物0”作为硬约束写进递推公式并在数值实验时给出失败路径的示例让读者直观看到边界条件的意义。实际操作中还有一种隐蔽的失败情况是“到达终点但超时”。有些队伍在DP里没有限制至少要在第几天之前到达只在最后输出终点的最优值结果程序为了多挖几天矿选择了超时到达的路径。为了避免这种情况我把“天数”直接放在状态里并且只记录“恰好第t天到达位置i”的最优值这样天然排除了所有超时路径。这个小细节看起来不起眼但能帮你避免一个很尴尬的结果错误。3. 第二问天气未知时从“最优”到“稳健”3.1 决策树与期望收益第二问把天气改成了“前若干天已知后续未知”。这意味着第一问的确定性DP不能直接用了。但好消息是天气虽然是随机的它的取值是有限的晴朗、高温、沙暴三种而且概率分布题目会给出。于是可以把问题建模成决策树树的每一层代表一天树的每个分支代表一种可能的天气状态。在决策树上做“期望资金最大化”思路和第一问的DP一致只是转移函数改为求期望。如果设V(t, i, s)为“第t天在位置i、当前物资状态为s时的最大期望剩余资金”那么转移时对每个可能的天气计算对应的消耗和决策后的资金再按概率加权求和。这个求解框架虽然简单但有一个隐藏问题如果直接在完整决策树上展开30天、每天3种天气会得到3的30次方个叶子节点这显然是不可行的。所以实际要做的是“剪枝”和“近似”。常用做法是在每个决策点只保留有限个候选动作再用蒙特卡洛抽样去评价这些动作的期望收益而不是枚举所有天气组合。我整理过的作品里有队伍用“随机动态规划”来求解状态转移方程写得很漂亮但运行时间极长。后来他们做了一个简化因为每种天气出现的概率是独立的未来10天的天气组合虽然很多但很多组合对应的消耗是一样的比如3个晴天、2个高温、5个沙暴和2个晴天、4个高温、4个沙暴如果只关心总消耗这两组天气的累计效果可能相同。这就能用“合并同类项”的思路大幅压缩状态。这个技巧在第二问里特别适用因为玩家关心的往往不是某一天具体是什么天气而是接下来若干天累计消耗了多少物资。3.2 稳健策略与后悔值分析第二问里很多优秀作品并没有直接追求“期望资金最大”而是引入了风险厌恶用“最大化最坏情况下的收益”或者“最小化最大后悔值”来建模。原因很实际期望最大化的策略可能在某些极端天气下直接失败比如为了多挖几天矿赌后续不会连续沙暴结果一旦连沙暴就资源耗尽。竞赛题目想要看到的是你能不能在不确定性下做出合理决策而不只是算一个期望值。最小最大后悔值的思路是先假设我们知道真实天气序列算出每个天气序列下的“事后最优收益”然后定义“后悔值”为当前策略收益与事后最优收益之差最后选择一个让最大后悔值最小的策略。这个思路在论文里写出来会非常加分因为它体现了你没有把随机性简单地平均化而是考虑了决策的稳健性。评委看到这部分通常会给较高的模型创新分。举一个很直观的例子假设两种策略A策略在90%的情况下收益是500在10%的情况下失败B策略在任何天气下收益都是400。期望收益算下来A更高但如果你把这个游戏重复玩一百次B策略永远不会失败而A策略有十次会直接出局。对于一次性的比赛你愿意赌A还是保B这个选择没有标准答案但你能不能在论文里把两种选择的利弊讲清楚就体现出建模思维成熟度了。3.3 蒙特卡洛模拟评估第二问里蒙特卡洛模拟不应该作为求解主算法而是作为验证工具。做法是按照题目给出的天气概率分布随机生成大量天气序列几千到几万条然后用第一问开发的确定性DP来求解每条天气序列下的最优策略得到收益分布。再把你设计的稳健策略在这些天气序列上跑一遍对比收益分布。这里有一个关键点模拟得到的收益分布直方图非常好用。第一可以直观展示某个策略在大多数情况下收益高不高第二能看出策略是否有“尾部风险”即在极端天气下是否容易翻车。论文里放一张收益直方图比十段文字都管用。我在整理作品时发现凡是拿到高分的队伍几乎都做了某种形式的蒙特卡洛验证。有的队伍还额外做了“在预测天气存在误差时策略的表现”分析这个属于加分项因为他们主动处理了模型对输入误差的敏感性。做蒙特卡洛模拟时一个常见的坑是随机数种子没有固定。结果每次运行程序得到的收益分布都不一样论文里写的数字和代码实际跑出来的数字对不上这在答辩时是致命的。我建议在代码里固定随机种子并且在论文的附录里写清楚“随机种子为2020抽样次数为1000095%置信区间为XXX到XXX”这样整个结果可复现、可验证也能体现你做实验的严谨性。4. 参赛作品的完整组织框架从摘要到灵敏度分析4.1 从摘要到灵敏度分析的布局整理了大量参赛作品之后我发现优秀论文的结构惊人地一致不是因为他们抄袭而是因为数学建模竞赛的评分维度非常稳定。通常一篇完整作品包含摘要、问题分析、模型假设、模型建立与求解、灵敏度分析、模型评价与推广这几大块。摘要300到500字直接决定评委的第一印象。高手会在这段里写清楚“问题是什么、我用了什么模型、得到什么结果”而且会写具体数字比如“在天气全知条件下最优资金为8400元瓶颈约束来自连续沙暴天气下物资储备不足”。避免写“我们采用动态规划求得了较好的结果”这种废话。问题分析部分用自然语言梳理决策链路画出问题拆解图或决策流程图这一步是为了让评委相信你真的理解规则。模型假设把赛题里没有明说但建模时默认的细节列出来比如“忽略购买物资时的时间成本”“水、食物可无限细分”等。模型建立与求解部分按问题拆成小节每个小节给出数学模型、递推公式、算法流程、运行结果。灵敏度分析是变化关键参数如初始资金、天气概率、物资价格观察结果变化。很多队伍把这一节写得像应付差事其实这是拉开分差的地方。模型评价与推广部分简单写优缺点的同时要说明模型思路可以迁移到哪些场景比如库存管理、物流调度、生产排程。4.2 评委视角下的常见丢分点第二问部分已知天气这种题目最容易出现“把随机问题当确定性问题做”的错误。很多队伍在第二问里直接沿用第一问的DP只在前若干天用已知天气后续天气就随便挑一种“最可能”的天气去跑。这种做法理论上不严谨评委一眼就能看出来。还有几个常见丢分点。模型假设过多把赛题核心矛盾假设没了比如假设“沙暴天气不会出现”或者“挖矿收益大于一切”这样后续模型再精巧也没意义。把算法实现了但缺少数学表达式评委需要看到具体的递推公式、约束条件表达式而不是只看到“用Python实现动态规划”一句话。结果没有解释写出“资金为8400”还不够要解释为什么是这个数比如“资金主要消耗在最后三天的连续高温天气”。灵敏度分析是空的只画图不加解释画完参数变化图后至少要说清楚“初始资金每降低100元最优收益下降多少原因是购买物资的边际成本上升”。我翻过的几十份作品里还有一个很普遍的毛病论文里贴了大段源代码。评委根本不会看你的代码他们要的是思路和结果。代码可以放附录但正文只放关键公式、核心算法伪代码和结果图。做这个调整之后论文的观感会提升不少。另外排版规范也是隐性分数公式编号、图表标题、参考文献格式统一这些细节做不好再好的内容也会被打折扣。5. 代码实现与复现从公式到可运行结果5.1 动态规划的Python实现思路写代码之前先定数据结构。我建议定义三个核心数据结构天气表、位置属性和状态记录。天气表是长度为总天数的一维数组位置属性是一个字典key是位置编号value说明这个位置是起点、终点、村庄、矿山还是普通地点状态记录则用多维数组或字典记录(day, pos, water, food, money)或者压缩后的状态。一个典型的确定性DP伪代码如下# 示例伪代码具体参数以官方赛题为准 days len(weather) # dp[t][i][carry] 表示第t天在位置i携带总重量为carry时最大剩余资金 dp [[[-inf] * (MAX_CAPACITY 1) for _ in range(N)] for _ in range(days 1)] dp[0][start][init_weight] init_money for t in range(days): for i in range(N): for carry in range(MAX_CAPACITY 1): if dp[t][i][carry] -inf: continue w_use, f_use consume_by_weather[weather[t]] # 决策1: 移动到下一个位置天气允许时 # 决策2: 停留在当前地点 # 决策3: 挖矿如果在矿山 # 决策4: 购买物资如果在村庄或起点注意这段伪代码里“购买”应该放在转移之后还是之前取决于你对“当天消费顺序”的定义。现实模型中玩家可以在一开始就购买也可以到达村庄当天购买再消费。不同的时序假设会带来不同的结果所以你要在模型假设里明确写清楚。我习惯上把“消费”放在每天的最后也就是先决策移动或挖矿再扣除当天消耗最后才允许购买补给。这样模拟的是“白天赶路或干活一天结束后再补货”的场景。5.2 参数标定与结果验证跑通代码之后不要急着写论文。第一件事是做小规模测试手动构造一个两三天的小沙漠手算最优解再和程序跑出来的结果对比。这样能快速发现时序错误、边界条件错误。我当年测试时发现代码里最常见的bug是“沙暴天仍然允许移动”和“购买后负重超限”这两个条件没有同时检查。这两个bug同时存在时程序会给出一个看似合理但实际不可行的最优策略。你如果不做小规模手动验证这种错误会一直藏到交卷。还有一种情况要特别注意程序求出的“最优路径”里可能会出现走到某个节点时剩余物资刚刚好够走到终点但完全没有预留应对意外天气的余量。在确定性第一问里这没问题因为天气已知不会有意外的沙暴但在第二问里如果还沿用这种“卡着边界走”的策略一旦实际天气和预测概率分布有偏差就很容易翻车。所以做第二问的策略时我建议在代码里人为设置一个“安全库存”比如始终保留至少一天的物资作为缓冲这样虽然期望收益会略微下降但大大降低了失败概率。5.3 可视化与结果呈现论文里放图不要放代码截图。最有用的图有三类最优路径图、资源消耗曲线、天气与决策对齐图。最优路径图是在地图上标出玩家每天的位置和动作颜色区分移动、停留、挖矿。资源消耗曲线画出每天结束时水、食物、资金的变化曲线直观展示资源是否逼近耗尽边界。天气与决策对齐图把天气条和决策条按天对齐显示哪几天因为沙暴被迫停留哪几天因为高温消耗激增。这类图不用画得多花哨用matplotlib画清楚就行。关键是让评委一眼看懂你的策略在关键节点上的取舍。我见过一个作品把“资金曲线”和“物资总量曲线”画在同一张图里并用阴影标出“可安全返回村庄的最晚时间”这个设计非常加分因为它把决策的“死线”可视化了出来。后来我自己做类似的调度问题时也沿用这个画法效果很好。画图的配色和字体也要统一避免出现花里胡哨的颜色毕竟这是学术论文不是海报设计。6. 从穿越沙漠沉淀出的通用建模能力6.1 一套可复用的资源-路径-随机三层框架比赛结束后回头再看这道题会发现它其实是一个通用问题框架的实例。底层是资源层水、食物、资金分别对应库存、消耗品、货币。中层是路径层移动、停留、挖矿、购买对应路径选择、加工、采购。上层是决策层确定性天气和随机天气对应确定性环境和随机环境下的序贯决策。把这三层拆开之后你会发现很多实际场景都能套进这个框架。外卖骑手的送餐路线规划要考虑时间、电量、订单收入“三坐标”平衡工厂的生产排程要处理原料库存、加工时间、机器产能的匹配仓储物流的补货策略要解决库存水位、需求随机、运输成本之间的冲突。这些问题的底层结构都和你在这道题里遇到的“水、食物、资金、天气、时间、负重”非常相似。所以打比赛的价值不只是学一个算法而是学会“把现实问题抽象成可求解的数学模型”。在整理合集的过程中我看到一支队伍用“库存-生产-销售”模型来类比穿越沙漠水、食物是原材料移动是生产过程挖矿是增值加工村庄是补货点终点是交付客户。这个类比看起来简单却能帮助队友快速对齐思路也方便后续把成熟的库存管理模型迁移过来。这也是我建议大家拿到新题以后先做的一件事用自己熟悉的领域去重新描述题目找到问题的“骨架”。6.2 对备赛选手的几点建议最后聊一点更实在的备赛建议。第一前三天不要急着写代码先把题目读三遍把所有规则写成一二三四条再开始建模。第二代码和论文要并行推进不要等模型完全跑通再写论文因为论文里的问题分析部分完全可以提前写。第三重要参数一定要做多组对比一组参数跑出结果就写进论文评委一眼就能看出你没有做系统分析。另外我想分享一个个人感受整理优秀作品集的时候你会发现那些拿国奖的队伍论文里的关键结果几乎都能复现而不是“比赛当天随手跑的运气产物”。他们把每一步推导都写清楚每个数字都能对上每个参数都是有意选择的这种严谨习惯比临时抱佛脚学某个高级算法有用得多。这道“穿越沙漠”看起来是个游戏题但把它的所有决策逻辑串起来之后你锻炼出的恰好是真实世界里的资源配置能力。这几年数学建模竞赛的题目越来越偏向规则复杂、数据量大、环境不确定的真实场景题穿越沙漠B题算是这种趋势的早期代表。如果你能把这道题的原理吃透再去做类似的任务调度、资源优化题目会顺畅很多。本文还有配套的精品资源点击获取
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
