农夫过河问题

关于“农夫过河”问的如何用状态空间法解决：

解：问题的状态可用三元组（x,y,z）来表示。其中x表示狼的位子、y表示羊的位置、z表示菜的位置；当各个未知数的值取0时表示物品在和的左岸，取1时相反。

那么所有可能的状态为：

S1(0,0,0)   (初始状态)

S2(0,0,1) 

S4(0,1,0)

S3(0,1,1)

S5(1,0,0)

S6(1,0,1)

S7(1,1,0)

S8(1,1,1)   (目标状态)

允许的操作有:

Cross()：农夫划船到对岸，状态不变，农夫位置改变；

Cross&Taken(x):农夫携带x到河的对岸使得x的状态发生变化，即(1_(x),y,z)→(0_(x),y,z)或(0_(x),y,z)→(1_(x),y,z)

这个问题的状态空间图为：

如图所示农夫过河问题中油初始状态到目标状态有两种方法：

方法一： {Taken(y)&Cross() , Cross() , Taken(x)&Cross() , Taken(y)&Cross() , Taken(z)&Cross() , Cross() , Taken(y)&Cross()}

方法二： {Taken(y)&Cross() , Cross() , Taken(z)&Cross() , Taken(y)&Cross() , Taken(x)&Cross() , Cross() , Taken(y)&Cross()}

农夫过河问题

原文：http://www.cnblogs.com/YuLonBlog/p/4358254.html