第5章推理与控制策略课件.ppt

1、2023-1-5Expert System and Application15.1 5.1 推理的基本概念推理的基本概念5.2 5.2 推理控制策略推理控制策略5.3 5.3 不精确推理的基本结构不精确推理的基本结构5.4 5.4 确定理论方法确定理论方法5.5 5.5 主观主观 Bayes Bayes 方法方法5.6 5.6 近似推理（可能性理论方法）近似推理（可能性理论方法）5.7 5.7 不精确推理方法的评价不精确推理方法的评价2023-1-5Expert System and Application2（1）推理）推理：根据一定的原则（或规则）从已知的事实（或判：根据一定的原则（或规则）

2、从已知的事实（或判断）推出新的事实的断）推出新的事实的思维过程思维过程。其中，推理所依据的事实。其中，推理所依据的事实称为称为前提前提（或（或条件条件），由前提所推出的新事实称为），由前提所推出的新事实称为结论结论。（2）在专家系统中，）在专家系统中，推理是以知识库中的已有知识为根据推理是以知识库中的已有知识为根据，是一种基于知识的推理。基于知识推理的计算机实现构成是一种基于知识的推理。基于知识推理的计算机实现构成了推理机。了推理机。（3）知识库和推理机是专家系统的核心部分）知识库和推理机是专家系统的核心部分。一个高性能的。一个高性能的专家系统不但要拥有大量的专门知识，而且要具有选择和专家系统

3、不但要拥有大量的专门知识，而且要具有选择和运用知识的能力。推理机的主要任务就是在问题求解过程运用知识的能力。推理机的主要任务就是在问题求解过程中适时地决定知识的选择和运用。中适时地决定知识的选择和运用。（4）推理机的）推理机的控制策略控制策略用来用来确定知识的选择确定知识的选择，推理方式确定推理方式确定具体知识的运用具体知识的运用。已知实事（或判断）已知实事（或判断）公理或规划公理或规划 新的事实新的事实 条件（前提）条件（前提）结论结论2023-1-5Expert System and Application3 归纳的过程是相对于演绎的。归纳的过程是相对于演绎的。1）演绎演绎：由一般到特殊：

4、由一般到特殊例：所有的人都会死的例：所有的人都会死的 Susan是一个人是一个人 所以，可以推出所以，可以推出“Susan是会死的是会死的”。这是由一般规律推出特殊的演绎。这是由一般规律推出特殊的演绎。2）归纳归纳：尝试将一般推广到特殊：尝试将一般推广到特殊例：我的光碟从未摔碎过（一般情况）例：我的光碟从未摔碎过（一般情况）我的光碟永远不会摔碎我的光碟永远不会摔碎 （这里的（这里的“”是对应与演绎的。）是对应与演绎的。）除了数学上的归纳，其他归纳论证从来不能证明是正除了数学上的归纳，其他归纳论证从来不能证明是正确的。所以，归纳论证只能提供一些结论正确的确的。所以，归纳论证只能提供一些结论正确的

5、可信度可信度。2023-1-5Expert System and Application4 专家系统可能包括演绎和归纳规则。其中，归纳规则专家系统可能包括演绎和归纳规则。其中，归纳规则是启发性的，归纳法被用于规则的自动生成。是启发性的，归纳法被用于规则的自动生成。除了不确定事实外，如果专家系统的规则是基于启除了不确定事实外，如果专家系统的规则是基于启发式，则它们可能存在不确定性，因为这些规则的产生是发式，则它们可能存在不确定性，因为这些规则的产生是基于经验的。基于经验的。3）人类专家的重要特征）人类专家的重要特征 （1）能够熟练地、在问题具有不确定性的情况下进行）能够熟练地、在问题具有不确定性

6、的情况下进行推理。即使在问题具有非常不确定性的情况下，专家通常推理。即使在问题具有非常不确定性的情况下，专家通常也可以作出很好的判断。也可以作出很好的判断。（2）若在实践中发现一些初始事实是错误的，专家很）若在实践中发现一些初始事实是错误的，专家很容易修改他们的观点。容易修改他们的观点。2023-1-5Expert System and Application5 4）结论）结论 （1）归纳和演绎存在的误差，是不确定推理误差，它将）归纳和演绎存在的误差，是不确定推理误差，它将导致规则的不确定。导致规则的不确定。（2）专家在处理具有不确定性的信息时也难免出错。如，）专家在处理具有不确定性的信息时也

