渡河问题

题意：一个人需要带着猫、鸡和米过河，除了人必须划船外，船每次最多只能载猫、鸡或米中的一种。同时，若无人看管，猫会吃鸡，鸡会吃米，因此需要设计一个安全的渡河策略，并尽量减少过河次数。

以(x, y, z, w)表示当前岸边的状态，分别对应人、猫、鸡和米的存在情况。

在第k次划船之前，当前岸边允许存在的状态集合为：

S = {(1,1,1,1), (1,0,1,1), (1,1,0,1), (1,1,1,0), (1,0,1,0), (0,0,0,0), (0,0,0,1), (0,0,1,0), (0,1,0,0), (0,1,0,1)}；

将向量Dk定义为允许的决策向量，表示船上所载的对象：

Dk = {(1,0,0,
(,
(,
(};

Sk+₁ = Sk + (-₁)^k(Dk) 即为状态转移方程，在实现时可使用异或操作。

目标是寻找从初始状态(1,
到目标状态（
的最短路径。

然而上述方法在实际操作中较为复杂。最近在一位专家的博客中了解到，采用最短路径算法来处理此问题更为简便。但前提是需先计算出各状态之间的转换关系。

随后可采用Dijkstra算法或Floyd算法