1. 从“过河”到“建模”一个经典问题的现代解法“商人过河”这个题目但凡接触过数学建模或者算法竞赛的朋友应该都不陌生。它听起来像是个古老的智力题但内核却是一个绝佳的离散状态空间搜索和决策优化案例。我第一次接触它是在大学数学建模的入门课上老师用它来告诉我们一个看似简单的故事背后可以抽象出多么严谨的数学模型。这么多年过去了我带学生、做项目依然会时不时拿这个例子出来讲因为它太经典了经典到几乎涵盖了建模思维从问题理解到代码实现的完整闭环。简单描述一下问题有三个商人和三个随从要过一条河只有一条小船船最多能载两个人。无论在河的哪一边如果随从的人数多于商人的人数随从就会攻击商人即不安全状态。目标是找到一种渡河方案让所有人都安全过河且船来回的次数尽可能少。很多人第一次想会觉得这还不简单试几次不就出来了。但当你真正用代码去“穷举”所有可能的、安全的渡河步骤并找到最优解时你会发现其中蕴含的“状态转移”、“图搜索”、“约束满足”等思想正是许多复杂系统建模的基石。今天我们就用Matlab这把“瑞士军刀”来从头到尾拆解这个问题。我会分享如何将故事转化为数学模型如何设计高效的搜索算法以及如何用Matlab清晰、优雅地实现并可视化整个过程。无论你是正在备战数学建模竞赛的学生还是对算法实现感兴趣的工程师相信这篇都能给你带来一些可以直接“抄作业”的启发。2. 问题抽象与状态空间建模把故事变成数学语言动手写代码之前最关键的一步是把文字描述的问题翻译成计算机能处理的数学模型。这一步走对了后面的路就顺了。2.1 定义“状态”抓住问题的核心变量问题的核心是“人”在“河”的两岸的分布。我们需要用最简洁的数学方式描述某一时刻的局面。通常我们以河的左岸出发岸为观察基准。定义状态向量为 (M, S, B)M: 左岸的商人数量0, 1, 2, 3。S: 左岸的随从数量0, 1, 2, 3。B: 船的位置0表示在左岸1表示在右岸。那么初始状态就是 (3, 3, 0)目标状态是 (0, 0, 1)。为什么目标状态船在右岸因为最后一步是船载着人从左岸划到右岸所有人就都在右岸了。注意这里有一个常见的建模分歧点。有些人喜欢用右岸人数做状态本质上等价但以左岸为基准更符合“从起点出发”的直观感受在编程实现时也更容易统一。2.2 定义“安全约束”将现实规则转化为不等式原问题的安全规则是“任何一岸随从人数不能超过商人人数除非商人数为0”。这句话需要小心拆解成对左岸和右岸的分别判断。对于任意一个状态 (M, S, B)左岸安全性必须满足(M 0) || (M S)。即要么左岸没有商人随从多少都无所谓没人可攻击要么商人人数不少于随从。右岸安全性右岸的商人数量是3 - M随从数量是3 - S。因此右岸安全的条件是((3 - M) 0) || ((3 - M) (3 - S))。这个不等式可以简化(3 - M) (3 - S)等价于S M。所以一个状态 (M, S, B) 是安全的当且仅当同时满足(M 0) || (M S)左岸安全((3 - M) 0) || (S M)右岸安全仔细看第二个条件S M它和第一个条件M S同时成立意味着什么意味着在安全状态下左岸的商人和随从人数必须相等除非其中一岸的商人数量为0。这是一个非常重要的简化结论能帮助我们快速在脑海中排除大量无效状态。例如(3,1) 或 (1,2) 这种左右岸商仆数都不相等且商人都不为0的状态根本不可能安全。2.3 定义“操作”状态转移小船如何改变世界船每次移动都会改变状态。操作由两部分描述船上的人员构成以及移动方向。船上人员由于船最多载2人且至少1人划船所以可能的乘船组合是1个商人、2个商人、1个随从、2个随从、1商1随。共5种。移动方向由当前状态中的 B 值决定。如果 B0船在左岸则下一步一定是载人从左岸到右岸这将导致左岸的 M 和 S 减少右岸增加。如果 B1船在右岸则反之。因此从一个安全状态出发我们可以根据船的位置遍历所有可能的乘船组合计算出“假设执行此操作”后的新状态 (M’, S’, B’)然后校验新状态是否安全。如果安全则这条“边”就通了。至此我们成功地将一个故事转化为了一个图论问题所有安全的状态是“顶点”所有合法的渡河操作是连接顶点的“有向边”。我们的目标就是从起点 (3,3,0) 找到一条路径走到终点 (0,0,1)。寻找最短路径就是寻找最少渡河次数的最优方案。3. 搜索算法选择与Matlab实现是“广搜”还是“深搜”模型建好了接下来要选择算法来搜索路径。对于这种状态空间不大所有可能状态也就4x4x232种安全状态更少且要求最优解步数最少的问题广度优先搜索BFS是天然的选择。BFS会一层一层地探索状态空间第一次到达目标状态的路径一定是最短路径。3.1 为什么不用深度优先搜索DFSDFS可能会钻进一条很深的无效分支浪费时间而且找到的第一条路径不一定是最短的需要搜索所有路径才能确定最优效率不如BFS直观。当然你也可以用迭代加深搜索IDS但对于这个简单问题BFS实现更直接。3.2 Matlab实现BFS的关键数据结构Matlab不是传统的面向对象语言但它的矩阵和元胞数组非常适合处理这类问题。我们需要队列用于BFS。可以用一个元胞数组queue来模拟每个元素存储一个状态和到达该状态的路径。已访问集合防止走回头路。因为状态是三维的我们可以用一个逻辑矩阵visited来标记尺寸为 4 x 4 x 2M, S 各4种B有2种。路径记录我们需要知道怎么来的。在将新状态加入队列时同时记录从起点到该状态的完整状态序列。下面是我的实现方案我会逐段解释为什么这么写function [solution_path, steps] merchant_crossing_river() % 初始化 start_state [3, 3, 0]; % [M, S, B] target_state [0, 0, 1]; % 定义所有可能的乘船组合船上人数的变化量从左岸出发视角 % 每一行代表一种操作: [delta_M, delta_S] % 船从左到右左岸人数减少所以delta为负 operations [-1, 0; % 运1个商人 -2, 0; % 运2个商人 0, -1; % 运1个随从 0, -2; % 运2个随从 -1, -1];% 运1商1随 % BFS初始化 queue {}; % 元胞数组作为队列每个元素是 {state, path_history} queue{1} {start_state, start_state}; % 路径历史初始包含起点 visited false(4, 4, 2); % 访问标记数组 visited(start_state(1)1, start_state(2)1, start_state(3)1) true; % Matlab索引从1开始 % 开始BFS循环 while ~isempty(queue) % 出队 current_node queue{1}; queue(1) []; % 移除队首元素 current_state current_node{1}; current_path current_node{2}; % current_path 是一个矩阵每一行是一个状态 % 检查是否到达目标 if isequal(current_state, target_state) solution_path current_path; steps size(current_path, 1) - 1; % 步数状态数-1 fprintf(找到最优解共需 %d 步渡河。\n, steps); return; end % 生成所有可能的下一状态 current_M current_state(1); current_S current_state(2); current_B current_state(3); % 根据船的位置决定操作方向系数 if current_B 0 % 船在左岸从左到右左岸人数减少 direction -1; else % 船在右岸从右到左左岸人数增加 direction 1; end for i 1:size(operations, 1) delta_M operations(i, 1) * direction; delta_S operations(i, 2) * direction; new_M current_M delta_M; new_S current_S delta_S; new_B 1 - current_B; % 船的位置取反 % 边界检查人数不能为负也不能超过3 if new_M 0 || new_M 3 || new_S 0 || new_S 3 continue; end % 安全性检查使用我们推导出的条件 % 左岸安全 left_safe (new_M 0) || (new_M new_S); % 右岸安全右岸商人3-new_M, 随从3-new_S right_safe ((3 - new_M) 0) || ((3 - new_M) (3 - new_S)); % 第二个条件简化为 (new_S new_M)这里用原始形式更清晰 if ~(left_safe right_safe) continue; % 状态不安全跳过 end % 检查是否已访问 if visited(new_M1, new_S1, new_B1) continue; end % 标记为已访问并入队 visited(new_M1, new_S1, new_B1) true; new_state [new_M, new_S, new_B]; % 将新状态追加到当前路径的末尾形成新路径 new_path [current_path; new_state]; % 垂直拼接 queue{end1} {new_state, new_path}; end end % 如果队列空仍未找到 solution_path []; steps -1; fprintf(未找到解决方案。\n); end代码关键点解读与避坑指南状态索引的“1”操作这是Matlab编程中处理此类映射问题的经典坑。我们的状态值范围是0-3但Matlab数组索引从1开始。因此状态(M,S,B)对应访问标记数组visited的索引是(M1, S1, B1)。忘记加1会导致索引越界错误或者更隐蔽地访问到错误的存储位置。操作的方向系数这是实现的核心技巧。我定义的操作operations是基于“船从左岸到右岸”视角的人数变化量delta为负。当船实际在右岸时操作方向相反direction 1即人数变化量取反。这样我们只需要定义一套操作集合通过乘以方向系数来适配船的不同位置避免了写两套几乎相同的逻辑代码更简洁也不容易出错。路径的记录方式我选择用一个矩阵current_path来记录从起点到当前状态的所有状态序列。每次发现新状态就通过[current_path; new_state]垂直拼接生成新路径。这样做的好处是直观路径信息完整保存在队列的每个节点里。缺点是当路径变长时反复复制矩阵会产生一些内存和性能开销。对于本题极小状态空间这完全不是问题。如果状态空间巨大可能需要记录前驱状态然后用回溯法重建路径。安全判断的清晰性在代码中我刻意没有使用简化后的条件MS而是保留了原始的、含义明确的逻辑判断left_safe和right_safe。这对于代码的可读性和可维护性至关重要。别人或者三个月后的你自己再看这段代码时能立刻看懂它是在检查“左岸商人数为0或不少于随从”以及“右岸商人数为0或不少于随从”而不需要去回想那个数学推导。写建模代码清晰性往往比极致的简洁性更重要。运行这个函数它会返回最优的solution_path一个n行3列的矩阵每一行是一个状态和步数steps。4. 结果解析、可视化与方案输出找到路径只是第一步如何清晰、美观地呈现结果是数学建模报告和代码实践中同样重要的一环。4.1 解析最优路径运行上面的函数我们得到的最优解通常是11步即11次状态转移对应船来回划行11次。让我们写一个函数来把状态序列翻译成人类看得懂的步骤描述function describe_solution(path) fprintf(渡河方案共%d步\n, size(path,1)-1); fprintf(步骤\t左岸(商,仆)\t右岸(商,仆)\t船\t行动描述\n); fprintf(-----------------------------------------------------------------\n); for i 1:size(path, 1)-1 s1 path(i, :); % 当前状态 s2 path(i1, :); % 下一状态 % 计算船上的变化 if s1(3) 0 % 船从左边出发 boat_from 左; boat_to 右; delta_M s1(1) - s2(1); % 左岸减少的人数 delta_S s1(2) - s2(2); else % 船从右边出发 boat_from 右; boat_to 左; delta_M s2(1) - s1(1); % 左岸增加的人数即从右岸过来的人数 delta_S s2(2) - s1(2); end % 生成行动描述 action_desc ; if delta_M 0 action_desc [action_desc, sprintf(%d商, delta_M)]; end if delta_S 0 action_desc [action_desc, sprintf(%d仆, delta_S)]; end if isempty(action_desc) action_desc 空船; % 理论上不会发生因为船至少1人 else action_desc [action_desc, 人]; end action_desc sprintf(载%s从%s岸到%s岸, action_desc, boat_from, boat_to); % 输出 fprintf(%2d\t (%d, %d)\t\t (%d, %d)\t\t %s岸\t %s\n, ... i, s1(1), s1(2), 3-s1(1), 3-s1(2), boat_from, action_desc); end end调用这个函数你会得到一个清晰的表格类似下面这样具体步骤顺序可能因操作遍历顺序略有不同但步数一致渡河方案共11步 步骤 左岸(商,仆) 右岸(商,仆) 船 行动描述 ----------------------------------------------------------------- 1 (3, 3) (0, 0) 左岸 载2仆人从左岸到右岸 2 (3, 1) (0, 2) 右岸 载1仆人从右岸到左岸 3 (3, 2) (0, 1) 左岸 载2仆人从左岸到右岸 4 (3, 0) (0, 3) 右岸 载1仆人从右岸到左岸 5 (3, 1) (0, 2) 左岸 载2商人从左岸到右岸 6 (1, 1) (2, 2) 右岸 载1商1仆从右岸到左岸 ...4.2 状态转移图可视化“一图胜千言”。用图形展示状态空间和最优路径能极大提升模型的可理解性。Matlab的绘图功能很强我们可以画一个简单的状态转移图。function visualize_state_graph(solution_path) % 此函数绘制所有安全状态及最优路径 figure(Position, [100, 100, 1200, 600]); hold on; % 1. 生成并绘制所有安全状态节点 all_states []; for m 0:3 for s 0:3 for b 0:1 % 安全检查 left_safe (m 0) || (m s); right_safe ((3-m) 0) || ((3-m) (3-s)); if left_safe right_safe all_states [all_states; m, s, b]; end end end end % 为绘图将三维状态映射到二维平面。一个简单映射横坐标MS*0.3纵坐标B % 更直观的用两个子图分别表示船在左岸(B0)和船在右岸(B1)的状态 colors lines(7); % 使用不同的颜色 % 子图1船在左岸 (B0) subplot(1,2,1); title(船在左岸的安全状态 (B0)); xlabel(商人数量 (M)); ylabel(随从数量 (S)); axis([-0.5 3.5 -0.5 3.5]); grid on; hold on; states_B0 all_states(all_states(:,3)0, :); for i 1:size(states_B0,1) st states_B0(i,:); plot(st(1), st(2), o, MarkerSize, 15, LineWidth, 2, ... MarkerFaceColor, colors(mod(i,7)1,:)); text(st(1), st(2), sprintf((%d,%d), st(1), st(2)), ... HorizontalAlignment, center, FontWeight, bold); end % 子图2船在右岸 (B1) subplot(1,2,2); title(船在右岸的安全状态 (B1)); xlabel(商人数量 (M)); ylabel(随从数量 (S)); axis([-0.5 3.5 -0.5 3.5]); grid on; hold on; states_B1 all_states(all_states(:,3)1, :); for i 1:size(states_B1,1) st states_B1(i,:); plot(st(1), st(2), s, MarkerSize, 15, LineWidth, 2, ... MarkerFaceColor, colors(mod(i,7)1,:)); text(st(1), st(2), sprintf((%d,%d), st(1), st(2)), ... HorizontalAlignment, center, FontWeight, bold); end % 2. 在高亮最优路径需要更复杂的绘图这里简化为在命令行标注 fprintf(\n最优路径状态序列\n); for i 1:size(solution_path, 1) st solution_path(i, :); fprintf( - (%d, %d, %d), st(1), st(2), st(3)); end fprintf(\n); hold off; end这个可视化方案将船在不同位置的状态分开画在两个图上并用不同形状圆圈和方块区分非常清晰。你可以看到安全状态其实并不多这解释了为什么BFS能很快找到解。在实际建模论文中你可以用更专业的工具如Graphviz生成美观的状态转移有向图但用Matlab快速画出核心分布已经足够有说服力。4.3 扩展思考模型与算法的泛化“商人过河”本身是个小问题但我们的建模和求解过程具有高度的泛化性。你可以通过修改几个参数来研究不同规模的问题改变商人和随从的数量比如4对4、5对5。状态空间会呈指数增长但BFS依然有效只是计算时间变长。你可以观察步数增长规律。改变船的容量比如船能载3人。只需要修改operations数组增加[-3,0],[0,-3],[-2,-1],[-1,-2]等组合即可。增加其他约束比如要求船不能空驶回来即船上至少要有一个人这只需要在生成新状态时检查一下操作是否是非空的即可。尝试修改这些参数重新运行代码看看解的变化。这是培养建模思维和算法调试能力的绝佳练习。你会发现当人数增加到4对4时最优解步数不再是11步而可能是更多并且安全状态的分布规律也会发生变化。5. 从具体问题到建模思维那些我踩过的“坑”与心得最后分享几点我在教学和实践中总结的经验这些在标准教材或代码注释里往往不会写。第一坑对“安全状态”的理解偏差。最初我像很多人一样只记住了“左岸安全”的条件写代码时忘了检查右岸结果程序跑出了明显不合理的“解”比如某一岸随从多于商人。这个bug让我花了半小时才定位到。教训建模时一定要把每一个约束条件用数学语言无歧义地、完整地写下来并立刻转化为代码中的判断语句。条件语句的和||要特别小心。第二坑BFS中路径记录的效率与正确性。早期版本我尝试用一个全局的parent指针数组来记录每个状态的前驱状态最后回溯。这在理论上是更节省空间的做法。但在Matlab中处理三维状态到一维索引的映射以及回溯时重建路径代码变得复杂且容易出错。后来我改用直接存储路径矩阵的方式代码简洁了十倍对于这个规模的问题性能毫无影响。心得在Matlab中做算法原型有时“空间换时间或代码清晰度”是值得的尤其是在数据规模不大的情况下。先追求正确和清晰再考虑优化。第三坑操作遍历顺序影响输出。我们的operations数组定义了五种乘船组合。如果你改变它们的排列顺序比如把[-1,-1]放在最前面BFS搜索分支的顺序就会变最终找到的“第一条”最短路径的具体步骤序列也可能不同虽然步数一样。这可能会让初学者困惑以为程序有错。解释BFS保证找到的路径是最短的但最短路径可能不止一条。我们的算法找到的是“按给定操作顺序搜索时最先遇到的那一条”。这是完全正常的。如果你想验证可以尝试所有操作顺序的排列看看能找到多少种不同的11步解。给建模新手的建议把这个项目当作一个模板。下次遇到类似“状态转移”、“最优步骤”的问题比如“狼羊菜过河”、“汉诺塔”、“华容道”尝试套用这个框架1. 定义状态2. 定义合法操作状态转移3. 定义目标状态4. 选择搜索算法BFS求最短DFS求全部5. 实现并可视化。你会发现很多看似迥异的问题在建模层面是相通的。Matlab的强大之处在于它不仅能让你快速实现算法核心矩阵操作和循环足够高效还能让你用几行代码就做出不错的结果分析和可视化这对于在数学建模竞赛中快速验证想法、呈现结果至关重要。希望这个详细的拆解能帮你不仅“做出”这道题更“吃透”这一类题。