7、难免出错。如，当专家知识要在规则中定量表示时，不确定性就成为知识当专家知识要在规则中定量表示时，不确定性就成为知识获取的一个主要问题。不一致、不精确和其他所有可能的获取的一个主要问题。不一致、不精确和其他所有可能的不确定误差都会暴露出来，这就需要专家对知识进行修正。不确定误差都会暴露出来，这就需要专家对知识进行修正。2023-1-5Expert System and Application65.1.1 演绎推理和归纳推理演绎推理和归纳推理1）演绎推理演绎推理从一般性较大的前提推出一般性较小的结从一般性较大的前提推出一般性较小的结论的推理。演绎推理不能生殖新知识。论的推理。演绎推理不能生殖新知识

8、。（1）演绎推理的核心是由三个）演绎推理的核心是由三个判断判断组成的组成的“三段论三段论”，即由两个前提（条件）和一个结论组成。即由两个前提（条件）和一个结论组成。例例1.前提前提1 太阳系的行星都是以椭圆轨道公转的。（一般）太阳系的行星都是以椭圆轨道公转的。（一般）前提前提2 天王星是太阳系的行星。天王星是太阳系的行星。结论结论 天王星是椭圆轨道公转的。（个别）天王星是椭圆轨道公转的。（个别）例例2.前提前提1 所有的电子元器件都是要坏的。（一般）所有的电子元器件都是要坏的。（一般）前提前提2 Intel 8255A 是一种电子元器件。是一种电子元器件。结论结论 Intel 8255A 是要

9、坏的。（个别）是要坏的。（个别）2023-1-5Expert System and Application7 （2）演绎推理是从具有一般性原理（原则）中推出关于）演绎推理是从具有一般性原理（原则）中推出关于个别事物的结论，其思维过程是个别事物的结论，其思维过程是由一般到个别由一般到个别。（3）演绎推理的结论在原则上不能超出前提的范围。）演绎推理的结论在原则上不能超出前提的范围。（4）演绎推理的结论与前提的联系是必然的，只要前提）演绎推理的结论与前提的联系是必然的，只要前提真实，推理形式正确，则结论一定是可靠的。真实，推理形式正确，则结论一定是可靠的。2023-1-5Expert System

10、and Application82）归纳推理归纳推理从一般性较小的前提推出一般性较大的结从一般性较小的前提推出一般性较大的结论的推理。归纳推理一般能生殖新知识。论的推理。归纳推理一般能生殖新知识。（1）归纳推理的思维过程是）归纳推理的思维过程是由个别到一般由个别到一般。（2）归纳推理的前提是个别的、特殊的知识，与经验、）归纳推理的前提是个别的、特殊的知识，与经验、试验等直接相关。试验等直接相关。（3）归纳推理的结论一般都超出前提的范围。）归纳推理的结论一般都超出前提的范围。（4）归纳推理的前提和结论的联系在很多情况下不是必）归纳推理的前提和结论的联系在很多情况下不是必然的，其结论的性质有的确实

11、可靠，有的却带有或然性。然的，其结论的性质有的确实可靠，有的却带有或然性。（5）只要前提真实，推理形式正确，则结论一定是可靠）只要前提真实，推理形式正确，则结论一定是可靠的。的。2023-1-5Expert System and Application9 归纳推理方法包括：归纳推理方法包括：（1 1）完全归纳推理完全归纳推理：根据某类事物中每一个对象（或每：根据某类事物中每一个对象（或每一个子类）的情况而做出的关于该类事物的一般性结论。一个子类）的情况而做出的关于该类事物的一般性结论。其推理形式为：其推理形式为：S1 PS1 P S2 P S2 P Sn P Sn P S1 S1，S2S2，S

12、n Sn 是是S S类的全部类的全部 S P S P2023-1-5Expert System and Application10 例：太阳系的大行星绕太阳公转。例：太阳系的大行星绕太阳公转。太阳系的小行星绕太阳公转。太阳系的小行星绕太阳公转。太阳系的行星只有大行星和小行星两类。太阳系的行星只有大行星和小行星两类。太阳系的所有行星都是绕太阳公转。太阳系的所有行星都是绕太阳公转。有的专家认为，完全归纳推理属于演绎推理。有的专家认为，完全归纳推理属于演绎推理。2023-1-5Expert System and Application11 （2）简单枚举法推理简单枚举法推理：通过枚举某类事物中一部分

