农夫过河算法与数据结构设计
摘要：农夫过河问题讲述的是一位农夫带着一只狼，一只羊和一颗白
菜要渡过一条河，只有农夫能开船，且每次农夫只能带最多一样东西，
并且农夫不在的时候，狼和羊，羊和白菜不能共存，我们需要在这个
前提下找到渡河的最短路径。
1. 问题抽象和数据组织
1.1 诸如此类问题都能先将其抽象成一个数学模型，再对这个模型
采取合适的算法来进行解答，从而避免繁琐的步骤。在渡河过程中，
若把每个对象渡河和未渡河视为两种不同的状态，那么 4 个对象与 2
种状态一共能组合成 2 的 4 次方种，即 16 种不同的状态，那么将这
些对象由初始状态经历这些不同的状态从而达到最终状态就是我们
算法的目的。
1.2 显然在题给条件的约束下，这 16 种状态中有一部分是不合法
的，我们需要将这些状态抽象化，再把它们剔除，然后在剩余状态中
寻找最短的渡河路径。不难发现这 16 种状态都是能一一列举出来的，
这样能用到的方法就多种多样。这里我们用到的是递归法，即把每个
对象的状态分离出来，从初始状态开始，每进行一次渡河就对对应的
对象进行一步操作，如此反复，直到所有对象都达到“渡河”的状态，
递归结束。
1.3 在递归过程中，需要注意 2 种情况。第一种是为了达到最短路
径，需要避免路径出现重复，为了达到这个目的有两种可行的手段。
评论0