⛵ 商人过河 · 数学模型可视化

3 个商人 + 3 个仆人 · 一只小船 · 11 步最优解 · 完整动画演示

#经典数学题 #状态空间搜索 #BFS最优解

速度

步骤 0 / 11 起点

👥 角色图例

商人 ×3 紫袍金边 · 头戴宝石冠

仆人 ×3 青衣短打 · 头系橙巾

木船 ×1 最多载 2 人 · 需人划桨

⚠️ 游戏规则

① 船每次最多载 2 人，至少 1 人 划船

② 任何一岸，若有商人在场，仆人不能多于商人

③ 目标：所有 6 人安全渡河至右岸

📍 当前状态

左岸商人3

左岸仆人3

右岸商人0

右岸仆人0

船的位置左岸

💡 本步说明

起始状态：3 个商人和 3 个仆人都在左岸，需要全部安全渡到右岸。

📜 11 步最优解

📐 数学模型完整讲解

从问题描述到状态空间搜索，一步看懂商人过河的最优解

1 问题描述

3 个商人带着 3 个仆人要乘小船渡河。小船每次最多容纳 2 人，必须有人划船。

核心约束：在任何一岸，只要有商人在场，仆人的数量不能多于商人，否则商人会被仆人加害。

目标：找到让所有 6 个人都安全到达对岸的最少渡河方案。

2 状态空间表示

用三元组 S = (m, s, b) 表示状态：

m：左岸商人数 (0~3)
s：左岸仆人数 (0~3)
b：船的位置，1 = 左岸，0 = 右岸

起点 S₀ = (3, 3, 1) → 终点 Sₑ = (0, 0, 0)

状态空间共 4×4×2 = 32 种，其中合法的安全状态仅有 16 种。

3 约束与可行决策

合法状态条件：

(m = 0 或 m ≥ s) 且 (3−m = 0 或 3−m ≥ 3−s)

每次乘船决策 d = (dm, ds)，满足 1 ≤ dm + ds ≤ 2，共 5 种：

(1,0) 1 商人过河
(2,0) 2 商人过河
(0,1) 1 仆人过河
(0,2) 2 仆人过河
(1,1) 1 商 1 仆过河

4 求解算法：BFS

由于状态空间很小，使用 广度优先搜索 可在毫秒内找到最优解：

          queue ← [S₀]

          while queue 非空:

            s ← queue.pop()

            if s = Sₑ: 返回路径

            for 每个合法决策 d:

              s' ← transit(s, d)

              if s' 合法且未访问: queue.push(s')

得到的最优解 = 11 步，是该问题的理论下界。

📊 最优解步骤表

步	方向	乘船人	左岸(商,仆)	右岸(商,仆)	船