使用回溯（Backtracking）算法解决狼，羊和卷心菜过河问题
发布于: June 9, 2010, 3:03 pm 分类: IT大杂烩 作者: Saturn 3 个评论
回溯算法（Backtracking algorithm）是机器搜索（Search）的基本算法之一，通常用于解决具有唯一解，但有多个限制条件的复杂问题。
以下是狼，羊和卷心菜问题的描述：
一个人需要用一条船将狼，羊河卷心菜运送到一条河的对岸。限制条件如下：
- 这条船比较小，每次仅能运送一个物体，且船的运行都需要人来控制
- 当没人看管的时候，狼会吃羊，而羊会吃卷心菜。
如何将这些这三个物体安全送到河的对岸？
对这个问题感兴趣的朋友可以玩玩这个逻辑游戏，看你玩多少次能够将他们成功运送到对岸。
下面看看，如何使用Backtrack算法合理的分析和解决这个问题：
首先，我们对这个问题里面涉及到的状态图形化（State Representation），这样有助于我们理解问题和编写程序解决问题。
上图分别描述了我们的初始状态和目标状态，其中的字母和数字分别表示：
- B 表示船的位置，在左边那个栏位时，表示船在起始岸边；反之，表示船在目标岸边；
- C表示cabbage（卷心菜），W表示wolf（狼），S表示sheep（羊）。
- 数字表示在当前岸边物体的个数
其次，我们要确定能够对状态进行的操作（Operators），显而易见，不管穿在那边，都可以进行如下四种操作：
- M(W)：将狼运到对岸
- M(S): 将羊运到对岸
- M(C)：将卷心菜运到对岸
- M()：不运送任何东西，只将穿运送到对岸
然后，我们要知道某个状态是否成功，即当前状态就是目标状态，还需要一个目标测试函数（Goal test），这个问题比较简单，不需要函数来表达，简单来说判断一个状态是否成功，需要判断起始岸的狼，羊和卷心菜数量之和为0，即以下函数：
N(C @ start) ＋ N(W @ start) + N(S @ start) = 0
以上函数，N表示数量，如N(C @ start)表示在起始岸上C的数目。
最后，在真正应用回溯（backtrack）算法之前，我们还需要确定一个或多个启发函数（heuristic function），这个函数如其名，用来指导和推测整个推导过程是否朝着正确的方向执行。这个案例的启发函数可以简单描述为：让目标岸边的狼，羊，卷心菜之和最大，即为3。
这是我们能从问题中发现的最直接的推导，好像没什么用。但对于一些没有固定答案的问题来说，它却是我们判断程序运行是否结束的依据（如果你将这种问题丢给程序去运行解决的话）。
那么没有这个函数，我们如何找出更有用的启发函数让程序知道如何最快的找到最优解。这个就需要分析具体问题了，如果你认真分析过这个问题，你会得到以下隐含条件：
狼是重口味，它不管在岸的哪一边都是不会吃卷心菜的。所以，我们需要先将狼和卷心菜运送到对岸。
这实际上我们能找到的另一个heuristic function，也可以称为一个子目标（sub goal）。有了它做指导，这个问题就迎刃而解了。
有了以上分析，我们只需要从初始状态开始，依次应用上面描述过的4个操作。如果该操作违反了问题中的限制条件，则需要将状态回推到上一个状态，并应用下一个操作。直到我们找到最后的目标状态，再将所有成功状态连在一起，就是我们的解决方案了。
（To be updated：需要补上backtrack流程图）