农夫过河问题 Python实现解题

7,016 阅读5分钟
原文链接: blog.yuccn.net

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)农夫带羊过去