解决狼、羊、白菜过河问题的编程思路

前几天女朋友复习人工智能的考试，看见了一道经典的狼、羊、白菜过河问题，题目如下：一个人带着一只羊，一条狼和一个白菜想过河，假设他每次只能带一只羊，或者一条狼，或者一棵白菜过河，并限定人不在场时，狼和羊，或羊和白菜不能单独在一起，试求出他带一只羊，一条狼，一个白菜过河的方法。

这样的题目小时候真的见过不少，虽然能够用笔头推导出来，但恰逢我最近在看算法之类的书，就想用这道题练练手，寻求其编程的解法。

首先第一步是把问题抽象化，我将白菜、羊、狼、人分别设为1、2、3、X。如果X不在的话，一旦出现两个数的差的绝对值为1的情况时，就说明发生了羊吃白菜或是狼吃羊的非法事件。这就是需要避免出现的。

然后我再来考虑解决的算法，一开始我考虑采用树状深度搜索的方法递归的向理想结果推进。在第n步的时候，枚举出全部的合法移动，分别向前递归出n+1的行动步骤。不过我发现遇到了一个问题，在不断向前递归的过程中可能会回到之前的某状态，从而造成死循环。而我当时没有想出排除已有路径前进的方法，边上的女朋友提醒我说可以从状态入手，我一想4个东西放左右，不过2^4=16种情况，的确比无休止的递归要简单多了，于是我就立刻转换了思路。

虽说一共有16种状态，其中还包括一些非法的状态，但它们直接的关系却是挺复杂的。比如{1、3、x}的状态可以变为{1}{3}{1、3}三种，而这些状态和状态的关系让我想起了我最近才看的图论，这不正是无向图嘛！

就这样我坚定了思路，开始了程序的第一步，获取全部的16种状态。这是一个求4个元素集合的全部子集的问题，用枚举显然挺麻烦的，一般采用递归的思路。一个包含n+1元素集合的子集是由：n个元素的子集（包含空集）和n个元素的子集+另一个元素的集合的并集。数学描述挺简单的2^(n+1)=2^n+2^n。

其python代码如下：

def subset(mainset):
    res=[]
    if len(mainset)==1:
        return [mainset,set()]
    left=mainset.pop()
    right_set=subset(mainset)
    for i in right_set:
        res.append(i)
        res.append(i|set(left))
    return res

 

就这样，我们获取了全部16个状态。现在来排除非法的状态。考虑到左右岸的情况，要求留下来的合法状态，它的补集也是合法的。

def check_legal(mainset):
    while len(mainset):
        tmp=mainset.pop()
        for i in mainset:
            if abs(int(i)-int(tmp))==1:
                return False
    return True

def deal_set():
    a=subset(set('123x'))
    b=copy.deepcopy(a)
    for i in b:
        if 'x' in i:
            if check_legal((set('123x')-i).copy())==False:
                a.remove(i)
        else:
            if check_legal(i.copy())==False:
                a.remove(i)
    a.sort()
    return a

就这样，我们获取了全部16个状态。现在来排除非法的状态。考虑到左右岸的情况，要求留下来的合法状态，它的补集也是合法的。

这样我们获取了10个合法的状态，分别为[{NULL}, {2}, {2、X}, {1}, {1、2、X}, {3}, {2、3、X}, {1、3}, {1、3、X}, {1、2、3、X}]

现在来讨论这些状态的关系，如果有两个状态，满足其中一个是另一个的子集，而关于这个子集的补集恰好是X（人的移动）或是X和1、2、3其中的一个时（人带着一个东西移动），我们称这两个状态有关系。一个状态元素变少了，称为离开，一个状态元素变多了就称为回来。

现在有了状态和状态之间的关系，我们就组成了一个无向图。这个是包含10个状态的有点繁琐的图，具体的图我就不画了。

现在问题变成了在一个无向图上从某个点到达另一个点的路径问题了。一般的做法是递归，从当前点递归到能够到达的下一个点，不过我们要排除已经遍历过的点，防止无限递归，这样我们就能从起点不断前进探索未知的点，直到到达终点。不过在本题中，情况要稍微复杂一点，因为人是不断的从左岸到右岸，再从右岸到左岸的。我们之前获取的有两个关系，一个是人离开，一个是人回来。对于某一个状态，如果人在里面，那么只有通过人离开的关系图，我们才能到达一个没有人在的状态里，而如果这个状态立没有人，那么只有通过人回来的关系才能到达人在的状态里。

程序的最终输出结果为：

123x->13->13x->1->12x->2->2x->NULL

123x->13->13x->3->23x->2->2x->NULL

做完这道题之后，我上网搜了一下标准做法。我最初的思路和网上的程序一样，不过我没有将它实现下去就改变了思路。不过采用了穷举状态和图论的解决方法给了我的一个很好的实践机会。其实对于某一个问题，将其分拆细化变成熟悉的问题是设计算法的一个很好的思路，如果再厉害点就可以根据具体问题来判断各自算法的利弊，不过可惜在算法上我只是一个初学者，也就只能走马观花，图得一乐了。

something.zip