1. 从“第一关”到“第二关”问题复杂度的跃迁与建模思路的转变很多初次接触2020年国赛B题“穿越沙漠”的同学在顺利通关第一关后往往会带着一种“不过如此”的轻松感进入第二关。然而现实很快就会给你上一课。第一关本质上是一个单角色、单目标、确定性资源的线性规划问题你只需要为“你自己”规划一条从起点到终点的最优路径计算水和食物的消耗与购买。但第二关开始游戏规则发生了根本性的变化——你不再是一个孤独的旅行者而是一名需要指挥多名玩家在动态天气和竞争环境下生存并争取胜利的指挥官。这种转变正是数学建模竞赛题目的典型套路先用一个简化版第一关让你熟悉规则和基本模型然后迅速引入多个核心变量将问题复杂度提升数个数量级。第二关至第六关虽然地图、基础规则一致但通过引入“多人博弈”、“不同天气规则”、“矿山工作”等条件考察的是我们对模型进行扩展、抽象和算法设计的能力。如果你还试图用第一关那种“手算”或简单动态规划的思路去硬刚结果必然是耗时巨大且收效甚微。我的核心思路是建立一套统一的、可扩展的智能体决策框架然后针对每一关的特殊规则调整框架中的评估函数和约束条件。接下来的分享将围绕这个框架的构建与各关卡的调整策略展开。2. 核心框架构建多智能体时序决策模型面对多人、多天、多状态的复杂决策问题我们需要一个结构化的模型来理清思路。我将其称为“多智能体时序决策模型”。这个模型不关心你具体用哪种算法实现动态规划、启发式搜索、甚至强化学习都可以它关注的是决策的逻辑流程。2.1 模型的基本要素定义首先我们必须将游戏中的所有元素进行数学抽象状态 (State, S_t)在任意第t天时段整个游戏世界的完整快照。它必须包含Weather[t]: 第t天的天气类型晴朗、高温、沙暴。Players: 所有玩家的状态集合。每个玩家i的状态P_i(t)包括Position_i(t): 所在区域坐标。Water_i(t),Food_i(t): 当前水和食物数量。Money_i(t): 当前资金。Status_i(t): 状态活跃、死亡、到达终点。BaseSupplies: 各个村庄的水和食物剩余量如果规则涉及限量补给。动作 (Action, A_t)在状态S_t下所有玩家同时做出的决策集合。每个玩家i的可选动作a_i包括Move(direction): 向相邻区域移动。Stay: 停留当前区域。Mine: 在矿山工作。Buy(water, food): 在村庄购买。Sell(water, food): 在村庄出售若规则允许。状态转移函数 (Transition Function, T)定义了从当前状态S_t和所有玩家动作A_t如何确定性地演化到下一状态S_{t1}的规则。这是题目规则的核心编码移动根据天气消耗资源更新位置。沙暴日不可移动。采矿消耗双倍资源获得资金。交易更新玩家和村庄的资源与资金库存。消耗所有存活玩家根据天气进行基础消耗。收益/奖励 (Reward, R_t)在状态S_t执行动作A_t后转移到S_{t1}所获得的即时收益。在穿越沙漠问题中最终收益是到达终点后的剩余资金但过程中的奖励设计是算法关键。我们可以定义中间奖励例如M: 成功采矿获得的资金。-C: 购买资源消耗的资金视为负奖励。-Penalty: 玩家死亡给予一个极大的负奖励如 -10000。策略 (Policy, π)一个函数它根据当前状态S_t为每个玩家i分配一个动作a_i。我们的目标就是为“我方玩家”找到一个最优策略π*使得在考虑其他玩家策略的情况下最终收益剩余资金的期望值最大。2.2 决策流程与关键挑战基于上述模型每一回合天的决策流程如下观察状态S_t获取当前所有玩家位置、资源、天气等信息。预测对手行为这是多人博弈的核心。我们需要对其他玩家的可能动作a_j (j≠i)做出假设或预测。评估动作价值对于我方玩家的每一个可选动作a_i结合对对手动作的预测模拟执行后得到新状态S_{t1}并评估从这个新状态出发直到游戏结束的“未来收益期望值”Q(S_t, a_i)。选择最优动作选择价值Q最高的动作执行a_i* argmax Q(S_t, a_i)。这里的核心挑战在于第2和第3步对手建模其他玩家是理性的吗他们目标是最大化自己收益还是故意阻碍我们不同关卡对手行为模式不同。搜索空间爆炸即使只有2个玩家每个玩家每天有约5个动作规划10天就有5^(2*10)种可能的动作序列这是无法穷举的。长期规划需要权衡“短期资源消耗”与“长期收益采矿、到达终点”。为了解决这些挑战我们必须引入启发式策略和近似算法这也是各关卡思路差异的根源。3. 第二关与第三关对抗环境下的保守与激进策略第二关和第三关都引入了另一名玩家玩家2且目标是“在有限天数内到达终点并尽可能保留更多资金”。区别在于第二关的天气是已知的而第三关的天气是随机的。这导致了策略重心的不同。3.1 第二关完全信息下的博弈与路径规划已知天气序列是巨大的优势。我的策略核心是在确保自身生存的前提下与对手进行资源竞争特别是关键节点村庄的“抢占”。最优单人路径复核首先忽略对手用第一关的方法计算出一条从起点到终点的理论最优路径包括可能的采矿和补给计划。这条路径是你的“基线方案”。识别关键冲突点分析这条基线路径找出几个容易发生竞争的关键点第一个村庄通常是初期重要的补给点。如果对手也直奔这里可能导致你到达时资源已被买空如果规则设置村庄资源有限。矿山如果采矿是盈利的矿山区域会成为必争之地。不仅要考虑自己采矿的天数还要预判对手可能采矿的时间。狭窄通道地图上连接关键区域的要道。虽然题目未直接设置“堵路”规则但若对手恰好在此区域停留可能间接影响你的移动计划尽管物理上不阻挡但需在决策时考虑其存在。构建博弈决策树简化版由于天数有限~30天我们可以进行有限深度的博弈树搜索。状态简化只精确跟踪双方的位置、核心资源水、食物和资金。忽略细微差异。动作剪枝对于每个玩家每天只考虑3-4个最合理的动作例如向目标移动、停留补给、采矿。对手模型在第二关通常假设对手也是理性人采用类似你的算法如最短路径优先。你可以用你的基线方案作为对手策略的第一次近似。滚动优化我们无法计算30步的完整树。采用模型预测控制MPC的思路在每个决策点t向前模拟H步例如H5或到下一个关键点在模拟中假设对手按固定策略行动评估我方不同动作序列的最终效果选择前k步最优动作执行然后到下一时刻重新进行滚动优化。具体策略调整抢先手如果计算发现对手可能与你同时到达关键村庄且资源可能不足则应提前出发或调整路径哪怕多花一天也要确保自己能率先完成补给。采矿博弈计算矿山的“价值”。如果提前到达矿山可以评估是立即开始采矿还是等对手到达、观察其行动后再决定。有时放弃采矿、直接前往终点让对手在矿山浪费时间反而能赢得比赛因为目标是最终资金不是采矿最多。终点冲刺最后阶段如果领先就选择最稳妥的路径直奔终点如果落后可能需要冒险选择一条更短但资源更紧张的路径或者赌对手会在补给点犯错。实操心得在第二关的编程实现中模拟器的准确性至关重要。你必须编写一个高度可靠、与题目规则完全一致的“游戏引擎”函数输入所有玩家动作输出下一状态。任何细微的规则错误如沙暴日移动的判断、矿山消耗的计算都会导致整个博弈模拟失效使你的策略建立在错误的基础上。建议单独测试这个模拟函数。3.2 第三关引入不确定性随机天气的风险管理第三关从完全信息博弈变成了不完全信息随机博弈。天气的随机性彻底改变了游戏性质。策略核心从“精确算计”转向风险管理与弹性规划。从期望值到风险厌恶在已知天气下我们可以精确计算每条路径的资源消耗。在随机天气下我们计算期望消耗。但更重要的是我们需要考虑最坏情况连续高温或沙暴。因此资源储备必须留有安全余量Buffer。关键策略实时重规划与多路径评估放弃固定路径不能再像第二关那样制定一条从头到尾的精确到天的计划。状态决策在每个决策点根据当前的资源、位置和剩余的天气概率分布重新评估所有可行的选项。价值函数设计评估一个动作的价值Q时不能只算一种天气而是要对未来可能的天气序列进行蒙特卡洛模拟Monte Carlo Simulation。例如从当前状态开始随机生成N条如1000条符合历史天气统计规律的未来天气序列对每条序列模拟执行候选动作及后续策略得到N个最终资金结果然后用这些结果的期望值或风险调整后的值如期望值减去方差的一定倍数作为Q值。信息集与对手建模的弱化由于天气随机对手也面临不确定性其行为更难以预测。此时过于复杂的对手建模可能收益不大。一个有效的简化是假设对手采用一种简单的鲁棒策略例如总是携带额外20%的资源缓冲并沿最短期望路径移动。你的主要博弈对象从“对手”变成了“随机天气”。村庄的核心作用提升随机天气下村庄作为“安全港”和“资源调节器”的价值急剧上升。策略应倾向于保持高流动性不要将资源一次性全部投入采矿确保随时有能力转向最近的村庄进行补给。分段推进将长途旅程分解为多个“从安全点到安全点”如村庄到村庄村庄到矿山的短途任务每个任务独立进行风险计算和资源准备。踩坑实录在第三关最容易犯的错误是用第二关的确定性思维去套随机问题。比如计算出一条期望消耗最小的路径就按此严格执行。结果一旦遇到连续高温中途资源耗尽直接崩盘。正确的做法是编程时你的决策函数必须内置随机模拟任何决策都应基于大量随机抽样的统计结果而不是单个数值。4. 第四关与第五关矿山运营与资本循环第四关开始游戏目标从“到达终点”变为“在指定天数内积累最大资金”并且玩家在终点区域不会结束游戏。这彻底改变了游戏的核心循环从资源消耗型旅行变成了资源转化型生产。矿山从可选项变成了必选项。4.1 第四关单矿山运营的利润最大化模型第四关通常是单人、单矿山、已知天气。问题简化为一个动态库存控制与生产调度问题。建立利润模型首先量化采矿的“利润率”。在矿山工作一天消耗水2*weather_consumption食物2*weather_consumption获得1000元。这些水和食物如果从村庄购买成本是5*water 10*food基础价格。假设水和食物消耗量相同为c则一天采矿的毛利润为1000 - (2c*5 2c*10) 1000 - 30c。晴朗日 (c3)毛利润1000 - 90 910。高温日 (c4.5)毛利润1000 - 135 865。沙暴日 (c0但无法移动和工作通常不在矿山停留。结论只要能从村庄买到补给采矿在任何天气下都是暴利。核心约束是初始资金和村庄到矿山的物流成本。核心决策循环第一阶段资本原始积累。用初始资金购买资源前往矿山开始采矿。直到资源耗尽。第二阶段补给与再生产。携带采矿所得资金返回村庄进行补给购买水、食物再返回矿山。这里产生一个关键决策每次补给多少多补少跑一次购买大量资源在矿山工作很长时间减少了往返村庄的次数减少了路上的消耗和天数浪费但占用了大量资金且可能因天气导致资源过剩浪费。少补多跑每次只购买少量资源频繁往返。资金占用少灵活性高但路上损耗比例大有效采矿时间短。第三阶段终局处理。在游戏结束前几天需要停止采矿计算返回终点所需的最少资源将剩余资金最大化。建模与优化这个问题可以构建一个动态规划模型。状态变量天数t位置loc资金m水w食物f。决策移动、停留、采矿、购买。状态转移由天气和动作决定。目标函数最后一天在终点区域时的资金m最大。由于状态空间较大直接求解较难。可采用值迭代或基于规则的启发式算法。启发式规则示例始终确保背包有空间如果规则有负重限制。在村庄时将几乎全部资金转化为资源但预留最后一次返回终点的路费。选择晴朗天气较多的时段进行长途移动从矿山到村庄或终点。在矿山时只要资源够就持续采矿直到资源低于某个安全阈值该阈值等于从矿山回到村庄所需资源加上缓冲。4.2 第五关多矿山选择与物流网络优化第五关在第四关基础上地图上可能出现多个矿山且天气可能随机。问题升级为多生产中心的供应链优化。矿山评估与选择不是所有矿山都值得去。评估一个矿山i的吸引力需考虑固定成本从起点或中心村庄到达该矿山i的初始路径消耗资源折合成资金C_route。运营成本从矿山i到最近补给村庄V的往返消耗C_roundtrip。预期收益在矿山i工作扣除自身消耗后的每日净收益P_day。简单评估指标(总天数 - 初始路径天数 - 终末返回天数) * P_day - C_route - n * C_roundtrip其中n是预计的往返补给次数。选择指标最高的矿山。多矿山情况下的策略单一矿山深耕大多数情况下选定一个最优矿山后持续在那里采矿直到结束是最佳策略。频繁切换矿山会产生额外的移动损耗。切换矿山的条件只有在极特殊情况下考虑切换例如当前矿山附近的村庄资源耗尽如果规则有限量。天气模式发生剧变使得另一个矿山-村庄路线的期望收益变得更高。游戏后期当前矿山距离终点更远而另一个矿山在返回终点的路径上。随机天气下的应对与第三关类似需要为运营计划添加缓冲。安全库存在矿山工作时资源不应刚好用到见底才去补给。应设定一个触发补给的阈值该阈值大于从矿山到村庄的最坏天气消耗例如连续高温。灵活补给路线如果有多个村庄应实时计算去哪个村庄补给成本最低考虑当前资源、天气预测、村庄价格。模拟决策在决定是否要进行一次补给旅程时可以快速模拟未来几天不同天气序列下的情况评估补给与不补给的风险。经验技巧对于第四、五关在编程求解时可以分阶段优化。首先用一个简单的启发式规则如“始终去最近矿山补满资源采矿”跑出一个可行解和基准收益。然后针对这个解中的关键决策点如第一次补给时机、补给量、返回终点的时间在其邻域内进行局部搜索或微调往往能快速提升结果。这比直接求解完整的动态规划要高效得多。5. 第六关多人合作与竞争的混合博弈第六关通常是多人游戏目标可能是团队资金总和最大或者个人排名。这引入了合作与竞争并存的复杂局面。策略核心是识别博弈结构决定采取合作、竞争还是中立策略。分析收益结构团队总和如果目标是团队总资金最大那么玩家之间是纯合作关系。最优策略是进行任务分工例如一人专门负责从村庄到矿山的资源运输另一人专门在矿山不间断采矿类似“供应链”协作以减少矿山玩家往返村庄的时间浪费。个人排名如果目标是个人排名如剩余资金最多者胜那么就是非零和博弈。可能存在合作空间但本质是竞争。合作的可能性与机制资源转移如果规则允许玩家之间交易题目通常不允许合作会非常直接。即使不允许直接交易也可以通过“市场”进行间接合作例如玩家A在村庄购买过剩食物在矿山区域以低于商店售价但高于成本价的价格“丢弃”玩家B捡起使用实现双赢。信息共享在随机天气下共享各自对天气的预测或探索到的路径信息对团队有益。分工协作如前所述采矿与运输的分工。竞争下的策略预判与规避如果判断其他玩家会去竞争热门矿山我可以选择去次优但竞争小的矿山避免初期资源争夺战。干扰策略在资源有限的村庄抢先买空关键资源如水即使自己略有浪费也能严重拖慢对手进度。这需要计算“干扰成本”与“收益”是否划算。跟随策略在信息不明时跟随一个看似强大的对手他去哪我去哪利用他探路并在关键时刻如最后冲刺选择不同路径实现反超。建模实现思路层次化决策首先用第四、五关的模型为我方每个玩家计算一个“不考虑对手”的最优生产计划。博弈层调整然后在高层引入一个博弈分析模块。评估如果所有玩家都执行自己的最优计划会在何时何地发生冲突资源点、矿山。策略调整对于每个冲突点根据收益结构合作/竞争重新计算调整后的策略。如果是竞争就评估“争夺”、“规避”、“干扰”哪种方案的期望收益更高如果是合作就重新规划分工方案。采用元策略在编程中可以让我方玩家具备几种不同的基础策略激进采矿者、保守旅行者、干扰者然后根据游戏前期对对手行为的观察动态切换策略。穿越沙漠从第二关到第六关是一个典型的从确定性规划到随机优化再到博弈决策的思维深化过程。它考察的不仅仅是数学工具的应用更是对复杂系统进行抽象、简化和分层求解的能力。我的建议是在动手编程前一定要先用纸笔或思维导图把每一关的决策主体、核心目标、关键约束和不确定性来源梳理清楚建立清晰的模型框架。然后再选择适合的算法动态规划、搜索、蒙特卡洛模拟、启发式规则去填充这个框架。记住没有“一招鲜”的算法最好的模型永远是那个最贴合题目规则内在逻辑的模型。