13、对：通过枚举某类事物中一部分对象的情况，根据没有遇到矛盾的事实，做出关于该类事象的情况，根据没有遇到矛盾的事实，做出关于该类事物的一般性结论。其推理形式为：物的一般性结论。其推理形式为：S1 PS1 P S2 P S2 P Sn P Sn P S1 S1，S2S2，Sn Sn 是是S S类的部分对象类的部分对象 未遇到与未遇到与S PS P相矛盾的情况相矛盾的情况 S P S P2023-1-5Expert System and Application12 例：河南的煤炭是黑的。例：河南的煤炭是黑的。河北的煤炭是黑的。河北的煤炭是黑的。山西的煤炭是黑的。山西的煤炭是黑的。北京的煤炭是黑的。北京

14、的煤炭是黑的。在考察过程中未遇到其他颜色的煤炭。在考察过程中未遇到其他颜色的煤炭。所有的煤炭都是黑的。所有的煤炭都是黑的。2023-1-5Expert System and Application13 （3）科学归纳法推理科学归纳法推理：通过枚举某类事物中一部分对：通过枚举某类事物中一部分对象的情况，并分析出制约此情况的原因，依此因果关象的情况，并分析出制约此情况的原因，依此因果关系为依据，从而做出关于该类事物的一般性结论。系为依据，从而做出关于该类事物的一般性结论。其推理形式为：其推理形式为：S1 PS1 P S2 P S2 P Sn P Sn P S1 S1，S2S2，Sn Sn 是是S

15、S类的一部分对象类的一部分对象 S P S P 是由于某种原因是由于某种原因 S P S P2023-1-5Expert System and Application14 例：铁受热，则体积膨胀。例：铁受热，则体积膨胀。银受热，则体积膨胀。银受热，则体积膨胀。铜受热，则体积膨胀。铜受热，则体积膨胀。铁、银、铜都是金属，而金属受热后其分子运动铁、银、铜都是金属，而金属受热后其分子运动 速度加快，分子之间距离加大，从而导致体积膨胀。速度加快，分子之间距离加大，从而导致体积膨胀。所有的金属受热后体积膨胀。所有的金属受热后体积膨胀。2023-1-5Expert System and Applicati

16、on15 例：碳膜电阻受热，呈非线性特性。例：碳膜电阻受热，呈非线性特性。多圈电阻受热，呈非线性特性。多圈电阻受热，呈非线性特性。精密电阻受热，呈非线性特性。精密电阻受热，呈非线性特性。碳膜电阻、多圈电阻、精密电阻都是电阻，受热碳膜电阻、多圈电阻、精密电阻都是电阻，受热 后分子运动速度加快，分子之间距离加大，从而后分子运动速度加快，分子之间距离加大，从而 呈非线性特性。呈非线性特性。所有的电阻受热后都是呈非线性特性。所有的电阻受热后都是呈非线性特性。2023-1-5Expert System and Application16 （4）类比法推理类比法推理：根据两个或两类对象有部分属性：根据两个

17、或两类对象有部分属性相同的事实，从而推出它们的其他属性也相同。相同的事实，从而推出它们的其他属性也相同。其推理形式为：其推理形式为：A A对象具有对象具有a a、b b、c c、d d属性。属性。B B对象具有对象具有a a、b b、c c属性。属性。B B对象可能也具有对象可能也具有d d属性。属性。例例.中亚有石油。中亚有石油。中国某地与中亚的地质结构有许多相同点。中国某地与中亚的地质结构有许多相同点。中国某地可能也有石油。中国某地可能也有石油。2023-1-5Expert System and Application17 归纳推理与演绎推理是相互联系、相互补充、密归纳推理与演绎推理是相互

18、联系、相互补充、密不可分的。不可分的。演绎离不开归纳。在演绎推理中，作为推理基础演绎离不开归纳。在演绎推理中，作为推理基础的大前提就是归纳的产物、归纳的结论。的大前提就是归纳的产物、归纳的结论。同样，归纳也离不开演绎。要研究客观对象之间同样，归纳也离不开演绎。要研究客观对象之间的因果关系，分析存在于个别事物中的一般，总离不的因果关系，分析存在于个别事物中的一般，总离不开一般原理、原则的指导。开一般原理、原则的指导。2023-1-5Expert System and Application185.1.2 精确推理和不精确推理精确推理和不精确推理1）精确推理精确推理前提与结论之间有确定的因果关系，

