过河问题

有一只狐狸、一只鹅和一袋大麦必须由农夫用船运过河。但是，移动过程有如下限制条件。

• 每次移动过程中，除了农夫以外，船上只能携带一件物品。
• 农夫必须参与每次移动过程。
• 狐狸不能单独和鹅待在一起，否则狐狸会吃掉鹅。
• 鹅不能单独和大麦待在一起，否则鹅会吃掉大麦。

首先，将系统的初始状态建模为图的顶点。我们将顶点命名为TGFB_，其中每个字符代表问题的一部分:

• T（船和农夫）
• G（鹅）
• F（狐狸）
• B（大麦）
• _（河）

上图说明了如果通过删除违反限制条件的状态(顶点)和相邻关系(边)来简化图，会发生什么情况。 可以通过删除任何连接回先前状态的边来进一步简化图，因为它们会将我们引向先前的状态(这种情况在图论中称为环)。