人工智能复习

启发式搜索

八数码难题 , 令估价函数

f(n)=d(n)+p(n)

*

启发函数h(n)=p(n),p(n)为不在位的棋子与其目标位置的距离之和，则有p(n)≤h(n),满

*

足A算法的限制条件。

3．假设：所有不贫穷并且聪明的人都是快乐的，那些看书的人是聪明的。李明能看书且不贫穷，快乐的人过着激动人心的生活。 求证：李明过着激动人心的生活。

解：先定义谓词： Poor(x) x是贫穷的，Smart(x) x是聪明的，Happy(x) x是快乐的，Read(x) x能看书，Exciting(x) x过着激动人心的生活。 再将问题用谓词表示如下：

“所有不贫穷并且聪明的人都是快乐的” (?x)((﹁Poor(x)∧Smart(x))→Happy(x)) “那些看书的人是聪明的” (?y) (Read(y) → Smart(y)) “李明能看书且不贫穷”

Read(Liming)∧﹁Poor(Liming) “快乐的人过着激动人心的生活” (?z) (Happy(z)→Exciting(z))

目标“李明过着激动人心的生活”的否定 ﹁Exciting(Liming)

将上述谓词公式转化为子句集如下： (1) Poor(x)∨﹁Smart(x)∨Happy(x) (2) ﹁Read(y)∨Smart(y) (3) Read(Liming) (4) ﹁Poor(Liming)

(5) ﹁Happy(z)∨Exciting(z)

(6) ﹁Exciting(Liming) (结论的否定)

任何通过计算机考试并获奖的人都是快乐的。任何肯学习或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。 解：将问题用谓词表示如下：

“任何通过计算机考试并获奖的人都是快乐的”

(?x)(Pass(x,computer) ? Win(x,prize)) ?Happy(x)) “任何肯学习或幸运的人都可以通过所有考试”

(?x)( ?y) (Study(x) ? Lucky(x) ?Pass(x,y)) “张不肯学习但他是幸运的”

?Study(zhang) ? Lucky(zhang) “任何幸运的人都能获奖”

(?x)(Lucky(x) ?Win(x,prize)) 结论“张是快乐的”的否定 ?Happy(zhang)

将谓词转化为子句集：

P1: ? Pass(x,computer) ? ? Win(x,prize) ?Happy(x) P2: ? Study(y) ? Pass(y,z) P3: ? Lucky(u) ? Pass(u,v) P4: ?Study(zhang) P5: Lucky(zhang)

P6: ? Lucky(w) ?Win(w,prize) ? Q: ?Happy(zhang)

’’’

所以：S={P1 , P2 , P3 , P4, P5 , P6}, S= {P1 , P2 , P3 , P4, P5 , P6, ? Q}

’’

对S进行归结操作，直至推出NIL。归结反演过程如下：

有一农夫带一只狼、一只羊和一筐菜欲从河的左岸乘船到右岸,但受下列条件限制： (1) 船太小,农夫每次只能带一样东西过河。 (2) 如果没有农夫看管, 则狼要吃羊,羊要吃菜。 请设计一个过河方案, 使得农夫、狼、羊、菜都能不受损失地过河。画出相应的状态空间图。 提示： (1) 用四元组(农夫、狼、羊、菜)表示状态,其中每个元素都可为0或1, 用0表示在左岸, 用1表示在右岸。 (2) 把每次过河的一种安排作为一个算符,每次过河都必须有农夫, 因为只有他可以划船。

解：初始S=(0，0，0，0)，目标G=(1，1，1，1) 定义操作符L(i)表示农夫带东西到右岸： 定义操作符R(i)表示农夫带东西到左岸： i=0 农夫自己到右岸； i=1 农夫带狼到右岸； i=2 农夫带羊到右岸； i=3 农夫带菜到右岸； 约束状态如下：

(1，0，0，X)狼、羊在左岸； (1，X，0，0)羊、菜在左岸； (0，1，1，X)狼、羊在右岸； (0，X，1，1)羊、菜在右岸；

农夫自己到左岸； i=1 农夫带狼到左岸； i=2 农夫带羊到左岸； i=3 农夫带菜到左岸； i=0