19、并前提与结论之间有确定的因果关系，并且事实与结论都是确定的。且事实与结论都是确定的。演绎推理以数理逻辑为基础，它所求解问题的事演绎推理以数理逻辑为基础，它所求解问题的事实与结论之间存在严格、精确的因果关系，并且事实实与结论之间存在严格、精确的因果关系，并且事实总是确定或精确的。因此，演绎推理是精确推理。总是确定或精确的。因此，演绎推理是精确推理。精确推理所使用的已知数据和知识是完整的、精精确推理所使用的已知数据和知识是完整的、精确的，推理所得到的结论同样是正确的、可靠的。确的，推理所得到的结论同样是正确的、可靠的。2023-1-5Expert System and Application19

20、例例.如果观察到的动物是鸟，如果观察到的动物是鸟，并且鸟不会飞，并且鸟不会飞，并且鸟是黑白色，并且鸟是黑白色，并且鸟会游泳；并且鸟会游泳；则该动物是企鹅。则该动物是企鹅。此例给出了一个确定性的因果关系，而且可以对它进此例给出了一个确定性的因果关系，而且可以对它进行演绎推理，判断一个对象是不是企鹅。行演绎推理，判断一个对象是不是企鹅。但是，在人类知识中有相当一部分属于人们的主观判但是，在人类知识中有相当一部分属于人们的主观判断，是不精确的和模糊的。另外，为了推理而收集的事实和断，是不精确的和模糊的。另外，为了推理而收集的事实和信息也往往是不完全和不精确的。因此，归纳出来的推理知信息也往往是不完全

21、和不精确的。因此，归纳出来的推理知识也往往是不精确的。对于这类问题就需要进行不精确推理。识也往往是不精确的。对于这类问题就需要进行不精确推理。2023-1-5Expert System and Application202）不精确推理不精确推理 采用不精确推理的条件：前提与结论之间没有确定采用不精确推理的条件：前提与结论之间没有确定的因果关系，并且事实与结论都是不精确或含糊的。的因果关系，并且事实与结论都是不精确或含糊的。基于这种不精确知识的推理，形成结论，称为不精基于这种不精确知识的推理，形成结论，称为不精确推理。确推理。在在ES中，通常采用不精确推理，原因是中，通常采用不精确推理，原因是E

22、S解决的问解决的问题大多属于题大多属于不良结构不良结构问题。问题。不精确推理包含两个内容：不精确推理包含两个内容：（1）根据前提推出结论。这是基于知识运用的推理方式。）根据前提推出结论。这是基于知识运用的推理方式。（2）根据前提和规则的不确定性（可信度）计算结论的）根据前提和规则的不确定性（可信度）计算结论的不精确性。这是基于知识选择的推理策略。不精确性。这是基于知识选择的推理策略。2023-1-5Expert System and Application21 例例.MYCIN系统中的不精确推理规则：系统中的不精确推理规则：IF 细菌的染色斑是革兰氏阴性细菌的染色斑是革兰氏阴性 且细菌未球状且

23、细菌未球状 且细菌生成结构呈链形且细菌生成结构呈链形 THEN 存在证据表明该细菌是链球菌类（可信度存在证据表明该细菌是链球菌类（可信度0.7）这条规则表明：即使前提为真，结论成立的可信度也只这条规则表明：即使前提为真，结论成立的可信度也只有有70%。而且，该条规则中的事实也不完全为真。即，该。而且，该条规则中的事实也不完全为真。即，该条规则给出了一个不确定性的因果关系。条规则给出了一个不确定性的因果关系。2023-1-5Expert System and Application223）不精确推理的基本内容）不精确推理的基本内容 （1）根据前提推理得到结论，是基于知识运用的推理方）根据前提推理

24、得到结论，是基于知识运用的推理方式。式。（2）根据前提的不确定性（可信度）或规则的不确定性）根据前提的不确定性（可信度）或规则的不确定性（可信度），通过计算得到结论的不精确性，是基于知识（可信度），通过计算得到结论的不精确性，是基于知识选择的推理策略。选择的推理策略。2023-1-5Expert System and Application235.1.3 经典经典概率概率1 1）概率（概率（ProbabilityProbability）是一个用于是一个用于AIAI问题求解古老但至今问题求解古老但至今仍然很重要问题的数学工具。概率是被用来处理一个不确仍然很重要问题的数学工具。概率是被用来处理一个

25、不确定性问题的量化方法。定性问题的量化方法。2 2）经典概率（经典概率（Classical probabilityClassical probability）经典概率（先验概率）是经典概率（先验概率）是PascalPascal和和FermatFermat于于16451645年提年提出的数学理论。出的数学理论。（1 1）在）在ESES中，经典概率被用来处理的理想系统。中，经典概率被用来处理的理想系统。（2 2）先验（超前）：不考虑真实世界。）先验（超前）：不考虑真实世界。（3 3）理想系统：不能显示真实世界会出现损耗的特性。）理想系统：不能显示真实世界会出现损耗的特性。2023-1-5Exper

