农夫过河问题

2026-03-24 暂无评论

全文共 495 字，阅读约 2 分钟

农夫过河问题

题目描述

一位农夫需要将猫、鸡、米从河的左岸运到右岸。

农夫有一条小船，但船每次只能载农夫本人加上一样东西。

限制条件

🐱🐔 猫和鸡不能单独待在一起（猫会吃鸡）
🐔🌾 鸡和米不能单独待在一起（鸡会吃米）
🐱🌾 猫和米可以单独待在一起（没有危险）

目标

找到一种安全的搬运顺序，使农夫、猫、鸡、米全部安全到达右岸。

初始状态

左岸：农夫 🧑、猫 🐱、鸡 🐔、米 🌾        右岸：（空）

目标状态

左岸：（空）        右岸：农夫 🧑、猫 🐱、鸡 🐔、米 🌾

规则说明

情况	是否允许
猫和鸡单独在同一岸	❌ 不允许
鸡和米单独在同一岸	❌ 不允许
猫和米单独在同一岸	✅ 允许
农夫单独过河	✅ 允许
农夫携带一样东西过河	✅ 允许
农夫一次携带多样东西	❌ 不允许

思考

最少需要几步才能完成？

Python 代码

# 猫 鸡 米 过河
# (人, 猫, 鸡, 米)
# 合法答案：(1, 1, 1, 1)
# 猫 不能跟 鸡，鸡 不能跟 米
# 左岸：0 右岸：1

from collections import deque

def is_safe(state):
    # 检查是否符合题意
    man, cat, chicken, rice = state
    # 人在左岸，猫和鸡不能在右岸，鸡和米不能在右岸
    if man == 0:
        if cat == chicken == 1: return False
        if chicken == rice == 1: return False
    else:
        if cat == chicken == 0: return False
        if chicken == rice == 0: return False
    return True

# 解
def solve():
    # 起始状态 目标状态
    start, target = (0, 0, 0, 0), (1, 1, 1, 1)
    q = deque([(start, [start])])
    vis = {start}

    while q:
        state, path = q.popleft()
        # 走到目标值
        if state == target: return path
        man, cat, chicken, rice = state
        # None表示单独 0-->猫 1-->鸡 2-->米
        for carry in [None, 0, 1, 2]:
            # 携带的物品
            items = [cat, chicken, rice]
            # 若人拿物品 --> 一次只能拿一个
            if carry is not None:
                # 如果物品位置与人的位置不同，无法拿取
                if items[carry] != man:
                    continue
                # 物品过河 0-->1 1-->0
                # 状态转移
                items[carry] = 1 - items[carry]
            # 人过河
            # 新状态
            new_state = (1 - man, items[0], items[1], items[2])
            # 没有走过的路径并且符合题意
            if new_state not in vis and is_safe(new_state):
                vis.add(new_state)
                q.append((new_state, path + [new_state]))
    return None

ans = solve()
i = 0
for i, x in enumerate(ans):
    if i == 0:
        print("初始状态：" + str(x))
    else:
        print(f"当前第{i}步：" + str(x))
print(f"一共用了：{i}步")

本题状态空间共 2^4 = 16 种，可利用 BFS 算法求解，也可借助离散数学中的图论方法建模。若使用图论，需将所有状态视为节点，枚举全部路径并剔除非法状态，再求从起点到终点的最短路径。

为什么选择 BFS 而非其他算法？
BFS 按层扩展，第一次到达目标状态时所经过的步数必然最少，因此能保证得到最优解。这正是它在最短路径问题中被广泛使用的原因。

具体实现时，每一步枚举农夫的四种选择（单独过河、带猫、带鸡、带米），对每种选择执行状态转移：

for carry in [None, 0, 1, 2]:
    items = [cat, chicken, rice]
    if carry is not None:
        if items[carry] != man:      # 物品不在同岸，无法携带
            continue
        items[carry] = 1 - items[carry]  # 物品随人过河，位置取反