人工智能 状态空间法 第二章主讲.ppt

2.1状态空间法（State Space Representation） 问题求解技术主要是两个方面： 问题的表示 求解的方法 状态空间法 状态（state） 算符（operator） 状态空间方法 2.1.1 问题状态描述 基本概念 状态(state)????它是为描述某类不同事物间的差别而引入的一组最少变q0,q1,…,qn的有序集合,其矢量形式如下:?????? Q=[q0,q1,…,qn]T??????(2.1) 式中每个元素qi(i=0,1,…,n)为集合的分量,称为状态变量。给定每个分量的一组值就得到一个具体的状态,如????? ?Qk=[q０k ,q1k,…,qnk]T??????(2.2) 操作符(operator)???? 称使问题从一种状态变化到另一种状态的手段为操作符或算符。 问题的状态空间： 是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。 2. 状态空间表示概念详释 例如下棋、迷宫及各种游戏。 例:三数码难题（3 puzzle problem） 2.3 谓词逻辑法 2.3.2 谓词公式 原子公式的的定义： 用P(x1，x2，…，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,…，xn为客体变量或变元。通常把P(x1,x2,…,xn)叫做谓词演算的原子公式，或原子谓词公式。 分子谓词公式 可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。 合适公式（WFF，well-formed formulas） 合适公式的递归定义 合适公式的性质 合适公式的真值 等价（Equivalence) 2.3 谓词逻辑法 合适公式(WFF ,well-formed formulas)的递归定义： 　　(1) 原子谓词公式是合适公式。 　　(2) 若A为合适公式，则～A也是一个合适公式。 　　(3) 若A和B都是合适公式， 则(A∧B),(A∨B),(ATB), (A←→B)也都是合适公式。 　　(4) 若A是合适公式，x为A中的自由变元， 则( x) A ,(Ex) A都是合适公式。 　　(5) 只有按上述规则(1)至(4)求得的那些公式，才是合适公式。 2.3 谓词逻辑法 例题： 对于所有的x，如果x是整数，则x或为正的或者为负的。 I(x)表示x是整数，P(x)表示x是正数，N(x)表示x是负数。 例题： 对于所有的x，如果x是整数，则x或为正的或者为负的。 例题：对于所有的x，如果x是整数，则x或为正的或者为负的。“ ( x) (I(x)=(P(x) ∨N(x) )) I(x)表示x是整数，P(x)表示x是正数，N(x)表示x是负数。 2.3 谓词逻辑法 　　2.合适公式的性质 　　 (1) 否定之否定 ? 　　(2) P∨Q ? 　　(3) 狄·摩根定理 ? ? 　　(4) 分配律 ? ? (5) 交换律 ? ? 　　(6) 结合律 ? ? 　　(7) 逆否律  在一个量化的表达式中的约束变量是一类虚元,它可以用任何一个不在表达式中出现过的其它变量符号来代替。举例如下： 2.3 谓词逻辑法 2.3.3 置换与合一 置换 概念 假元推理 全称化推理 综合推理 定义 就是在该表达式中用置换项置换变量 性质 可结合的 不可交换的 2.3 谓词逻辑法 置换：用项(A)替换函数表达式中的变量(x)，记为ES， 即表示一个表达式E (Expression)，用一个置换S (Substitution)而得到的表达式的置换。 例1表达式P [x, f(y) ,B]的4个置换为 ： s1={z/x, w/y} s2={A/y} s3={q(z)/x , A/y} s4={c/x , A/y} 我们用Es来表示一个表达式E用置换s所得到的表达式的置换。 于是，我们可得到P[x,f(y),B]的4个置换的例，如下： P[x,f(y),B]s1=P[z, f(w), B] P[x,f(y),B]s2=P[x, f(A), B] P[x,f(y),B]s3=P[q(z), f(A) ,B] P[x,f(y),B]s4=P[c,f(A),B]2) 2.3 谓词逻辑法 合一（Unification) 合一：寻找项对变量的置换，以使两表达式一致。 可合一：如果一个置换s作用于表达式集{Ei}的每个元素，则我们用{Ei} s来表示置换例的集。我们称表达式集{Ei}是可合一的。