26、t System and Application24 （4 4）经典概率（先验概率）的）经典概率（先验概率）的基本公式及其应用基本公式及其应用 P=W/N 其中，其中，W为获胜的数目，为获胜的数目，N为等可能性事件。为等可能性事件。当重复试验并得到同一结果时，系统为确定的；否当重复试验并得到同一结果时，系统为确定的；否则，系统为不确定的。则，系统为不确定的。2023-1-5Expert System and Application255.1.4 样本空间样本空间（1）样本点）样本点：一次试验的结果，称为一个样本点：一次试验的结果，称为一个样本点（Sample point）。）。（2）样本空间）

27、样本空间：所有可能的样本点的集合，定义了一个样：所有可能的样本点的集合，定义了一个样本空间（本空间（Sample space）。一个事件是样本空间的一个）。一个事件是样本空间的一个子集。子集。（3）简单事件）简单事件：只有一个元素的事件。：只有一个元素的事件。（4）复合事件）复合事件：多于一个元素的事件。：多于一个元素的事件。归纳和演绎是有关种群推理的基础。演绎可以作出归纳和演绎是有关种群推理的基础。演绎可以作出有关未知样本的推断。相应地，给定一个已知样本，归有关未知样本的推断。相应地，给定一个已知样本，归纳可以作出有关未知种群的推断。纳可以作出有关未知种群的推断。2023-1-5Expert

28、 System and Application265 5）条件条件概率（概率（Conditional probabilityConditional probability）事件事件A在另外一个事件在另外一个事件B已经发生条件下的发生概率，已经发生条件下的发生概率，称为称为条件概率（后验概率，条件概率（后验概率，Posterior probabilityPosterior probability）。）。若只有两个事件若只有两个事件A，B，那么，那么，如果事件如果事件 B 的概率的概率 P(B)0，那么，那么 Q(A)=P(A|B)在所在所有事件有事件 A 上所定义的函数上所定义的函数 Q 就是就

29、是概率测度概率测度。如果如果 P(B)=0，P(A|B)没有定义。没有定义。表示两个事件共同发生的概率为表示两个事件共同发生的概率为联合概率联合概率。A与与B的联的联合概率表示为合概率表示为 P(AB)，或者，或者P(A,B)，或者，或者P（AB）。）。PABPA BPB2023-1-5Expert System and Application276 6）全概率公式全概率公式和和贝叶斯公式贝叶斯公式 全概率公式：全概率公式：P(B)=P(B|Ai)P(Ai)贝叶斯公式：贝叶斯公式：P(Ai|B)=P(B|Ai)P(Ai)/P(B|Aj)P(Aj)=P(B|Ai)P(Ai)/P(B)说明：说明：

30、i,j 均为下标，求和均是从均为下标，求和均是从1到到n。可以看到，贝叶斯公式的推出要用到全概率公式，贝可以看到，贝叶斯公式的推出要用到全概率公式，贝叶斯公式的分母即全概率公式的等式右边。叶斯公式的分母即全概率公式的等式右边。在基于概率的不确定推理模型中，证据在基于概率的不确定推理模型中，证据E E的不确定性的不确定性用用E E发生的概率发生的概率P(E)P(E)表示，产生式规则表示，产生式规则“IF E THEN HIF E THEN H”的的不确定性表示为事件不确定性表示为事件E E（证据）已经发生的条件下，事件（证据）已经发生的条件下，事件H H（结论）发生的概率（结论）发生的概率 P(

31、H|E)P(H|E)。2023-1-5Expert System and Application285.1.5 单调推理和非单调推理单调推理和非单调推理1）单调推理）单调推理：增加了新的命题，新的定理又可以被证明出，：增加了新的命题，新的定理又可以被证明出，而且这种加入和证明出的命题，绝对不会与以前已知为真的而且这种加入和证明出的命题，绝对不会与以前已知为真的命题相矛盾，从而不会将已知为真的命题变为无效。命题相矛盾，从而不会将已知为真的命题变为无效。2）非单调推理）非单调推理：当新的命题加入时，可能对原有知识要加以：当新的命题加入时，可能对原有知识要加以修改，甚至抛弃。特点是：当公理增加时，公

