数学建模——过河问题一（人狼羊草）
1. （1，1，1，1） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（0，0，1，1） × =（0，1，0，1） √ =（0，1，1，0） × =（0，1，1，1） ×
2. （0，1，0，1） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（1，0，0，1） × =（1，1，1，1） × =（1，1，0，0） × =（1，1，0，1） √
（1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（0，0，0，1） √ =（0，1，1，1） × =（0，1，0，0） √ =（0，1，0，1） √ 3. （1，1，0，1） +
4.1 （0，1，0，1）与上述第二步重复，必定不是最优解，故不用进行下去。
4.2 （0，0，0，1） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（1，1，0，1） √ =（1，0，1，1） √ =（1，0，0，0） × =（1，0，0，1） ×
4.2.1 （ 1，1，0，1 ）与上述第3步重复，必定不是最优解，不用进行下去
6 / 15
数学建模——过河问题一（人狼羊草）
4.2.2 （1，0，1，1） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（0，1，1，1） × =（0，0，0，1） √ =（0，0，1，0） √ =（0，0，1，1） ×
4.2.2.1 （0，0，0，1）与上述4.2重复，必定不是最优解，不用进行下去
4.2.2.2 （0，0，1，0） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（1，1，1，0） √ =（1，0，0，0） × =（1，0，1，1） √ =（1，0，1，0） √
4.2.2.2.1 （1，0，1，1）与上述4.2.2重复，必定不是最优解，不用进行下去
4.2.2.2.1 （1，0，1，0） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（0，1，1，0） × =（0，0，0，0） √ =（0，0，1，1） × =（0，0，1，0） √
已得最终状态向量（0，0，0，0），过程无重复，此即为最优解。
（1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（1，0，0，0） × =（1，1，1，0） √ =（1，1，0，1） √ =（1，1，0，0） × 4.3 （0，1，0，0） +
7 / 15
数学建模——过河问题一（人狼羊草）
4.3.1 （ 1，1，0，1 ）与上述第3步重复，必定不是最优解，不用进行下去
4.3.2 （1，1，1，0） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（0，0，1，0） √ =（0，1，0，0） √ =（0，1，1，1） × =（0，1，1，0） ×
4.3.2.1 （0，1，0，0）与上述4.3重复，必定不是最优解，不用进行下去
4.3.2.2 （ 0，0，1，0 ）与按上述4.2.2.2步骤进行即可得相同的最优解 模型的解 最终结果：
解一： D1（1，1，1，1）→D2（0，1，0，1）→D3（ 1，1，0，1 ）→D4（0，1，0，0）→D5（ 1，1，1，0 ）→D6（ 0，0，1，0 ）→D7（1，0，1，0）→D8（0，0，0，0）
8 / 15
数学建模——过河问题一（人狼羊草）
解二： D1（1，1，1，1）→D2（0，1，0，1）→D3（ 1，1，0，1 ）→D4（0，0，0，1）→D5（1，0，1，1）→D6（ 0，0，1，0 ）→D7（1，0，1，0）→D8（0，0，0，0） n=7 解法(2):图解法
绘图要求：（1）连线两端必须是允许状态向量；
（2）相邻两点（通过一次运载得到的点）相连； （3）从（1，1，1，1）至（0，0，0，0）结束。 连线如下：
（1，1，1，1） （1，0，1，0） （0，0，0，0） （0，0，0，1） （1，1，0，1） （0，0，1，0） （1，0，1，1） （1，1，1，0） （0，1，0，0） （0，1，0，1）
最终结果：
9 / 15
数学建模——过河问题一（人狼羊草）
模型的解
解一： D1（1，1，1，1）→D2（0，1，0，1）→D3（ 1，1，0，1 ）→D4（0，1，0，0）→D5（ 1，1，1，0 ）→D6（ 0，0，1，0 ）→D7（1，0，1，0）→D8（0，0，0，0）
解二： D1（1，1，1，1）→D2（0，1，0，1）→D3（ 1，1，0，1 ）→D4（0，0，0，1）→D5（1，0，1，1）→D6（ 0，0，1，0 ）→D7（1，0，1，0）→D8（0，0，0，0） n=7
与解法（1）解相同
五、计算机编程法（C语言）
要解决这个问题就要使过河时载两个过河，返回时尽量只有一个回来。用一个字符串数组来存人，狼，羊，草；下标依次为0，1，2，3；但他们都有河这边和那边两种状态；为方便则定义一个结构，只含一个int型变量n；当在河这边时n设为0；在河那边时n设为1。由于每次过河与返回都要考虑狼能否吃羊或羊能否吃草；则需要一个函数来判断每次选择是否满足条件。 源代码：
10 / 15