农夫过河问题.doc

农夫过河问题1.题目描述：一个农夫带着一只狼，一只羊和一筐菜，欲从河的左岸坐船到右岸，由于船太小，农夫每次只能带一样东西过河，并且没有农夫看管的话，狼会吃掉羊，羊会吃菜设计一个方案，使农夫可以无损失的过河2.题目分析：假设人、狼、菜、羊都在河岸a,要到b河岸去题中的食物链关系为：菜T羊一狼所以，第一次人只能带羊到b河岸；回到a时，人不能再将刚带过来的羊带回去，所以人是空手回到a的在a河岸，人有两个选择菜狼AB选择一：(1) 带狼到b,人再回到a时，因为不能把狼和羊同时留下，所以只能带走羊;(2)再次回到a后，人再到b时，不能把羊和菜同时留下，所以只能带走菜;(3)再次回到a时，因为狼和菜可以同时留下，所以优先选择空手过河；到a后发现只剩下羊，所以带羊过河选择二：(1)带菜到b,人再回到a时，因为不能把菜和羊同时留下，所以只能带走羊；(2) 再次回到a后，人再到b时，不能把羊和狼同时留下，所以只能带走狼；(3) 再次回到a时，因为狼和菜可以同时留下，所以优先选择空手过河;到a后发现只剩下羊，所以带羊过河•*菜狼羊AB解：用四元组S表示状态，即S=(L,J,M,N)其中L：农夫J：狼M：羊N：菜用0表示在左岸岸，1表示在右岸，即S=(0,0,0,0)目标G=(1,1,1,1)定义操作符L(i)表示农夫带东西到右岸：i=0农夫自己到右岸；i=1农夫带狼到右岸；i=2农夫带羊到右岸；i=3农夫带菜到右岸；定义操作符R(i)表示农夫带东西到左岸:i=0农夫自己到左岸；i=1农夫带狼到左岸i=2农夫带羊到左岸i=3农夫带菜到左岸约束状态如下：(1,0,0,1)狼、羊在左岸；(1,1,0,0)羊、菜在左岸；(0,1,1,0)狼、羊在右岸；(0,0,1,1)羊、菜在右岸；(1,0,0,0)狼、羊、菜在左岸(0,1,1,1)狼、羊、菜在右岸帯箪対右舜U2)ME-iftJS>2£余方能畑^(U0,1,0入“古并1J1>0)芾不冋左萃R«誓羊回左蟹W2)ii保窑左岸£0」1,0,0)(OpOpOi门“古萍ii洛遼劲右毎5；WKS&J右津U3)ii人、祚”棄生力岸(1/1>0»I)cuno/1)a.ft.i。