1 题目
一农夫带着一头狼，一只羊和一担草过河，小船只能一次装载农夫和一样货物，狼会吃羊，羊会吃草，只有农夫在时才安全。现欲让所有物品包括农夫都安全过道河对岸，使用程序实现求解。

2 设计分析
把农夫、狼、羊、草四个按顺序「农夫、狼、羊、草」排列，使用一个布尔数组表示它们的状态，布尔值状态 false 代表对应的人（物）还没有过河，状态 true 代表对应人（物）已经过河了。使用布尔值有个好处，就是当前状态，取反即可得到是过河对面的状态（不管原来是否过河）。

可知初始状态时候它们是：
status[4] = [false, false, false, false]
最终过河后它们的状态应该是[true, true, true, true]

用status[4]数组的一次状态变化前后表示渡河情况，则渡河规则对应成计算机逻辑为：
1）每次过河时候，都需要农夫参与——每次状态改变时候，第0位(注：0下标开始算)必须改变；
2）每次过河只能带一样物品，而且需要农夫来撑船——每次改变时候，第1、2、3位最多只能改变其中1位，变化位情况必须和第0位同步；
3）狼、羊、草三个中， 某一个为另一个食物时候，必须有农夫在场才安全——每次改变后，第1、2、3位中相邻如果相同，则必须和第0位相同。

根据这规则，使用数组作为当前状态根节点，生成了后续所有状态，再对后续的情况再做情况枚举，便可得到一棵数形状态结构：

这棵树中，第3层的右侧那个状态（也就是农夫带羊过去后，再带羊回来）出现和根部结果一样，那么就可以不继续生成其子数了。其他的节点（如第4层最右边的状态），如果出现和父辈某一个节点一样，也是不需要再继续生成（遍历）子树了，因为此状态生成的后续情况必然和之前的状态出现重复局面了。

3 编码

先上流程图：

根据规则，判断一个状态是否是安全的（合法的）——一物为另一物的食物时候，如果它们在河的同一侧，则必须要有农夫在才安全。代码逻辑就是如下了（python代码）：

def is_valid_status(status):
    if status[1] == status[2]:
        if status[0] != status[1]:
            # 狼和羊同侧，没有人在场
            return False

    if status[2] == status[3]:
        if status[0] != status[2]:
            # 羊和草同侧，没有人在场
            return False

    return True

在当前状态，枚举生成下一个状态的所有情况，也就是下一步渡河的所有可行情况。对一个状态取反即是渡河，不管是过去还是回来都是一样——取反即可。代码逻辑如下：

def create_all_next_status(status):
    next_status_list = []

    for i in range(0, 4):
        if status[0] != status[i]: # 和农夫不同一侧？
            continue

        next_status = [status[0],status[1],status[2],status[3]]
        # 农夫和其中一个过河，i 为 0 时候，农夫自己过河。
        next_status[0] = not next_status[0]
        next_status[i] = next_status[0] # 和农夫一起过河

        if is_valid_status(next_status):
            next_status_list.append(next_status)

    return next_status_list

 

树形递归遍历逻辑代码步骤大概如下，
1）在根据当前状态，生成所有下一种状态的所有情况，
2）对生成的状态所有情况进行遍历判断，
（1）如果下一个状态是最终期望状态（都过河了），则输出当前路径结果，
（2）如果下一个状态已经出现过在历史中，则无视，
（3）如果下一个状态是新的状态，把该状态记录到历史中，递归进入步骤1。

搜索代码就是如下了，也就是树形递归遍历逻辑的中心思想（题外话：棋类游戏的递归遍历逻辑也是类似）：

def search(history_status):
    global scheme_count
    current_status = history_status[len(history_status) - 1]

    next_status_list = create_all_next_status(current_status)
    for next_status in next_status_list:
        if next_status in history_status:
            # 出现重复的情况了
            continue

        history_status.append(next_status)

        if is_done(next_status):
            scheme_count += 1
            print("scheme " + str(scheme_count) + ":")
            print_history_status(history_status)
        else:
            search(history_status)

        history_status.pop()

判断是否都过河了，更加简单：

def is_done(status):
    return status[0] and status[1] and status[2] and status[3]

 

完整代码如下：

#-*- coding: UTF-8 -*-

name = ["farmer", "wolf", "sheep", "grass"]
scheme_count = 0

# 完成局面
def is_done(status):
    return status[0] and status[1] and status[2] and status[3]

# 生成下一个局面的所有情况
def create_all_next_status(status):
    next_status_list = []

    for i in range(0, 4):
        if status[0] != status[i]: # 和农夫不同一侧？
            continue

        next_status = [status[0],status[1],status[2],status[3]]
        # 农夫和其中一个过河，i 为 0 时候，农夫自己过河。
        next_status[0] = not next_status[0]
        next_status[i] = next_status[0] # 和农夫一起过河

        if is_valid_status(next_status):
            next_status_list.append(next_status)

    return next_status_list

# 判断是否合法的局面
def is_valid_status(status):
    if status[1] == status[2]:
        if status[0] != status[1]:
            # 狼和羊同侧，没有人在场
            return False

    if status[2] == status[3]:
        if status[0] != status[2]:
            # 羊和草同侧，没有人在场
            return False

    return True

def search(history_status):
    global scheme_count
    current_status = history_status[len(history_status) - 1]

    next_status_list = create_all_next_status(current_status)
    for next_status in next_status_list:
        if next_status in history_status:
            # 出现重复的情况了
            continue

        history_status.append(next_status)

        if is_done(next_status):
            scheme_count += 1
            print("scheme " + str(scheme_count) + ":")
            print_history_status(history_status)
        else:
            search(history_status)

        history_status.pop()

def readable_status(status, is_across):
    result = ""
    for i in range(0,4):
        if status[i] == is_across:
            if len(result) != 0:
                result += ","
            result += name[i]

    return "[" + result + "]"

#打印结果
def print_history_status(history_status):
    for status in history_status:
        print(readable_status(status, False) + "≈≈≈≈≈≈≈≈≈≈" + readable_status(status, True))

if __name__ == "__main__":
    # 初始局面
    status = [False, False, False, False]
    # 局面队列
    history_status = [status]

    search(history_status)

    print("finish search, find " + str(scheme_count) + " scheme")

5 运行结果

由输出结果可知有两种情况：

方案A：
1）农夫带羊过去
2）农夫自己回来
3）农夫带狼过去
4）农夫带羊回来
5）农夫带草过去
6）农夫自己回来
7）农夫带羊过去

方案B：
1）农夫带羊过去
2）农夫自己回来
3）农夫带草过去
4）农夫带羊回来
5）农夫带狼过去
6）农夫自己回来
7）农夫带羊过去

（全文完）

（欢迎转载本站文章，但请注明作者和出处 云域 – Yuccn ）