第6章问题求解范型.doc

《第6章问题求解范型.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第6章问题求解范型AI的许多方面涉及问题求解。因此，研究人类的问题求解方法是AI领域的重要课题。在AI的研究和实践中，总结出来一整套一般问题求解方法－－问题求解范型。下面的列表给出了AI的主要问题求解范型，但不是一个完全的表：l描述—匹配（第2章）；l目标归约（第2章）；l约束传播（第3章）；l搜索（第4章）；l手段－结局分析（第5章）；l产生－测试（第6章）；l规则系统（第6章）；l形式逻辑（第7章）；l遗传算法等本章介绍两种重要的、常用的问题求解范型：产生—测试和基于规则系统。产生－测试问题求解范型在很多实际系统中得到应用。本章我

2、们分析两个系统中使用的该类问题求解范型：lDENTRAL：用于有机化学领域，从质谱图分析有机物的结构；lACRONYM：用于图象处理，从航空照片中辨别飞机。基于规则系统，又称为产生式系统，常见于知识工程中，很多专家系统属于基于规则系统问题求解范型。专家系统执行的任务的类型可有：l综合（Synthesis）：如，XCON组配计算机；l分析（Analysis）：如，MYCIN诊断感染疾病；l解释（Interpretation）：如，PROSPECTOR解释油井日志。学习这一章的目的是，通过学习，能根据问题求解特征，选择适宜的范型，建立问题

3、求解器。另外，在AI文献中，经常提及“弱方法（weakmethods）”概念。它是指弱方法：不需要对问题领域有深刻理解的问题求解范型。6.1产生和测试产生－测试范型的组成l产生器：枚举可能的解，即产生假设。l测试器：评估假设，判断是否接受产生的解。产生－测试范型的工作方式l第一种：首先产生所有可能的解，然后对所有的解进行测试；l第二种：产生器和测试器交替工作，产生一个解，就进行测试。终止条件有三种可能：其一，一旦发现一个可接受的解，系统终止工作；其二，一旦发现指定数目的解，系统终止工作；其三，发现所有的解后，系统终止工作。6.1.1产

4、生－测试系统在识别问题中的应用产生－测试范型经常用来解决识别问题。但是，一般限制于问题的可能解答在102量级上的情况。若可能的解答太多，产生－测试的问题求解效率会很低。下面有两个例子说明怎样用产生－测试范型解决识别问题。例子1，识别树。假设有一未知名的树，希望通过查阅一本有关树的书，来识别它。一般做法是一页一页地依次翻书，当发现书中某张图片与要识别的树相同时，停止翻书。一页一页地翻书就是产生过程，把图片与树匹配就是测试过程。例子2，开保险柜的密码锁。假设保险柜由6位数字组成，而你忘记了密码。可能的做法是依次尝试密码的所有组合：00－0

5、0－00，00－00－01，00-00-02，…直到打开保险柜的门。生成密码的各种组合就是产生过程，转动保险柜的手柄就是测试过程。6位数字密码的可能组合是106，打开密码锁的平均尝试次数是500000。因此，用产生－测试方法开密码锁是很低效的。6.1.2产生器特性一个好的产生器应该具有下列三个特性：l产生器是完全的。产生器应有能力产生所有可能的解。l产生器是无冗余的。产生器不能多次提出相同的解，以免损害效率。l产生器具有启发能力。产生器能使用可能的约束信息，限制解空间。对于一个产生器来说，启发能力是非常重要的，因为在一般情况下，可能解

6、的数目非常大。用上面的例子来说明怎样使用启发式。在识别树的例子中，若时间是冬季，并发现要识别的树是光秃的，则翻书时会跳过常青乔本（针叶树）部分。在开密码锁的例子中，若能确定密码的组合是素数，且在00～99之间，则尝试的可能是253=15625。6.1.3DENTRAL与产生--测试范型DENTRAL是使用产生－测试范型的典型专家系统。DENTRAL代表DENTRiticAlgorithm（所谓树状算法），是第一个专家系统。由斯坦福大学Feigenbaum领导的研究小组于1965年开始开发的，1968年基本开发成功，主要开发者是J.Le

7、derbeg。DENTRAL的知识表示产生器用过程语言实现，测试器用InterLisp语言实现，这是一种规则表示语言。META－DENTRA随后，开发了META－DENTRAL，用于获取DENTRAL所需的知识，它带学习功能，帮助化学家确定质谱片段（fragmentation）与子结构特性之间的关系，即学习给定分子类的片段规则。META－DENTRAL也是用InterLisp语言实现的。META－DENTRAL使用示例学习方法，其过程如下：输入：已知分子的三维结构，及一组质谱图。输出：关于分子结构与质谱图的关系的规则。1.生成规则：产

8、生一组关于特定分子的单一分片过程的、高度特殊化的规则。2.规则一般化：用训练实例将特殊规则一般化。3.精化规则：移去冗余或错误规则。有机化学家鉴别分子结构的过程有机化学家在测试试管中生成了一种新物质，欲知道这种物质的化学