農(nóng)夫過河問題

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

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

3、；時，因?yàn)椴荒馨牙呛脱蛲瑫r留下，所以只能帶走羊；AA羊AB羊狼菜怎么辦呢B羊B狼菜菜狼（3）再次回到再次回到a時，因?yàn)槔呛筒丝梢酝瑫r留下，所以優(yōu)先選擇空手過河；時，因?yàn)槔呛筒丝梢酝瑫r留下，所以優(yōu)先選擇空手過河；到a后發(fā)現(xiàn)只剩下羊，所以帶羊過河。后發(fā)現(xiàn)只剩下羊，所以帶羊過河。解：用四元組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