知识表示方法part2人工智能课件西电

《知识表示方法part2人工智能课件西电》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ArtificialIntelligence(AI)人工智能主讲：戚玉涛Email：qi_yutao@163.com第二章：知识表示方法内容提要第二章：知识表示方法1.状态空间法2.问题归约法3.谓词逻辑法4.语义网络法5.其他方法问题归约法问题归约（ProblemReduction）是另外一种基于状态空间的问题描述与求解方法已知问题的描述，通过一系列变换把此问题变为一个子问题集合这些子问题的解可以直接得到（本原问题），从而解决了初始问题问题归约法问题归约法的组成部分一个初始问题描述；一套把问题变换为子问题的操

2、作符；一套本原问题描述。(本原问题:不能再分解或变换且直接可解的子问题)问题归约的实质：从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直到最后把初始问题归约为一个本原问题集合。问题归约法问题归约法举例：汉诺塔问题（Hanoi）从1移到3每次移动一个盘子大盘在下小盘在上123CBA初始状态（111）目标状态（333）CBA汉诺塔问题原始问题可以归约为下列3个子问题：子问题1：移动圆盘A和B至柱子2（借助柱子3）子问题2：移动圆盘C至柱子3子问题3：把圆盘A和B移至柱子3（借助柱子1）汉诺塔问题

3、归约过程（3个圆盘）汉诺塔问题汉诺塔问题归约图本原问题本原问题与或图CBA问题归约法与或图表示：用一个类似于图的结构来表示把问题归约为后继问题的替换集合。与图：把一个复杂问题分解为若干个较为简单的子问题，形成“与”树。或图：把原问题变换为若干个较为容易求解的新问题，形成“或”树。问题归约法与或图表示：BCDEFGAHMBCDEFGAN子问题替代集合结构图与或图问题归约法一些关于与或图的术语起始节点对应于原始问题描述终叶节点对应于本原问题问题归约法与或图的构成规则1）与或图中的每个节点代表一个要解决的单一问题或问

4、题集合。图中所含起始节点对应于原始问题A。2）对应于本原问题的节点称为终叶节点，它没有后继节点。3）对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点表示所求得的子问题集合。HMBCDEFGAN问题归约法与或图的构成规则4）一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向次子问题集合中的各个节点。由于只有当集合中所有项都有解时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。5）特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具

5、有一个以上子问题的某个集合时，由上述规则3）和规则4）所产生的图可以得到简化。MDEFAADEF简化问题归约法与或图的搜索：目的在于表明起始节点是有解的。可解节点终叶节点是可解节点（对应于本原问题）。如果某个非终叶节点含有或后继节点，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。问题归约法不可解节点没有后裔的非终叶节点为不可解节点。如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非

6、终叶节点才是不可解的。如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。解树由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树。解树中一定包含初始节点，它对应于原始问题。问题归约法ttttttttt有解节点无解节点终叶节点与或图例子原始问题有一个以上的解原始问题有解内容提要第二章：知识表示方法1.状态空间法2.问题归约法3.谓词逻辑法4.语义网络法5.其他方法谓词逻辑法命题逻辑与谓词逻辑命题逻辑与谓词逻辑是最先用于人工智能的两种逻辑，对于知

7、识的形式化表示，特别是定理的证明发挥了重要作用虽然命题逻辑能够把客观世界的各种事实表示为逻辑命题，但是它具有较大的局限性。命题逻辑只能进行命题间关系的推理，无法解决与命题结构和成分有关的推理问题，不适合表示比较复杂的问题。谓词逻辑是在命题逻辑的基础上发展而来的，命题逻辑可以看作是谓词逻辑的一种特殊形式。谓词逻辑法命题命题是具有真假意义的语句命题代表人们进行思维时的一种判断，若命题的意义为真，称它的真值为“真”，记作“T”；若命题的意义为假，称它的真值为“假”，记作“F”。例如：“西安是陕西省省会”“10大于6”

8、是真值为“T”的命题“月亮是方的”“煤炭是白的”是真值为“F”的命题一个命题不能同时即为真又为假，但可以在一定条件下为真，在另一种条件下为假。例如：“1+1=10”在二进制情况下为真，十进制情况下为假谓词逻辑法命题没有真假意义的语句，如感叹句、疑问句等，不是命题。通常用大写英文字母表示一个命题，例如：P：西安是座古老的城市命题逻辑的局限性？客观事物的结构及逻辑特征？不同事物间的共同特征