1.题目：

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

2.设计思路：

使用布尔列表来设置人狼羊草的状态, false代表不过河,true 代表渡河
那么人狼羊草的初始状态就是 status = [ false , false , false , false ]
最后状态应该是 status = [ true , true , true , true ]

渡河规则:

1.每次渡河农夫的状态都必须改变
2.每次渡河, 狼 羊 草的状态最多改变一位
3.狼 羊 草 存在食物链克制情况下必须有农夫存在

根据规则以初始状态为根节点,生成后续状态,再做枚举,生成状态树
如果子节点出现与根节点相同的状态,则不再生成子树

编码流程:

1,创建状态历史列表
2.生成所有方案
3.遍历判断所生成方案,判断是否是最终状态,是则输出
4.不是则判断改状态是否存在于状态历史列表
5.是则回到 3 ,继续遍历,不是则存入状态历史列表,回到 2 继续执行
(ps.算法流程图就不画了,凑活看,有人画可以发给我)

代码:

status = [False, False, False, False]
          # 人    狼     羊     草

判断状态是否合规

def judge_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 judge_status(next_status):
            next_status_list.append(next_status)

    return next_status_list

树形递归遍历

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()
# 这里是找到满足方案后,将其弹出历史状态列表,继续查找下一个方案

判断是否达到最终状态,都过河,则返回Ture

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

最后可以写个方法处理一下列表,打印出过程

求其他思路,最好能不用遍历树