商人们怎样安全过河

问题（智力游戏）

随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。
乘船渡河的方案由商人决定。
商人们怎样才能安全过河？

已知条件

  • 3名商人
  • 3名随从
  • 小船至多可载2人
  • 两岸均需满足：随从人数 ≤ 商人人数（若某岸商人人数为0，则随从人数可任意）

问题分析

这是一个多步决策过程：

  • 决策：每一步（此岸到彼岸或彼岸到此岸）船上的人员。
  • 要求：在安全的前提下（两岸的随从数不比商人多），经有限步使全体人员过河。

建模过程

我们利用DFS和BFS来进行数学建模，用DFS找出所有的符合题意且合法的状态，再利用BFS找出最短路径（图论），在BFS中记录从起点到终点的路径，一种合法的路径 --> 之前的路径，利用哈希表记录。

设置状态 (左岸商人, 左岸随从, 船的方向)
设置起点 (3, 3, '左')
设置终点 (0, 0, '右')

在遍历到目标的时候，执行函数ok，还原路径。

代码

# (左岸商人, 左岸随从, 船位置)
# (m_left, c_left, boat)
# 目标：(0, 0, '右')
import sys
from collections import deque
sys.setrecursionlimit(10000)

# 检测是否符合题意
def check(m_left, c_left):
    m_right = 3 - m_left
    c_right = 3 - c_left

    # 左岸
    if 0 < m_left < c_left:
        return False

    # 右岸
    if 0 < m_right < c_right:
        return False

    return True

# 随从可以单独过河
# 列举所有状态
res = []

# 访问标记
vis = set()

"""
深度优先搜索部分
"""

def dfs(m_left, c_left, boat):
    state = (m_left, c_left, boat)
    if state in vis:
        return
    if not check(m_left, c_left):
        return
    vis.add(state)
    res.append(state)
    for m, c in [(1, 0), (0, 1), (1, 1), (2, 0), (0, 2)]:
        if boat == '左':
            new_m = m_left - m
            new_c = c_left - c
            new_boat = '右'
        else:
            new_m = m_left + m
            new_c = c_left + c
            new_boat = '左'
        # 排除非法情况
        if 0 <= new_m <= 3 and 0 <= new_c <= 3:
            dfs(new_m, new_c, new_boat)

# 获取所有状态
dfs(3, 3, '左')
print("所有合法状态：")
print(res)
print("开始寻找最短路径（BFS）......")

"""
广度优先搜索部分
"""
# BFS
res_set = set(res)
ans = []
vis.clear()
parent = {}

def ok():
    path = []
    cur = (0, 0, '右')
    while cur != (3, 3, '左'):
        path.append(cur)
        cur = parent[cur]
    path.append((3, 3, '左'))
    path.reverse()
    print("最短路径：")
    for p in path:
        print(p)

q = deque([(3, 3, '左')])
vis.add((3, 3, '左'))

while q:
    cur = q.popleft()
    m_left, c_left, boat = cur
    if m_left == 0 and c_left == 0 and boat == '右':
        ok()
        break
    for m, c in [(1, 0), (0, 1), (1, 1), (2, 0), (0, 2)]:
        if boat == '左':
            new_m = m_left - m
            new_c = c_left - c
            new_boat = '右'
        else:
            new_m = m_left + m
            new_c = c_left + c
            new_boat = '左'
        if 0 <= new_m <= 3 and 0 <= new_c <= 3:
            nxt = (new_m, new_c, new_boat)
            if nxt in res_set and nxt not in vis:
                vis.add(nxt)
                parent[nxt] = cur
                q.append(nxt)

输出

所有合法状态：
[(3, 3, '左'), (3, 2, '右'), (2, 2, '右'), (3, 2, '左'), (3, 1, '右'), (3, 0, '右'), (3, 1, '左'), (1, 1, '右'), (2, 2, '左'), (0, 2, '右'), (0, 3, '左'), (0, 1, '右'), (1, 1, '左'), (0, 0, '右'), (0, 1, '左'), (0, 2, '左')]
开始寻找最短路径（BFS）......
最短路径：
(3, 3, '左')
(2, 2, '右')
(3, 2, '左')
(3, 0, '右')
(3, 1, '左')
(1, 1, '右')
(2, 2, '左')
(0, 2, '右')
(0, 3, '左')
(0, 1, '右')
(1, 1, '左')
(0, 0, '右')

因此所有的合法状态得出：

(3, 3, '左') (3, 2, '右') (2, 2, '右') (3, 2, '左')
(3, 1, '右') (3, 0, '右') (3, 1, '左') (1, 1, '右')
(2, 2, '左') (0, 2, '右') (0, 3, '左') (0, 1, '右')
(1, 1, '左') (0, 0, '右') (0, 1, '左') (0, 2, '左')

最短的合法路径：

(3, 3, '左') → (2, 2, '右') → (3, 2, '左') → (3, 0, '右') → 

 → (3, 1, '左') → (1, 1, '右') → (2, 2, '左') → (0, 2, '右') → 

 → (0, 3, '左') → (0, 1, '右') → (1, 1, '左') → (0, 0, '右')

最终结论

一共需要11趟
过河过程（共 11 步）：

1 商 1 从过河  
1 商返回  
2 从过河  
1 从返回  
2 商过河  
1 商 1 从返回  
2 商过河  
1 从返回  
2 从过河  
1 商 1 从返回  
1 商 1 从过河

完成，全部过河。