32、理系统中定理修改，甚至抛弃。特点是：当公理增加时，公理系统中定理得数目并不一定随之增加。得数目并不一定随之增加。非单调推理的方法有两种：非单调推理的方法有两种：（1）默认推理）默认推理：当且仅当事实证明：当且仅当事实证明S不成立时，不成立时，S总是成立的。总是成立的。（2）约束推理：）约束推理：当且仅当没有事实证明当且仅当没有事实证明S在更大范围内成立在更大范围内成立时，时，S只能在指定范围内成立。只能在指定范围内成立。2023-1-5Expert System and Application295.1.6 推理与知识表示推理与知识表示 在专家系统中，一般采用基于专门知识的推理。这种推在专家系

33、统中，一般采用基于专门知识的推理。这种推理方式以拥有知识的利用为前提，而知识在系统中有一定的理方式以拥有知识的利用为前提，而知识在系统中有一定的表示模式，推理方式和控制策略在很多程度上依赖于知识的表示模式，推理方式和控制策略在很多程度上依赖于知识的表示模式。表示模式。知识的表示模式的不同，决定了知识的选择和运用方式知识的表示模式的不同，决定了知识的选择和运用方式的不同，即推理策略和推理方式的不同。的不同，即推理策略和推理方式的不同。2023-1-5Expert System and Application30 根据专家系统中知识表示方法的不同特征，推理可分根据专家系统中知识表示方法的不同特征，

34、推理可分为如下几种不同形式：为如下几种不同形式：推理方式推理方式基于规则的推理基于规则的推理基于谓词逻辑基于谓词逻辑的推理的推理基于语义网络的基于语义网络的推理推理基于框架的推理基于框架的推理知识运用知识运用知识选择知识选择2023-1-5Expert System and Application31 推理包括两个基本内容：知识运用的推理方式和知推理包括两个基本内容：知识运用的推理方式和知识选择的推理策略。识选择的推理策略。推理策略主要解决整个问题求解过程中的知识选择推理策略主要解决整个问题求解过程中的知识选择和应用顺序，即解决先做什么，后做什么，并根据问题求和应用顺序，即解决先做什么，后做什

35、么，并根据问题求解的当前状态分别做不同的工作。一旦出现异常情况，还解的当前状态分别做不同的工作。一旦出现异常情况，还能知道如何处理异常。能知道如何处理异常。目前，专家系统中采用的推理策略有如下几种。目前，专家系统中采用的推理策略有如下几种。2023-1-5Expert System and Application325.2.1 冲突消解策略冲突消解策略5.2.2 正向推理控制策略正向推理控制策略5.2.3 反向推理控制策略反向推理控制策略5.2.4 混合推理控制策略混合推理控制策略5.2.5 双向推理控制策略双向推理控制策略5.2.6 元控制策略元控制策略5.2.7 推理效率与推理效果推理效率

36、与推理效果2023-1-5Expert System and Application335.2.1 冲突消解策略冲突消解策略1）冲突消解策略在）冲突消解策略在ES中的作用中的作用 冲突消解策略解决如何在多条可用知识中，合理的选择冲突消解策略解决如何在多条可用知识中，合理的选择一条知识的问题，是一种基本的推理控制策略。一条知识的问题，是一种基本的推理控制策略。在专家系统问题求解过程中，知识与当前数据库中的内在专家系统问题求解过程中，知识与当前数据库中的内容进行匹配，如果匹配，则成为可用知识。当可用知识不止容进行匹配，如果匹配，则成为可用知识。当可用知识不止一条时，会发生一条时，会发生“冲突冲突”

37、，在多条可用知识中，选择一条知，在多条可用知识中，选择一条知识启用的过程，称为识启用的过程，称为“冲突消解冲突消解”。通常问题求解中，冲突消解策略有通常问题求解中，冲突消解策略有深度优先深度优先和和广度优先广度优先策略。策略。2023-1-5Expert System and Application34 在专家系统问题求解过程中，推理机的基本任务是决定在专家系统问题求解过程中，推理机的基本任务是决定下一步应该做什么，既选择哪些知识，完成哪些操作，进一下一步应该做什么，既选择哪些知识，完成哪些操作，进一步通过操作来修改和增加全局数据库的内容，直到问题求解步通过操作来修改和增加全局数据库的内容，直

