農(nóng)夫過(guò)河問(wèn)題

1、農(nóng)夫過(guò)河問(wèn)題農(nóng)夫過(guò)河問(wèn)題1.題目描述：題目描述：一個(gè)農(nóng)夫帶著一只狼，一只羊和一筐菜，欲從河的左岸坐船到右岸，由于一個(gè)農(nóng)夫帶著一只狼，一只羊和一筐菜，欲從河的左岸坐船到右岸，由于船太小，農(nóng)夫每次只能帶一樣?xùn)|西過(guò)河，并且沒(méi)有農(nóng)夫看管的話，狼會(huì)吃船太小，農(nóng)夫每次只能帶一樣?xùn)|西過(guò)河，并且沒(méi)有農(nóng)夫看管的話，狼會(huì)吃掉羊，羊會(huì)吃菜。設(shè)計(jì)一個(gè)方案，使農(nóng)夫可以無(wú)損失的過(guò)河掉羊，羊會(huì)吃菜。設(shè)計(jì)一個(gè)方案，使農(nóng)夫可以無(wú)損失的過(guò)河2.題目分析：題目分析：假設(shè)人、

2、狼、菜、羊都在河岸假設(shè)人、狼、菜、羊都在河岸a要到要到b河岸去。河岸去。題中的食物鏈關(guān)系為題中的食物鏈關(guān)系為:菜?羊?狼所以，第一次人只能帶羊到所以，第一次人只能帶羊到b河岸；河岸；回到回到a時(shí)，人不能再將剛帶過(guò)來(lái)的羊帶回去，所以人是空手回到時(shí)，人不能再將剛帶過(guò)來(lái)的羊帶回去，所以人是空手回到a的；的；在a河岸，人有兩個(gè)選擇河岸，人有兩個(gè)選擇選擇一：選擇一：（1）帶狼到帶狼到b人再回到人再回到a時(shí)，因?yàn)椴荒馨牙呛脱蛲瑫r(shí)留下，所以只能帶走羊

3、；時(shí)，因?yàn)椴荒馨牙呛脱蛲瑫r(shí)留下，所以只能帶走羊；AA羊AB羊狼菜怎么辦呢B羊B狼菜菜狼（3）再次回到再次回到a時(shí)，因?yàn)槔呛筒丝梢酝瑫r(shí)留下，所以優(yōu)先選擇空手過(guò)河；時(shí)，因?yàn)槔呛筒丝梢酝瑫r(shí)留下，所以優(yōu)先選擇空手過(guò)河；到a后發(fā)現(xiàn)只剩下羊，所以帶羊過(guò)河。后發(fā)現(xiàn)只剩下羊，所以帶羊過(guò)河。解：用四元組S表示狀態(tài)，即S＝（L，J，M，N）其中L：農(nóng)夫J：狼M：羊N：菜用0表示在左岸岸，1表示在右岸，即S=（0，0，0，0）目標(biāo)G＝（1，1，1，1）定義操

4、作符L（i）表示農(nóng)夫帶東西到右岸：i=0農(nóng)夫自己到右岸；i=1農(nóng)夫帶狼到右岸；i=2農(nóng)夫帶羊到右岸；i=3農(nóng)夫帶菜到右岸；定義操作符R（i）表示農(nóng)夫帶東西到左岸：i=0農(nóng)夫自己到左岸；i=1農(nóng)夫帶狼到左岸；i=2農(nóng)夫帶羊到左岸；i=3農(nóng)夫帶菜到左岸；約束狀態(tài)如下：（1，0，0，1）狼、羊在左岸；（1，1，0，0）羊、菜在左岸；（0，1，1，0）狼、羊在右岸；（0，0，1，1）羊、菜在右岸；（1，0，0，0）狼、羊、菜在左岸；（0，1，1