★ FEATURED ARTICLE 数学建模之初等模型——商人过河问题Matlab实现商人过河这个问题从小学奥数到数学建模课堂几乎是所有接触过离散模型的人绕不开的一道经典题。题面本身非常简单三个商人带着三个仆人过河船一次最多坐两个人而当某一岸的仆人数多于商人数时仆人就会抢走商人的货物。问题是怎么安排才能让所有人都安全过河。如果只是把它当成脑筋急转弯翻翻答案几分钟就能记住那套11步走法但这道题放在初等模型这个章节里真正要练的并不是那个答案而是从现实问题到数学状态再到算法求解的完整链条。今天我想用Matlab从零把这个过程完整跑一遍把每一步建模思路、代码实现和踩过的坑都摊开讲。适合正在学数学建模、准备建模竞赛或者单纯想了解怎么用程序解状态搜索题的朋友。1. 题目本身与它背后的建模价值先明确一下问题。三个商人A、B、C和三个仆人x、y、z要过河河上有一条船船一次最多载两人。规则是无论在左岸还是右岸任何时候只要仆人数量比商人数量多商人就会被抢劫问题就失败了。初始时六个人都在左岸船也在左岸目标是把所有人都运到右岸。很多人第一次看到这个题第一反应是这就是个逻辑谜题嘛然后开始手工枚举。手工枚举确实能出来而且你最终会发现最短需要11次单程渡河。但数学建模课的安排是有深意的这道题被放在初等模型这个位置恰恰因为它不涉及微积分、不涉及微分方程、不涉及复杂的数值计算只需要离散数学里最基础的状态转移和搜索思想。换句话说它是从现实问题过渡到图论模型的一座完美桥梁。你可能会问这种题在真实建模竞赛里有什么用其实用处很大。很多实际问题比如路径规划、任务调度、物流配送中的约束优化本质上都是状态空间搜索——把每个时刻的局面抽象成一个状态再在状态之间做合法转移最后找到一条从初态到终态的路径。商人过河就是这一类问题的微型样板。你把它彻底搞明白之后再去看那些复杂的规划问题会感觉骨架是相似的。这道题还有一层训练价值它考验你的约束提取能力。题目里仆人数多于商人数就危险是一句自然语言怎么把它变成计算机能判断的数学表达式这是建模的第一步也是最容易出错的一步。后面我会详细讲这个转化过程。2. 建模过程从自然语言到数学状态2.1 状态设计给局面拍一张照片建模的第一步永远是确定状态怎么表示。我的做法是只关心左岸的情况即用一个三元组表示一个局面(i, j, k)其中 i 表示左岸商人数量j 表示左岸仆人数量k 表示船的位置。k1 表示船在左岸k0 表示船在右岸。为什么只需要左岸的信息因为总人数固定是3个商人、3个仆人右岸人数可以用总数减去左岸人数得到。比如左岸是 (2, 1)右岸自然就是 (1, 2)。这是一个非常典型的降维思路很多实际问题都能用这种减法减少状态变量的个数。船的位置必须记录。没有 k 这一维我们就不知道下一步船能往哪个方向走。船在左岸时下一步只能从左岸载人出发到右岸船在右岸时下一步只能从右岸载人回到左岸。所以状态空间大小为 4 × 4 × 2 32 个节点也就是左岸商人0到3四种可能、左岸仆人0到3四种可能、船位两种可能。这32个状态里并不是所有状态都合法。我们需要用安全约束去筛掉那些商人会被抢劫的局面。2.2 安全约束的数学化表达某一岸仆人数多于商人数时危险这句话翻译成数学条件是左岸安全i0 或 i j。左岸没有商人时不存在抢劫对象安全左岸有商人时商人数量必须不少于仆人数量。右岸安全(3-i)0 或 (3-i) (3-j)。右岸没有商人时安全右岸有商人时右岸商人数量(3-i)必须不少于右岸仆人数量(3-j)。注意右岸的条件可以化简一下。(3-i) (3-j) 等价于 i j。所以最终合法状态需要同时满足(i0 或 ij) 且 (i3 或 ij)这个简化后的式子非常漂亮。你仔细想它的含义左岸要么没商人要么商人不少于仆人右岸要么没商人要么右岸商人不比仆人少。而右岸商人不比仆人少用左岸变量表达就是 ij。于是合法状态就限定在两类里一类是 i0 或 i3 的单边全空状态另一类是 ij 的人数平衡状态。我把所有合法状态列出来一共20个格式(左岸商人数, 左岸仆人数, 船位1左0右) (0,0,0) (0,0,1) (0,1,0) (0,1,1) (0,2,0) (0,2,1) (0,3,0) (0,3,1) (1,1,0) (1,1,1) (2,2,0) (2,2,1) (3,0,0) (3,0,1) (3,1,0) (3,1,1) (3,2,0) (3,2,1) (3,3,0) (3,3,1)这个清单是你调试程序时的黄金参考。如果你实现的代码跑出来的合法状态不是20个说明安全条件写错了不要继续往下做先把这个数对上再说。2.3 状态转移规则船怎么动有了状态定义接下来定义转移。从一个状态出发船只能朝一个方向移动。船上的人可以是一名或两名可以是任意组合商人、仆人、或一商一仆。我把船上可能的组合枚举成五种1商0仆、0商1仆、2商0仆、0商2仆、1商1仆。当船在左岸k1时从当前左岸状态 (i, j) 中减去船上的人数得到新的左岸状态船位变0。当船在右岸k0时从右岸带回来船上的人相当于左岸人数增加船位变1。判断一条转移是否合法需要检查三件事第一新状态的人数不能为负、不能超过3第二新状态必须落在上面那20个合法状态里第三这个状态之前没有被访问过。前两条保证物理上可能且安全第三条保证搜索不会绕圈子。你可能会注意到我自始至终没有记录船上是谁作为状态的一部分。因为船位确定以后船上的人是从船所在的那一岸上船的它是转移动作的属性而不是局面的属性。初学者最容易犯的错误就是把问题建模复杂比如试图把船上的人、左岸的人、右岸的人全都记下来结果状态维度爆炸。保持状态最小的原则是建模的基本功。3. 求解算法为什么BFS是这个题的天然选择3.1 从状态图到最短路径状态空间建好之后问题就变成一个标准的图搜索问题在一个有向图里从起点节点 (3,3,1) 走到终点节点 (0,0,0)每条边的代价都是1次渡河要求总代价最小。为什么用BFS而不是DFS因为BFS是逐层扩展的从起点出发先扩展所有一步能到达的节点再扩展两步能到达的节点。因此当BFS第一次到达目标节点时走的步数必然是最少的。DFS虽然也能找到一条路径但它不能保证最短在这个题目里DFS可能会一头扎进很长的无效分支里白白浪费很多时间。BFS的直观逻辑很好理解把起点放入队列然后不断从队首取出节点扩展出所有合法的、未访问过的邻居节点放入队尾直到取出的节点是终点。因为状态空间只有32个节点合法节点只有20个BFS跑起来是瞬间完成的事情根本不需要任何高级优化。3.2 为什么必须做已访问标记这是新手最容易踩的坑。如果不记录哪些节点已经被访问过BFS会怎样从一个状态出发经常能回到之前的状态。比如 (3,3,1) 出发可以到 (2,2,0)从 (2,2,0) 又可以带两个人回到 (3,3,1)。如果允许反复进出同一个节点搜索就会在几个状态之间打转程序会陷入无限循环永远跑不完。解决办法是维护一个 visited 数组在节点第一次入队时就标记为已访问后续再遇到直接跳过。这里有一个细节标记必须发生在入队时而不是出队时。如果等到节点出队才标记队列里可能会存在大量重复节点虽然最终也能搜完但效率会差很多。对于这个题目差异不大但在更大的状态空间里这是性能瓶颈之一。3.3 路径回溯从终点反推起点BFS只负责找到目标节点它不直接给出路径。我们需要在搜索过程中记录每个节点的父节点。当找到终点节点后从终点出发不断沿着父指针往回找一直找到起点再把这一串节点反过来排列就是完整的路径。这个反向回溯的思路非常通用几乎所有最短路径算法都用它。在实现上只需要一个 parent 数组长度和状态总数一样初始化为0扩展节点时把父节点索引存进去。4. Matlab完整实现可以直接跑的代码4.1 状态编码与合法状态表生成在Matlab里我建议不要用字符串或 containers.Map 来管理状态直接用线性编码最省事。因为 (i, j, k) 三个变量的范围很小可以用一个公式映射到1到32的整数索引stateIdx (i,j,k) i*8 j*2 k 1;这个公式的原理是把 i 当成高位j 当中间位k 当低位形成一个二进制混合编码。解码的时候逆向操作c idx - 1; i floor(c / 8); j floor(mod(c, 8) / 2); k mod(c, 2);为什么要做编码因为数组下标必须从1开始而且一维数组比多维数组在记录 visited、parent 时更方便。另外这种编码方式让查一个状态是否合法变成查一个布尔数组时间复杂度O(1)。生成合法状态表就是一个三重循环legal false(32, 1); for i 0:3 for j 0:3 leftSafe (i 0) || (i j); rightSafe (i 3) || (i j); if leftSafe rightSafe for k 0:1 legal(stateIdx(i,j,k)) true; end end end end注意这里我用了化简后的右岸安全条件 (i3 || ij)。我之前强调过右岸商人数 (3-i) 不小于右岸仆人数 (3-j)等价于 ij。如果你在代码里直接写 (3-i) (3-j)逻辑也是对的但容易把变量弄混所以我建议用化简形式干净利落。4.2 BFS主循环实现BFS主体用数组模拟队列。Matlab数组动态追加的性能虽然一般但这个题目里队列长度撑死不超过20完全无所谓。startIdx stateIdx(3,3,1); targetIdx stateIdx(0,0,0); queue startIdx; head 1; visited false(32, 1); visited(startIdx) true; parent zeros(32, 1); found false; while head length(queue) curIdx queue(head); head head 1; if curIdx targetIdx found true; break; end c curIdx - 1; ci floor(c / 8); cj floor(mod(c, 8) / 2); ck mod(c, 2); for p 0:2 for q 0:2 if p q 1 || p q 2 continue; end if ck 1 ni ci - p; nj cj - q; nk 0; else ni ci p; nj cj q; nk 1; end if ni 0 || ni 3 || nj 0 || nj 3 continue; end nIdx stateIdx(ni,nj,nk); if ~legal(nIdx) || visited(nIdx) continue; end visited(nIdx) true; parent(nIdx) curIdx; queue(end1) nIdx; end end end if ~found error(未找到可行路径); end这里 p 表示船上商人数q 表示船上仆人数。内层循环枚举了所有 pq 在1到2之间的组合其实就是前面说的五种情况。这个写法比手写五条判断更通用以后想改船容量只要调整循环上界就行。判断新状态是否越界只检查 ni 和 nj 的范围就够了。因为右岸人数分别为 (3-ni) 和 (3-nj)只要 ni∈[0,3]、nj∈[0,3]右岸人数自动落在合法范围里。这也是用减法表达状态的便利之处。4.3 路径回溯与结果打印找到终点后沿着 parent 数组回溯并打印路径pathIdx []; cur targetIdx; while cur ~ 0 pathIdx [cur, pathIdx]; cur parent(cur); end fprintf(初始状态左岸(3,3)船在左岸\n\n); for t 1:length(pathIdx) c pathIdx(t) - 1; i floor(c / 8); j floor(mod(c, 8) / 2); k mod(c, 2); side 左岸; if k 0 side 右岸; end if t 1 fprintf(起点\t\t左岸(%d,%d)船在%s\n, i, j, side); else pc pathIdx(t-1) - 1; pi floor(pc / 8); pj floor(mod(pc, 8) / 2); pk mod(pc, 2); if pk 1 mi pi - i; mj pj - j; dirStr 左岸 - 右岸; else mi i - pi; mj j - pj; dirStr 右岸 - 左岸; end fprintf(第%d步\t%d商%d仆 %s\t左岸(%d,%d)船在%s\n, ... t-1, mi, mj, dirStr, i, j, side); end end回溯时用一个 while 循环从终点一路找 parent直到 parent 为0起点。这里需要理解起点的 parent 初始化为0所以回溯到起点就自然停止。pathIdx 构建时采用头插法最后得到的顺序就是起点到终点。打印动作描述时根据父节点船位判断本步方向。如果父节点船在左岸那么这一步是从左到右船上人数等于父节点左岸人数减去当前左岸人数如果父节点船在右岸那么这一步是从右回左船上人数等于当前左岸人数减去父节点左岸人数。4.4 完整代码汇总把上面几段拼在一起就是一个完整的脚本。我建议你直接复制跑一遍跑通之后再逐段改着玩。%% 商人过河问题 BFS 求解 clear; clc; stateIdx (i,j,k) i*8 j*2 k 1; % 合法状态表 legal false(32, 1); for i 0:3 for j 0:3 leftSafe (i 0) || (i j); rightSafe (i 3) || (i j); if leftSafe rightSafe for k 0:1 legal(stateIdx(i,j,k)) true; end end end end startIdx stateIdx(3,3,1); targetIdx stateIdx(0,0,0); queue startIdx; head 1; visited false(32, 1); visited(startIdx) true; parent zeros(32, 1); found false; while head length(queue) curIdx queue(head); head head 1; if curIdx targetIdx found true; break; end c curIdx - 1; ci floor(c / 8); cj floor(mod(c, 8) / 2); ck mod(c, 2); for p 0:2 for q 0:2 if p q 1 || p q 2 continue; end if ck 1 ni ci - p; nj cj - q; nk 0; else ni ci p; nj cj q; nk 1; end if ni 0 || ni 3 || nj 0 || nj 3 continue; end nIdx stateIdx(ni,nj,nk); if ~legal(nIdx) || visited(nIdx) continue; end visited(nIdx) true; parent(nIdx) curIdx; queue(end1) nIdx; end end end if ~found error(未找到可行路径); end % 回溯路径 pathIdx []; cur targetIdx; while cur ~ 0 pathIdx [cur, pathIdx]; cur parent(cur); end % 打印路径 fprintf(初始状态左岸(3,3)船在左岸\n\n); for t 1:length(pathIdx) c pathIdx(t) - 1; i floor(c / 8); j floor(mod(c, 8) / 2); k mod(c, 2); side 左岸; if k 0 side 右岸; end if t 1 fprintf(起点\t\t左岸(%d,%d)船在%s\n, i, j, side); else pc pathIdx(t-1) - 1; pi floor(pc / 8); pj floor(mod(pc, 8) / 2); pk mod(pc, 2); if pk 1 mi pi - i; mj pj - j; dirStr 左岸 - 右岸; else mi i - pi; mj j - pj; dirStr 右岸 - 左岸; end fprintf(第%d步\t%d商%d仆 %s\t左岸(%d,%d)船在%s\n, ... t-1, mi, mj, dirStr, i, j, side); end end运行这段代码你会在命令窗口看到一条完整的最短路径。整个脚本不到100行没有用任何工具箱Matlab基础版本就能跑。5. 运行结果与验证5.1 程序输出的最短路径我本地运行上面这段代码得到的结果如下你运行输出的路径可能和我展示的略有不同取决于邻居枚举顺序但步数一定是11次单程渡河初始状态左岸(3,3)船在左岸 起点 左岸(3,3)船在左岸 第1步 0商2仆 左岸 - 右岸 左岸(3,1)船在右岸 第2步 0商1仆 右岸 - 左岸 左岸(3,2)船在左岸 第3步 0商2仆 左岸 - 右岸 左岸(3,0)船在右岸 第4步 0商1仆 右岸 - 左岸 左岸(3,1)船在左岸 第5步 2商0仆 左岸 - 右岸 左岸(1,1)船在右岸 第6步 1商1仆 右岸 - 左岸 左岸(2,2)船在左岸 第7步 2商0仆 左岸 - 右岸 左岸(0,2)船在右岸 第8步 0商1仆 右岸 - 左岸 左岸(0,3)船在左岸 第9步 0商2仆 左岸 - 右岸 左岸(0,1)船在右岸 第10步 0商1仆 右岸 - 左岸 左岸(0,2)船在左岸 第11步 0商2仆 左岸 - 右岸 左岸(0,0)船在右岸这条路径非常经典。前四步先把三个仆人全部运到右岸再运一个仆人回来保证左岸始终有超过仆人数的商人中间两步完成两个商人的过河再用一商一仆回来平衡局面最后三步把剩余人员全部送过去。5.2 为什么步数一定是11BFS的性质决定了第一次碰到的目标节点一定是距离起点最近的节点所以输出的路径一定是最短的。但这个最短到底是多少BFS不会预先告诉你它只是保证自己找到的就是最短的。手工验证11步是下界其实不容易但你可以在程序结果里观察到每一步之后左岸状态都是合法状态没有出现任何仆人数多于商人数的局面。逐行检查上面每一步的左岸数据你会发现安全条件全部满足。比如第5步之后左岸是(1,1)右岸是(2,2)两岸都是人数平衡状态第7步之后左岸是(0,2)左岸没商人所以安全右岸是(3,1)商人3大于仆人1安全。注意如果你的程序输出的路径不是11步那一定是哪里出了问题。最常见的情况是 visited 标记写错比如不小心把已访问状态又放回队列会导致搜索退化但一般不会变长更可能的是你的邻居扩展写错了漏掉了某些合法转移导致路径绕远。5.3 加一段自动安全校验为了保险起见还可以在程序末尾加上一段自动校验验证路径上的每个状态都是合法的以及每一步转移都符合规则。这个习惯非常好很多实际项目里对拍和断言是保证代码正确性的重要手段。%% 安全校验 for t 1:length(pathIdx) c pathIdx(t) - 1; i floor(c / 8); j floor(mod(c, 8) / 2); k mod(c, 2); leftSafe (i 0) || (i j); rightSafe (i 3) || (i j); if ~(leftSafe rightSafe) error(路径第%d个状态不合法, t); end end fprintf(\n路径安全校验通过\n);这段校验相当于给程序上了一道保险。以后你把这个框架改造成其他状态搜索问题时这套生成状态表 BFS 回溯 校验的流程可以原样复用。6. 常见问题与排查经验6.1 高频错误速查表我在带朋友调试这个程序时收集了一批高频问题整理成表格供你参考。现象可能原因排查方法程序卡死不退出没有做已访问标记或标记写错检查 visited 是否在入队时置true找不到任何路径合法状态表生成错误打印合法状态数量核对是否等于20路径中包含非法状态安全条件写反了方向重点检查右岸安全条件的推导输出路径步数很长邻居枚举顺序导致绕路改用BFS并确认逐层扩展报错下标越界状态编码和解码不对称用起点和终点索引做单步测试输出中出现5个人在左岸越界检查漏写检查 ni3、nj3 是否覆盖两个变量其中安全条件写反是最隐蔽的错误。有一个很典型的写法错误是有人把右岸条件写成 (3-i) (3-j)但在某个分支里用的是左岸变量结果条件变成 i j 却在代码里写成了 i j直接导致合法状态全部错位。我的建议是安全条件单独写成一个函数或者独立段落加注释标明每个变量的含义先手工推导一遍再写代码。6.2 调试小技巧从小规模开始测我调试这类状态搜索程序有一个习惯先做小规模验证再做完整规模。比如你可以临时把问题改成2个商人2个仆人初始状态 (2,2,1)目标 (0,0,0)。2商2仆船容量2的最短路径是5步很容易手工验证。如果小规模能跑通再改回3商3仆大概率也不会出错。另一种快速定位的方法是在 BFS 主循环里加打印输出当前出队的节点和它扩展出的邻居。比如在第20行左右加fprintf(扩展节点 (%d,%d,%d) - , ci, cj, ck);注意观察每个节点扩展出的邻居是否都满足状态范围和安全条件。一旦发现某个邻居状态不合法立刻就能定位是转移逻辑的问题还是合法状态表的问题。6.3 扩展方向从经典题到通用框架这个BFS框架改造成本很低稍微改几个参数就能解决一批类似问题。第一改成N个商人N个仆人。只需要把代码里的3全部替换成N同时调整 stateIdx 编码公式和循环上界。不过要注意当N大于3时船容量2可能无解。这是一个经典的结论你可以跑跑看观察程序输出未找到可行路径的情况。第二改成求解所有最短路径方案。BFS只保证找出一条最短路径但如果想统计一共有多少条最短路径可以在BFS过程中不打断而是记录到达每个节点的最短距离最后用回溯计数。对于这个20个节点的图方案总数是个很有意思的数字。第三用图论视角可视化。把20个合法节点和它们之间的转移画出来你会发现整个状态图是一个有向图从 (3,3,1) 到 (0,0,0) 的路径关系清晰可见。Matlab里可以用 graph 对象配合 plot 把状态转移图可视化这对理解问题结构帮助很大。第四改造为其他经典过河问题。人狼羊菜过河、传教士与食人族问题、家庭过桥问题本质上都是状态搜索。区别只在于状态维度和约束条件不同。比如人狼羊菜需要用四个布尔量表示人和动物的位置约束条件是狼和羊不能单独在一起、羊和菜不能单独在一起。你只要重新定义状态和解码逻辑BFS框架完全不用改。最后再分享一点个人体会我每次给人讲这个题都会强调状态设计比算法更重要。很多初学者上来就抱着DFS或者BFS的模板套结果状态没设计好代码写得痛苦不堪。实际上当你把 (i,j,k) 这个三元组想清楚、把安全条件推导明白剩下的事情都是顺水推舟。还有一个小经验这个问题的代码实现非常适合作为Matlab脚本练习。它足够简单能让新手专注理解状态搜索而不被复杂语法干扰又足够完整包含了状态编码、合法性判断、图搜索、路径回溯、结果校验这些在更大项目中都会用到的套路。把这套思路吃透后面遇到再复杂的搜索题你心里会有一个清晰的参照系。
阅读完成 · 觉得有帮助？
