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 问题归约法
➢问题归约法的概念
❖已知问题的描述,通过一系列变换把此 问题最终变为一个子问题集合;这些子 问题的解可以直接得到,从而解决了初 始问题。
❖该方法也就是从目标(要解决的问题)出发 逆向推理,建立子问题以及子问题的子 问题,直至最后把初始问题归约为一个 平凡的本原问题集合。这就是问题归约 的实质。