企业官网建设流程全解析

数学建模之初等模型——商人过河问题（Matlab实现）

商人过河这个问题，从小学奥数到数学建模课堂，几乎是所有接触过离散模型的人绕不开的一道经典题。题面本身非常简单：三个商人带着三个仆人过河，船一次最多坐两个人，而当某一岸的仆人数多于商人数时，仆人就会抢走商人的货物。问题是怎么安排才能让所有人都安全过河。

如果只是把它当成脑筋急转弯，翻翻答案几分钟就能记住那套11步走法，但这道题放在"初等模型"这个章节里，真正要练的并不是那个答案，而是"从现实问题到数学状态，再到算法求解"的完整链条。今天我想用Matlab从零把这个过程完整跑一遍，把每一步建模思路、代码实现和踩过的坑都摊开讲。适合正在学数学建模、准备建模竞赛，或者单纯想了解怎么用程序解状态搜索题的朋友。

1. 题目本身与它背后的建模价值

先明确一下问题。三个商人A、B、C和三个仆人x、y、z要过河，河上有一条船，船一次最多载两人。规则是：无论在左岸还是右岸，任何时候只要仆人数量比商人数量多，商人就会被抢劫，问题就失败了。初始时六个人都在左岸，船也在左岸，目标是把所有人都运到右岸。

很多人第一次看到这个题，第一反应是"这就是个逻辑谜题嘛"，然后开始手工枚举。手工枚举确实能出来，而且你最终会发现最短需要11次单程渡河。但数学建模课的安排是有深意的：这道题被放在"初等模型"这个位置，恰恰因为它不涉及微积分、不涉及微分方程、不涉及复杂的数值计算，只需要离散数学里最基础的状态转移和搜索思想。换句话说，它是从"现实问题"过渡到"图论模型"的一座完美桥梁。

你可能会问，这种题在真实建模竞赛里有什么用？其实用处很大。很多实际问题，比如路径规划、任务调度、物流配送中的约束优化，本质上都是"状态空间搜索"——把每个时刻的局面抽象成一个状态，再在状态之间做合法转移，最后找到一条从初态到终态的路径。商人过河就是这一类问题的微型样板。你把它彻底搞明白之后，再去看那些复杂的规划问题，会感觉骨架是相似的。

这道题还有一层训练价值：它考验你的"约束提取"能力。题目里"仆人数多于商人数就危险"是一句自然语言，怎么把它变成计算机能判断的数学表达式，这是建模的第一步，也是最容易出错的一步。后面我会详细讲这个转化过程。

2. 建模过程：从自然语言到数学状态

2.1 状态设计：给局面拍一张照片

建模的第一步永远是确定状态怎么表示。我的做法是只关心左岸的情况，即用一个三元组表示一个局面：

(i, j, k)

其中 i 表示左岸商人数量，j 表示左岸仆人数量，k 表示船的位置。k=1 表示船在左岸，k=0 表示船在右岸。

为什么只需要左岸的信息？因为总人数固定是3个商人、3个仆人，右岸人数可以用总数减去左岸人数得到。比如左岸是 (2, 1)，右岸自然就是 (1, 2)。这是一个非常典型的"降维"思路，很多实际问题都能用这种减法减少状态变量的个数。

船的位置必须记录。没有 k 这一维，我们就不知道下一步船能往哪个方向走。船在左岸时，下一步只能从左岸载人出发到右岸；船在右岸时，下一步只能从右岸载人回到左岸。所以状态空间大小为 4 × 4 × 2 = 32 个节点，也就是左岸商人0到3四种可能、左岸仆人0到3四种可能、船位两种可能。

这32个状态里，并不是所有状态都合法。我们需要用安全约束去筛掉那些"商人会被抢劫"的局面。

2.2 安全约束的数学化表达

"某一岸仆人数多于商人数时危险"这句话，翻译成数学条件是：

• 左岸安全：i=0 或 i >= j。左岸没有商人时，不存在抢劫对象，安全；左岸有商人时，商人数量必须不少于仆人数量。
• 右岸安全：(3-i)=0 或 (3-i) >= (3-j)。右岸没有商人时安全；右岸有商人时，右岸商人数量(3-i)必须不少于右岸仆人数量(3-j)。

注意右岸的条件可以化简一下。(3-i) >= (3-j) 等价于 i <= j。所以最终合法状态需要同时满足：

• (i=0 或 i>=j) 且 (i=3 或 i<=j)

这个简化后的式子非常漂亮。你仔细想它的含义：左岸要么没商人，要么商人不少于仆人；右岸要么没商人，要么右岸商人不比仆人少。而"右岸商人不比仆人少"用左岸变量表达就是 i<=j。于是合法状态就限定在两类里：一类是 i=0 或 i=3 的"单边全空"状态，另一类是 i=j 的"人数平衡"状态。

我把所有合法状态列出来，一共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仆。

当船在左岸（k=1）时，从当前左岸状态 (i, j) 中减去船上的人数，得到新的左岸状态，船位变0。当船在右岸（k=0）时，从右岸"带回来"船上的人，相当于左岸人数增加，船位变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

注意这里我用了化简后的右岸安全条件 (i==3 || i<=j)。我之前强调过，右岸商人数 (3-i) 不小于右岸仆人数 (3-j)，等价于 i<=j。如果你在代码里直接写 (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(end+1) = nIdx; end end end if ~found error('未找到可行路径'); end

这里 p 表示船上商人数，q 表示船上仆人数。内层循环枚举了所有 p+q 在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(end+1) = 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 为什么步数一定是11

BFS的性质决定了第一次碰到的目标节点一定是距离起点最近的节点，所以输出的路径一定是最短的。但这个最短到底是多少，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 高频错误速查表

我在带朋友调试这个程序时，收集了一批高频问题，整理成表格供你参考。

其中"安全条件写反"是最隐蔽的错误。有一个很典型的写法错误是有人把右岸条件写成 (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脚本练习。它足够简单，能让新手专注理解状态搜索而不被复杂语法干扰；又足够完整，包含了状态编码、合法性判断、图搜索、路径回溯、结果校验这些在更大项目中都会用到的套路。把这套思路吃透，后面遇到再复杂的搜索题，你心里会有一个清晰的参照系。