2020数学建模B题沙漠穿越：Matlab动态规划与剪枝实战解析-北京尧图网络

简介面向备战2020年数学建模B题的参赛者完整Matlab源代码覆盖四关求解流程从第一关基础路径规划到第四关随机天气下的最优策略涉及距离矩阵处理、单目标优化、动态规划、数学期望与随机分布建模等方法。第二关重点解决双地图与双村庄下的矿山选择和物资补给问题第三、四关则针对仅知当天天气的情况用历史概率预测未知天气并比较期望与随机分布两种建模的优劣赛题思路与代码实现对应清晰。压缩包共含一百一十四个文件其中九十三个m主程序文件用于各关核心计算十五个mat数据文件保存地图与参数数据另有五个asv备份文件及一个xlsx结果表格整体仅六十六KB便于快速下载。已有一千二百三十九人学习浏览适合需要在实战代码中理解优化建模与编程的数学建模爱好者。1. 2020年数学建模B题别急着找源代码先搞懂它考什么2020年数学建模B题的核心场景是沙漠穿越当年很多人一看到题目就上头一张地图、一份天气表玩家要在规定天数内从起点到终点每天选择行走、挖矿或休息水和食物按天气消耗负重有上限村庄能买补给矿山能赚钱最后手里的现金越多越好。这道题表面是游戏策略实际是多阶段资源调度问题。很多同学一上来就搜Matlab源代码下载一堆脚本却跑不出合理结果因为代码好搬约束条件却藏在题目细节里少写一条就全盘翻车。这篇文章从建模思路、最小Matlab实现、剪枝加速到避坑清单给你一条能落地的路径适合准备数模竞赛的学生、想练Matlab优化建模的开发者以及想把策略优化问题写清楚的技术爱好者。2. 把B题拆成状态、决策与目标Matlab建模前的三个选择拿到题先别急着写代码先回答三个问题状态怎么定义、决策怎么枚举、目标函数怎么算。这一章讲清楚这三件事后面写代码才不会返工。2.1 状态空间怎么压缩你不需要记录所有历史沙漠穿越问题里玩家一天的流程是先看天气再决定行动然后扣水和食物检查负重和生存条件。如果走到村庄可以选择买水买食物如果走到矿山挖矿的收益比休息高但消耗也更大。一个最直观的状态是五元组当前天数、当前地点、剩余水、剩余食物、剩余现金。这个状态是“马尔可夫”的只要这五个值确定后续最优决策就不依赖之前走过哪些路。但坏消息是状态空间巨大。假设水有100档、食物有100档、地点有10个、天数30天直接存五元组就是300万维。如果再把每个维度细分到个位数内存直接爆掉。常见做法是分层外层决策路线也就是经过哪些村庄和矿山、哪天到达内层决策每天行动比如在矿山挖几天、在村庄休整几天。路线数量是有限的可用搜索枚举日常行动用贪心或动态规划处理。状态从五元组压缩成“当前路线当前剩余资源”内存一下子小两个数量级。我实际调代码时还会再把水和食物分别量化成10一档这样状态数量又除以100。损失的一点精度在最终得分上通常不明显换来的是搜索能跑完。所以压缩不是偷懒是这个题必须做的工程取舍。2.2 为什么贪心不能保证最优而动态规划能很多第一次做这个题的人会想天气好就赶路天气差就挖矿休息这不是很自然吗但贪心在这里会掉链子。举例来说如果后面连续三天高温你为了多走一段路省了一天却因为水不够被迫在村庄高价买水最终可能比少走一天、早进村庄补给更亏。贪心只看眼前看不到全局的资源约束。动态规划的思路是把问题分解成“当前一天的行动剩余天数的子问题”。递推关系可以写成当前状态的价值等于所有合法行动中能让下一状态价值最大化的那个行动。真正的难点不在这个式子而在约束条件沙暴天不能行走、水和食物不能为负、负重不能超限、最后一天必须到达终点。每一条都会改变状态转移的合法范围写漏一条递推式就跑出荒谬结果。所以第一版代码不要急着上动态规划。我习惯先用模拟器把约束跑通确保任意一条策略的得分是一致的再去套DP或搜索。模拟器就像一个公平裁判裁判靠谱了后面优化才有意义。2.3 动态规划、遗传算法、模拟退火怎么选如果只需要“得分高”而不是“证明最优”遗传算法或模拟退火是更省内存的选择。它们把一条完整策略当作个体用交叉变异去搜索对状态空间不敏感适合天数更长、地图更大的变种题。但启发式算法的缺点是结果不稳定同一套参数跑两次分数不一样调参也需要额外时间。如果题目规模固定、规则明确动态规划或记忆化搜索仍然最稳每一步都在全局最优框架下做选择不会掉进局部最优。我的建议是先用记忆化搜索做一版能跑通、能验证正确性的基准如果内存顶不住再降级到遗传算法。Matlab里记忆化搜索可以用 containers.Map 实现代码量不大下一章会给出框架。2.4 目标函数的两个坑剩余物资不算钱透支要判死目标函数也要提前定清楚。题目一般只看最终到达终点时的现金余额不要试图把剩余水和食物按购买价折算进得分。否则你的搜索会倾向带着一堆物资到达终点看起来资源丰富实际现金少了排名吃亏。另一个坑是中途现金不够买水、但还没到山穷水尽时怎么处理。有的规则允许现金透支到终点再一起结算有的规则直接判失败。我处理的方式是在Params结构体里加一个 allow_negative_money 标志模拟器里按这个标志决定是继续跑还是直接返回失败。这样换题目变体时只改一行。3. 用Matlab写最小可运行框架初始化、主循环与结果回收这一章给出一套可以直接复制、改参数就能跑的最小实现。它不追求最优只求把规则跑完整、结果可复现。3.1 参数初始化把题目给的表格翻译成变量在Matlab里不要把这些参数撒在脚本各处而是集中放在一个结构体里。后面模拟器、搜索、画图都读这个结构体避免改参数时漏改。%% 参数初始化示例值请按题目实际表格替换 clc; clear; params.weather [1, 2, 1, 3, 1, 1, 2, 1, 1, 1, ... 2, 2, 1, 1, 3, 1, 1, 1, 2, 1]; % 天气序列1晴朗, 2高温, 3沙暴 params.num_days length(params.weather); params.start_loc 1; % 起点编号 params.end_loc 10; % 终点编号 params.init_money 3000; % 初始现金 params.init_water 0; % 初始水按题目实际 params.init_food 0; % 初始食物按题目实际 params.max_load 1000; % 负重上限 params.water_weight 3; % 每份水重量 params.food_weight 2; % 每份食物重量 params.water_price 5; % 水单价 params.food_price 10; % 食物单价 % 每日基础消耗按天气索引 params.base_water [3, 5, 0]; % 晴朗、高温、沙暴 params.base_food [3, 5, 0]; % 挖矿额外消耗 params.mine_extra_water 3; params.mine_extra_food 3; params.mine_income 250; % 每天挖矿收入按题目实际 % 地图邻接矩阵 a(i,j)1 表示可以从 i 到 j params.adj zeros(10, 10); params.adj(1,2) 1; params.adj(2,3) 1; % 按题图继续补全 % 矿山标记 params.is_mine zeros(1, 10); params.is_mine([3, 5]) 1;这里所有数值都是示例。你在用的时候要把天气序列、价格、消耗量、地图连接关系换成题目给的表格。关键点是向量化基础消耗用向量存后面用 weather(day) 作为下标避免一大串 if-else。写 if-else 不但慢还容易把天气和消耗的对应关系搞错。3.2 主循环让模拟器按行动序列跑一遍模拟器是整个代码的发动机。它接收一条行动序列输出角色是否活到终点、最终现金、每天的状态。function [alive, final_money, history] simulate_desert(actions, params) % actions(day): 1行走, 2挖矿, 3休息 % 返回 alive是否活到终点, final_money最终现金 % history 每天记录: 水, 食物, 现金, 位置 alive true; water params.init_water; food params.init_food; money params.init_money; loc params.start_loc; history zeros(params.num_days, 4); for day 1:params.num_days w params.weather(day); a actions(day); % 沙暴天不能行走 if w 3 a 1 alive false; return; end % 计算当天消耗 dw params.base_water(w); df params.base_food(w); if a 2 dw dw params.mine_extra_water; df df params.mine_extra_food; elseif a 3 % 部分版本休息也有消耗按需调整 dw 0; df 0; end % 扣资源 water water - dw; food food - df; if water 0 || food 0 alive false; return; end % 挖矿收益且必须在矿山 if a 2 if ~params.is_mine(loc) alive false; return; end money money params.mine_income; end % 行走则更新位置 if a 1 next_locs find(params.adj(loc, :)); if isempty(next_locs) alive false; return; end loc next_locs(1); % 示例取第一个实际按路线决策 end history(day, :) [water, food, money, loc]; end % 最后必须到达终点 if loc ~ params.end_loc alive false; return; end final_money money; end这个模拟器有几个容易出错的地方沙暴天直接禁止行走挖矿收益只有当位置在矿山时才能拿到休息的消耗默认置0但如果题目规则里休息也消耗就把这里改成对应值。行走时按邻接矩阵取下一个地点示例代码只取了第一个邻居实际搜索时应该由外层决策传入目标地点而不是在模拟器里自动选。3.3 购买逻辑村庄补给的边界判断上面主循环没写购买因为购买本身就是策略的一部分。常见做法是在每次行动之前判断当前位置是不是村庄然后调用购买函数。function [water, food, money] buy_supply(water, food, money, params, need_w, need_f) % 在村庄购买直到满足后段需求或负重撞到上限 while money params.water_price water need_w w_add params.water_weight; if (water 1) * params.water_weight food * params.food_weight params.max_load break; end water water 1; money money - params.water_price; end % 食物购买逻辑同理 end这段代码的关键是买前先算负重。很多人会忘掉 weight 项直接判断 water food 是否超限结果跑出来的策略背着重物飞天。购买策略里 need_w 和 need_f 是“接下来几天需要的量”由上层策略决定这里只做机械补足。3.4 结果回收每次实验留证据模拟器跑完把结果打出来并画图。%% 评估一条策略 actions ones(1, params.num_days); % 全部行走 [alive, money, hist] simulate_desert(actions, params); if alive fprintf(最终现金: %.1f\n, money); else fprintf(策略失败角色没活到终点。\n); end % 画现金和物资变化 figure; yyaxis left; plot(hist(:,3), -, LineWidth, 1.5); ylabel(现金); yyaxis right; plot(hist(:,1), --, hist(:,2), :, LineWidth, 1.2); ylabel(水/食物); xlabel(天数); legend(现金, 水, 食物); title(策略收益曲线);这个“策略评估闭环”非常重要。有了它后面任何搜索算法都只是不断生成行动序列、交给模拟器打分。模拟器保持独立搜索算法的改动不会污染规则实现。4. 从能跑到跑快剪枝、记忆化与可视化验证模拟器跑通后下一步是搜索最优策略。这一章讲怎么在Matlab里把搜索做快。4.1 剪枝把“活不到明天”的分支直接砍掉搜索树最容易爆的是每层三种行动的分叉。剪枝第一原则当前剩余资源连下一站都到不了后面就不用看。% 在搜索前判断 next_supply params.adj(loc, :); % 附近可达补给点 if isempty(next_supply) % 无路可走剪枝 return; end % 估算到最近补给点的天数 est_days 1; % 按地图实际距离算 % 按最省天气估算消耗留20%余量 need_water ceil(est_days * min(params.base_water) * 1.2); need_food ceil(est_days * min(params.base_food) * 1.2); if water need_water || food need_food return; % 剪枝 end这里最容易犯的错是余量系数。按最坏天气剪枝会把很多可行方案误杀按最好天气剪枝剪不掉多少分支。我一般用平均消耗乘1.2到1.3作为余量。这个系数可以调调大剪枝多但可能漏最优解调小搜索慢但更稳。建议先设1.3跑一遍如果时间有富余再降到1.1。4.2 记忆化同一个状态别算第二遍记忆化搜索是动态规划的递归实现。在Matlab里用 containers.Map 缓存已经算过的状态避免重复计算。M containers.Map(KeyType, char, ValueType, double); function best_money dfs(day, loc, water, food, money, params) key sprintf(%d_%d_%d_%d, day, loc, water, food); if M.isKey(key) best_money M(key); return; end % 递归边界 if day params.num_days if loc params.end_loc best_money money; else best_money -inf; end M(key) best_money; return; end candidates [1, 2, 3]; % 行走、挖矿、休息 best_money -inf; for a candidates % 这里调用模拟器单日逻辑或直接写状态转移 % 只保留合法分支 [alive, new_water, new_food, new_loc, new_money] ... step_desert(day, loc, water, food, money, a, params); if ~alive continue; end val dfs(day 1, new_loc, new_water, new_food, new_money, params); if val best_money best_money val; end end M(key) best_money; end注意 key 不能包含 money。如果把现金也塞进key状态数会爆炸。这个题里同样的资源状态下现金越多越好所以缓存时只保留该状态下能达到的最大现金。另外水和食物是连续值直接做 key 也会导致状态太多建议量化成10的倍数再存。4.3 可视化把路线和资金画出来比看数字有用搜索结束后把最优策略的路线画出来。用位置曲线能直观看到角色是不是绕了远路用资金曲线能判断策略是否“走钢丝”。figure; subplot(2,1,1); plot(hist(:,4), o-, LineWidth, 1.5); xlabel(天数); ylabel(地点编号); title(最优路线); grid on; subplot(2,1,2); plot(hist(:,3), -, LineWidth, 1.5); xlabel(天数); ylabel(现金); title(现金变化); grid on;如果现金曲线在最后几天突然掉一大截多半是买了高价补给如果水一直贴着0运行说明策略在极限边缘换一份天气序列就可能翻车。可视化不是用来好看是用来发现策略的脆弱点。4.4 搜索顺序先试挖矿还是先试行走在DFS里候选行动的顺序会影响剪枝效果。我习惯按消耗从大到小排列先挖矿再行走最后休息。因为挖矿收益高、消耗也大先试它更容易找到一个高分可行解这个解的分值越高后面剪枝时能剪掉更多低分分支。如果你先试休息找到的第一个可行解往往很平庸剪枝力度就差很多。这个顺序对结果没有影响只影响搜索时间。同样的题目先挖矿后行走可能只要几秒反过来可能跑几分钟还结束不了算是Matlab实现里最省力的加速项。5. B题Matlab实现避坑清单5个让结果翻车的细节这一章记录我在调试中反复踩过的坑每条都按现象、原因、解决写好。5.1 天气序列从第0天开始读导致第一天消耗算错现象模拟器跑出来角色第一天的水和食物消耗比题目表格多一份。原因题目里的天气序列是从到达后第一天开始编号但Matlab数组从1开始。如果代码里把 weather(0) 当成第一天或者把题目Excel第一行标题误当成数据读进来就会整体错位。解决把天气序列复制进脚本时直接从 weather(1) 开始。如果题目明确给了第0天的状态也单独设一个变量不要往数组里硬塞。检查方法很简单第一天结束后手动算一遍水和食物和模拟器输出对比。5.2 把负重上限当成“水和食物的总份数”而不是总重量现象背包里显示水300、食物200负重却超过了上限程序没报错但最终现金偏大。原因题目里水和食物有各自的单位重量负重上限是水重量加食物重量不是份数之和。解决购买和检查时统一用 water * water_weight food * food_weight 判断。在 buy_supply 函数里买之前先算一次重量超了就停止购买。5.3 在村庄“顺手买满”导致后面资金崩盘现象策略在村庄把所有钱都买了水和食物后面没现金矿山收益又不够补最终现金为负。原因村庄购买是用现金换物资不是免费补给。买满会同时占用负重和现金严重影响后段决策。解决把购买量作为决策变量交给搜索不要默认买满。我一般把购买逻辑拆成 need_w 和 need_f 两个参数由上层策略算出“接下来几天还差多少”然后精确补足最多留10%余量。5.4 递归深度太大Matlab直接栈溢出现象搜索30天时程序运行到一半报错提示递归层数超限。原因DFS递归30层本身没问题但每个节点里又调用多级子函数实际调用栈翻了几倍。解决在脚本开头执行 set(0, RecursionLimit, 1000) 加大限制如果还溢出就把DFS改成显式栈的循环版本。另外加上记忆化后分支数量会大幅减少栈溢出问题也会缓解。5.5 提前到达终点后还在继续模拟资金被扣成负数现象策略在第25天就到终点了但模拟器还在按行动序列跑后面5天最终现金莫名变低。原因循环终止条件只写了“跑完全部天数”没写“到了终点就和后续天气无关”。解决在循环开头判断如果 loc 已经等于 end_loc直接跳出循环后续天数不做任何消耗。注意有的题目允许提前到达然后在终点等到结束资源不再变化。6. 进阶用基准例和蒙特卡洛验证你的策略是真的优代码能跑、能搜索、能画图之后还差最后一步验证。否则你精心调出来的“最优策略”可能只是在一组固定天气序列下自嗨。先做一个手工基准例。构造一个3天、2个地点的最小地图自己算一遍最优解。比如起点到终点1天晴天行走消耗3水3食物终点不需要买补给最优策略显然是第一天直接走到终点后面原地休息。用你的模拟器跑一遍如果输出不一致问题一定出在消耗或到达判定上。这个基准例很简单却能一次性抓住“位置更新”“沙暴禁止”“提前到达”这几类最常见的bug。我每次改完模拟器都会先跑它再跑完整30天。再用蒙特卡洛给结果画一条下界。随机生成几万条合法行动序列交给模拟器打分记录最高分。如果你的搜索算法跑出来的结果比随机还差那基本可以断定代码有bug而不是题目难。best_random 0; for i 1:20000 actions randi([1, 3], 1, params.num_days); [alive, money, ~] simulate_desert(actions, params); if alive money best_random best_random money; end end fprintf(随机策略最佳分数: %.1f\n, best_random);注意随机序列里大部分是无效的所以这个下界通常不高只能用来排除严重bug。最后和贪心策略对比一下量化你的搜索收益。写一个简单贪心天气好就走天气差就休息缺水就去村庄买。拿它和你的记忆化搜索结果比。如果差距小于5%说明题目本身优化空间有限你已经接近上限如果差距大于20%说明全局约束确实重要你的搜索有价值。我自己的习惯是保留一张参数速查表把每次实验的天气序列、初始现金、价格、最终得分记在脚本头注释里。下次换题目变体或调整规则时直接对照修改不用重新推导。这个方法也帮我避免过很多次“换一天天气就翻车”的尴尬。希望帮到你。本文还有配套的精品资源点击获取

2020数学建模B题沙漠穿越：Matlab动态规划与剪枝实战解析

相关推荐

CEF4Delphi 控件：Delphi 与 JavaScript 双向通信及避坑指南

端侧推理引擎：AI模型落地的最后一公里

创成式AI完全指南：从原理到落地的工作流实践

更多资讯

smol developer 全程序生成实战：从 shared_deps.md 共享依赖契约解读 AI 生成的 Pong 游戏架构

Apache OpenDAL 接入 MongoDB GridFS：从配置到源码级的完整实战指南

AI生成HTML课件如何转成可编辑PPTX？语义解析与版式重建实战

Unity WebGL打包实战：四层决策树与37个线上坑的诊断手册

线激光传感器工程实践：Gocator从硬件选型到多传感器对齐的完整指南

如何在windows11禁止ollama开机启动

今日更新

小波包能量谱原理与MATLAB实现：从频带分解到故障特征提取

基于LSTM的网易云音乐评论情感分析：数据清洗与模型调优实战

Alpha-Beta剪枝与极大极小值算法：博弈树搜索原理与实战优化

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？