0,1,0 L(0,1)
L(1,0) L(0,1)
2,2,0
3,1,0
L(1,1)
R(1,1)L(0,2) R(0,2)
3,3,1
R(1,0) R(0,1)
1,1,1
0,2,1
L(1,1)R(0,2)
R(1,1)
L(0,2)
0,0,0
L(0,1) R(0,1)
R(0,1) L(0,1)
3,2,0
0,1,1
➢例1：设有下列事实性知识： 张晓辉是一名计算机系的学生，但他不喜欢 编程序。李晓鹏比他父亲长得高。
请用谓词公式表示这些知识。
（1）定义谓词及个体。 Computer(x):x是计算机系的学生。 Like(x,y):x喜欢y。 Higher(x,y):x比y长得高。
这里涉及的个体有：张晓辉(zhangxh),编程 序(programming), 李晓鹏(lixp)，以及函数 father(lixp)表示李晓鹏的父亲。
由上述状态空间图，可见从初始状态 (3,3,1)到目标状态(0,0,0)的任何一条通路都是 问题的一个解。
其中：
{R(1,1), L(1,0), R(0,2), L(0,1), R(2,0), L(1,1), R(2,0), L(0,1), R(0,2), L(1,0), R(1,1)}是算符最 少的解之一。
2.2 问题归约法
➢问题归约法的概念
❖已知问题的描述，通过一系列变换把此 问题最终变为一个子问题集合；这些子 问题的解可以直接得到，从而解决了初 始问题。
❖该方法也就是从目标(要解决的问题)出发 逆向推理，建立子问题以及子问题的子 问题，直至最后把初始问题归约为一个 平凡的本原问题集合。这就是问题归约 的实质。
第三步： 求解过程：
f1：从A瓶往B瓶倒油，
把B瓶倒满。
f7
2,0
f6 f5
0,2
f4
2,3
f1f15ff,7105ff,3530,ff017f05,ff3363,f08
f5
f3 f8
f8 f1
0,3
f7
f5
f1 f3
f7 f3
3,3
f4 f2
5,1
f2：从C瓶往B瓶倒油， 把B瓶倒满。
f3：从A瓶往C瓶倒油， 把C瓶倒满。
由上述状态空间图，可见从初始状态(0,1) 到目标状态(4,0)的任何一条通路都是问题的一 个解。其中：
{f1, f4, f7, f6, f1, f4, f7}是算符最少的解之一。
例：设有3个传教士和3个野人来到河边， 打算乘一只船从右岸渡到左岸去。该船的 负载能力为两人。在任何时候，如果野人 人数超过传教士人数，那么野人就会把传 教士吃掉。他们怎样才能用这条船安全地 把所有人都渡过河去？
第三步：求解过程。
R(2,0)
1,1,0 R(1,1)
L(2,0) 3,1,1 L(0,1) R(0,1)
3,0,0 L(0,2) R(0,2)
L(1,1) 2,2,1
L(2,0) R(2,0)
L(1,0)
0,2,0
0,3,1
R(0,1)
L(0,2) R(0,2)
R(1,0)
3,2,1
R(0,1) L(1,0)
第二步：将这些个体代入谓词中，得到 Computer(zhangxh), ~Like(zhangxh, programming), Higher(lixp, father(lixp))
人工智能清华大学课件
第1章 绪论
1、重点掌握人工智能的几种定义。 2、掌握目前人工智能的三个主要学派及
其认知观。 3、一般了解人工智能的主要研究范围和
应用领域。
例2：(分油问题) 有A、B、C三个不带刻度的 瓶子，分别能装8kg, 5kg和3kg油。如果A瓶 装满油，B和C是空瓶，怎样操作三个瓶，使 A中的油平分两份？(假设分油过程中不耗油)
解：第一步： 定义问题状态的描述形式： 设Sk=(M,C,B)表示传教士和野人在河右岸
的状态。 其中：
M表示传教士在右岸的人数。 C表示野人在右岸的人数。 B用来表示船是不是在右岸。
(B=1表示在右岸，B=0表示在左岸)。 初始状态集：S={(3,3,1)} 目标状态集：G={(0,0,0)}
第二步：定义算符。 算符R(i, j)表示划船将i个传教士和j个野
f4：从B瓶往C瓶倒油， 把C瓶倒满。
f5：从B瓶往A瓶倒油， 把B瓶倒空。
f6：从B瓶往C瓶倒油， 把B瓶倒空。
f1 f5 f7 0,0
f7
f1 f5
f7：从C瓶往A瓶倒油，
5,2
f4 f2
f3
4,3 f1 5,3
f7 f3
f8
4,0
f4
f5
0,1
f6 f8
f1
1,0
f7 f3
1,3
把C瓶倒空。
f8：从C瓶往B瓶倒油， 把C瓶倒空。
人送到左岸的操作。 算符L(i, j)表示划船从左岸将i个传教士和j
个野人带回右岸的操作。 由于过河的船每次最多载两个人，所以
i+j≤2。这样定义的算符集F中只可能有如下10 个算符。 F：R(1,0), R(2,0), R(1,1), R(0,1), R(0,2)
L(1,0), L(2,0), L(1,1), L(0,1), L(0,2)
解：第一步： 定义问题状态的描述形式： 设Sk=(b,c)表示B瓶和C瓶中的油量的状态。
其中： b表示B瓶中的油量。 c表示C瓶中的油量。 初始状态集：S={(0,0)} 目标
操作：把瓶子倒满油，或把瓶子的油倒空。 f1：从A瓶往B瓶倒油，把B瓶倒满。 f2：从C瓶往B瓶倒油，把B瓶倒满。 f3：从A瓶往C瓶倒油，把C瓶倒满。 f4：从B瓶往C瓶倒油，把C瓶倒满。 f5：从B瓶往A瓶倒油，把B瓶倒空。 f6：从B瓶往C瓶倒油，把B瓶倒空。 f7：从C瓶往A瓶倒油，把C瓶倒空。 f8：从C瓶往B瓶倒油，把C瓶倒空。
2.2 问题归约法
➢问题归约法的组成部分 （1）一个初始问题描述； （2）一套把问题变换为子问题的操 作符； （3）一套本原问题描述。
2.3 谓词逻辑法
➢ 一阶谓词逻辑表示法适于表示确定 性的知识。它具有自然性、精确性、严 密性及易实现等特点。
2.3 谓词逻辑法
➢ 用一阶谓词逻辑法表示知识的步骤 如下： （1）定义谓词及个体，确定每个谓词及 个体的确切含义。 （2）根据所要表达的事物或概念，为每 个谓词中的变元赋以特定的值。 （3）根据所要表达的知识的语义，用适 当的连接符号将各个谓词连接起来，形 成谓词公式。