人工智能+试题+课件

人工智能的定义AI ( Artificial Intelligence )

是研究如何使用机器，能够做一些通常需要人的智慧才能完成的工作。或人工智能就是机器（计算机）执行某些与人的智能有关的复杂功能（如判断、识别、学习、理解、问题求解等）的能力。 1.2 人工智能的研究途径与方法 1.2.1 结构模拟，神经计算

④采用结构模拟，运用神经网络和神经计算的方法研究人工智能者→生理学派、连接主义。 1.2.2 功能模拟（符号主义、心理学派、逻辑学派） 1.2.3 行为模拟（行为主义、进化主义、控制论学派）

④以行为模拟法研究人工智能者→行为主义、进化主义、控制论学派。 1.4 人工智能的基本技术

推理技术。基于谓词逻辑的自然演绎推理和归结反演推理。

搜索技术。盲目搜索、启发式搜索。神经网络搜索。启发式搜索是人工智能的核心课题，

1.5、人工智能的发展概况，需要处理的是知识。由数据处理范围扩展到符号知识处理范畴的转变是人工智能诞生的重要因素之一。

而试探性的搜索、启发式的不精确的模糊的甚至允许出现错误的推理方法指导了人工智能的求解方法。 在许多应用中，被编码进入产生式系统数据库的信息来源于说明语句，这些语句难以或者不能自然地用像数组或集合那样的简单结构来表示。 而逻辑语句，或者更具体地说，一阶谓词演算能用来表示种类众多的语句,且能给出一种从旧知识直接求得新知识的有效方法——数学演绎。

如果我们把句子限制为我们至今已介绍过的造句法所能表示的那些句子，而且也不使用变量项，那么我们可以把这个谓词演算的子集叫做命题演算。

例：每个有理数都是实数 有些实数是有理数 并非每个实数都是有理数 解： 令原子谓词公式 P(x) 表示 x 是有理数 Q(x) 表示 x 是实数 （x）［P(x) => Q(x)］ （彐x）［Q(x) ∧ P(x)］

～(（x）［Q(x) => P(x)］) 等价于 （彐x）［Q(x) ∧ ～P(x)］ 例： 每一个人的外祖父都是他母亲的父亲。

令 P(x) 表示 x 是人 O(x,y) 表示 x 是y的外祖父 F(x,y) 表示 x 是y的父亲

M(x,y) 表示 x 是y的母亲

将原句转化为：每一个人y的外祖父x都是该y的母亲z的父亲。

（x）（y）(P(x)∧P(y)∧O(x,y))=>(彐z)(P(z)∧F(x,z)∧M(z,y))

在一个量化的表达式中的约束变量是一个虚元，它可以用任何一个不在表达式中出现过的其他变量符号来代替。

All blocks on top of blocks that have been moved or that are attached to block that have been moved also have been moved.

可表示为：（x）（y）{{BLOCK（x）∧BLOCK（y）∧［ONTOP（x，y）∨ ATTACHED（x，y）］∧MOVED（y）}→MOVED（x）} 寻找项对变量的置换，以使表达式一致，叫做合一。 求mgu的算法：非递归算法

例：求公式集{P［a，x，f(g(y))］，P［z，h(z,u)，f(u)］}的最一般合一者 mgu。 解： k=0; F0 = F; б0 =ε; F0 不是单一元素集，有 D0 ={a ,z} б1=б0·{ a /z }=ε·{ a /z }={ a /z }； F1=F0·{ a /z }={P［a，x，f(g(y))］，P［a，h(a,u)，f(u)］}； k=1; F1 不是单一元素集，有 D1 ={x ,h(a,u)}

б2=б1·{ h(a,u) /x }={ a /z }·{ h(a,u) /x }={ a /z, h(a,u) /x }； F2=F1·{ h(a,u) /x }={P［a，h(a,u)，f(g(y))］，P［a，h(a,u)，f(u)］}； k=2; F2 非单一，有 D2 ={g(y) ,u}

б3=б2·{ g(y) /u }={ a /z, h(a,g(y)) /x, g(y) /u }； F3=F2·{ g(y) /u }={P［a，h(a, g(y))，f(g(y))］}； k=3;F3 已为单一元素集

