农夫过河——python贪心算法实现

1.问题描述：

一个农夫在河的西岸带了一匹狼、一只羊和一棵白菜，他需要把这三样东西用船带到河的东岸。然而，这艘船只能容下农夫本人和另外一样东西。如果农夫不在场的话，狼会吃掉羊，羊也会吃掉白菜。

2.问题分析：

由于整个过程涉及四个对象，多个步骤，而各个步骤中各个对象所处位置相对不同，因此可以定义一个二维数组，分别存储对象及初始状态——

initial_state[0][0]，[1][0]，[1][1]，[1][2]，[1][3]，分别代表农夫，狼，羊，蔬菜，0和1分别表示所处东岸或西岸。

initial_state = [[1], [1, 1, 1, 1]]

3.算法设计：

首先，由于每下一步行动都与上一步行动后的状态有关，因此可以考虑使用递归算法。

其次注意到，为达到农夫过河最优解，即所有东西都带过河，则每一步骤应考虑最优解，亦即不存在狼吃羊，羊吃草的情况，因此可以考虑使用贪心算法。

for i in range(4):  # 依次判断农夫带何种东西过河为该次最优解
    state[-1][i] = 0 if state[-1][i] == 1 else 1
    ret = 0
    for pri in range(len(state) - 1):  # 遍历过往状态，防止重复步骤
        if state[-1] == state[pri]:
            ret = 1
            break
    # 判断是否为该步骤最优解，亦即不存在狼吃羊，羊吃草的情况
    if ret == 1 or state[0][0] != state[-1][2] and (state[-1][1] == state[-1][2] or state[-1][2] == state[-1][3]):
        state[-1][i] = 0 if state[-1][i] == 1 else 1  # 否则回到上一步初始状态
        continue
    else:
        all_step.append(i)  # 步骤列表，存储每一步最优解
        break

4.完整程序：

import copy


def nextstep(state):
    state.append(copy.copy(state[-1]))      # 解决上下步骤列表处理问题，此处用到浅拷贝
    state[0][0] = 0 if state[0][0] == 1 else 1      # 农夫每走一步即到河对岸去
    for i in range(4):                  # 依次判断农夫带何种东西过河为该次最优解
        state[-1][i] = 0 if state[-1][i] == 1 else 1
        ret = 0
        for pri in range(len(state) - 1):   # 遍历过往状态，防止重复步骤
            if state[-1] == state[pri]:
                ret = 1
                break
        # 判断是否为该步骤最优解，亦即不存在狼吃羊，羊吃草的情况
        if ret == 1 or state[0][0] != state[-1][2] and (state[-1][1] == state[-1][2] or state[-1][2] == state[-1][3]):
            state[-1][i] = 0 if state[-1][i] == 1 else 1    # 否则回到上一步初始状态
            continue
        else:
            all_step.append(i)      # 步骤列表，存储每一步最优解
            break
    if state[0][0] == 0 and state[-1][1:] == [0, 0, 0]:     # 判断是否为最优解
        print(state)
    else:
        return nextstep(state)


if __name__ == '__main__':
    all_step = []
    initial_state = [[1], [1, 1, 1, 1]]     # 定义各个对象初始状态
    nextstep(initial_state)
    # 打印各个步骤
    step = ['啥没带', '带蔬菜', '带了羊', '带了狼']
    stp = 0
    for sp in all_step:
        stp += 1
        if stp % 2 == 1:
            print("第"+str(stp)+"步 "+"农夫从西岸到东岸"+step[sp]+"过去")
        else:
            print("第"+str(stp)+"步 "+"农夫从东岸到西岸"+step[sp]+"回来")

5.运行结果

​​​​​​​