简介2020年全国大学生数学建模竞赛B题“穿越沙漠”的全国赛二等奖完整代码包面向备战建模竞赛的学生、算法爱好者及相关课程实践者。压缩包共54个文件以45个MATLAB脚本、8个MAT数据文件与1个Excel结果表为主体整体仅36KB体积虽小却覆盖了从建模、求解到结果输出的完整链路。代码按第一关到第六关分层组织每一关都区分不同情形与最优方案模块包含最短路径搜索、距离矩阵构建、资源消耗核算、关卡排名评估等便于按需调用和二次开发。已有29428人浏览学习该资源。对想深入理解图论和最优化方法如何解决实际赛题、以及如何把复杂问题逐步拆解为可执行代码的读者这套获奖代码提供了从数据输入、中间计算到最终决策的全过程参考兼具学术价值与工程参考意义适合参赛复盘、算法演练与课程设计复用。1. 2020年数学建模B题穿越沙漠的二等奖代码它是什么、谁能用、值不值得解压在数学建模竞赛圈子里2020年数学建模B题穿越沙漠全部代码全国赛二等奖.rar这串文件名并不陌生国赛B题“穿越沙漠”的一份完整提交代码署名团队拿了全国二等奖压缩包被反复转存。但多数人解压后会失望——里面不是一份能一键复现的成品而是一支队伍解决这道题的完整工程痕迹建模思路、代码、跑数脚本、图表和论文内容。它适合两类人一是备赛队伍想研究获奖团队如何把一道运筹优化题拆成可执行代码二是想借真实场景练手的状态搜索和路径规划学习者。我的建议是别把它当答案背把它当一份别人踩过坑的施工图。下面我以复现这类题目的经验按“建模—最小可跑代码—冲奖—避坑”的顺序带你看懂这套代码背后要解决什么问题。2. 把“穿越沙漠”翻译成算法能听懂的语言状态机、有向图与三类约束B题“穿越沙漠”在运筹学里属于带资源约束的路径规划但它比课本例题苛刻每一次决策同时被天气、物资、时间三组因素夹击。晴天每天耗水 3 单位、食物 3 单位高温天水消耗可能涨到 9沙暴日不能移动但物资照常消耗。如果只把路径当作主线到第二关遇到“矿区—村庄—终点”的多趟往返就会发现传统最短路根本表达不了“我为了挖矿愿意多耗三天”这种权衡。所以建模的第一件事是定状态机某天站在哪个节点、手里多少水、多少食物然后才在有向图上做搜索最后把矿区收益、村庄补给折算成决策收益。很多队伍一上来就写 Dijkstra 或 A*跳过了状态建模直接套图算法这是最典型的起手错误。图算法只能回答“哪条路最短”回答不了“哪条路在物资约束下既可行又最优”。2.1 为什么这道题不是最短路资源消耗让路径与背包绑定把 B 题压缩成一句话就是“带背包容量的时空路径选择”。地图的边权是走过这段路需要的天数但真正的成本不是天数而是这些天里水、食物消耗了多少。一个反直觉的结论高温日密集的天气序列里一条多绕两天但避开高温节点的路线往往比最短路线更优因为节省下的水能让你多背几天物资或者多挖几天矿。第一关和第二关的建模目标差异很大我习惯先列一张对比表再动手写代码对比维度第一关第二关目标到达终点时剩余资源最大总收益最大挖矿收益减去补给支出决策变量每天是否移动、走哪条边每天移动、停留、挖矿、购买天气处理已知确定性序列已知序列但需留安全余量常用解法动态规划、记忆化搜索线性规划、停留收益二分、蒙特卡洛这张表决定了代码结构第一关只要把搜索写好就行第二关必须引入“收益”维度代码复杂度完全不在一个量级。2.2 用邻接表建沙漠地图节点、边权与天气规则的代码原型拿到题目第一步是把地图抽象成有向图。节点是地图上的格点边权是从一个节点走到另一个节点消耗的天数。很多人直接用二维矩阵存地图但搜索阶段邻接表更好扩展尤其是第二关要动态加入矿区与村庄之间的往返边。# desert 邻接表节点编号沿用题目地图这里只给结构示例 desert { 1: {2: 1, 6: 1}, # 从节点1走一天可达节点2或6 2: {1: 1, 3: 1, 7: 1}, 6: {1: 1, 7: 1, 11: 1}, 7: {2: 1, 6: 1, 8: 1, 12: 1}, # 节点12通常指向矿区方向 # 其余节点按题目地图补全 } # 天气序列先给一组确定值让代码能跑通 weather [sunny, hot, sand, sunny, sunny, hot, sand, sunny, sunny, hot] # 每天消耗规则单位是“单位/天” consume { sunny: {water: 3, food: 3}, hot: {water: 9, food: 3}, sand: {water: 3, food: 3}, # 沙暴日不能移动但物资照扣 }逻辑说明weather列表的下标就是第几天搜索时按day索引去查当天天气。consume定义三档消耗沙暴天是“不能移动但消耗照常”这是题目里最容易写错的地方。参数说明水、食物的单位必须统一建议从最开始就用“单位”计量把单价换算留到第二关再做否则后面做负重上限时会莫名其妙差一倍。2.3 状态压缩用 (day, node, water, food) 把搜索空间限制住直接裸搜的状态是“第几天、人在哪、水多少、食物多少”四维乘积非常大。一个常用的技巧是只保留(day, node, water, food)作为记忆化键把“现金收益”放到目标函数里而不是状态里。原因是现金不会影响后续移动能力只有水和食物影响生存。from functools import lru_cache lru_cache(maxsizeNone) def dfs(day, node, water, food): 从 (day, node, water, food) 出发能到达终点的最大剩余资源 # 终止条件和剪枝写在这里下一章给完整代码 pass这里还应该加一条支配规则同一个状态下如果水、食物都不少于另一个状态后者在整个搜索树里都不可能超过前者可以剪掉。这条规则听起来简单在第二关的挖矿循环里却能让状态量缩到原来的十分之一属于性价比最高的剪枝。提示先用确定性天气写搜索再用随机天气加蒙特卡洛验证不要一上来就写随机模型。随机模型的问题出问题时你根本分不清是算法错还是抽样错。3. 先跑通最小可运行版确定性天气下的记忆化搜索代码只建模不写代码等于纸上谈兵。这一章给一个可运行的最小方案解决第一关给定天气序列求出从起点到终点的行动策略让到达终点时剩余资源最大。这段代码刻意压缩成单文件新手能直接跑老手可以按这个结构改成第二关。3.1 动作生成器怎么写移动与停留的合法性检查动作生成器是搜索的交通规则每天只能选择停在原地或者移动到相邻节点移动需要支付跨天数的天气消耗。这里有一个关键约束移动跨多天时逐日结算资源不能只看出发日的天气。def generate_actions(day, node, water, food): 返回所有可行动作(stay,) 或 (move, next_node, cost_days) actions [(stay,)] # 停留永远是合法动作 if weather[day] ! sand: # 沙暴日不能移动 for nxt, cost in desert[node].items(): actions.append((move, nxt, cost)) return actions逻辑说明停留分支不受沙暴限制因为沙暴日只是不能走不是不能待。移动分支要先判断出发日天气但真正的资源扣减要在下一步逐日计算不能只看weather[day]。参数说明cost是边权表示从当前节点到邻接节点需要经过的天数跨天移动时每一天的天气都要逐一处理。3.2 记忆化DFS核心代码剪枝条件与支配规则把动作生成器接进搜索函数加上终止条件和资源扣减就是第一关的完整解法from functools import lru_cache lru_cache(maxsizeNone) def dfs(day, node, water, food): # 到达终点直接返回剩余物资 if node end: return water food # 超出时间窗口判负 if day len(weather): return -float(inf) # 扣掉今天的基础消耗 w consume[weather[day]][water] f consume[weather[day]][food] water - w food - f if water 0 or food 0: return -float(inf) best -float(inf) # 决策1原地停留 best max(best, dfs(day 1, node, water, food)) # 决策2走向相邻节点沙暴日不能走 if weather[day] ! sand: for nxt, cost in desert[node].items(): w2, f2 water, food ok True for k in range(cost): w2 - consume[weather[day k]][water] f2 - consume[weather[day k]][food] if w2 0 or f2 0: ok False break if ok: best max(best, dfs(day cost, nxt, w2, f2)) return best # 调用起点为 1初始水、食物各 300天气序列见 2.2 print(dfs(0, 1, 300, 300))逻辑说明代码用lru_cache做了状态记忆化同一天站在同一节点、水食物也相同的状态不会重复搜索。移动跨多天的循环里逐日扣水扣食物一旦出现负值就放弃该分支。-float(inf)表示此状态不可行保证max比较不会被错误分支干扰。参数说明dfs的四个参数就是上一章说的状态四元组调用时的300, 300是初始水和食物实战里要根据题目给的载重上限来定。3.3 三个必须调参数载重上限、基础消耗、沙暴日资源规则第一版跑通后三个参数最容易让你翻车。第一个是载重上限。题目会给负重上限水和食物共用这个上限。我建议把载重设成常量在动作生成器里加检查避免装得下但走不动的尴尬。MAX_LOAD 1000 # 水和食物共用载重单位同 consume第二个是基础消耗。三档天气值必须和题目表对齐晴天、高温、沙暴的水和食物消耗分别是多少。有的代码把高温水消耗写成 6 而不是 9整棵搜索树的排序就全变了结果自然不对。第三个是沙暴日规则。沙暴天能不能原地停留是隐含条件——能停但物资照扣。如果你写成沙暴天不能停留状态空间直接少了一半到第二关几乎无解。注意搜索代码里所有单位必须一致水和食物分别用什么计量单位、载重的单位是什么这三者互相换算关系要写清楚。我见过最离谱的翻车是水和食物分别按“箱”和“单位”计载重却是按“公斤”三个单位混在一起最优解全乱。4. 从“能跑”到“冲奖”第二关挖矿—补给模型与随机天气的蒙特卡洛补全第二关开始目标切换成“总收益最大”。在矿区挖矿带来收益在村庄买水买食物要花钱你需要在两者之间反复往返这时问题变成了“停留几天、带多少物资折返”的最优控制。如果还用第一关的 DFS 硬搜状态空间会迅速爆炸因为收益也变成了状态的一部分。4.1 第二关的真正难点在矿山和村庄之间循环的“停留收益”第二关的路线通常不是起点到终点的一条直线而是起点—矿山—村庄—起点这样的多趟往返。矿山是现金产出节点村庄是补给消耗节点一次往返的收益等于矿山停留天数的现金产出减去往返路上消耗物资的购置费。于是问题变成总天数有限如何在“挖矿—回村补给—再挖矿—最后出沙漠”之间分配天数。这个问题的难点在于矿点停留天数不是简单枚举就能求到最优的。如果时间窗是 30 天矿山待 10 天和待 11 天之间的收益差异可能很微妙两个解之间夹着一个假最优让你把次优方案写进论文。我常用的做法是把“收益函数”拆成“往返次数”和“单次带水量”两个变量先手算几组候选再用线性规划或二分确定最优停留天数。4.2 用线性规划做整体寻优pulp建模与约束清单停留天数多、往返次数多时手算效率太低。把每天的挖矿、购买、移动建模成 0/1 变量用线性规划做整体寻优是更省事的方式。import pulp prob pulp.LpProblem(desert_mine_opt, pulp.LpMaximize) day_count 30 mine_income_day 200 # 矿山每天收益按题目给的实际值填写 water_price 5 # 村庄水价元/单位 food_price 10 # 村庄食物价元/单位 # 0/1 变量第 i 天是否挖矿、是否购买、是否移动 x_mine pulp.LpVariable.dicts(mine, range(day_count), catBinary) x_buy pulp.LpVariable.dicts(buy, range(day_count), catBinary) x_move pulp.LpVariable.dicts(move, range(day_count), catBinary) # 目标挖矿收益 - 购买支出 prob pulp.lpSum(x_mine[i] * mine_income_day for i in range(day_count)) - \ pulp.lpSum(x_buy[i] * (water_price food_price) for i in range(day_count)) # 每天只能做一个动作 for i in range(day_count): prob x_mine[i] x_buy[i] x_move[i] 1 # 资源动态约束在这里用简化线性演示 # 严格求解时要写成逐天等式 # water[i] water[i-1] - consume[i] buy_amount[i] prob.solve() print(pulp.value(prob.objective))逻辑说明pulp 把每天拆成三个互斥动作目标函数是现金收入减购买支出。这段代码是示意级——真正提交时还要把天气序列逐日写进约束、把负重上限写成不等式。参数说明mine_income_day、water_price、food_price都来自题目数据单独放在代码前几行定义是获奖代码的常见习惯调参时不用满文件找魔数。4.3 随机天气下怎么补确定性最优 蒙特卡洛扰动如果题目给的是天气概率分布而不是固定序列确定性搜索的结果会偏乐观。最常用的补稳手段是先搜索得到一个动作序列再随机生成大量天气样本跑一遍统计期望收益。这个方法在比赛里往往成为判断策略优劣的分水岭。import random def evaluate(plan, sample_count2000): plan 是 (day, action) 动作序列weather_samples 是自己抽的天气样本 total 0 for _ in range(sample_count): weather_seq [random.choice([sunny, hot, sand]) for _ in range(30)] total simulate_with_weather(plan, weather_seq) # simulate_with_weather 是你自己的策略封装 return total / sample_count逻辑说明plan是搜索阶段输出的动作序列simulate_with_weather是自定义的模拟函数把动作序列放到一组随机天气下重跑返回该序列的收益值。sample_count越大期望收益越稳定一般 2000 次足够看出策略差异。比赛论文里放一张“不同策略在 2000 次模拟下的收益分布箱线图”说服力远大于一句“该策略最优”。5. 避坑穿越沙漠代码里最容易翻车的五个位置下面五条来自我两轮做 B 题的调试笔记也浓缩了近几年的常见问题。每条按“现象—原因—解决”三步写你可以在自己的代码里直接对照排查。5.1 翻车位置一状态记录用可变类型缓存永远不命中现象DFS 在第二关跑得极慢甚至几分钟不出结果但代码逻辑看起来没问题。原因把water和food作为 list 传入dfs而lru_cache对 list 无法哈希缓存永远不会命中等于每次都重新搜索整棵树。解决把资源改成整数或 tuple 传入。如果数据必须用 list在函数入口先转成 tuple。这一处修改常能让第二关搜索提速几十倍。5.2 翻车位置二矿石重量未计入负重现象代码输出“最佳策略是反复挖矿 30 天”收益高得离谱但仔细一算返程背着几千单位矿石远超负重上限。原因把现金当成唯一约束忽略了矿石本身要占载重。矿石挖出来不是凭空消失要运到终点才有收益。解决在挖矿分支里加一行if load ore_weight MAX_LOAD: continue同时把负重上限设成容差参数而不是硬编码。5.3 翻车位置三沙暴日“原地停留”被写成“不能停留”现象代码一进入第二关就频繁报无解把天气序列里的沙暴日删掉却能跑出结果。原因沙暴日只是不允许移动不是不允许停留但很多代码在动作生成器里把沙暴日整体禁掉了漏掉了一大类可行解。解决动作生成器里用if weather[day] ! sand控制移动分支不控制停留分支。停留永远合法只是要正常扣资源。5.4 翻车位置四载重上限和初始资源写死在代码里换数据就炸现象代码在自造的样例上跑得很好换成官方数据后一上来就“超重”或“缺水”。原因把MAX_LOAD、start_water这类参数在代码里多处写死换题目数据时只改了一处另一处漏改。解决把所有物理参数集中到一个CONFIG {...}字典搜索内部一律用CONFIG[max_load]引用。每次跑新数据只改 CONFIG不碰函数主体。5.5 翻车位置五把第一关的“最小消耗”目标搬到第二关现象程序输出一条正常路线但算总收益时始终比参考答案少一截。原因第一关是消耗最小化第二关是净收益最大化净收益等于挖矿收益减去购买支出消耗量本身不是钱。第一关的最优路线不代表第二关的现金收益最大。解决第二关的目标函数改成分段评估先算挖矿收益再算购买支出再减回程剩余物资价值。用线性规划时确保目标函数系数不要混用“消耗量”和“货币量”。提示第二关的购买支出要和挖矿收益使用同一套货币单位这听起来是废话但把“消耗单位”直接乘价格、再把“收益”减进去就会差一个数量级。6. 代码跑通之后验证、可视化和参数锐化才是二等奖和一等奖的分水岭搜索能出结果只是开始评委判断一个方案是否可信看的是验证过程是否扎实。我每次跑完一组策略第一件事不是看收益数字而是导出“行动日志”每天在哪个节点、水食物剩多少、现金变化多少逐行核对前三天和后三天的物理逻辑。有一次我在这上面吃过亏调参数调了一个下午觉得收益比之前高了 20%结果导出日志发现第七天开始水是负的还能继续走因为我把终止条件的判断写在了动作生成器之后。所以我现在固定先跑确定性天气人工核对三天日志再进随机验证。第二步是可视化。用 Matplotlib 把路径画在地图上节点和边标注天数、剩余物资再用颜色区分沙暴日。这张图既帮自己发现路径重叠也是论文里最有说服力的结果图。第三步是参数锐化把载重上限、初始物资、消耗系数分别做单因素扫描画出收益随参数变化的曲线。这项工作能证明你的方案不是碰运气而是有稳定边界。另外如果代码里用了线性规划建议把pulp.LpStatus[prob.status]打印出来确认是Optimal而不是Infeasible。最后一句经验是比赛代码不要追求一次成型先跑通最小版本再逐步加复杂度每加一个模块就重新验证一次。这样做出来的代码哪怕最后没拿到国奖也能清楚讲出每一步为什么这么设计。希望这些踩坑和验证习惯帮到你。本文还有配套的精品资源点击获取