∴ б3= { a /z, h(a,g(y)) /x, g(y) /u }为公式集F的mgu 递归

例： E1=’P［a，x，f(g(y))］’

E2=’P［z，h(z,u)，f(u)］’

则： unify(E1,E2); Z1:=unify(‘P’,’P’) Z2:= unify(‘[a ,….]’,’[z,…]’)

return {Z1·Z2} 取值分析

第i层次 F1值 F2值 Z1值 F1属性 F2属性 1 P P 谓词符号 谓词符号 2 [ [ 方括号 方括号 3 a z {a/z} 常量符号 变量符号 4 ， ，

5 x h(a,u) {h(a,u)/x} 变量 函数符号(参数) 6 , , 逗号 逗号 7 f f 函数符号 函数符号 8 ( ( 圆括号 圆括号 9 g(y) u {g(y)/u} 函数符号(参数) 变量 10 ) ) 圆括号 圆括号 11 ] ] 方括号 方括号 归结: 是一种可用于一定的子句公式的重要推理规则。 例 将下列谓词公式

（x）{P（x）→{（y）［P(y)→P(f(x,y))］∧～（按标准步骤化为子句集。

y）［Q(x,y)→P（y）］}}

y)［～Q（x，y）∨P（y）］}}(2) (

x){～

解：(1) (x){～P(x)∨{(y)［～P(y)∨P(f(x,y))］∧～(

P（x）∨{(y)［～P(y)∨P(f(x,y))］∧ （彐y）{～［～Q（x，y）∨P（y）］}}}

(x){～P（x）∨{(y)［～P(y)∨P(f(x,y))］∧（彐y）［Q（x，y）∧～P（y）］}} (3) (x){～P（x）∨{(y)［～P(y)∨P(f(x,y))］∧（彐w）［Q（x，w）∧～P（w）］}} (4) (x) {～P（x）∨{(y)［～P(y)∨P(f(x,y))］∧［Q（x，g（x））∧～P（g（x））］}} 式中，g（x）为一Skolem函数。

(5) (x)(y){～P（x）∨{［～P(y)∨P(f(x,y))］∧［Q（x，g（x））∧～P（g（x））］}} (6) (x)(y){［～P（x）∨～P（y）∨P（f（x，y））］∧［～P（x）∨Q（x，g（x））］∧［～P（x）∨～P（g（x））］}

(7) {［～P（x）∨～P（y）∨P（f（x，y））］∧［～P（x）∨Q（x，g（x））］∧ ［～P（x）∨～P（g（x））］}

(8) ～P（x）∨～P（y）∨P（f（x，y）） ～P（x）∨Q（x，g（x）） ～P（x）∨～P（g（x））

(9)更改变量名称，在上述第(8)步的三个子句中，我们分别以x1，x2和x3代替变量x。这种更改变量名称的过程，有时称为变量分离标准化。于是，我们可以得到下列子句集： ～P（x1）∨～P（y）∨P［f（x1，y）］ ～P（x2）∨Q［x2，g（x2）］ ～P（x3）∨～P［g（x3）］

一般归结规则：设有两个子句 {Li}与{Mi}，

若 {li} 是{Li}的一个子集，{mi}是{Mi}的一个子集， 且存在一个最一般合一者s, 使得 {li}s={～mi}s , 则可归结前提子句{Li}与{Mi}成为 {{Li}-{li}}s∪{{Mi}-{mi}}s

例：考虑两个子句：P［x，f（A）］∨P［x，f（y）］∨Q（y）和～P［z，f（A）］∨～Q（z）如果我们取 {li} = {P［x，f（A）］} {mi} = {～P［z，f（A）］} 那么我们得到归结式：P［z，f（y）］∨～Q（z）∨Q（y） 如果我们取 {li} = {Q（y）} {mi} = {～Q（z）} 那么我们得到归结式： P［x，f（A）］∨P［x，f（y）］∨～P［y，f（A）］ 进一步归结得归结式： P［y，f（y）］ 设有前提公式集S，欲证结论公式L。 步骤：(1)否定L，得～L (2)把～L添加到S中去 (3)把新产生的集合{～L，S}化成子句集； (4)应用归

结原理，力图推导出一个表示矛盾的空子句。 例：前提： 每个储蓄钱的人都获得利息。

结论： 如果没有利息，那么就没有人去储蓄钱。 证明： 令S（x，y）表示“x储蓄y”

M（x）表示“x是钱”I（x）表示“x是利息”E（x，y）表示“x获得y” 于是我们可把上述命题写成下列形式：

前提： ( x)［（彐y）(S(x,y)∧M(y))→（彐y）(I(y)∧E(x,y))］ 结论：～（彐x）I(x)→(x) (y)(S(x,y)→～M(y)) 把前提化为子句形：

( x) [～（彐y）(S(x,y)∧M(y))∨（彐y）(I(y)∧E(x,y))]

( x)[( y) (～S(x,y) ∨～M(y))∨（彐y）(I(y)∧E(x,y))] 令y=f(x)为Skolem函数,则可得子句形如下： (1)～S（x，y）∨～M（y）∨I(f(x)) (2)～S（x，y）∨～M（y）∨E(x，f(x))

又结论的否定为：～(～(彐x)I(x)→(x)( y)(S(x,y)→～M(y))) 化为子句形：～((彐x)I(x)∨(x)( y)(～S(x,y)∨～M(y))) (～(彐x)I(x))∧(～(x)( y)(～S(x,y)∨～M(y)))

(x)(～I(x))∧(彐x) (彐y)(S(x,y)∧M(y))

变量分离标准化之后得下列各子句：(3)～I（z）(4)S（a，b） (5)M（b）

子句(1) 子句(3) {f(x)/z} 子句(6) 子句(4) ～S(x,y)∨～M(y) {a/x,b/y} 子句(7) 子句(5) ～M(b)

NIL 例: 对于所有的x和y，如果x是y的父亲，y是z的父亲，那么x是z的祖父。每个人都有一个父亲。是否会有这样的两个人x和y，使得x是y的祖父？

证明： 令 F(x,y)表示“x是y的父亲” G(x,y)表示“x是y的祖父” 把命题写成下列公式：

(1) (x) (y) (z) [(F(x,y)∧F(y,z))→G(x,z)] (2) (y)(彐x) F(x,y) (3) (彐x)(彐y)G(x,y)

其中，公式(3)是我们试图证明的结论。将公式(1)、(2)化为子句形，得： （1′）～F（x，y）∨～F（y，z）∨G（x，z） （2′）F（f（w），w）x=f（w）为一Skolem函数 取公式(3)的否定：～(3) ～[(彐x)(彐y)G(x,y)] 得其子句形为：

（3′）～G（u，v） 子句(1’) 子句(3’) {u/x,v/z} ～F(u ,y)∨～F(y ,v) 子句(2’)

{f(w)/y,v/w} ～F(u , f(v)) 子句(2’)

{f(w)/u,f(v)/w}

宽度优先搜索方法: 如： (1) P∨Q

S0: (2) ～P∨Q

(3) P∨～Q (4) ～P∨～Q

(5) Q {1-2} (6) P {1-3} (7) Q∨～Q {1-4(i)} S1: (8) P∨～P {1-4(ii)} (9) Q∨～Q {2-3(i)} (10) P∨～P {2-3(ii)} (11) ～P {2-4} (12) ～Q {3-4} S2: ? NIL ?

例： 前提 （1）(x) [R(x)=>L(x)] 任何能阅读的人都是能识字的。

（2）(x) [D(x)=> ～L(x)] 任何海豚都不识字。 （3）(彐x) [D(x) ∧I(x)] 有些海豚是有智力的。

结论：（4）(彐x) [I(x) ∧～R(x)] 有些有智力者不能阅读。 解： 将(1)(2)(3)及(4)的否定化成子句集： (1) I(A) S0: (2) ～I(z)∨R(z)

(3) ～R(x) ∨L(x) (4) ～D(y)∨～L(y)

(5) D(A) (6)R(A) {1-2 A/z} S1: (7) ～I(z)∨L(z) {2-3 z/x}

(8) ～R(y) ∨～D(y) {3-4 y/x}

(9) ～L(A) {4-5 A/y}

NIL (10) L(A) {1-7 A/z } (11) ～I(z) ∨～D(z) {2-8 z/y} (12) L(A) {3-6 A/x} S2: (13) ～R(A) {3-9 A/x } (14) ～I(z) ∨～D(z) {4-7 z/y} (15) ～R(A) {5-8 A/y} (16) ～D(A) {6-8 A/y} (17) ～I(A) {7-9 A/z} S3 ? NIL ?

3.4.3 改进策略 1．支持集策略

准则： 每个归结式的父辈中至少有一个是从目标公式的否定或者从它们的后裔（即从支持集）所引起的子句中间选择的。

结论：若任意反演存在，则支持集反演就存在。 特点：逆向推理之风格，一般可加快推导速度。

例： (1) ～I(z)∨R(z) 目标之否定 S0:(2) I(A) (3) ～R(x) ∨L(x)

(4) ～D(y)∨～L(y) (5) D(A)

S1:(6) R(A) {1-2 A/z} (7) ～I(z)∨L(z) {1-3 z/x}

S2: (8) L(A) {2-7 A/z} (9) L(A) {3-6 A/x} (10)～I(y)∨D(y) {4-7 y/z}

S3:(11)～D(A) {2-10 A/y} (12)～D(A) {4-8 A/y} (13)～D(A) {4-9 A/y} (14)～I(A) {5-10 A/y} S4:

2.线性输入形（藤形）策略

准则： 每个归结式的中至少要有一个父辈属于原始子句集。 不完备性：有时候存在一个反演，但不存在线性输入形反演。 例: (1) I(A) S0: (2) ～I(z)∨R(z) (3) ～R(x) ∨L(x) (4) ～D(y)∨～L(y) (5) D(A) (6) R(A) {1-2 A/z} S1 (7)～I(z)∨L(z) {2-3 z/x} (8)～R(y)∨～D(y) {3-4y/x} (9)～L(A) {4-5 A/y} (10) L(A) {1-7 A/z } (11)～I(z)∨～D(z){2-8 z/y} S2: (12) L(A) {3-6 A/x} (13) ～R(A) {3-9 A/x }

=?（1,1,1）（1,2,2） （1,1,1）?（1,1,3） （1,1,1）=?（3,3,3） （1,2,2）=?（3,2,2） ? （3,2,2）=?（3,3,3） （1,1,3）?（1,2,3） （1,2,3）?（1,2,2） （3,2,2）?（3,2,1） ?

（3,2,1）?（3,3,1） ?

（3,3,1）?（3,3,3） ?

?

?

?

可把状态空间中每一状态（节点）看成是从该状态到目标状态所形成的问题： 第二节 与或图表示 5.2.1 与或图

例如，设想问题A既可由求解问题B和C，也可由求解问题D、E和F，或者由单独求解问题G来解决。这一关系可由如下图所示的结构来表示。图中各节点由它们所表示的问题来标记。

A G 替换集合 M N G A b c d 被归约为单一替换子问题M、N、G.

可解节点:

E F B C D E F M和N 作为附加节点分别为{B,C} {D,E,F}的唯一父辈节点，将M和N理解为具有问题描述作用。问题A

1.终叶节点是可解节点（因为它们与本原问题相关连）。

2.如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解时，此非终叶节点才是可解的。

3.如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。

不可解节点:

1.没有后裔的非终叶节点为不可解节点。

2.如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。

3.如果某个非终叶节点含有与后继节点，那么只有当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。

第三节 与或图的盲目搜索

5.3.1 与或图搜索过程

可解标示过程： 一旦生成了某个可解节点，就要“自下而上”地根据祖先节点与该可解节点的“与或”关系

来标记其祖先节点的可解性。若初始节点能被标示为可解，则算法就成功结束。

不可解标示过程： 一旦生成了某个不可解节点，也要“自下而上”地根据各祖先节点与该节点的“与或”关

系来标记其祖先节点的可解性。若初始节点一被标示为不可解的，则搜索就不成功地终止。

1

2 3 4 5 6 7 8 9 B C D 10 11 12 A 扩展前8个OPEN表下之部分内容

扩展8个节点 删除标记 节点名称 指针 √ 9 B C D 10 11 12 A 扩展第9个节点后 删除标记 节点名称 指针 √ √ √ √ B C D 10 11 12 A 1 2 3 扩展第9个节点,其后继均 4 5 6 7 终叶节点

8 9 B C D 10 11 12 A t t 5.4.1 解树的费用

定义: 总和费用 解树上所有弧线费用的总和

最大费用 解树上具有最大路径费用的那条路径之费用

4 4 5 5 2 6 t 6 3 1 7 t t t 解答A ( 左分枝解) 总和费用 = 4 + 5 + 5 + 6 = 20 最大费用 = 4 + 5 + 6 = 15 解答B ( 右分枝解) 总和费用 = 4 + 6 + 1 + 7= 18 最大费用 = 4 + 6 + 7= 17 5.4.2 费用估计在直接搜索中的应用

例: 设扩展S后得两组与节点(B,C)及(E,F),并设定弧线费用为1,采用总和费用计算:

S A D B C E F .B、C、E、F 新生成点，设由估价函数算出 h(B)=3 h(C)=3 h(E)=3 h(F)=2

h(A)= ∑[C(n,ni)+h(ni)] = 1 + 3 + 1 + 3 = 8 h(D)= ∑[C(n,ni)+h(ni)] = 1 + 3 + 1 + 2 = 7

Min

∴ h（S）= [C(n,ni)+h(ni)]= min [1+8,1+7] = 8 1≤i≤2 5.4.3 与或树的有序搜索算法 例： 下设弧线费用为1

S A D B C E F 3 3 3 2

第一循环.T ：（S） 扩展S 各端代价分别为3，3，3，2 h(B)=3 h(C)=3 h(E)=3 h(F)=2 自下而上算出 h(A)= 8 h(D)= 7 ∴ h(S) = 8

S A D B C E F W V 3 2 2 2 第二循环.T ：（S D E,F ）选n=E 扩展E (2级)

各端估计代价分别为3，2，2，2 重算祖先节点W、V、E、D、S之h值

h(W)=7 h(V)=6 h(E)=7（原为3） h(D)=1+ h(E)+1+h(F)=11 h(S) = 9 5.6.2 博弈树搜索的极小极大过程

例：（1）生成两回合的博弈树，对端节点进行静态估值

min max 2 9 3 1 -1-1 36 8 –12 0 3 4-2 6 –18 –7 –1 0 3 -5 7

(2) 由端点层逐层向上算出各节点的倒推估值(MIN点求最小,MAX点求最大),最后找出始点具有最大倒推估值的步作为欲寻找的最好棋步。

例：一字棋博弈 {3X3棋盘，先成一线者为胜 } 静态估值函数 e(P)

P为MAX获胜节点 e(P) = ∞ P为MIN获胜节点 e(P) = -∞

P为不分胜负节点 e(P) = MAX的“尚可成线之条数”

如：P 为 X e(P) = 8 – 4 = 4

O X e(P) = 5– 4 = 1

5.6.3 α－β过程

当算法采用择优方式进行搜索时，则可配合使用如下的α－β剪枝过程（α－β剪枝技术）

? MAX点α值---- 可能不够大的MAX值 ? MIN点β值---- 可能不够小的MIN值 例1： 假设以有界深度优先方式进行搜索（2层）

max 点 α

=-1

=-2 -1 min 点 β

0 1 -1 -2

α

例2：

min 点 β= 1

- cut off

1 此 max 点α

1 0 3 =3 (由最左子代而定) 要做β剪枝

β

- cut off

α－β剪枝规则：

(1) α剪枝: 若任何MIN节点的β值小于或等于任何它的祖先节点MAX的α值时，则可以终止该MIN节点以下的搜索，这个MIN节点最终的倒推值可设置为它的β值。

(2) β剪枝: 若任何MAX节点的α值大于或等于它的祖先节点MIN的β值，则可以终止该MAX节点以下的搜索，这个MAX节点的最终倒推值可设置为它的α值。

如何将已获得的有关知识以计算机内部代码形式加以合理地描述、存储，以便有效地利用这些知识便是知识表示

ROBIN AKO part-of

BIRD 动物 WIN 是一种 羽毛 part-of 鸟 AKO AKO 不会 飞 鸵鸟 鹦鹉 CLYDE Isa ROBIN AKO BIRD part-of WING NEST-1 NEST owns isa {增加新知识}

例 John gave Mary the book.

动作“给”可以看做一个三元关系，其中三个属性为给予者、接收者和一个被给的物体。 GIVE(John,Mary,book)化为二元关系表示:

Isa(G1,Giving-events)∧giver(G1,John)∧recip(G1,Mary)∧obj(G1,book)

Giving-events ISA Giver obj John G1 book

Recip Isa

Mary Phys-objs 或关系的表示 （附加 DIS 界限标注） Disjunction 析取

例 isa(A,B) ∨part-of(B,C) C part-of B isa

A “非”关系表示(采用~isa , ~part-of或加NEG界限标注 )

例: ~isa { ~[isa(A,B)] }

A B

B ~ part-of C { ~[part-of(B,C)] } NEG part-of B { ~[isa(A,B) ∧part-of(B,C)] } isa A C “蕴含”关系的表示(附加ANTE 及CONSE界限标注,并将两者连接起来)前因 后果

例: Every one who lives at 37 Maple street is a programmer.

ADDRESS-EVENTS OCCUPATION-EVENTS ANTE CONSE Isa isa y person x worker O(x,y) {处所} {职业} loc prefession 37-Maple-ST PROGRAMMER 6.2.7 单元表示方法简介

假设我们有以下事实： John gave Mary the book（约翰给玛丽这本书）

通常我们可以用谓词逻辑来表示这些事实： GIVE（JOHN，MARY，BOOK）

在单元表示法中，使用槽来表示知识。每个槽表示事物的一个方面。槽又由槽名和槽值或填充值两部分组成。用单元表示法，首先要把多元关系转换成一组二元关系的合取“约翰给玛丽这本书”这件事用G1来表示。它是GIVING-EVENTS这个事件的一个实例。所以，G1和GIVING-EVENTS之间的关系可表示为：

ISA（G1，GIVING-EVENTS）

则上述例子可表示为下述二元关系的合取： ISA（G1，GIVING-EVENTS） GIVER（G1，JOHN） RECEIP（G1，MARY） OBJ（G1，BOOK）

用单元表示法，上述事实可表示为

G1Self:（element-of GIVING-EVENTS）giver：JOHN

receip：MARY obj：BOOK

有时槽值不是如JOHN这样的常量符号，而是函数表示式，特别是这个函数可能相当于另一单元的槽名。“例如句子“John gave the book to Mary”（约翰给玛丽这本书）和“Bill gave the pen to person to whom John gave the book”（比尔把笔给那个约翰给他书的人）。我们可以用下述单元来表示： G1Self:（element-of GIVING-EVENTS） giver：JOHN receip：MARY obj：BOOK

G2Self:（element-of GIVING-EVENTS）

Giver：BILL

Receip：receip（G1） Obj：PEN

“或”与“非”的表示 定义函数

the-set-of : 由一批个体构成的集合 intersection:两个集合的交集 union : 两个集合的并集

complement:某个集合的补集（“非”的概念） 例 John gave the book to Mary or Bill . 用单元可表示为：(或) G3  Self：（element-of GIVING-EVENTS）

Giver：JOHN Receip：（element-of the-set-of（MARY，BILL））

Obj：BOOK

例： John买了一支笔，它是钢笔或是圆珠笔，但不是红色的。 B1 Self: （element-of BUYING-EVENTS）

Buyer: John

Bought: element-of intersection(union(pens,BALL-pens),complement(RED-THINGS))

本文来源：https://www.bwwdw.com/article/vgzd.html