题目:
用谓词表示法求解农夫、狼、山羊、白菜问题。农夫、狼、山羊、白菜全部放在一条河的左岸,现在要把他们全部送到河的右岸去,农夫有一条船,过河时,除农夫外船上至多能载狼、山羊、白菜中的一种。狼要吃山羊,山羊要吃白菜,除非农夫在那里。请完成以下问题:
问题:
用一阶谓词逻辑设计给出一个确保全部安全过河的规划,写出所用谓词的定义及本问题的求解过程。
解题思路:
步骤一:使用自然语言求解出问题答案;
步骤二:将问题求解过程中的事物的状态,位置,动作进行谓词定义;
步骤三:明晰问题的初始状态和目标状态;
步骤四:设置状态转换中的操作(包含条件和动作两部分),并且根据实际求解步骤连接起来;
步骤五:完善出从初始状态到目标状态的所有状态;
具体:
步骤一:使用自然语言求解出问题答案:
第一回合:左岸到右岸:农夫带羊
右岸到左岸:不带东西
第二回合:左岸到右岸:农夫带狼
右岸到左岸:农夫带羊
第三回合:左岸到右岸:农夫带白菜
右岸到左岸:不带东西
第四回合:左岸到右岸:农夫带羊
(从第二回合起问题有另一种最优解:
① 第二回合:左岸到右岸:农夫带菜
右岸到左岸:农夫带羊
② 第三回合:左岸到右岸:农夫带狼
右岸到左岸:不带东西
③ 第四回合:左岸到右岸:农夫代羊
可见从第二回合起有先带狼或者白菜两种选择,但求解问题无太大差异,故下面的第三问以第一种解决方法为例编写。
)
步骤二:将问题求解过程中的事物的状态,位置,动作进行谓词定义;
(将农夫定义为可主动操作体,用AT表示他的位置,将狼白菜羊定义为无主动操作的个体,用ON表示它的位置 )
BANK(w):w是岸边;
EMPTY(x):x什么都没带;
AT(x,w):x在w处;
HOLDS(x,z):x带着z;
ON(z,w):z在w处;
w的个体域是{left,right};
x的个体域是{farmer};
z的个体域是{wolf,sheep,cabbage};
步骤三:明晰问题的初始状态和目标状态;
问题初始状态是:
AT(farmer,left)
EMPTY(farmer)
ON(wolf,left)
ON(sheep,left)
ON(cabbage,left)
BANK(left)
BANK(right)
问题目标状态是:
AT(farmer,right)
EMPTY(farmer)
ON(wolf,right)
ON(sheep,right)
ON(cabbage,right)
BANK(left)
BANK(right)
步骤四:设置状态转换中的操作(包含条件和动作两部分),并且根据实际求解步骤连接起来;
BOATING(x,y):农夫划船从x到y岸
条件:AT(x,y)
动作:删除表:AT(farmer,x)
添加表:AT(farmer,y)
PICKUP(x,y):农夫在x处带上y
条件:ON(y,x),BANK(x),AT(farmer,x),EMPTY(farmer)
动作:删除表:EMPTY(farmer),ON(y,x)
添加表:HOLDS(farmer,y)
SETDOWN(x,y):农夫在x处放下y
条件:AT(farmer,x),BANK(x),HOLDS(farmer,y)
动作:删除表:HOLDS(farmer,y)
添加表:EMPTY(farmer),ON(y,x)
第一回合:PICKUP(left,sheep),BOATING(left,right),SETDOWN(right,sheep),BOATING(right,left)
第二回合:PICKUP(left,wolf),BOATING(left,right),SETDOWN(right,wolf),PICKUP(right,sheep)
BOATING(right,left),SETDOWN(left,sheep)
第三回合:PICKUP(left,cabbage),BOATING(left,right),SETDOWN(right,cabbage),BOATING(right,left)
第四回合:PICKUP(left,sheep),BOATING(left,right),SETDOWN(right,sheep)
步骤五:完善出从初始状态到目标状态的所有状态;
上一篇:招聘专员的岗位职责说明