中图分类号：G4 文献标识码：A
　　人、狗、鸡、米均要过河，船需要人划，每次只能运载其中的一物和人本身，而当人不在时，狗要吃鸡，鸡要吃米。问人、狗、鸡、米怎样过河？
　　分析：问题的初始状态是人、狗、鸡、米均在本岸，要求经过一系列的过河运载（每次运载只能一人一物，而且不能把狗和鸡留在一起，也不能把鸡和米留在一起），最后达到目标状态，，即人、狗、鸡、米均在对岸。为了将问题数学化，我们用四元数组（即由4个数所组成的数组来表示初始状态，目标状态以及中间的各种可取状态。当一物在本岸时，用数字“1”表示;在对岸时，用数字“0”表示。于是，人、狗、鸡、米的状态可以用每个数取0或1的四元数组来表示。例如，（1，0，1，0）表示人在本岸，狗在对岸，鸡在本岸，米在对岸，每个数取0或1的四元数组共有16个：
　　（1，1，1，1）       （0，0，0，0）
　　（1，1，1，0）       （0，0，0，1）
　　（1，1，0，1）       （0，0，1，0）
　　（1，0，1，1）       （0，1，0，0）
　　（1，1，0，0）       （0，0，1，1）
　　（1，0，1，0）       （0，1，0，1）
　　（1，0，0，1）       （0，1，1，0）
　　（1，0，0，0）       （0，1，1，1）
　　由于鸡和米或者狗和鸡不能留在一起，所以（1，1，0，0），（0，0，1，1），（1，0，0，1），（0，1，1，0）（1，0，0，0），（0，1，1，1）所表示的状态都是不允许的，而其他10个状态都是允许存在的，也就是说，是可取状态，它们分别是
　　（1，1，1，1）       （0，0，0，0）
　　（1，1，1，0）       （0，0，0，1）
　　（1，1，0，1）       （0，0，1，0）
　　（1，0，1，1）       （0，1，0，0）
　　（1，0，1，0）       （0，1，0，1）
　　我们用10个顶点分别表示以上10个可取状态。如果一个可取状态可以经过一次过河运载转移到另一个可取状态，那么在表示这两个可取状态的顶点之间联结一条边，从而构成一个图（图29-1）。例如，（1，0，1，1）和（0，0，1，0）之间联结一条边表示如果人把米从本岸运到对岸，那么可取状态（1，0，1，1）就转移到可取状态（0，0，1，0）;反过来，如果人把米从对岸运到本岸，那么可取状态（0，0，1，0）就轉移到可取状态（1，0，1，1）。现在问题变为在图29-1中找一条从顶点（1，1，1，1）通过相联结的边到顶点（0，0，0，0）的路径，每条路径就是一个解。
　　解：从图29-1可以找到两条从顶点（1，1，1，1）到顶点（0，0，0，0）的路径（如图29-2所示），其中一条所表示的解为
　　（1）人把鸡运到对岸;
　　（2）留下鸡，人返回;
　　（3）人把狗运到对岸;
　　（4）留下狗，人把鸡带回;
　　（5）人把米运到对岸;
　　（6）人独自返回，留下米（还有狗）;
　　（7）人把鸡运到对岸。
　　只要把（3），（4），（5）分别改为
　　（3）人把米运到对岸;
　　（4）留下米，人把鸡带回;
　　（5）人把狗运到对岸
　　就得到另一解。
　　这二解所需的运载次数相等，所以是等优的。
　　回顾：以上我们采用图作数学模型，直观明了地解决了问题。由于人狗鸡米过河问题比较简单，也可以用递推方法来解，这方法基于逻辑推理。
　　为了直观起见，我们可以如表29-1所示边画边思考。
　　由于狗鸡或鸡米不能留在一起，第1次过河只能是人把鸡运到对岸;第2次过河只能考虑留下鸡，人返回，否则人与鸡都返回，那么又恢复原状;第3次过河可以考虑人把狗运到对岸（如果考虑人把米运到对岸，那么可能得到另一解）;第4次过河人不能把狗带回（否则又恢复第3次过河前的状态），也不能人独自返回（否则狗鸡留在一起），所以只能考虑人把鸡带回;同样，第5次过河也只能人把米运到对岸;第6次过河将是人独自返回;最后，只有人与鸡在本岸;于是，第7次过河只要人把鸡运到对岸，就完成了过河问题。