人狼羊菜渡河问题(含Matlab 程序)(2 页)Good is good, but better carries it
精益求精，善益求善
人、狼、羊、菜安全渡河问题安全渡河问题又称作“人狼羊菜”问题，其具体描述为：一个人带着一条狼、一只羊、一筐白菜过河但由于船太小，人一次只能带一样东西乘船过河
狼和羊、羊和白菜不能单独留在同岸，否则羊或白菜会被吃掉
该问题可使用图论中的最短路算法进行求解
问题分析 根据题意，人不在场时，狼要吃羊，羊要吃菜，因此，人不在场时，不能将狼与羊、羊与菜留在河的任一岸
可用四维向量 v=（m，n，p，q）来表示状态， m 表示人，n 代表狼，p 代表羊，q 代表白菜，且 m,n,p,q ∈{0,1},0 代表在对岸，1 代表在此岸
例如，状态（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={v1,…, v10}中的顶点（根据上面的顺序编号）分别表示上述１０个可行状态，当且仅当对应的两个可行状态之间存在一个可行转移时两顶点之间才有边连接，并且对应的权重取为１，当两个顶点之间不存在可行转移时，可以把相应的权重取为∞
因此问题变为在图Ｇ中寻找一条由初始状态（１,１,１,１）出发，经最小次数转移到达最终状态（０,０,０,０）的转移过程，即求从状态（１,１,１,１）到状态（０,０,０,０）的最短路径
该问题难点在于计算邻接矩阵，由于摆渡一次就改变现有状态，为此再
