人工智能全册配套完整精品课件.ppt

1、人工智能全册配套完整人工智能全册配套完整 精品课件精品课件 2 人工智能人工智能 Artificial Intelligence；简称；简称AI 教学安排 理论：16*2 考试：期末闭卷理论考试 3/56 作业 平时表现 课程成绩 AB 期末考试 C 中期考试 作业和平时表现：30% 期末考试：70% 课程要求：课程要求： 5 人工智能原理及其应用（第三版），王万人工智能原理及其应用（第三版），王万 森著，电子工业出版社森著，电子工业出版社. . C1和和C2的因子的因子C22的二元归结式；的二元归结式； C1的因子的因子C11和和C2的二元归结式；的二元归结式； C1的因子的因子C11和和C

2、2的因子的因子C22的二元归结式。的二元归结式。 这四种二元归结式都是子句这四种二元归结式都是子句C1和和C2的二元归结式，记为的二元归结式，记为C12。 例例2.29 设设C1=P(y)P(f(x)Q(g(x) ，C2=P(f(g(a)Q(b)，求，求C12。 解：解：对对C1 ，取合一，取合一=f(x)/y，得，得C1的因子的因子 C1=P(f(x)Q(g(x) 对对C1的因子和的因子和C2归结（归结（=g(a)/x ），可得到），可得到C1和和C2的二元归结式的二元归结式 C12=Q(g(g(a)Q(b) 说明：说明： 对谓词逻辑，对谓词逻辑，定理定理2.2仍然适用，即归结式仍然适用，即

3、归结式C12是其亲本子句是其亲本子句C1和和C2的逻辑的逻辑 结论。用归结式取代它在子句集结论。用归结式取代它在子句集S中的亲本子句，所得到的子句集仍然保持中的亲本子句，所得到的子句集仍然保持 着原子句集着原子句集S的不可满足性。的不可满足性。 此外，对谓词逻辑此外，对谓词逻辑定理定理2.3也仍然适用，即从不可满足的意义上说，一阶也仍然适用，即从不可满足的意义上说，一阶 谓词逻辑的归结原理也是完备的谓词逻辑的归结原理也是完备的 189 4. 归结演绎推理的方法归结演绎推理的方法 命题逻辑的归结反演命题逻辑的归结反演(1/2) 归结原理归结原理 假设假设F为已知前提，为已知前提，G为欲证明的结论

4、，归结原理把证明为欲证明的结论，归结原理把证明G为为F的逻辑结论的逻辑结论 转化为证明转化为证明FG为不可满足。为不可满足。 再根据定理再根据定理3.1，在不可满足的意义上，公式集，在不可满足的意义上，公式集FG与其子句集是等价与其子句集是等价 的，即把公式集上的不可满足转化为子句集上的不可满足。的，即把公式集上的不可满足转化为子句集上的不可满足。 归结反演归结反演 应用归结原理证明定理的过程称为应用归结原理证明定理的过程称为归结反演归结反演。 归结反演过程归结反演过程 在命题逻辑中，已知在命题逻辑中，已知F，证明，证明G为真的归结反演过程如下：为真的归结反演过程如下： 否定目标公式否定目标公

5、式G，得，得G; 把把G并入到公式集并入到公式集F中，得到中，得到F，G； 把把F，G化为子句集化为子句集S。 应用归结原理对子句集应用归结原理对子句集S中的子句进行归结，并把每次得到的归结式并中的子句进行归结，并把每次得到的归结式并 入入S中。如此反复进行，若出现空子句，则停止归结，此时就证明了中。如此反复进行，若出现空子句，则停止归结，此时就证明了G为真。为真。 190 4. 归结演绎推理的方法归结演绎推理的方法 命题逻辑的归结反演命题逻辑的归结反演(2/2) P QR R P QP QT Q T T NIL 例例2.30 设已知的公式集为设已知的公式集为P, (PQ)R, (ST)Q,

6、T，求证结论，求证结论R 解：解：假设结论假设结论R为假为假, 将将R加入公式集，加入公式集， 并化为子句集并化为子句集 S=P,PQR, SQ, TQ, T, R 其归结过程如右图的归结树所示。其归结过程如右图的归结树所示。 其含义为：其含义为：先假设子句集先假设子句集S中的所有子中的所有子 句均为真，即原公式集为真句均为真，即原公式集为真,R也为真；也为真； 然后利用归结原理，对子句集进行归结，然后利用归结原理，对子句集进行归结， 并把所得的归结式并入子句集中；重复这并把所得的归结式并入子句集中；重复这 一过程，最后归结出了空子句。一过程，最后归结出了空子句。 根据归结原理的完备性，可知子

7、句集根据归结原理的完备性，可知子句集S 是不可满足的，即开始时假设是不可满足的，即开始时假设R为真是为真是 错误的，这就证明了错误的，这就证明了R为真。为真。 191 4. 归结演绎推理的方法归结演绎推理的方法 谓词逻辑的归结演绎推理谓词逻辑的归结演绎推理(1/3) 谓词逻辑的归结反演谓词逻辑的归结反演 谓词逻辑的归结反演过程与命题逻辑的归结反演过程相比，其步骤基本相谓词逻辑的归结反演过程与命题逻辑的归结反演过程相比，其步骤基本相 同，但每步的处理对象不同。例如，在步骤同，但每步的处理对象不同。例如，在步骤(3)化简子句集时，谓词逻辑需要化简子句集时，谓词逻辑需要 把由谓词构成的公式集化为子句

8、集；在步骤把由谓词构成的公式集化为子句集；在步骤(4)按归结原理进行归结时，谓词按归结原理进行归结时，谓词 逻辑的归结原理需要考虑两个亲本子句的合一。逻辑的归结原理需要考虑两个亲本子句的合一。 例例2.31 已知已知 F: (x)(y)(A(x, y)B(y)(y)(C(y)D(x, y) G: (x)C(x)(x)(y)(A(x, y)B(y) 求证求证G是是F的逻辑结论。的逻辑结论。 证明：证明：先把先把G否定，并放入否定，并放入F中，得到的中，得到的F, G为为 ( x)( y)(A(x,y)B(y)( y)(C(y)D(x,y), ( x)C(x)( x)( y)(A(x,y) B(y

9、) 192 4. 归结演绎推理的方法归结演绎推理的方法 谓词逻辑的归结演绎推理谓词逻辑的归结演绎推理(2/3) 再把再把F,G化成子句集，得到化成子句集，得到 (1) A(x,y) B(y) C(f(x) (2) A(u,v) B(v) D(u,f(u) (3) C(z) (4) A(m,n) (5) B(k) 其中，其中，(1)、(2)是由是由F 化出的两个子句，化出的两个子句，(3)、(4)、(5)是由是由G化出的化出的3个子句。个子句。 最后应用谓词逻辑的归结原理对上述子句集进行归结，其过程为最后应用谓词逻辑的归结原理对上述子句集进行归结，其过程为 (6) A(x,y) B(y) 由由(

10、1)和和(3)归结，取归结，取=f(x)/z (7) B(n) 由由(4)和和(6)归结，取归结，取=m/x,n/y (8) NIL 由由(5)和和(7)归结，取归结，取=n/k 因此，因此，G是是F 的逻辑结论。的逻辑结论。 上述归结过程可用如下归结树来表示上述归结过程可用如下归结树来表示 193 4. 归结演绎推理的方法归结演绎推理的方法 谓词逻辑的归结演绎推理谓词逻辑的归结演绎推理(3) A(x,y) B(y)C(f(x) C(z) A(x,y) B(y)A(m,n) B(n)B(k) NIL f(x)/z m/x,n/y n/k 194 5. 用归结反演求取问题的答案用归结反演求取问题

11、的答案 归结原理除了可用于定理证明外，归结原理除了可用于定理证明外，还可用来求取问题答案，其思想与定理还可用来求取问题答案，其思想与定理 证明相似。证明相似。 一般步骤为：一般步骤为： (1) 把问题的已知条件用谓词公式表示出来，并化为相应的子句集；把问题的已知条件用谓词公式表示出来，并化为相应的子句集； (2) 把问题的目标的否定用谓词公式表示出来，并化为子句集；把问题的目标的否定用谓词公式表示出来，并化为子句集； (3) 对目标否定子句集中的每个子句，构造该子句的重言式（即把该目标对目标否定子句集中的每个子句，构造该子句的重言式（即把该目标 否定子句和此目标否定子句的否定之间再进行析取所得

12、到的子句），用这些否定子句和此目标否定子句的否定之间再进行析取所得到的子句），用这些 重言式代替相应的目标否定子句式，并把这些重言式加入到前提子句集中，重言式代替相应的目标否定子句式，并把这些重言式加入到前提子句集中， 得到一个新的子句集；得到一个新的子句集； (4) 对这个新的子句集，应用归结原理求出其证明树，这时证明树的根子对这个新的子句集，应用归结原理求出其证明树，这时证明树的根子 句不为空，称这个证明树为句不为空，称这个证明树为修改的证明树修改的证明树； (5) 用修改证明树的根子句作为回答语句，则答案就在此根子句中。用修改证明树的根子句作为回答语句，则答案就在此根子句中。 195 5

13、. 用归结反演求取问题的答案用归结反演求取问题的答案 例例2.32 已知：已知：“张和李是同班同学，如果张和李是同班同学，如果x和和y是同班同学，则是同班同学，则x的教室也的教室也 是是y的教室，现在张在的教室，现在张在302教室上课。教室上课。” 问：问：“现在李在哪个教室上课？现在李在哪个教室上课？” 解：解：首先定义谓词：首先定义谓词： C(x, y) x和和y是同班同学；是同班同学； At(x, u) x在在u教室上课。教室上课。 把已知前提用谓词公式表示如下：把已知前提用谓词公式表示如下： C(zhang, li) (x) (y) (u) (C(x, y)At(x, u)At(y,u

14、) At(zhang, 302) 把目标的否定用谓词公式表示如下：把目标的否定用谓词公式表示如下： (v)At(li, v) 196 5. 用归结反演求取问题的答案用归结反演求取问题的答案 把上述公式化为子句集：把上述公式化为子句集： C(zhang, li) C(x, y)At(x, u)At(y, u) At(zhang, 302) 把目标的否定化成子句式，并用重言式把目标的否定化成子句式，并用重言式 At(li,v) At(li,v) 代替之。代替之。 把此重言式加入前提子句集中，得到一个新的子句集，对这个新的子句集，把此重言式加入前提子句集中，得到一个新的子句集，对这个新的子句集， 应

15、用归结原理求出其证明树。应用归结原理求出其证明树。 其求解过程如下图所示。其求解过程如下图所示。 197 5. 用归结反演求取问题的答案用归结反演求取问题的答案 At(li,v)At(li,v) C(x, y)At(x, u)At(y, u) At(li,v) C(x, li)At(x, v)C(zhang, li) At(zhang,v)At(li, v) At(zhang, 302) At(li, 302) li/y,v/u Zhang/x 302/v 该证明树的根子句就是所求的答案，即该证明树的根子句就是所求的答案，即“李明在李明在302教室教室”。 198 第第2章章 确定性知识系统确

16、定性知识系统 按照符号主义的观点，知识是一切智能行为的基础，要使计算机具有智能，按照符号主义的观点，知识是一切智能行为的基础，要使计算机具有智能， 首先必须使它拥有知识，并且能够使用知识。首先必须使它拥有知识，并且能够使用知识。 2.1 确定性知识系统概述确定性知识系统概述 2.2 确定性知识表示方法确定性知识表示方法 2.3 确定性知识推理方法确定性知识推理方法 2.4 确定性知识系统简介确定性知识系统简介 2.4.1 产生式系统简例产生式系统简例 2.4.2 归结演绎系统简例归结演绎系统简例 199 2.4.1 产生式系统简例产生式系统简例 基于规则的动物识别系统基于规则的动物识别系统(1

17、/4) 例例2.23 一个用于动物识别的产生式系统一个用于动物识别的产生式系统 该系统可以识别老虎、金钱豹、斑马、长颈鹿、企鹅、信天翁这该系统可以识别老虎、金钱豹、斑马、长颈鹿、企鹅、信天翁这6种动物。种动物。 其规则库包含如下其规则库包含如下15条规则：条规则： r1 IF 动物有毛发动物有毛发 THEN 动物是哺乳动物动物是哺乳动物 r2 IF 动物有奶动物有奶 THEN 动物是哺乳动物动物是哺乳动物 r3 IF 动物有羽毛动物有羽毛 THEN 动物是鸟动物是鸟 r4 IF 动物会飞动物会飞 AND 动物会下蛋动物会下蛋 THEN 动物是鸟动物是鸟 r5 IF 动物吃肉动物吃肉 THEN

18、动物是食肉动物动物是食肉动物 r6 IF 动物有犬齿动物有犬齿 AND 动物有爪动物有爪 AND 该物眼盯前方该物眼盯前方 THEN 动物是食肉动物动物是食肉动物 r7 IF 动物是哺乳动物动物是哺乳动物 AND 动物有蹄动物有蹄 THEN 动物是有蹄类动物动物是有蹄类动物 r8 IF 动物是哺乳动物动物是哺乳动物 AND 动物是嚼反刍动物动物是嚼反刍动物 THEN 动物是有蹄类动物动物是有蹄类动物 r9 IF 动物是哺乳动物动物是哺乳动物 AND 动物是食肉动物动物是食肉动物 AND 动物是黄褐色动物是黄褐色 AND 动物身上有暗斑点动物身上有暗斑点 THEN 动物是金钱豹动物是金钱豹 20

19、0 2.4.1 产生式系统简例产生式系统简例 基于规则的动物识别系统基于规则的动物识别系统(2/4) r10 IF 动物是哺乳动物动物是哺乳动物 AND 动物是食肉动物动物是食肉动物 AND 动物是黄褐色动物是黄褐色 AND 动物身上有黑色条纹动物身上有黑色条纹 THEN 动物是虎动物是虎 r11 IF 动物是有蹄类动物动物是有蹄类动物 AND 动物有长脖子动物有长脖子 AND 动物有长腿动物有长腿 AND 动物身上有暗斑点动物身上有暗斑点 THEN 动物是长颈鹿动物是长颈鹿 r12 IF 动物是有蹄类动物动物是有蹄类动物 AND 动物身上有黑色条纹动物身上有黑色条纹 THEN 动物是斑马动物

20、是斑马 r13 IF 动物是鸟动物是鸟 AND 动物有长脖子动物有长脖子 AND 动物有长腿动物有长腿 AND 动物不会飞动物不会飞 AND 动物有黑白二色动物有黑白二色 THEN 动物是鸵鸟动物是鸵鸟 r14 IF 动物是鸟动物是鸟 AND 动物会游泳动物会游泳 AND 动物不会飞动物不会飞 AND 动物有黑白二色动物有黑白二色 THEN 动物是企鹅动物是企鹅 r15 IF 动物是鸟动物是鸟 AND 动物善飞动物善飞 THEN 动物是信天翁动物是信天翁 其中，其中，ri(i=1,2,.,15)是规则的编号是规则的编号 初始综合数据库包含的事实有：初始综合数据库包含的事实有： 动物有暗斑点，动

21、物有暗斑点，动物动物有长脖子，有长脖子，动物动物有长腿，有长腿，动物动物有奶，有奶，动物动物有蹄有蹄 该例子的部分推理网络如下：该例子的部分推理网络如下： 201 2.4.1 产生式系统简例产生式系统简例 基于规则的动物识别系统基于规则的动物识别系统(3/4) r2 r8 r11 r12 r1 图中最上层的结点称为图中最上层的结点称为“假设假设”或或“结论结论” 中间结点称为中间结点称为“中间假设中间假设”； 终结点称为终结点称为“证据证据”或或“事实事实”； 每个每个“结论结论”都是本问题的一个目标，所有都是本问题的一个目标，所有“假设假设”构成了本问题的目标集构成了本问题的目标集 合合 动

22、物是长颈鹿动物是长颈鹿 动物有暗斑点动物有暗斑点动物有长脖子动物有长脖子 动物有蹄动物有蹄 动物是有蹄类动物动物是有蹄类动物 动物是斑马动物是斑马 动物是嚼反刍动物动物是嚼反刍动物 动物是哺乳动物动物是哺乳动物 动物有奶动物有奶 动物有毛发动物有毛发 动物有长腿动物有长腿动物有黑条纹动物有黑条纹 r7 202 2.4.1 产生式系统简例产生式系统简例 基于规则的动物识别系统基于规则的动物识别系统(4/4) 系统的推理过程系统的推理过程 (1) 先从规则库中取出第一条规则先从规则库中取出第一条规则r1，检查其前提是否可与综合数据库中的已，检查其前提是否可与综合数据库中的已 知事实相匹配。知事实相

23、匹配。 r1的前提是的前提是“动物有毛发动物有毛发”，但事实库中无此事实，故匹配失败。，但事实库中无此事实，故匹配失败。 然后取然后取r2，该前提可与已知事实，该前提可与已知事实“动物有奶动物有奶”相匹配，相匹配，r2被执行，并将其结论被执行，并将其结论 “动物是哺乳动物动物是哺乳动物”作为新的事实加入到综合数据库中。此时，综合数据库的内作为新的事实加入到综合数据库中。此时，综合数据库的内 容为：容为： 动物有暗斑，动物有长脖子，动物有长腿，动物有奶，动物有蹄动物有暗斑，动物有长脖子，动物有长腿，动物有奶，动物有蹄 动物是哺乳动物动物是哺乳动物 (2) 再从规则库中取再从规则库中取r3，r4，

24、r5，r6进行匹配，均失败。接着取进行匹配，均失败。接着取r7，该前提与已，该前提与已 知事实知事实“动物是哺乳动物动物是哺乳动物”相匹配，相匹配，r7被执行，并将其结论被执行，并将其结论“动物是有蹄类动物动物是有蹄类动物” 作为新的事实加入到综合数据库中。此时，综合数据库的内容变为：作为新的事实加入到综合数据库中。此时，综合数据库的内容变为： 动物有暗斑，动物有长脖子，动物有长腿，动物有奶，动物有蹄动物有暗斑，动物有长脖子，动物有长腿，动物有奶，动物有蹄 动物是哺乳动物，动物是有蹄类动物动物是哺乳动物，动物是有蹄类动物 (3) 此后，此后，r8，r9，r10均匹配失败。接着取均匹配失败。接着

25、取r11，该前提，该前提 “动物是有蹄类动物动物是有蹄类动物 AND 动物有长脖子动物有长脖子 AND 动物有长腿动物有长腿 AND 动物身上有暗斑动物身上有暗斑” 与已知事实相与已知事实相 匹配，匹配，r11被执行，并推出被执行，并推出“动物是长颈鹿动物是长颈鹿”。由于。由于“长颈鹿长颈鹿”已是目标集合中已是目标集合中 的一个具体动物，即已推出最终结果，故问题求解过程结束。的一个具体动物，即已推出最终结果，故问题求解过程结束。 203 2.4.2 归结演绎系统简例归结演绎系统简例 归结演绎推理的经典例子归结演绎推理的经典例子(1/8) 例例2.34 “快乐学生快乐学生”问题问题 假设：任何通

26、过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的假设：任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的 人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。 求证：张是快乐的。求证：张是快乐的。 解：解：先定义谓词：先定义谓词： Pass(x, y) x可以通过可以通过y考试考试 Win(x, prize) x能获得奖励能获得奖励 Study(x) x肯学习肯学习 Happy(x) x是快乐的是快乐的 Lucky(x) x是幸运的是幸运的 204 2.4.2 归结演绎系统简例归结演绎系统简例 归结

27、演绎推理的经典例子归结演绎推理的经典例子(2/8) 再将问题用谓词表示如下：再将问题用谓词表示如下： “任何通过计算机考试并奖的人都是快乐的任何通过计算机考试并奖的人都是快乐的” (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

28、(x, prize) 结论结论“张是快乐的张是快乐的”的否定的否定 Happy(zhang) 205 2.4.2 归结演绎推理的方法归结演绎推理的方法 归结演绎推理的经典例子归结演绎推理的经典例子(3/8) 将上述谓词公式转化为子句集如下：将上述谓词公式转化为子句集如下： (1) Pass(x, computer)Win(x, prize)Happy(x) (2) Study(y)Pass(y, z) (3) Lucky(u)Pass(u, v) (4) Study(zhang) (5) Lucky(zhang) (6) Lucky(w)Win(w, prize) (7) Happy(zhan

29、g) (结论的否定结论的否定) 206 2.4.2 归结演绎推理的方法归结演绎推理的方法 归结演绎推理的经典例子归结演绎推理的经典例子(4/8) Pass(x, computer)Win(x, prize)Happy(x) Lucky(w)Win(w, prize) Pass(w, Computer)Happy(w) Lucky(w) Happy(zhang) Lucky(zhang)Pass(zhang, Computer)Lucky(zhang) Pass(zhang, Computer)Lucky(u)Pass(u, v) Lucky(zhang)Lucky(zhang) NIL w/x

30、 zhang/w zhang/u, computer/v 207 2.4.2 归结演绎推理的方法归结演绎推理的方法 归结演绎推理的经典例子归结演绎推理的经典例子(5/8) 下面再给出一个经典的归结问题下面再给出一个经典的归结问题 例例2.25 “激动人心的生活激动人心的生活”问题问题 假设：所有不贫穷并且聪明的人都是快乐的，那些看书的人是聪明的。李假设：所有不贫穷并且聪明的人都是快乐的，那些看书的人是聪明的。李 明能看书且不贫穷，快乐的人过着激动人心的生活。明能看书且不贫穷，快乐的人过着激动人心的生活。 求证：李明过着激动人心的生活。求证：李明过着激动人心的生活。 解：先定义谓词：解：先定义谓

31、词： Poor(x) x是贫穷的是贫穷的 Smart(x) x是聪明的是聪明的 Happy(x) x是快乐的是快乐的 Read(x) x能看书能看书 Exciting(x) x过着激动人心的生活过着激动人心的生活 208 2.4.2 归结演绎推理的方法归结演绎推理的方法 归结演绎推理的经典例子归结演绎推理的经典例子(6/8) 再将问题用谓词表示如下：再将问题用谓词表示如下： “所有不贫穷并且聪明的人都是快乐的所有不贫穷并且聪明的人都是快乐的” (x)(Poor(x)Smart(x)Happy(x) “那些看书的人是聪明的那些看书的人是聪明的” (y) (Read(y) Smart(y) “李明

32、能看书且不贫穷李明能看书且不贫穷” Read(Liming)Poor(Liming) “快乐的人过着激动人心的生活快乐的人过着激动人心的生活” (z) (Happy(z)Exciting(z) 目标目标“李明过着激动人心的生活李明过着激动人心的生活”的否定的否定 Exciting(Liming) 209 2.4.2 归结演绎推理的方法归结演绎推理的方法 归结演绎推理的经典例子归结演绎推理的经典例子(7/8) 将上述谓词公式转化为子句集如下：将上述谓词公式转化为子句集如下： (1) Poor(x)Smart(x)Happy(x) (2) Read(y)Smart(y) (3) Read(Limi

33、ng) (4) Poor(Liming) (5) Happy(z)Exciting(z) (6) Exciting(Liming) (结论的否定结论的否定) 210 2.4.2 归结演绎推理的方法归结演绎推理的方法 归结演绎推理的经典例子归结演绎推理的经典例子(8/8) Exciting(Liming)Happy(z)Exciting(z) Happy(Liming)Poor(x)Smart(x)Happy(x) Poor(Liming)Smart(Liming)Read(y)Smart(y ) Poor(Liming)Read(Liming)Poor(Liming) Read(Liming)

34、Read(Liming) NIL Liming/z Liming/x Liming/y 211 Thanks! 212 搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将 直接影响到智能系统的性能与推理效率。直接影响到智能系统的性能与推理效率。 3.1 搜索概述搜索概述 3.1.1 搜索的含义搜索的含义 3.1.2 状态空间问题求解方法状态空间问题求解方法 3.1.3 问题归约求解方法问题归约求解方法 3.2 搜索的盲目策略搜索的盲目策略 3.3 状态空间的启发式搜索状态空间的启发式搜索 3.4 与与/或树的

35、启发式搜索或树的启发式搜索 3.5 博弈树的启发式搜索博弈树的启发式搜索 第第3章章 搜索策略搜索策略 213 3.1.1 搜索的含义搜索的含义 概念：概念： 依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造 一条代价最小的推理路线，使问题得以解决的过程称为搜索一条代价最小的推理路线，使问题得以解决的过程称为搜索 适用情况：适用情况： 不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供 求解使用。求解使用。

36、 搜索的类型搜索的类型 按是否使用启发式信息：按是否使用启发式信息： 盲目搜索：盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控并不改变控 制策略制策略。 启发式搜索：启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希 望的方向前进，加速问题的求解过程并找到最优解。望的方向前进，加速问题的求解过程并找到最优解。 按问题的表示方式：按问题的表示方式： 状态空间搜索：状态空间搜索：用状态空间法来求解问题所进行的搜索用状态空间法来求解问题所进行

37、的搜索 与或树搜索：与或树搜索：用问题归约法来求解问题时所进行的搜索用问题归约法来求解问题时所进行的搜索 214 3.1.2 状态空间问题求解方法状态空间问题求解方法 1. 状态空间问题表示状态空间问题表示 状态状态(State) 是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为： Sk=Sk0, Sk1, 当对每一个分量都给以确定的值时，就得到了一个具体的状态。当对每一个分量都给以确定的值时，就得到了一个具体的状态。 操作操作(Operator) 也称为算符，它是把问题从一种状态变换为另一种状态的手段。它可理解为状

38、态集也称为算符，它是把问题从一种状态变换为另一种状态的手段。它可理解为状态集 合上的一个函数，它描述了状态之间的关系。合上的一个函数，它描述了状态之间的关系。 状态空间状态空间(State space) 用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示 为：为： (S, F, G) 其中，其中，S为问题的所有初始状态集合；为问题的所有初始状态集合；F为操作的集合；为操作的集合；G为目标状态的集合。为目标状态的集合。 状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间状态空间也可

39、用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间 图中，节点表示问题的状态，有向边表示操作。图中，节点表示问题的状态，有向边表示操作。 215 状态空间法求解问题的基本过程：状态空间法求解问题的基本过程： 首先，为问题选择适当的首先，为问题选择适当的“状态状态”及及“操作操作”的形式化描述方法；的形式化描述方法； 然后，从某个初始状态出发，每次使用一个然后，从某个初始状态出发，每次使用一个“操作操作”，递增地建立起操作序列，递增地建立起操作序列， 直到达到目标状态为止；直到达到目标状态为止； 最后，由初始状态到目标状态所使用的算符序列就是该问题的一个解。最后，由初始状态到目标状态所

40、使用的算符序列就是该问题的一个解。 3.1.2 状态空间问题求解方法状态空间问题求解方法 2. 状态空间问题求解状态空间问题求解 216 例例3.1 二阶梵塔问题二阶梵塔问题 设有三根钢针，它们的编号分别是设有三根钢针，它们的编号分别是1号、号、2号和号和3号。在初始情况下，号。在初始情况下，1号钢针上穿号钢针上穿 有有A、B两个金片，两个金片，A比比B小，小，A位于位于B的上面。要求把这两个金片全部移到另一根钢的上面。要求把这两个金片全部移到另一根钢 针上，而且规定每次只能移动一个金片，任何时刻都不能使大的位于小的上面针上，而且规定每次只能移动一个金片，任何时刻都不能使大的位于小的上面。 解

41、：解：设用设用Sk=(SkA, SkB)表示问题的状态，其中，表示问题的状态，其中，SkA表示金片表示金片A所在的钢针号，所在的钢针号，SkB 表示金片表示金片B所在的钢针号。所在的钢针号。 全部可能的问题状态共有以下全部可能的问题状态共有以下9种：种： S0=(1, 1) S1=(1, 2) S2=(1, 3) S3=(2, 1) S4=(2, 2) S5=(2, 3) S6=(3, 1) S7=(3, 2) S8=(3, 3) 3.1.2 状态空间问题求解方法状态空间问题求解方法 3. 状态空间的例子状态空间的例子(1/10) 217 A B A B A B 1 2 3 1 2 3 1 2

42、 3 图图3.1 二阶梵塔问题的初始状态和目标状态二阶梵塔问题的初始状态和目标状态 初始状态集合初始状态集合 S=S0 目标状态集合目标状态集合 G=S4, S8 初始状态初始状态S0和目标状态和目标状态S4、S8如下图如下图 S0=(1, 1)S4=(2, 2)S8=(3, 3) 3.1.2 状态空间问题求解方法状态空间问题求解方法 3. 状态空间的例子状态空间的例子(2/10) 218 操作操作 Aij 表示把金片表示把金片A从第从第i号钢针移到号钢针移到j号钢针上；号钢针上； Bij 表示把金片表示把金片B从第从第i号钢针一到第号钢针一到第j号钢针上。号钢针上。 共有共有12种操作，它们

43、分别是：种操作，它们分别是： A12 A13 A21 A23 A31 A32 B12 B13 B21 B23 B31 B32 根据上述根据上述9种可能的状态和种可能的状态和12种操作，可构成二阶梵塔问题的状态空间图，如下图种操作，可构成二阶梵塔问题的状态空间图，如下图 所示。所示。 3.1.2 状态空间问题求解方法状态空间问题求解方法 3. 状态空间的例子状态空间的例子(3/10) 219 从初始节点从初始节点(1, 1)到目标节点到目标节点(2, 2)及及(3, 3)的任何一条路径都是问题的一个解。其的任何一条路径都是问题的一个解。其 中，最短的路径长度是中，最短的路径长度是3，它由，它由3

44、个操作组成。例如，从个操作组成。例如，从 (1, 1)开始，通过使用操作开始，通过使用操作 A13、B12及及A32，可到达，可到达 (3, 3)。 (1,1) B12 A13 (2,1) (3,2) (2,3) (3,3) (1,3) (3,1) (1,2)(2,2) A32 A12 B13 A23 3.1.2 状态空间问题求解方法状态空间问题求解方法 3. 状态空间的例子状态空间的例子(4/10) 图图3.2 二阶梵塔的状态空间图二阶梵塔的状态空间图 220 例例3.2 修道士修道士(Missionaries)和野人和野人(Cannibals)问题问题(简称简称M-C问题问题)。 设在河的

45、一岸有设在河的一岸有3个野人、个野人、3个修道士和个修道士和1条船，修道士想用这条船把所有的人运到条船，修道士想用这条船把所有的人运到 河对岸，但受以下条件的约束：河对岸，但受以下条件的约束： 第一，修道士和野人都会划船，但每次船上至多可载第一，修道士和野人都会划船，但每次船上至多可载2个人；个人； 第二，在河的任一岸，如果野人数目超过修道士数，修道士会被野人吃掉。第二，在河的任一岸，如果野人数目超过修道士数，修道士会被野人吃掉。 如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没 有修道士被野人吃掉

46、的安全过河计划。有修道士被野人吃掉的安全过河计划。 解：解：先选取描述问题状态的方法。这里，需要考虑两岸的修道士人数和野人数，还先选取描述问题状态的方法。这里，需要考虑两岸的修道士人数和野人数，还 需要考虑船在左岸还是在右岸，故可用如下三元组来表示状态需要考虑船在左岸还是在右岸，故可用如下三元组来表示状态 S=(m, c, b) 其中，其中，m表示左岸的修道士人数，表示左岸的修道士人数，c表示左岸的野人数，表示左岸的野人数，b表示左岸的船数。而右岸的表示左岸的船数。而右岸的 状态可由下式确定：状态可由下式确定： 右岸修道士数右岸修道士数 m=3-m 右岸野人数右岸野人数 c=3-c 右岸船数右

47、岸船数 b=1-b 在这种表示方式下，在这种表示方式下，m和和c都可取都可取0、1、2、3中之一，中之一，b可取可取0和和1中之一。因此，中之一。因此， 共有共有442=32种状态。种状态。 3.1.2 状态空间问题求解方法状态空间问题求解方法 3. 状态空间的例子状态空间的例子(5/10) 221 有效状态有效状态 在在32种状中，除去不合法和修道士被野人吃掉的状态，有效状态只种状中，除去不合法和修道士被野人吃掉的状态，有效状态只16种：种： S0=(3, 3, 1) S1=(3, 2, 1) S2=(3, 1, 1) S3=(2, 2, 1) S4=(1, 1, 1) S5=(0, 3,

48、1) S6=(0, 2, 1) S7=(0, 1, 1) S8=(3, 2, 0) S9=(3, 1, 0) S10=(3, 0, 0) S11=(2, 2, 0) S12=(1, 1,0) S13=(0, 2, 0) S14=(0, 1, 0) S15=(0, 0, 0) 过河操作过河操作 过河操作是指用船把修道士或野人从河的左岸运到右岸，或从右岸运到左岸的动作。过河操作是指用船把修道士或野人从河的左岸运到右岸，或从右岸运到左岸的动作。 每个操作都应当满足如下条件：每个操作都应当满足如下条件： 第一，船上至少有一个人（第一，船上至少有一个人（m或或c）操作，离开岸边的）操作，离开岸边的m和和

49、c的减少数目应该等于到的减少数目应该等于到 达岸边的达岸边的m和和c的增加数目；的增加数目； 第二，每次操作船上人数不得超过第二，每次操作船上人数不得超过2个；个； 第三，操作应保证不产生非法状态。第三，操作应保证不产生非法状态。 操作的结构操作的结构 条件：条件：只有当其条件具备时才能使用只有当其条件具备时才能使用 动作：动作：刻划了应用此操作所产生的结果。刻划了应用此操作所产生的结果。 3.1.2 状态空间问题求解方法状态空间问题求解方法 3. 状态空间的例子状态空间的例子(6/10) 222 操作的表示操作的表示 Lij 表示有表示有i个修道士和个修道士和j个野人，从左岸到右岸的操作个野

50、人，从左岸到右岸的操作 Rij 表示有表示有i个修道士和个修道士和j个野人，从右岸到左岸的操作个野人，从右岸到左岸的操作 操作集操作集 本问题有本问题有10种操作可供选择，他们的集合称为操作集，即种操作可供选择，他们的集合称为操作集，即 A=L01, L10, L11, L02, L20,R01, R10, R11, R02, R20 操作的例子操作的例子 下面以下面以L01和和R01为例来说明这些操作的条件和动作。为例来说明这些操作的条件和动作。 操作符号操作符号 条件条件 动作动作 L01 b=1, m=0或或3, c1 b=0, c=c-1 R01 b=0, m=0或或3，c2 b=1,