38、到问题求解完毕。完毕。在问题求解的每个状态下，一条知识是否可用，取决于在问题求解的每个状态下，一条知识是否可用，取决于这条知识的条件部分与问题求解的当前数据库中内容的匹配这条知识的条件部分与问题求解的当前数据库中内容的匹配程度，即使匹配，知识的最终选择和运用要由推理机来确定。程度，即使匹配，知识的最终选择和运用要由推理机来确定。2023-1-5Expert System and Application35 一般情况下，在求解的每个中间状态，可用的知识不一般情况下，在求解的每个中间状态，可用的知识不只一条，即可能发生所谓的只一条，即可能发生所谓的“冲突冲突”。在多条可用知识中。在多条可用知识中选

39、择一条知识的启用过程称为选择一条知识的启用过程称为“冲突消解冲突消解”。在通常的数学问题求解过程中，再回溯其他知识。在通常的数学问题求解过程中，再回溯其他知识。在在ES求解问题的环境中，冲突消解策略往往采用深度求解问题的环境中，冲突消解策略往往采用深度优先策略或广度优先策略。其基本思想是：先试用一条知优先策略或广度优先策略。其基本思想是：先试用一条知识，若这条知识在运用过程中出现失效，再回溯其他知识。识，若这条知识在运用过程中出现失效，再回溯其他知识。2023-1-5Expert System and Application36 在在ES求解问题的环境中，这种策略往往是低效的。这求解问题的环境

40、中，这种策略往往是低效的。这是由于：是由于：（1）随着问题复杂性增加，企图试探每一种可能的求）随着问题复杂性增加，企图试探每一种可能的求解路径，知识的检索和选择会出现解路径，知识的检索和选择会出现“组合爆炸组合爆炸”现象。使现象。使得在有限时间内可能给不出解。得在有限时间内可能给不出解。（2）有些实际问题（病人急诊、生产过程的实时监控）有些实际问题（病人急诊、生产过程的实时监控）对求解响应的速度要求非常高，根本不允许试探各种可能对求解响应的速度要求非常高，根本不允许试探各种可能求解路径后再给出问题的解。求解路径后再给出问题的解。2023-1-5Expert System and Applica

41、tion372）冲突消解的实现）冲突消解的实现 简单冲突消解策略是将多条知识按优先级排序。排序简单冲突消解策略是将多条知识按优先级排序。排序策略大致有如下几种：策略大致有如下几种：（1）专一性排序）专一性排序 若一条知识比另一条知识更具体，即一条知识的条件若一条知识比另一条知识更具体，即一条知识的条件部分是另一条知识条件的弱化，则弱化知识比强化知识具部分是另一条知识条件的弱化，则弱化知识比强化知识具有更高的优先级。有更高的优先级。（2）知识库组织次序排序）知识库组织次序排序 以知识在知识库组织中的顺序决定优先级的次序。在以知识在知识库组织中的顺序决定优先级的次序。在问题求解中，一旦一条知识为可

42、用知识，就立刻选择该知问题求解中，一旦一条知识为可用知识，就立刻选择该知识，进入下一环节的推理。识，进入下一环节的推理。2023-1-5Expert System and Application38 （3）数据排序）数据排序 把知识条件部分的所有条件项按优先级的次序组织，把知识条件部分的所有条件项按优先级的次序组织，可用知识的次序由这些知识所含条件的字典排序方法进行可用知识的次序由这些知识所含条件的字典排序方法进行选择。选择。（4）就近排序）就近排序 就近排序策略有一个动态修改知识优先级的算法，把就近排序策略有一个动态修改知识优先级的算法，把最近使用的知识标记为最高优先级。最近使用的知识标记为

43、最高优先级。（5）分块组织）分块组织 知识库的组织按它们所对应的问题求解状态进行分块知识库的组织按它们所对应的问题求解状态进行分块（或分组）。在问题求解过程中，只能从相应的知识库中（或分组）。在问题求解过程中，只能从相应的知识库中选择可用知识。选择可用知识。2023-1-5Expert System and Application39 （6）数据冗余）数据冗余 当一条知识的操作产生冗余事实时，则这条知识的优当一条知识的操作产生冗余事实时，则这条知识的优先级降低。冗余事实越多，优先级越低。如果产生的事实先级降低。冗余事实越多，优先级越低。如果产生的事实全部为冗余事实时，则这条知识为不可用知识。全

44、部为冗余事实时，则这条知识为不可用知识。除上述除上述6条排序策略外，还有其他策略。条排序策略外，还有其他策略。需要注意的是：冲突消解策略是一个基本控制策略，需要注意的是：冲突消解策略是一个基本控制策略，以后许多内容都会涉及冲突消解策略的基本方法。以后许多内容都会涉及冲突消解策略的基本方法。2023-1-5Expert System and Application40例例.移动球的问题移动球的问题（一一）将将10个盒子排成一列，前面两个是空的，后面盒子里个盒子排成一列，前面两个是空的，后面盒子里相间放着相间放着4个红球和个红球和4个白球，若每次可移动任意两个相邻个白球，若每次可移动任意两个相邻的

