求matlab程序解人狼羊菜问题

求matlab程序解人狼羊菜问题

解：该问题可以使用图论中的最短路算法进行求解。
我们可以用四维向量来表示状态，其中第一分量表示人，第二分量表示狼，第三分量表
示羊，第四分量表示蔬菜；当人或物在此岸时相应分量取1，在对岸时则取0。
根据题意，人不在场时，狼要吃羊，羊要吃菜，因此，人不在场时，不能将狼与羊，羊
与蔬菜留在河的任一岸。例如，状态（0，1，1，0）表示人和菜在对岸，而狼和羊在此岸，
这时人不在场的情况下狼要吃羊，因此，这个状态是不可行的。
我们通过穷举法将所有可行的状态列举出来，可行的状态有
（1，1，1，1），（1，1，1，0），（1，1，0，1），（1，0，1，1），（1，0，1，0）
（0，1，0，1），（0，1，0，0），（0，0，1，0），（0，0，0，1），（0，0，0，0）
可行状态共有十种。每一次的渡河行为改变现有的状态。现构造赋权图G = (V, E,W) ，
其中集合V 中的顶点表示十个可行状态，当且仅当对应的两个可行状态之间存在一个可行
转移时两顶点之间才有线连接，并且对应的权重取为1，当两个顶点之间不存在可行转移时，
可以把相应的权重取为∞ 。
因此问题变为在图G 中寻找一条由初始状态（1，1，1，1）出发，经最小次数转移达到
最终状态（0，0，0，0）的转移过程，即求从状态（1，1，1，1）到状态（0，0，0，0）的
最短路径。这就将问题转化成了图论中的最短路问题。
下面首先计算邻接矩阵，由于摆渡一次就改变现有的状态，为此再引入一个四维状态转
移向量，用它来反映摆渡情况。用1 表示过河，0 表示未过河。例如，（1，1，0，0）表示
人带狗过河。状态转移只有四种情况，用如下的向量表示。
（1，0，0，0），（1，1，0，0），（1，0，1，0），（1，0，0，1）
现在规定状态向量与转移向量之间的运算为
0 + 0 =1，1+ 0 =1 ， 0 +1 =1 ，1+1 =1
通过上面的定义，如果某一个可行状态加上转移向量得到的新向量还属于可行状态，则这两
个可行状态对应的顶点之间就存在一条边。用计算机编程时，我们可以利用普通的向量运算
与模2 运算实现。

源程序联系我 我发给你