状态可逆即农夫可以带着某种东西过去也可以带着该东西回来。箭头上的字母表示农夫所携带的东西ffarmerwwolfggoatccabbage分别表示农夫自己、农夫携带狼、农夫携带羊、农夫携带菜过河。现在的问题转化为找一条合法路径相邻状态之间的转移合法从开始状态到某个结束状态途中不经过不安全状态。
3
f312算法的设计求农夫、狼、白菜和羊的当前状态的函数为每一种状态做测试状态安全则返回0否则返回1。安全性判断函数若状态安全则返回0i
tfarmeri
tlocatio
判断农夫位置对0做与运算，还是原来的数字，用来判断位置retur
0locatio
0x08i
twolfi
tlocatio
判断狼位置retur
0locatio
0x04i
tcabbagei
tlocatio
判断白菜位置retur
0locatio
0x02i
tgoati
tlocatio
判断羊的位置retur
0locatio
0x01i
tsafei
tlocatio
若状态安全则返回trueifgoatlocatio
cabbagelocatio
goatlocatio
farmerlocatio
retur
0ifgoatlocatio
wolflocatio
goatlocatio
farmerlocatio
retur
0retur
1其他状态是安全的借助于位向量和按位运算符很容易描述过河动作这种问题表示的设计使得程序的实现比较容易。算法的基本思想利用队列moveTo记录可到的尚未向前探试的状态数组元素routei记录状态i的路径前一状态1表示尚未访问。则算法的高级抽象可描速为
4
f初始状态出发点入队列所有其他点状态标记为未访问whileisEmptyQueueseqmoveToroute151从moveTo取出一个状态试探所有由这个状态出发可能到达的状态if能到达的状态安全且未访问过记录到它的路径压入队列精化上速算法得到问题的具体算法如下voidfarmerProblemi
tmoversilocatio
ewlocatio
i
troute16记录已考虑的状态路径i
tpri
tMAXNUMPSeqQueuemoveTomoveTocreateEmptyQueue_seq新的队列判断路径e
Queue_seqmoveTo0x00初始状态为0fori0i16iroutei11表示没有记录过路径route00whileisEmptyQueue_seqmoveToroute151队列不为空，路径未满时循环locatio
fro
tQueue_seqmoveTo从队头出队，locatio
表示位置，0为北岸，1为南岸deQueue_seqmoveTo已出队的删除formovers1movers8movers1向左移位，movers分别0001，0010，0100，1000也就是依次判断过河的可行性if0locatio
0x080locatio
movers判断农夫和要移动的物品是否在同岸
5
f
ewlocatio
locatio
0x08movers过岸ifsafe
ewlocatio
route
ewlocatio
1判断是否安全，以及路径是否可用route
ewr