AI-9(本)人工智能课件.ppt

人工智能基础人工智能基础三、知识表示三、知识表示n人工智能研究的一个重要议题人工智能研究的一个重要议题如何表示知识如何表示知识?智能体的问题求解能力取决于拥有的领域特有的知识智能体的问题求解能力取决于拥有的领域特有的知识n知识表示技术知识表示技术以计算机能自动处理的形式化方式来表示以计算机能自动处理的形式化方式来表示知识的技术，已趋于成熟。知识的技术，已趋于成熟。n内容：内容：n知识和知识表示的一般概念知识和知识表示的一般概念n基本的知识表示方式基本的知识表示方式产生式表示和结构化表示产生式表示和结构化表示n知识表示的实用化问题知识表示的实用化问题三、知识表示三、知识表示3.1 知识和知识表示知识和知识表示n主要内容：主要内容：n知识原则知识原则n知识表示的作用知识表示的作用n知识表示的功能知识表示的功能n知识表示的性能知识表示的性能n基本的知识表示方法基本的知识表示方法1.知识原则知识原则 n里南里南(D.B.Lenat)&费根鲍姆费根鲍姆(E.A.Feigenbaum)，IJCAI-10 一个系统展示高级的智能理解和行为，主要是因为拥有应一个系统展示高级的智能理解和行为，主要是因为拥有应用领域用领域特有特有的知识：概念、事实、表示、方法、模型、隐喻和的知识：概念、事实、表示、方法、模型、隐喻和启发式。启发式。n特有特有意指应用领域中有效地求解问题主要靠该领域特有意指应用领域中有效地求解问题主要靠该领域特有的知识的知识n足够的约束来自特别知识足够的约束来自特别知识通用知识作用微弱，不能为问通用知识作用微弱，不能为问题求解提供足够的约束题求解提供足够的约束1.知识原则知识原则 n系统拥有的知识和其性能系统拥有的知识和其性能(问题求解能力和效率问题求解能力和效率)的关系的关系,如图如图:n知识门槛：知识门槛：n使能门槛使能门槛W指知识量超过该门槛时，系统就拥有了为执行任指知识量超过该门槛时，系统就拥有了为执行任务所需的最低限度知识。务所需的最低限度知识。n胜任门槛胜任门槛C到达到达C点时成为某应用领域中求解问题的专家，点时成为某应用领域中求解问题的专家，胜任只有专家才能解决的问题求解任务。胜任只有专家才能解决的问题求解任务。n全能门槛全能门槛E到此门槛，由于知识量的空前增加到此门槛，由于知识量的空前增加(丰富丰富)，使系，使系统能解决该应用领域内的几乎统能解决该应用领域内的几乎 所有问题，成为全能专家。所有问题，成为全能专家。知识门槛知识门槛性能知识量1.知识原则知识原则n知识门槛的分析：知识门槛的分析：n知识量差异知识量差异 达到达到C级，只需级，只需501000条规则；再加等量的规则，可达条规则；再加等量的规则，可达E级。级。n智能体知识是逐步积累的，涉及到智能体知识是逐步积累的，涉及到获取、修正和学习新知识获取、修正和学习新知识。n智能系统的能力智能系统的能力主要由知识库中包含的领域特有的知识来决定主要由知识库中包含的领域特有的知识来决定 作为启发式知识作为启发式知识(经验性关联知识经验性关联知识)高效地指导问题求解。高效地指导问题求解。n70-80年代年代专家系统专家系统和知识工程的成功证明了知识原则的有效性。和知识工程的成功证明了知识原则的有效性。n许多其它的人工智能研究也逐步转向基于知识的观点。许多其它的人工智能研究也逐步转向基于知识的观点。性能知识量2.知识表示的作用知识表示的作用n以适当的方式表示知识，才导致智能体展示出智能行为。以适当的方式表示知识，才导致智能体展示出智能行为。n表示表示=数据结构数据结构 十十 处理机制处理机制n恰当的数据结构恰当的数据结构用于存储要解决的问题、可能的中间解答和用于存储要解决的问题、可能的中间解答和最终解答以及解决问题涉及之世界的描述。最终解答以及解决问题涉及之世界的描述。符号结构导致了知识符号结构导致了知识的显式表示。的显式表示。n配套的处理机制配套的处理机制仅有符号结构并不能体现出系统具有知识，仅有符号结构并不能体现出系统具有知识，符号结构本身并不构成意义，只有对其作适当的处理才构成意义。符号结构本身并不构成意义，只有对其作适当的处理才构成意义。如：汽车自动驾驶系统如：汽车自动驾驶系统规则：在路口遇红灯时停下规则：在路口遇红灯时停下 规则解释程序规则解释程序2.知识表示的作用知识表示的作用n知识表示假设知识表示假设史密斯史密斯(B.Simth)，1982 任何机械设置的智能过程均由任何机械设置的智能过程均由结构成分结构成分组成，人们作为外部观察者组成，人们作为外部观察者,自然地引用这些结构对该智能过程展示的知识作陈述性描述；独立自然地引用这些结构对该智能过程展示的知识作陈述性描述；独立于这样的外部语义，它们在于这样的外部语义，它们在产生显示出有知识的行为产生显示出有知识的行为中起到基本的中起到基本的作用。作用。n从概念上阐明了知识表示在建造智能化软件系统中的作用从概念上阐明了知识表示在建造智能化软件系统中的作用n把知识表示的研究与其它涉及符号处理的技术区分开来把知识表示的研究与其它涉及符号处理的技术区分开来2.知识表示的作用知识表示的作用n结构成分结构成分KB系统中的符号结构，满足两个主要系统中的符号结构，满足两个主要特性特性：1)可解释为表示知识的命题可解释为表示知识的命题n知识表示隐含地要求符号结构能以真值理论来解释，从而知识表示隐含地要求符号结构能以真值理论来解释，从而可以因某些命题的存在而说世界必定是什么样子的。可以因某些命题的存在而说世界必定是什么样子的。n符号结构本身不必是命题形式，但我们作为符号结构本身不必是命题形式，但我们作为KB系统的外系统的外部观察者，能把它们解释为命题而加以理解。部观察者，能把它们解释为命题而加以理解。例：语义网络中的节点例：语义网络中的节点包括若干槽的符号结构包括若干槽的符号结构(Node G-al Isa:Grade-assignment Student:John Course:CS100 Mark:85)Grade-assignment(G-al)Student(G-al,John)Course(G-al,CS100)Mark(G-al,85)Grade(John，CS100，85)2.知识表示的作用知识表示的作用结构成分的特性结构成分的特性 2)在在KB系统的行为中起因果作用系统的行为中起因果作用n这种作用与将符号结构理解为表示知识的命题是一致的这种作用与将符号结构理解为表示知识的命题是一致的n能把系统的智能行为归因为是系统具有某种表示于符号结能把系统的智能行为归因为是系统具有某种表示于符号结构中的知识构中的知识n注意：并不是系统能意识到它有知识，而是观察者从观察注意：并不是系统能意识到它有知识，而是观察者从观察到的行为中认为系统具有某种知识到的行为中认为系统具有某种知识n颜色问题例颜色问题例说出雪、草和天空的颜色说出雪、草和天空的颜色2.知识表示的作用知识表示的作用知识表示假设知识表示假设结构成分结构成分KB系统中的符号结构，满足两个主要特性：系统中的符号结构，满足两个主要特性：1)可解释为表示知识的命题可解释为表示知识的命题 2)在在KB系统的行为中起因果作用系统的行为中起因果作用n颜色问题例颜色问题例说出雪、说出雪、草和天空的颜色草和天空的颜色n系统应如何设计才成系统应如何设计才成为为KB系统系统?两种设计方式等价？两种设计方式等价？风格很不相同风格很不相同(2)以清晰的符号结构以清晰的符号结构表示关于颜色的知识表示关于颜色的知识颜色问题的颜色问题的KB系统：系统：(1)PrintColour(snow):-!,write(“Its white.”).PrintColour(grass):-!,write(“Its green.”).PrintColour(sky):-!,write(“Its yellow.”).PrintColour(x):-!,write(“Beats me!”).若问题是：若问题是：?-PrintColour(grass)，则系统回答：则系统回答：Its green(2)PrintColour(x):-Colour(x,y),!,write(“Its”),write(y),write(“.”).PrintColour(x):-write(“Beats me!”).Colour(snow,white).Colour(grass,green).Colour(sky,yellow).Prolog 语言：语言：Horn子句子句:-!2.知识表示的作用知识表示的作用知识表示假设知识表示假设结构成分结构成分KB系统中的符号结构，满足两个主要特性：系统中的符号结构，满足两个主要特性：1)可解释为表示知识的命题可解释为表示知识的命题 2)在在KB系统的行为中起因果作用系统的行为中起因果作用n第二种方式设计了一个第二种方式设计了一个KB系统：系统：n以清晰的符号结构表示关于颜色的知识以清晰的符号结构表示关于颜色的知识；n以规则的形式以规则的形式(逆向推理规则逆向推理规则)表示表示“要打印要打印x的颜色，必须知道的颜色，必须知道x的颜色是的颜色是y”；n此符号结构在系统回答关于颜色问题的行为中明显地起到因果作用；此符号结构在系统回答关于颜色问题的行为中明显地起到因果作用；n因为系统拥有关于颜色的知识因为系统拥有关于颜色的知识,当接收关于颜色的问题时当接收关于颜色的问题时,系统才会作出正确回答系统才会作出正确回答.n第一种方式设计的系统不能称为第一种方式设计的系统不能称为KB系统系统n未能清晰地表示关于颜色的知识未能清晰地表示关于颜色的知识n奇怪的知识：奇怪的知识：写字符串和打印颜色的关联写字符串和打印颜色的关联颜色问题的颜色问题的KB系统：系统：(1)PrintColour(snow):-!,write(“Its white.”).PrintColour(grass):-!,write(“Its green.”).PrintColour(sky):-!,write(“Its yellow.”).PrintColour(x):-!,write(“Beats me!”).若问题是：若问题是：?-PrintColour(grass)，则系统回答：则系统回答：Its green(2)PrintColour(x):-Colour(x,y),!,write(“Its”),write(y),write(“.”).PrintColour(x):-write(“Beats me!”).Colour(snow,white).Colour(grass,green).Colour(sky,yellow).2.知识表示的作用知识表示的作用n工作假设工作假设用合理方式去建造智能软件系统：用合理方式去建造智能软件系统：从开发从开发KB系统的实用角度，阐述设计符号结构去表示知识在系统的实用角度，阐述设计符号结构去表示知识在实现人工的智能行为中的关键作用，目的不是解释认知行为。实现人工的智能行为中的关键作用，目的不是解释认知行为。nKB系统的设计：系统的设计：n知识表示：知识表示：n表示语言表示语言以符号结构描述获取到的领域知识以符号结构描述获取到的领域知识n推理机制推理机制应用这些知识实现智能行为应用这些知识实现智能行为n领域特有的知识领域特有的知识知识表示假设知识表示假设史密斯史密斯(B.Simth),1982 任何机械设置的智能过程均由结构成分任何机械设置的智能过程均由结构成分组成，人们作为外部观察者组成，人们作为外部观察者,自然地引用自然地引用这些结构对该智能过程展示的知识作陈述这些结构对该智能过程展示的知识作陈述性描述；独立于这样的外部语义，它们在性描述；独立于这样的外部语义，它们在产生显示出有知识的行为中起到基本的作产生显示出有知识的行为中起到基本的作用。用。3.知识表示的功能知识表示的功能n解决复杂问题解决复杂问题知识的表示必须能支持多种不同的问题求解活动知识的表示必须能支持多种不同的问题求解活动n不同的活动往往需用不同方式表示的知识；不同的活动往往需用不同方式表示的知识；n知识表示面临的抉择：知识表示面临的抉择：n以统一的表示方式表示所有的知识以统一的表示方式表示所有的知识以统一的符号结构来换取知以统一的符号结构来换取知识获取和知识库维护上的简易性，但导致推理的低效性；识获取和知识库维护上的简易性，但导致推理的低效性；n以不同的表示方式表示特性不同的知识以不同的表示方式表示特性不同的知识n知识表示的设计是一个要根据实际应用加以权衡利弊的问题。知识表示的设计是一个要根据实际应用加以权衡利弊的问题。n支持三种类型的问题求解活动支持三种类型的问题求解活动n知识获取知识获取支持智能体渐增地获取知识，使其内部模型越来越精确支持智能体渐增地获取知识，使其内部模型越来越精确地反映外部世界，以便有效地完成问题求解任务。地反映外部世界，以便有效地完成问题求解任务。(个性、共性个性、共性)n感知感知感知其是否处于其拥有的知识可利用的世界状态中。搜索感知其是否处于其拥有的知识可利用的世界状态中。搜索n行动规划行动规划能正确表示计划、目标、假设和期望。能正确表示计划、目标、假设和期望。4.知识表示的性能知识表示的性能 伍兹伍兹(Woods)，从两方面评价，从两方面评价:n表示的充分性表示的充分性作重要区分和避免不必要区分的能力作重要区分和避免不必要区分的能力n才能恰当地描述问题求解涉及的事物，以及智能体对于外部世界才能恰当地描述问题求解涉及的事物，以及智能体对于外部世界的信念、目的和猜测等。的信念、目的和猜测等。n表示法效用表示法效用支持被表示知识的使用，即表示知识的元素和处理支持被表示知识的使用，即表示知识的元素和处理这些元素的操作应能有效地支持使用知识的推理活动。这些元素的操作应能有效地支持使用知识的推理活动。n概念效率概念效率n知识表示方式应能有利于知识库以自然的方式吸收随意的新知识知识表示方式应能有利于知识库以自然的方式吸收随意的新知识.利于知识库的逐步精化，使包含于知识库中的有关世界的内部模型利于知识库的逐步精化，使包含于知识库中的有关世界的内部模型能逐步地精化和调整到接近于正确地反映外部世界。能逐步地精化和调整到接近于正确地反映外部世界。n计算效率计算效率推理的有效性，如推理的速度、结论的正确性和有效性推理的有效性，如推理的速度、结论的正确性和有效性4.知识表示的性能知识表示的性能权衡分析权衡分析n兼顾概念效率和计算效率往往是困难的：兼顾概念效率和计算效率往往是困难的：n概念效率概念效率要求表示知识的符号结构与知识的获取和知识库维护要求表示知识的符号结构与知识的获取和知识库维护相容相容(人的思维方式人的思维方式)计算效率计算效率要求与推理机相容要求与推理机相容(计算机目标代码方式计算机目标代码方式)n提供两套符号结构提供两套符号结构，分别面向知识获取和机器推理，并设计自动，分别面向知识获取和机器推理，并设计自动转变程序来实现两者间的映射。转变程序来实现两者间的映射。n表示的充分性和表示法效用相互制约表示的充分性和表示法效用相互制约n提高一个方面的性能以牺牲另一方面的性能为代价提高一个方面的性能以牺牲另一方面的性能为代价n根据应用环境和问题特征作取舍权衡，以能否满足需求为最实用根据应用环境和问题特征作取舍权衡，以能否满足需求为最实用的评价准则，否定绝对的性能比较准则的评价准则，否定绝对的性能比较准则一阶谓词逻辑具有最好的表示充分性一阶谓词逻辑具有最好的表示充分性 产生式系统、结构化表示具有更好的表示法效用产生式系统、结构化表示具有更好的表示法效用5.基本的知识表示方式基本的知识表示方式一阶谓词逻辑一阶谓词逻辑 知识表示方式知识表示方式 一阶谓词逻辑一阶谓词逻辑、产生式表示、结构化表示、产生式表示、结构化表示n表示元素：谓词公式、连词和量词表示元素：谓词公式、连词和量词n优点：优点：n表示元素具有良好定义的语义表示元素具有良好定义的语义,便于自然地表示概念便于自然地表示概念,准确灵活准确灵活n很好的很好的表示充分性表示充分性，能适用于各种应用领域，能适用于各种应用领域n缺点：缺点：n归结演绎推理不能应用启发式知识控制推理，知识库较大时推理归结演绎推理不能应用启发式知识控制推理，知识库较大时推理效率极低效率极低n不能保证在合理的时间内给出解答不能保证在合理的时间内给出解答(不可判定不可判定)，实用领域狭窄，实用领域狭窄n对一阶谓词逻辑作种种限制对一阶谓词逻辑作种种限制Prolog和各种演绎推理系统和各种演绎推理系统以减弱表示的充分性为代价，大幅度增加了表示法的效用以减弱表示的充分性为代价，大幅度增加了表示法的效用n表示知识的符号结构过于简单，无法有效描述结构复杂的事物表示知识的符号结构过于简单，无法有效描述结构复杂的事物5.基本的知识表示方式基本的知识表示方式产生式表示产生式表示 n用产生式表示的系统用产生式表示的系统(产生式系统产生式系统)由三个部分组成：由三个部分组成：n规则库规则库产生式的规则集合产生式的规则集合n综合数据库综合数据库记载问题求解的初始状态和中间结果记载问题求解的初始状态和中间结果n控制子系统控制子系统执行识别执行识别行动循环，并在每一循环中选行动循环，并在每一循环中选择激活的规则和执行规则右部拟定的动作择激活的规则和执行规则右部拟定的动作例例:设综合数据库的初始内容设综合数据库的初始内容db为集合为集合a,b,c,其中其中a、b、c均均为字符；建立规则库，其包含以下三条插入双字符的规则：为字符；建立规则库，其包含以下三条插入双字符的规则：R1:(ab db)insert(db,“ab”)R2:(ac db)insert(db,“ac”)R3:(bc db)insert(db,“bc”)推理的目标是使推理的目标是使db成为：成为：a,b,c,ab,ac,bc推理控制策略推理控制策略无信息控制无信息控制5.基本的知识表示方式基本的知识表示方式产生式表示产生式表示 n用产生式表示的系统用产生式表示的系统(产生式系统产生式系统)由三个部分组成：由三个部分组成：n规则库、综合数据库规则库、综合数据库、控制子系统控制子系统n优点：优点：n增加表示法的概念效率增加表示法的概念效率规则的条件部分不限于谓词公式：可以是规则的条件部分不限于谓词公式：可以是关系表达式和真值函数；且动作可以是任何操作关系表达式和真值函数；且动作可以是任何操作(演绎推理系统中规则演绎推理系统中规则的右部只能是推理结论的右部只能是推理结论)n增加表示法的计算效率增加表示法的计算效率通过设置控制元素于综合数据库和采用多通过设置控制元素于综合数据库和采用多规则激活情况下的冲突解法，可以有效地控制推理过程规则激活情况下的冲突解法，可以有效地控制推理过程n产生式规则最适合于表示各种启发式知识以指示事物间的经验性关联，产生式规则最适合于表示各种启发式知识以指示事物间的经验性关联，广泛应用于专家系统的设计广泛应用于专家系统的设计n缺点：缺点：n规则的堆积存储，缺乏组织；冲突解法的单一性不能自然地适应于许规则的堆积存储，缺乏组织；冲突解法的单一性不能自然地适应于许多场合多场合 通过设置控制元素来设计控制策略，在复杂的情况下常不可行通过设置控制元素来设计控制策略，在复杂的情况下常不可行n缺乏结构化手段，产生式表示无法有效地描述结构复杂的事物缺乏结构化手段，产生式表示无法有效地描述结构复杂的事物例例:设综合数据库的初始内容设综合数据库的初始内容db为集合为集合a,b,c,其中其中a、b、c均为字符；建立规均为字符；建立规则库则库,其包含以下三条插入双字符的规则：其包含以下三条插入双字符的规则：R1:(ab db)insert(db,“ab”)R2:(ac db)insert(db,“ac”)R3:(bc db)insert(db,“bc”)推理的目标是使推理的目标是使db成为：成为：a,b,c,ab,ac,bc 推理控制策略推理控制策略无信息控制无信息控制5.基本的知识表示方式基本的知识表示方式结构化表示：语义网络、框架表示结构化表示：语义网络、框架表示 n表示知识的符号结构表示知识的符号结构节点和框架：节点和框架：n由一组由一组slots(槽槽)构成构成 用于集中表示对象用于集中表示对象(概念或个体事物概念或个体事物)的属性和对象间的关的属性和对象间的关系系n语义网络语义网络注重表示对象间的关系注重表示对象间的关系 框架系统框架系统更强调对象的内部结构更强调对象的内部结构5.基本的知识表示方式基本的知识表示方式结构化表示：语义网络、框架表示结构化表示：语义网络、框架表示 n表示知识的符号结构表示知识的符号结构节点和框架：节点和框架：n优点：优点：n在知识库中进行检索时具有较高的效率在知识库中进行检索时具有较高的效率n节点节点(框架框架)集中了概念或个体的所有属性描述和关系描述，又可用集中了概念或个体的所有属性描述和关系描述，又可用槽作为索引槽作为索引n特性继承和程序附加功能，使有效地组织和处理知识成为可能特性继承和程序附加功能，使有效地组织和处理知识成为可能n缺点：缺点：n在刻画真值理论方面过于自由化，在刻画真值理论方面过于自由化，易引起二义性甚至严重错误易引起二义性甚至严重错误 开发开发KB系统的陷阱系统的陷阱n框架的语义允许严格定义和典型范例这两种不相容的解释框架的语义允许严格定义和典型范例这两种不相容的解释nIsa链同时用于表示集合一子集关系、集合一成员关系链同时用于表示集合一子集关系、集合一成员关系n表示集合概念的框架定义集合本身的特性，又记载其成员的共性表示集合概念的框架定义集合本身的特性，又记载其成员的共性n由于结构化表示的复杂性，知识库维护需付出高得多的代价由于结构化表示的复杂性，知识库维护需付出高得多的代价5.基本的知识表示方式基本的知识表示方式综合分析综合分析 一阶谓词逻辑一阶谓词逻辑、产生式表示、结构化表示、产生式表示、结构化表示n一阶逻辑是知识表示的基本手段一阶逻辑是知识表示的基本手段，进而构成人工智能研究的基础；，进而构成人工智能研究的基础；后二种均可转变为等价的一阶逻辑表示方式。后二种均可转变为等价的一阶逻辑表示方式。n后二种减弱表示的充分性，却后二种减弱表示的充分性，却提高了表示法效用提高了表示法效用，使这些表示方式，使这些表示方式能应用于许多实际问题的解决。能应用于许多实际问题的解决。牺牲表示的充分性是允许的也是合理的，实用的人工智能系统往往牺牲表示的充分性是允许的也是合理的，实用的人工智能系统往往只涉及到某些方面的表示充分性，其它方面可以忽略。只涉及到某些方面的表示充分性，其它方面可以忽略。n综合多种知识表示方式综合多种知识表示方式，利于充分、有效地表示和解决复杂问题。，利于充分、有效地表示和解决复杂问题。3.2 产生式表示产生式表示起源起源n美国数学家美国数学家波斯特波斯特(Post)，1943年年,产生式系统产生式系统n以产生式的规则描述符号串替代运算以产生式的规则描述符号串替代运算n用于描述形式语言的语法，表示人类心理活动的认知过程等用于描述形式语言的语法，表示人类心理活动的认知过程等n现代产生式系统：现代产生式系统：n与与模型很不相同，但基本概念相同模型很不相同，但基本概念相同(使用产生式规则表示知识使用产生式规则表示知识)n便于模拟人求解问题的思维方式便于模拟人求解问题的思维方式,系统模块性强系统模块性强,易于修改扩充易于修改扩充,应应用广泛用广泛n目前大多数专家系统目前大多数专家系统(尤其是中小型系统尤其是中小型系统)都采用产生式系统的结都采用产生式系统的结构方式来建立。构方式来建立。DENDRAL、MYCIN3.2 产生式表示产生式表示n主要内容：主要内容：n产生式系统产生式系统n控制策略控制策略n产生式系统的分类产生式系统的分类3.2.1 产生式系统产生式系统1.产生式规则产生式规则n产生式规则产生式规则用于表示事物间的启发式关联用于表示事物间的启发式关联 P Q 或或 IF P then QnP规则得以激活使用的条件规则得以激活使用的条件(或称前提或称前提)nQ指示规则激活时应该执行的动作指示规则激活时应该执行的动作(或应该得出的结论或应该得出的结论)n依据规则右部的表示方式，规则分类依据规则右部的表示方式，规则分类n条件条件-动作型、前提动作型、前提-结论型结论型例：例：(前提前提-结论型结论型)关于动物世界的产生式系统有规则：关于动物世界的产生式系统有规则：若某动物是哺乳动物，且吃肉；则这种动物是食肉动物。若某动物是哺乳动物，且吃肉；则这种动物是食肉动物。(Mammal?x)(Eat?x Meat)(Carnivore?x)模式变量模式变量?x视为隐含地受全称量词约束，该规则实际为一视为隐含地受全称量词约束，该规则实际为一条正向演绎推理规则条正向演绎推理规则n产生式规则与演绎推理规则的比较：产生式规则与演绎推理规则的比较：不要求遵从一阶谓词演算的表示形式不要求遵从一阶谓词演算的表示形式n前提前提-结论型结论型 规则前提规则前提匹配模式匹配模式(即谓词公式即谓词公式)、关系表达式、关系表达式和真值函数的任意与、或、非组合和真值函数的任意与、或、非组合 规则结论规则结论任意数据结构任意数据结构(向量、数组、表格等向量、数组、表格等)n条件条件-动作型规则的右部动作型规则的右部任意操作函数任意操作函数 例：例：x-1 1 null(y)x:=0 n规则的左部规则的左部(前件前件)、右部、右部(后件后件)3.2.1 产生式系统产生式系统1.产生式规则产生式规则 2.产生式系统组成产生式系统组成 n前二者构成产生式系统的问题表示前二者构成产生式系统的问题表示(描述描述)n后者控制应用规则推出解答的全过程后者控制应用规则推出解答的全过程n规则库规则库存放应用领域的常识和启发式知识存放应用领域的常识和启发式知识n产生式规则的集合产生式规则的集合n综合数据库综合数据库描述问题求解状态描述问题求解状态(简称问题状态简称问题状态)n表示为谓词公式的事实元素集表示为谓词公式的事实元素集 或任何数据结构，如向量、数组和表格等或任何数据结构，如向量、数组和表格等 例：关于动物世界的产生式系统有：例：关于动物世界的产生式系统有：n推理过程中间结果的存贮池推理过程中间结果的存贮池 n控制系统控制系统产生式系统的推理机产生式系统的推理机(规则的解释器规则的解释器)2.产生式系统组成产生式系统组成 n控制系统控制系统产生式系统的推理机产生式系统的推理机(规则的解释器规则的解释器)n驱动和控制整个系统的运行驱动和控制整个系统的运行n基本的控制流程：基本的控制流程：识别识别行动行动 循环循环n识别阶段识别阶段在规则库中识别条件为真的规则在规则库中识别条件为真的规则,使它们激活；使它们激活；n行动阶段行动阶段执行激活的规则，即执行规则右部指定的对于执行激活的规则，即执行规则右部指定的对于综合数据库的操作和任何其它合适的操作。综合数据库的操作和任何其它合适的操作。n冲突冲突多于一条的规则激活多于一条的规则激活n冲突解决冲突解决基于某种控制策略去选定需要执行的规则基于某种控制策略去选定需要执行的规则nFirst选用首条激活的规则加以执行选用首条激活的规则加以执行nBest选用已激活规则中最好的加以执行选用已激活规则中最好的加以执行 “最好最好”的评价依赖于应用领域制定的准则的评价依赖于应用领域制定的准则nAll执行所有激活的规则执行所有激活的规则2.产生式系统组成产生式系统组成n规则库规则库存放应用领域的常识和启发式知识存放应用领域的常识和启发式知识n综合数据库综合数据库描述问题求解状态描述问题求解状态(简称问题状态简称问题状态)n控制系统控制系统产生式系统的推理机产生式系统的推理机(规则的解释器规则的解释器)n控制机制就是不断地挑选可激活的规则对综合数据库进行操作控制机制就是不断地挑选可激活的规则对综合数据库进行操作,直至直至n得到解答得到解答 综合数据库内容综合数据库内容转变转变描述的目标状态描述的目标状态n失败结束失败结束 (Mammal?x)(Eat?x Meat)(Carnivore?x)(Mammal Dog)(Eat Dog Meat)(Carnivore Dog)3.应用实例应用实例n产生式系统问题表示的设计产生式系统问题表示的设计:综合数据库综合数据库问题状态问题状态规则库规则库操作算子操作算子n实例：实例：n八数码游戏八数码游戏n传教士与野人问题传教士与野人问题n旅行商问题：旅行商问题：R1:not-visit(x)move(x),R2:visit-all()move(A)n文法分析问题：设计一组重写规则作为产生式规则文法分析问题：设计一组重写规则作为产生式规则n问题状态：问题状态：33 矩阵矩阵每个矩阵元素每个矩阵元素S ij0,1,8；其中，其中，1i,j3数字数字0 空格空格数字数字1-8 相应棋牌。相应棋牌。n操作算子：操作算子：L(0),R(0),U(0),D(0)约束：空格不能移出棋盘。约束：空格不能移出棋盘。评价函数评价函数：f(nf(n)=)=d(nd(n)+)+w(nw(n)d(nd(n)当前被考察的节点当前被考察的节点n n在搜索在搜索图中的节点深度；图中的节点深度；w(nw(n)其值是节点其值是节点n n与目标状态节与目标状态节点相比较，错位棋牌个数点相比较，错位棋牌个数应用应用算法算法A的八数码问题搜索图的八数码问题搜索图综合数据库综合数据库表示棋盘布局表示棋盘布局(问题状态问题状态)的矩阵的矩阵定义一组定义一组产生式规则产生式规则由于改变棋盘布局的操作可通过空格由于改变棋盘布局的操作可通过空格 移动实现，建立移动实现，建立4个条件个条件-动作型规则来为空格的左、上、动作型规则来为空格的左、上、右、下移动操作建立激活条件右、下移动操作建立激活条件设设Sij指示矩阵第指示矩阵第i行第行第j列的数码列的数码(1i,j3)，i0,j0指示空格所指示空格所在的行、列数，则有：在的行、列数，则有：R1:j0 1 1 Siojo:=Sio(jo-1)Sio(jo-1):=0 (空格左移空格左移)R2:i0 1 1 Siojo:=S(io-1)jo S(io-1)jo:=0 (空格上移空格上移)R3:j0+1 3 Siojo:=Sio(jo+1)Sio(jo+1):=0 (空格右移空格右移)R4:i0+1 3 Siojo:=S(io+1)jo S(io+1)jo:=0 (空格下移空格下移)3.应用实例应用实例八数码游戏八数码游戏(2.1.1.1节节)设计为产生式系统设计为产生式系统n问题状态：问题状态：33 矩阵矩阵每个矩阵元素每个矩阵元素S ij0,1,8；其中；其中,1i,j3 数字数字0 空格数字空格数字1-8 相应棋牌。相应棋牌。n操作算子：操作算子：L(0),R(0),U(0),D(0)约束：空格不能移出棋盘。约束：空格不能移出棋盘。综合数据库综合数据库表示棋盘布局表示棋盘布局(问题状态问题状态)的矩阵的矩阵产生式规则产生式规则建立建立4个条件个条件-动作型规则为空格的移动操作建立激活条件动作型规则为空格的移动操作建立激活条件设设Sij指示矩阵第指示矩阵第i行第行第j列的数码列的数码(1i,j3),i0,j0指示空格所在的行指示空格所在的行、列数列数,则则有有:R1:j0 1 1 Siojo:=Sio(jo-1)Sio(jo-1):=0 (空格左移空格左移)R2:i0 1 1 Siojo:=S(io-1)jo S(io-1)jo:=0 (空格上移空格上移)R3:j0+1 3 Siojo:=Sio(jo+1)Sio(jo+1):=0 (空格右移空格右移)R4:i0+1 3 Siojo:=S(io+1)jo S(io+1)jo:=0 (空格下移空格下移)例如当前棋盘布局为例如当前棋盘布局为:则综合数据库内容为则综合数据库内容为:规则规则R2、R3和和R4均可激活均可激活3.应用实例应用实例八数码游戏八数码游戏(2.1.1.1节节)设计为产生式系统设计为产生式系统若若冲突解决策略采用冲突解决策略采用First,则执行则执行R2右部操作，综合数据库内容变换为右部操作，综合数据库内容变换为:采用采用Best策略策略选取激活的规则：选取激活的规则：用启发式函数用启发式函数W(n)判别导致下一判别导致下一 状状态与目标状态差距最小的规则，可快态与目标状态差距最小的规则，可快速搜索到解答速搜索到解答(即目标状态即目标状态)综合数据库综合数据库表示棋盘布局表示棋盘布局(问题状态问题状态)的矩阵的矩阵定义一组定义一组产生式规则产生式规则由于改变棋盘布局的操作可通过空格移动实现，建立由于改变棋盘布局的操作可通过空格移动实现，建立4 个条件个条件-动作型规则来为空格的左、上、右、下移动操作建立激活条件动作型规则来为空格的左、上、右、下移动操作建立激活条件设设Sij指示矩阵第指示矩阵第i行第行第j列的数码列的数码(1i,j3)，i0,j0指示空格所在的行指示空格所在的行、列数列数，则有：则有：R1:j0 1 1 Siojo:=Sio(jo-1)Sio(jo-1):=0 (空格左移空格左移)R2:i0 1 1 Siojo:=S(io-1)jo S(io-1)jo:=0 (空格上移空格上移)R3:j0+1 3 Siojo:=Sio(jo+1)Sio(jo+1):=0 (空格右移空格右移)R4:i0+1 3 Siojo:=S(io+1)jo S(io+1)jo:=0 (空格下移空格下移)例如当前棋盘布局为例如当前棋盘布局为:则综合数据库内容为则综合数据库内容为:规则规则R2、R3和和R4均可激活均可激活若若冲突解决策略采用冲突解决策略采用First,则执行则执行R2右部操作，综合数据库内容变换为右部操作，综合数据库内容变换为:采用采用Best策略策略选取激活的规则：用启发式函数选取激活的规则：用启发式函数W(n)判别导致下一状态与目标判别导致下一状态与目标 状态差距最小的规则，可快速搜索到解答状态差距最小的规则，可快速搜索到解答(即目标状态即目标状态)3.应用实例应用实例八数码游戏八数码游戏(2.1.1.1节节)设计为产生式系统设计为产生式系统状态空间表示状态空间表示传教士和野人问题传教士和野人问题 n3个传教士带领个传教士带领3个野人划船渡河个野人划船渡河 m传教士在左岸或船上的实际人数传教士在左岸或船上的实际人数 c 野人在左岸或船上的实际人数野人在左岸或船上的实际人数 b 1 船在左岸，否则为船在左岸，否则为0 n约束条件约束条件：m=c,船上人数船上人数算法的上次调用算法的上次调用-7-4从从rs取用取用 表首规则，从另一推理分支前进表首规则，从另一推理分支前进 由于递归算法，从失败状态回溯上一状态由于递归算法，从失败状态回溯上一状态 时，上一状态的描述即时，上一状态的描述即db仍保留，回溯仍保留，回溯 时不需作任何状态恢复工作。时不需作任何状态恢复工作。n缺点：缺点：n若启发式知识不健全，过多的回溯影响推理效率若启发式知识不健全，过多的回溯影响推理效率n按时序回溯的盲目性按时序回溯的盲目性只能回溯到上一个推理分支点，不能只能回溯到上一个推理分支点，不能准确地直接返回到推理失败的根源相应的推理分支点，使许多准确地直接返回到推理失败的根源相应的推理分支点，使许多回溯工作白白浪费回溯工作白白浪费.(图图)1.若若db指示了目标状态，则输出指示了目标状态，则输出(显示显示)db 作为解答，算法成功结束；作为解答，算法成功结束；2.若若db指示了失败状态，则返回真值指示了失败状态，则返回真值F；3.rs:=RULE-ACTIVATE(db)，并用启发式，并用启发式 知识对知识对rs中的规则按从优到劣的次序排列中的规则按从优到劣的次序排列;4.若若rs为空，则返回真值为空，则返回真值F；5.r:=MOVE-FIRST(rs)；6.PS-BACKTRACK(TRANSFORM(db,r);7.返回语句返回语句(4)db回溯策略回溯策略四皇后问题例四皇后问题例n综合数