45、球进入空盒，移动时两球不得更动原来次序。的球进入空盒，移动时两球不得更动原来次序。目标是将目标是将4个红球连在一起，而空盒位置不限。试编程，个红球连在一起，而空盒位置不限。试编程，求出一种方案并输出每一次移动后球的状态。求出一种方案并输出每一次移动后球的状态。下面是一种球放置的最初状态下面是一种球放置的最初状态，其中其中O表示空盒子，表示空盒子，A表示红球，表示红球，B表示白球。表示白球。O O A B A B A B A B 2023-1-5Expert System and Application41解：解：1）定义状态结点）定义状态结点 用一个数组用一个数组ball10存放球的放置状态，

46、变量存放球的放置状态，变量last和和spac分别存储父结点编号和第一个空盒的位置。分别存储父结点编号和第一个空盒的位置。2）扩展规则）扩展规则 因为只能同时移动两个球并且不改变顺序，因此球移因为只能同时移动两个球并且不改变顺序，因此球移动的目标是两个相连的空盒，否则不能移动。移动球后状动的目标是两个相连的空盒，否则不能移动。移动球后状态改变。态改变。3）重复结点与目标结点的判断）重复结点与目标结点的判断 判断是判断是比较简单比较简单的的，只需顺次检查盒子状态即可。，只需顺次检查盒子状态即可。2023-1-5Expert System and Application42 （2）深度优先搜索策略

47、深度优先搜索策略（Depth-first search）p 基本思想：基本思想：首先扩展最新产生的（最深的）节点首先扩展最新产生的（最深的）节点，深度相，深度相等的节点可以任意排列。扩展最深节点的结果使得搜索沿着等的节点可以任意排列。扩展最深节点的结果使得搜索沿着状态空间某条单一路径从起始节点向下进行下去，只有当搜状态空间某条单一路径从起始节点向下进行下去，只有当搜索到达一个没有后裔的状态时，才会考虑另一条替代路径。索到达一个没有后裔的状态时，才会考虑另一条替代路径。替代路径与前面已经试过的路径不同之处仅在于改变最后替代路径与前面已经试过的路径不同之处仅在于改变最后n步搜索，而且保持步搜索，而

48、且保持n尽可能小。尽可能小。对于许多问题，其状态空间搜索树的深度可能为无限深，对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度的上限或者可能至少要比某个可接受的解答序列的已知深度的上限还要深，为了避免考虑过长的路径，往往给出一个节点扩展还要深，为了避免考虑过长的路径，往往给出一个节点扩展的的最大深度最大深度（深度界限），如果任何节点达到了深度界限，（深度界限），如果任何节点达到了深度界限，则将它作为没有后裔的节点处理。则将它作为没有后裔的节点处理。2023-1-5Expert System and Application43 值得注意的是：即使应

49、用了深度界限值得注意的是：即使应用了深度界限n，得到的解答路，得到的解答路径并不一定是最短路径。径并不一定是最短路径。在深度优先搜索中，首先扩展最新产生的（即最深的）在深度优先搜索中，首先扩展最新产生的（即最深的）节点。深度相等的节点可以任意排列。节点。深度相等的节点可以任意排列。深度定义如下：深度定义如下：（1）起始节点（即根节点）的深度为）起始节点（即根节点）的深度为0（2）任何其它节点的深度等于其父辈节点深度）任何其它节点的深度等于其父辈节点深度+1 首先，扩展最深的节点的结果，使得搜索沿着状态空间首先，扩展最深的节点的结果，使得搜索沿着状态空间某条单一的路径，从起始节点向下进行下去；只

50、有当搜索到某条单一的路径，从起始节点向下进行下去；只有当搜索到达一个没有后裔节点的状态时，它才考虑另一条替代路径。达一个没有后裔节点的状态时，它才考虑另一条替代路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后替代路径与前面已经试过的路径不同之处仅仅在于改变最后n步，而且保持步，而且保持n尽可能小。尽可能小。2023-1-5Expert System and Application44 由于冲突消解策略的由于冲突消解策略的宽宽度优先度优先和和深度优先搜索深度优先搜索一般只适一般只适用于求解比较简单的问题，对于复杂问题的求解必须采用更用于求解比较简单的问题，对于复杂问题的求解必须采用更为