智能系统中深度搜索与广度搜索相结合推理方法的研究毕业论文.docVIP

摘要 智能系统中深度搜索与广度搜索相结合推理方法的研究摘 要人工智能是模拟人的思维活动而用机器语言来实现某些活动。它是机器智能化处理问题的重大应用。本文研究了智能辅导系统中深度搜索与广度搜索的结合应用。首先，本文简要概述了人工智能、daok语言开发工具、智能辅导系统。然后，重点讲了深度搜索与广度搜索的概念、特称及优缺点。接下来，本文研究了在智能辅导系统中深度搜索中的问题，然后给出深度搜索转化为广度搜索的解决方法，及最后的转化设计流程。最后，本文用编程来实现其中的一些设计方案。本文重点研究了智能辅导系统中深度搜索转化为广度搜索的方法，它在智能辅导系统中有很好的应用。关键词：智能系统 深度搜索 广度搜索 数学解题ABSTRACTArtificial intelligence is simulated person thinking activity and in machine language to realize some activities. It is the machine major application intelligent processing problem.This paper studies in depth the intelligent tutoring system with breadth first search search application combined. First, this paper briefly summarizes the artificial intelligence, daok language development tools, intelligent tutoring system. Then, the key told the depth and breadth of search search concept, doggett says and disadvantages. Next, this paper studied in intelligent tutoring system in depth the problem, then give search depth search into breadth first search solutions, and the final transformation design process. Finally, this paper uses programming realize some of the design scheme. This article focuses on intelligent tutoring system is transformed into breadth first search depth search method of intelligent tutoring system, it has very good applications.Keywords: intelligent system depth search breadth search mathematics problem-solving 目录 目录第一章绪论11.1人工智能概述11.2Daok语言概述21.3智能系统在智能辅导系统中的应用41.4本文的研究内容51.5本章小结5第二章深度搜索与广度搜索72.1 深度搜索72.1.1深度搜索的概念72.1.2深度搜索的特征72.2 广度搜索82.2.1广度搜索的概念82.2.2广度搜索的特征92.3深度搜索与广度搜索的比较102.4本章小结10第三章辅导系统中的深度搜索转化为广度搜索的需求分析113.1辅导系统在深度搜索下的概述113.1.2输出模版与堆栈123.1.3对输出的解释153.2辅导系统对深度搜索转化为广度搜索的需求213.3本章小结23第四章智能辅导系统中深度搜索转为广度搜索的方案设计254.1深度搜素与广度搜索的结合过程概述254.1.1结合过程254.1.2结合方法254.1.3深度转化为广度的分类294.2最简单的深度转为广度的过程294.2.1实现功能294.2.2流程图的设计304.3同层异堆栈的转化过程314.3.1实现功能314.3.2流程图的设计324.4同层同堆栈的转化过程344.4.1实现功能344.4.2流程图的设计354.5本章小结37第五章智能辅导系统中深度转为广度的实现过程395.1最简单转化的实现过程395.1.1程序设计395.1.2运行程序415.2 同层异堆栈的转化实现过程445.2.1程序设计445.2.2运行程序455.3 同层同堆栈的转化实现过程495.3.1程序设计495.3.2运行程序525.4本章小结56第六章总结57第七章致谢59第八章 参考文献61 第一章 绪论 3第一章绪论1.1 人工智能概述人工智能（Artificial Intelligence）, 英文缩写为 AI, 是一门由计算机科学、控制论、信息论、语言学、神经生理学、心理学、数学、哲学等多种学科相互渗透而发展起来的综合性新学科。自问世以来AI经过波波折折，但终于作为一门边缘新学科得到世界的承认并且日益引起人们的兴趣和关注。不仅许多其他学科开始引入或借用AI技术，而且AI中的专家系统、自然语言处理和图象识别已成为新兴的知识产业的三大突破口。人工智能是当前科学技术发展中的一门前沿学科，同时也是一门新思想、新观念、新理论、新技术不断出现的新兴学科以及正在迅速发展的学科。它的出现及所取得的成就引起了人们的高度重视，并得到了很高的评价。有的人把它与空间技术、原子能技术一起誉为20世纪的三大科学技术成就；有的人把它称为继三次工业革命后的又一次革命，并称前三次工业革命主要是延长了人手的功能，把人类从繁重的体力劳动中解放出来，而人工智能则是延伸人脑的功能，实现脑力劳动的自动化。人工智能的定义可以分为两部分，即“人工”和“智能”。“人工”比较好理解，争议性也不大。有时我们会要考虑什么是人力所能及制造的，或着人自身的智能程度有没有高到可以创造人工智能的地步，等等。但总的来说，“人工系统”就是通常意义下的人工系统。人工智能研究的题材可分为：(1)联络沟通(connectionism)，以及如何使电脑更有智慧了解人的语言和知识。(2)符号处理(symbol manipulation)，如LISP人工智能语言，生产系统，黑板系统(blackboard system)等领域的研究。(3)经验法则搜寻技巧(heuristic search)。(4)逻辑(logic)系统，如复杂事实的归纳及推理等。未来人工智能的发展包含：将人工智能技术应用在机器上，将原来顺序逻辑架构的电脑改为高速平行架构的电脑，以及发展具有经济价值的商业应用产品。研究的方式包括理论和实践两个层面，其中实验层面还可细分为基础部分和应用部分。研究的方向则有生物的方向和世界整体现象的方向。人工智能的研究途径主要有以下三种方法：第一种是以符号处理为核心的方法，第二种是以网络连接为主的连接机制方法，最后一种是系统集成。由于前两种方法各有所长，也各有所短，因此把两种方法结合起来也就更具适应性。就目前的研究而言，把两种方法结合起来的途径主要有两种方法：一种是结合，即两者分别保持原有的结构，但密切合作，任何一方都可把自己不能解决的问题转化给另一方；另一种是统一，即把两者自然的统一在一个系统中，既有逻辑思维的功能，又有形象思维的功能。1.2Daok语言概述一、daok Daok智能系统开发工具描述的是资源模型的推理模块，它完全用Java语言编写，Daok采用基于规则的系统，它能与强大的可移动的Java语言代码紧密结合。 Daok来自于一套Java源文件，它起源于CLIPS，是十分有效的解释规则语言的程序。作为CLIPS的继承物这种规则语言是基于LISP的较小的。Daok的工具函数仅仅是CLIPS的小子集，但它与一般的程序设计语言（如：C程序设计语言）相比，Daok处理集合的功能是十分强大的，绝大部分的Daok函数运用中，输入和输出参数都是集合即Daok中的多值域的形式出现，另一部分是以字符串为参数的函数。在本文中还出现了单纯的数字为参数的情况。目前，新版本的Daok有以下特点：引擎运行速度快遵守LHSS规则，能从Daok语言中直接操作Java对象和Java对象的模式匹配，同样的，作为函数能在Daok中写JavaGUIS和假设事件处理。支持I/O路由器支持条件元件和返回值限制，允许重写LHSs规则Daok语言设计中的基本参数形式有：原子，数字，字符串，语句，注释，函数，变量，构造等等。本文主要运用了其中的函数。Daok中包括了大量的内部函数，其中许多都是可扩展，也可以编写自己的函数。在Daok中，函数调用使用前缀表示法。在Daok中，运用函数要特别注意其输入输出，参数类型及其应用范围。二、Daok语言设计中的函数与规则Daok中使用Deffunction结构定义函数，从Daok中调用它们，deffunction结构表示如下： (deffunction函数名注释(参数1参数2) 表达式1表达式2 返回值)函数名必须是原子，任意参数必须是变量名(所有函数都采用值传递)，可选项(注释)是一个由双引号引起来的字符串，用来描述函数的功能。表达式是一系列的式子，可选项(返回值)给出函数的返回值,它既可以是一个简单的return函数调用，也可是任何值或表达式。在deffunction中由特殊的流向控制结构if和while实现程序流向的控制。Daok语言设计中也包含一系列的“事实”，或者说是关于系统当前状态的信息。事实以两种形式出现：规则的和不规则的。规则的事实仅仅是一个以原子开头的表，例如(shoping-list bread milk pater-towels)；不规则的事实是比较复杂的，包含有限个“槽”(每个槽都要有个槽名)。与规则的事实相比较，规则的事实不加定义即可应用，而不规则的事实必须用deftemplate结构加以定义。事实是由assert函数产生并置于事实表中的,可用“facts”函数来察看当前事实表；也可以用retract将一个事实从事实表中移去，只要你知道它的“事实序号”；事实库中的事实在某些槽值发生变化时，可以对相应的事实进行修改，事实修改由modify函数完成。用Deftemplate结构来定义一系列不规则的事实。(deftemplate 注释 (slot槽名 (default 缺省值 )(type typespec) (slot)模板名是即将由该模板创立的事实的头部，槽名必须是原子。修饰词“default”表明新事实中的槽的缺省值由“缺省值”给出；若没有给出缺省值，则缺省值为原子“nil”槽修饰词“type”Daok可以接受，(为了与CLIPS兼容)但不起任何作用。Daok中的规则有点像其他语言中的Ifthen结构；在操作过程中，Daok不停的检查是否有某一规则的If部分成为真，然后执行相应的then事实部分。事实上，一个智能规则系统的“智能”包含在规则中，defrule结构用于为Daok制定规则。(defrule 注释行 优先级声明 模式赋值 模式1 其他模式=操作1操作2）一个规则有一个模式表( If部分,在规则的左半部分 LHS)和一个操作表(then部分,在规则的右半部分 RHS)模式与事实表相匹配。当一个事实被发现与一个规则的所有模式相匹配，则这个规则被激活，意味着它可以被启用(执行它的行为部分)。一个处于激活状态的规则可能在起用前退出激活状态，如果匹配它的模式的事实被收回或被从事实表中移去，这时它将处于等待启用状态。 1.3 智能系统在智能辅导系统中的应用初中代数智能辅导软件主要针对初中代数的一个专家系统，它摹仿人类思维方式，通过提供逐步提示、解后难点重点分析、一题多解、学习问题汇总等功能，给学生提供完全符合人类思维习惯的学习辅导。 第一章 绪论 51.1智能辅导系统的组成模块初中代数智能辅导软件主要由自然语言理解，建模，解题系统和输出界面四个部分组成.题目进入系统后，经过自然语言的理解并归类，带着理解后的信息进入到建模这一模块，此模块再进一步将信息细分为各小类，然后进入解题系统解题，最后将结果输出给用户。1.4 本文的研究内容在智能辅导系统中，我们是按照深度搜索的顺序来解题。但是在实际的解题过程中，往往由于深度搜索的弊端存在，使得我们的解题过程显得不是那么的完美。为此，我们需要用广度搜索的方法来弥补深度搜索过程中的不足。即，我们需要将深度搜索与广度搜索结合起来的方法而来处理问题。本文重点研究了在深度解释后的输出结果中，把满足条件的输出通过转化为广度搜索而记录其可以合并的输出事实的过程。1.5本章小结本章讲了人工智能的相关情况、daok语言的基本规则以及智能辅导系统的概述，完了之后又简单说明了下本文研究的内容。 第二章 深度探索与广度探索 9第二章深度搜索与广度搜索2.1 深度搜索2.1.1深度搜索的概念深度优先搜索算法（Depth-First-Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。如图2.1.1所示。图2.1深度优先算法对深度为4的树的遍历顺序2.1.2 深度搜索的特征空间复杂性深度优先搜索队内存的需求是比较适中的。它只需要保存从根到叶的单条路径，包括在这条路径上每个节点的未扩展的兄弟节点。当搜索过程到达了最大深度的时候，所需要的内存最大。假定每个节点的分支系数为b,当我们考虑深度为d的一个节点时，保存在内存中的节点的数量包括到达深度d的唯有扩展的节点以及在正在被考虑的节点。因此，在每个层次上都有（b-1）个未扩展的节点，总的内存需要量为d(b-1)+1。因此深度优先搜索的空间复杂度是b的线性函数O（bd）而广度优先搜索的空间复杂度是b的指数函数。事实上，这也是深度优先搜索最有用的一个方面。时间复杂性如果搜索d层如果搜索在d层最左边的位置找到了目标，则检查的节点数位（d+1）。另一方面，如果只是搜索到d层，而在d层最右边找到了目标，则检查的节点包括了树中所有的节点，其数量为：所以，平均来说，检查的节点数量为：上式就是深度优先搜索的平均时间复杂度。2.2 广度搜索2.2.1 广度搜索的概念广度优先搜索算法（Breadth-First-Search），又译作宽度优先搜索，或横向优先搜索，简称BFS，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。如图2.1.2所。图2.2 广度优先算法对深度为4的树的遍历顺序2.2.2 广度搜索的特征时间复杂度为了便于分析，我们考虑一棵树，其每个节点的分支系数都为b，最大深度为d.其中分支系数是指每一个节点可以扩展产生的新的节点数目。因此搜索树的根节点在第1层会产生b个节点，每个节点又产生b个新的节点，这样在第2层就会有个节点。因为目标不会出现在深度为（d-1）层，失败搜索的最小节点数目为： b1而在找到目标节点之间可能扩展到得最大节点数目为：对于d层，目标节点可能是第一个状态，也可能是最后一个状态。因此，平均需要访问的d层节点数目为：（1+）/2所以，平均总的搜索的节点数目为：因此，广度优先搜索的时间复杂度和搜索的节点数目成正比。空间复杂度广度优先搜索中，空间复杂度和时间复杂度一样，需要很大的空间，这是因为树的所有的叶节点都同时需要储存起来。根节点扩展后，队列中有b个节点。第1层的最左边节点扩展后，队列中有（2b-1）个节点。而当d层最左边的节点正在检查是否是目标节点的时候，在队列中的节点数目最多，为（）。该算法的空间复杂度和队列的长度有关，在最坏的情况下约为指数级O()。2.3 深度搜索与广度搜索的比较深度优先搜索的优点是比广度优先搜索算法需要较少的空间，该算法只需要保存搜索树种的一部分，它由当前正在搜索的路径和该路径上海没有完全展开的节点标志所组成。因此，深度优先搜索的存储器要求是深度约束的线性函数。但是其主要问题是可能搜索到了错误的路径上。很多问题可能具有很深甚至是无限的搜索树，如果不幸选择了一个错误的路径，则深度优先搜索会一直搜索下去，而不会回到正确的路径上。这样对于这些问题，深度优先搜索要么陷入无限的循环而不能给出答案，要么最后找到一个答案，单路径很长而且不是最优的答案。这就是说深度优先搜索既不是完备的，也不是最优的。广度优先搜索是一种盲目搜索，时间和空间复杂度都比较高，当目标结点距离初始节点较远时（即d较大时）会产生很多无用的节点，搜索效率较低。从表2.1可以看出，广度优先搜索中，时间需求是一个很大的问题，特别是党搜索的深度比较大时，尤为严重，但是空间需求是比执行时间更严重的一个问题。但是广度优先搜索也有其优点，目标节点如果存在，用广度优先搜索算法总可以找到目标结点，而且d最小（即最短路径）的节点。2.4 本章小结本文开头讲了深度搜索与广度搜索的概念及特征，之后对于深度搜索与广度搜索的优缺点作了说明。深度搜索与广度搜索时本文研究的重点内容，所以对其专门的研究是很有必要的。第三章 辅导系统在深度探索转化为广度探索的需求分析 23第三章 辅导系统中的深度搜索转化为广度搜索的需求分析3.1 辅导系统在深度搜索下的概述3.1.1 深度搜索下解释总流程深度搜索的解释总流程主要包括代数解释、优化解释、区域合并、比较相邻行删除多余、解释后处理几大模块。其总流程图如下:图3.1 深度搜索下的解释总流程3.1.2输出模版与堆栈1. 输出模版(deftemplate 输出 (slot 序列号 (default +) 主要用于对输出事实重新排序时作标记 (slot 初始序列号 (default 1) 每记录一条输出事实，“初始序列号”都会自动加1，“初始序列号”的递增顺序就记录了解题的基本过程。它是区分输出事实的唯一标志。(multislot 堆栈参数 (default (create$ 1) 记录解题递归的层次，在生成子式且子式与父式发生改变时将当前序列号入栈，子式返回时出栈(slot 表达式 (default 空)存储解题中间结果 (slot 输出 (default 空) 存储输出中间结果，在解释时填写，解题时不用填写(slot 层数 (default 空) 方程生成子方程时记录(multislot 局部处理参数 (default (create$ 空) 解释时用到(multislot 结果 (default (create$ 空) 存储最终结果，最后一条事实填写，其余事实结果均为空，标志着解题结束(slot 方法 (default 空) 操作所用的基本方法，在方法名后加“se”标识在最终界面会被删除，加“没用”时，在解释过程中会被删除，加qq时，表示强制保留(slot 级别 (default 50) 用于知识点输出，每个模块都有自己的级别范围，知识点越难级别越高(slot 分组信息 (default 空) 用于输出的控制，在槽中加上“”，表明输出要求保留(slot 题目类型 (default 一般题目) 用于区分一般题目和特殊题目 (multislot 配方信息 (default (create$ 空) 记录配方的基本信息，主要为逐步提示和解后反思提供所需要的数据信息(slot 父表达式 (default 空) 主要在因式分解、化简中用到(slot 标识信息 (default 空) 求值删除等号标记(slot 化简标识信息 (default 空) 求值中的化简删除等号标记(slot 输出标识 (default 空) 用于反映输出中模块间调用关系(multislot 暂存表达式 (default (create$ ) 优化输出时记录前面合并过的子式(multislot 对应栈 (default (create$ )子式合并时，用于存放暂存表达式中表达式对应的栈 “输出标识”各个位置所代表的意思说明：表示的各位与个模块的对应表第1位展开 第2位因式分解第3位化简 第4位方程第5位不等式 第6位不等式组第7位方程组 第8位证明第9位求值 第10位单变量代换第11位整体代换 第12位当前模块第13位模块层次 第14位预留3第15位预留4 第16位预留5第17位预留6 第18位预留7举例：(输出标识 标识%01010000000220000000)第2位为1，表示因式分解模块被调用了一次第4位为1，表示方程模块被调用了一次第12位为2，表示当前模块为因式分解模块第13位为2，表示当前模块的所处的调用层次 2.堆栈(1)栈的出栈和入栈：在生成子式且子式（或子方程）与父式（或父方程）发生改变时，成为入栈；相反，子式返回时成为出栈。(2)前出栈处理：(judge-pop-stack-2 (create$ 1 3) (create$ 1 7) 第一个多值域长度等于第二个多值域长度，输出第一个多值域与第二个多值域不同的项，否则输出FALSE若上面函数输出不为FALSE，则删除表达式中标记上面函数输出；否则不予处理。(3)后出栈处理：(judge-pop-stack-1 (create$ 1 3 7) (create$ 1 3) 第一个多值域长度大于第二个多值域长度，输出两个多值域不同的项，否则输出FALSE若上面函数输出不为FALSE，则删除表达式中标记上面函数输出；否则不予处理。3.1.3对输出的解释解释规则总共由两个文件组成：explain.clp 和 explain_to_simple.clp，在执行时先调用 文件 explain.clp 再调用 文件 explain_to_simple.clp一、explain.clp1.功能：(1)填“输出事实”的 输出槽(2)删除没用的方法 (依据:方法槽中值的头部 为 “没用”)(3)删除多余的解释（依据:如果前一个输出与后一个输出的输出槽相等则删除后一个输出）(最后一条输出（即结果）除外，永远都不会被删除)生成的事实为：“输出式” 例：解方程 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0 利用解整分方程的规则后生成的初始输出事实为：(堆栈参数 1) (表达式 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0) (堆栈参数 1) (表达式 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0)(堆栈参数 1) (表达式 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0)(堆栈参数 1 4) (表达式 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6)(堆栈参数 1 4) (表达式 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6)(堆栈参数 1 4 6) (表达式 !6_*x_!4)(堆栈参数 1 4 6) (表达式 !6_*x_!4)(堆栈参数 1 4 6) (表达式 _+!6_*x_!4#)(堆栈参数 1 4 9) (表达式 _-!9_*x_!3)(堆栈参数 1 4 9) (表达式 _-!9_*x_!3)(堆栈参数 1 4 9) (表达式 _-!9_*x_!3)(堆栈参数 1 4 12) (表达式 !6_*x_!2)(堆栈参数 1 4 12) (表达式 !6_*x_!2)(堆栈参数 1 4 12) (表达式 _+!6_*x_!2#)(堆栈参数 1 4 15) (表达式 _-!9_*x)(堆栈参数 1 4 15) (表达式 _-!9_*x)(堆栈参数 1 4 15) (表达式 _-!9_*x)(堆栈参数 1 4) (表达式 !6_+!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x)(堆栈参数 1 4) (表达式 !6_+!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x)(堆栈参数 1 4) (表达式 !6_+!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x)(堆栈参数 1 4) (表达式 !3_*!2_+!2_*x_!4_-!3_*x_!3_+!2_*x_!2_-!3_*x#)(堆栈参数 1 4 21) (表达式 !2_+!2_*x_!4_-!3_*x_!3_+!2_*x_!2_-!3_*x)(堆栈参数 1 4 21) (表达式 !2_+!2_*x_!4_-!3_*x_!3_+!2_*x_!2_-!3_*x#)(堆栈参数 1 4) (表达式 !3_*!2_+!2_*x_!4_-!3_*x_!3_+!2_*x_!2_-!3_*x#)(堆栈参数 1 4) (表达式 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3#)(堆栈参数 1 4) (表达式 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3#)(堆栈参数 1 4) (表达式 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3#)(堆栈参数 1 4) (表达式 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3#)(堆栈参数 1 4) (表达式 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3#)(堆栈参数 1) (表达式 sr!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3#=!0er)2.执行规则 explain.clp(1)填输出槽-1原则：从第一条输出事实开始，在表达式的首尾加上堆栈参数中的数字作为压栈标志，将其存入输出槽中。接下来循环处里每一条输出事实，如果当前处理的输出事实与前一条输出处于同一层栈中，则用其表达式替换同一栈标记中的部分；如果当前事实处于压栈状态，则找出前条输出中与当前输出中的表达式相同的部分并在其首尾加上压栈的数字作为标志，将其存入输出槽中；如果当输出处与出栈状态，则删除出栈数字的标志。(堆栈参数 1) (输出 1!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!01)(堆栈参数 1) (输出 1!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!01)(堆栈参数 1) (输出 1!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!01)(堆栈参数 1 4) (输出 14!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!64=!01)(堆栈参数 1 4) (输出 14!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!64=!01)(堆栈参数 1 4 6) (输出 146!6_*x_!46_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!64=!01)(堆栈参数 1 4 6) (输出 146!6_*x_!46_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!64=!01)(堆栈参数 1 4 6) (输出 146_+!6_*x_!4#6_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!64=!01)(堆栈参数 1 4) (输出 14 !6_+!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x 4=!01)(堆栈参数 1 4) (输出 14 !6_+!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x 4=!01)(堆栈参数 1 4) (输出 14 !6_+!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x 4=!01)(堆栈参数 1 4) (输出 14 !3_*!2_+!2_*x_!4_-!3_*x_!3_+!2_*x_!2_-!3_*x# 4=!01)(堆栈参数 1 4 21) (输出 14 !3_*21!2_+!2_*x_!4_-!3_*x_!3_+!2_*x_!2_-!3_*x21# 4=!01)(堆栈参数 1 4 21) (输出 14 !3_*21 !2_+!2_*x_!4_-!3_*x_!3_+!2_*x_!2_-!3_*x# 21# 4=!01)(堆栈参数 1 4) (输出 14 !3_*!2_+!2_*x_!4_-!3_*x_!3_+!2_*x_!2_-!3_*x# 4=!01)(堆栈参数 1 4) (输出 14 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3# 4=!01)(堆栈参数 1 4) (输出 14 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3# 4=!01)(堆栈参数 1 4) (输出 14 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3# 4=!01)(堆栈参数 1 4) (输出 14 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3# 4=!01)(堆栈参数 1 4) (输出 14 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3# 4=!01)(堆栈参数 1) (输出 1 sr!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3#=!0er 1)填输出槽-2 删标记(堆栈参数 1) (输出 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0)(堆栈参数 1) (输出 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0)(堆栈参数 1) (输出 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0)(堆栈参数 1 4) (输出 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0)(堆栈参数 1 4) (输出 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0)(堆栈参数 1 4 6) (输出 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0)(堆栈参数 1 4 6) (输出 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0)(堆栈参数 1 4 6) (输出 _+!6_*x_!4#_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0) (堆栈参数 1 4) (输出 !6_+!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x =!0)(堆栈参数 1 4) (输出 !6_+!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x =!0)(堆栈参数 1 4) (输出 !6_+!6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x =!0)(堆栈参数 1 4) (输出 !3_*!2_+!2_*x_!4_-!3_*x_!3_+!2_*x_!2_-!3_*x# =!0)(堆栈参数 1 4 21) (输出 !3_*!2_+!2_*x_!4_-!3_*x_!3_+!2_*x_!2_-!3_*x# =!0)(堆栈参数 1 4 21) (输出 !3_* !2_+!2_*x_!4_-!3_*x_!3_+!2_*x_!2_-!3_*x# # =!0)(堆栈参数 1 4) (输出 !3_*!2_+!2_*x_!4_-!3_*x_!3_+!2_*x_!2_-!3_*x# =!0)(堆栈参数 1 4) (输出 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3# =!0)(堆栈参数 1 4) (输出 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3# =!0)(堆栈参数 1 4) (输出 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3# =!0)(堆栈参数 1 4) (输出 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3# =!0)(堆栈参数 1 4) (输出 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3# =!0)(堆栈参数 1) (输出 sr!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3#=!0er )(2)删除没用的方法(3)删除多余的解释最后生成的输出式为：(输出式 (表达式 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0) (方法 解方程开始) (级别 50) (序列号 1) (分组信息 空)(输出式 (表达式 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3#=!0) (方法 得：) (级别 50) (序列号 2) (分组信息 空)(输出式 (表达式 sr!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3#=!0er) (方法 即-生成子方程) (级别 50) (序列号 3) (分组信息 空)二、执行规则 explain_to_simple.clp1功能：比较相邻的两条输出式，对于后一条输出式只输出与前一条表达式不同的部分生成的事实为：“简化输出式” 2对于上面的 三条输出式 生成的简化输出式为：(简化输出式 (表达式 !6_*x_!4_-!9_*x_!3_+!6_*x_!2_-!9_*x_+!6=!0) (方法 解方程开始) (级别 50)(简化输出式 (表达式 !3_*!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3#=!0) (方法 得：) (级别 50)(简化输出式 (表达式 sr!2_+!2_*x_!2_+!2_*x_!4_-!3_*x_-!3_*x_!3=!0er) (方法 即-生成子方程) (级别 50)3如果前后两条输出式为：(输出式 (表达式 srx=!1ersrx=!1er)(输出式 (表达式 srx=!1ersrx=!2er)=(简化输出式 (表达式 srx=!1ersrx=!1er)(简化输出式 (表达式 srx=!2er)4如果希望后一条输出式中的表达式全部输出则必须在所对应的输出事实的“分组信息槽”中加上(输出式 (表达式 srx=!1ersrx=!1er)(输出式 (表达式 srx=!1ersrx=!2er (分组信息 )=(简化输出式 (表达式 srx=!1ersrx=!1er)(简化输出式 (表达式 srx=!1ersrx=!2er)4.结束语3.2 辅导系统对深度搜索转化为广度搜索的需求为了更好的说明辅导系统中，深度搜索转化为广度搜索的必要性，下面举一个深度搜索下的辅导系统中一个解题实例。如下图所示：图3.2 深度搜索下的解体流程图上题是按照深度搜索来处理的流程。而实际应用中，第二三步是采用的是同一种方法，因此其实可以合并的。这样才更符合辅导系统的真正应用。即如下图所示：图3.3 深度搜索中可合并的情况也就是说，最佳的解体过程应该如下图所示：图3.4 深度搜索转化为广度搜索的解体流程也就是说得把深度搜索的解释过程转为广度搜索来解释。因为，这样解释会将上面例子中的同种方法合并。3.3本章小结本章前部分主要讲了在深度搜索下的辅导系统对输出的解释过程，其中包括解释总流程、输出模版与堆栈的定义、以及对输出的解释过程。后半部分，重点讲了本文对深度搜索转化为广度搜索的需求分析。第四章 智能辅导系统中深度探索转为广度探索的方案设计 37第四章 智能辅导系统中深度搜索转为广度搜索的方案设计4.1 深度搜素与广度搜索的结合过程概述4.1.1结合过程在智能辅导系统中，深度搜索与广度搜索是最基本的工具来实现问题的解释。首先，我们按照深度优先搜索的流程来解释问题，等处理完毕后，再判断此处理过还有没有可以合并的解释过程，而这些解释过程可否用广度优先搜索的方法来实现。如果可以，可通过广度优先搜索来查询可以合并的解释，并且合并处理。否则，我们按照正常的深度搜索的处理流程来解释问题。如图4.1所示。图4.1 智能系统中深度搜索与广度搜素结合的流程图4.1.2结合方法在上一章中，我们知道在深度搜索的处理流程中，当子式发生该变且与父式不同时，将当前序列号入栈。而返回时，出栈。因此，可以得知，每一次处理过程，都会影响到堆栈参数的变化。因此，堆栈参数记录了输出事实中上下层关系。1.下图是一个实例的解题过程：图4.2 范例的解题过程2.下面是该解题过程中堆栈参数的记录(输出 (初始序列号 1) (堆栈参数 1)(输出 (初始序列号 2) (堆栈参数 1)(输出 (初始序列号 3) (堆栈参数 1 3)(输出 (初始序列号 4) (堆栈参数 1 3 4)(输出 (初始序列号 5) (堆栈参数 1 3 4 5)(输出 (初始序列号 6) (堆栈参数 1 3 4 5 6)(输出 (初始序列号 7) (堆栈参数 1 3 4 5 6)(输出 (初始序列号 8) (堆栈参数 1 3 4 5 6) )(输出 (初始序列号 9) (堆栈参数 1 3 4 5 6) )(输出 (初始序列号 10) (堆栈参数 1 3 4 5)(输出 (初始序列号 11) (堆栈参数 1 3 4) )(输出 (初始序列号 12) (堆栈参数 1 3 4) )(输出 (初始序列号 13) (堆栈参数 1 3 4) )(输出 (初始序列号 14) (堆栈参数 1 3 14) )(输出 (初始序列号 15) (堆栈参数 1 3 14 15)(输出 (初始序列号 16) (堆栈参数 1 3 14 15 16)(输出 (初始序列号 17) (堆栈参数 1 3 14 15 16) )(输出 (初始序列号 18) (堆栈参数 1 3 14 15 16) )(输出 (初始序列号 19) (堆栈参数 1 3 14 15 16) )(输出 (初始序列号 20) (堆栈参数 1 3 14 15) )(输出 (初始序列号 21) (堆栈参数 1 3 14) )(输出 (初始序列号 22) (堆栈参数 1 3 14) )(输出 (初始序列号 23) (堆栈参数 1 3 14) )(输出 (初始序列号 24) (堆栈参数 1 3) )(输出 (初始序列号 25) (堆栈参数 1 3) )(输出 (初始序列号 26) (堆栈参数 1 3) )(输出 (初始序列号 27) (堆栈参数 1 3) )(输出 (初始序列号 28) (堆栈参数 1 3) )(输出 (初始序列号 29) (堆栈参数 1 29)(输出 (初始序列号 30) (堆栈参数 1 29) )(输出 (初始序列号 31) (堆栈参数 1 29) )(输出 (初始序列号 32) (堆栈参数 1 29 32)(输出 (初始序列号 33) (堆栈参数 1 29 32)(输出 (初始序列号 34) (堆栈参数 1 29 32)(输出 (初始序列号 35) (堆栈参数 1 29 32 35)(输出 (初始序列号 37) (堆栈参数 1 29 32)(输出 (初始序列号 38) (堆栈参数 1 29 32) )(输出 (初始序列号 39) (堆栈参数 1 29 32)(输出 (初始序列号 40) (堆栈参数 1 29)(输出 (初始序列号 41) (堆栈参数 1 41) )(输出 (初始序列号 42) (堆栈参数 1 41 42)(输出 (初始序列号 43) (堆栈参数 1 41 42) )(输出 (初始序列号 44) (堆栈参数 1 41 42) )(输出 (初始序列号 45) (堆栈参数 1 41 42 45)(输出 (初始序列号 47) (堆栈参数 1 41 42) )(输出 (初始序列号 48) (堆栈参数 1 41 42) )(输出 (初始序列号 49) (堆栈参数 1 41 42) )(输出 (初始序列号 50) (堆栈参数 1 41)(输出 (初始序列号 51) (堆栈参数 1 51) )(输出 (初始序列号 52) (堆栈参数 1 51)(输出 (初始序列号 53) (堆栈参数 1 51 53)(输出 (初始序列号 54) (堆栈参数 1 51 53)(输出 (初始序列号 55) (堆栈参数 1 51)(输出 (初始序列号 56) (堆栈参数 1)(输出 (初始序列号 65) (堆栈参数 1)(输出 (初始序列号 66) (堆栈参数 1)(输出 (初始序列号 67) (堆栈参数 1)3.下面此图是根据上面的输出事实的堆栈参数的记录下来的层级关系图。如下图4.3所示图4.3 深度搜索解释中堆栈参数表示的层级关系由上可知，表示连接深度搜索与广度搜索的层级关系式通过“堆栈参数”，若入栈则参数增1，若出栈则参数减1。因此，深度搜索与广度搜素结合的关键就是在记录同一层的结点。其次，就可以合并同层次的结点。为了更好的解决数学问题。在转化的同时还得判断它们的解释方法，即合并的同一层的结点他们必须具有一样的方法。若方法不同，则合并也没有意义，该转化也没有意义。4.1.3 深度转化为广度的分类依据实现功能的不同，本文将深度转为广度分为三大类。包括最简单的转化，同层同堆栈层的转化，同层异堆栈的转化三部分。4.2最简单的深度转为广度的过程4.2.1 实现功能同堆栈参数的输出事实只储存第一个；同层方法不同的输出事实，则他们的下一层即使方法相同也不合并。如下图4.4，则只储存其中二三四层中方法相同的结点，且若父层方法不同，则该层的结点也不考虑合并。储存逻辑关系下的合并：图4.4 最简单转化下逻辑关系的合并实际解题时的合并：图4.5最简单转化实际解题下的合并4.2.2 流程图的设计首先，访问可合并层的第一层，匹配第一层中的所有结点；匹配完成后，然后就开始寻找该层中每一个结点的子结点；匹配成功后，将其结点存储到合并层中以记录；匹配完后，就指向下一层，循环以此来匹配。其中，若子结点匹配成功的话，就得储存起来，放到可合并层里。而满足储存条件应该是：一、处于可合并层中的同一层，即匹配的都是同一层的子结点 二、储存的结点的方法都一致。否则就没有储存的价值，因为储存是为了在解题过程中能同时以一步来解多步的运算。最后，而一轮匹配完后，得预处理下，指针指向下一层，然后循环搜索。需要建立一个事实储存的模版，以记录可以合并结点的信息。这个模版就是可合并层。具体流程图如下：图4.6 最简单的深度搜索转化为广度搜索的流程图4.3同层异堆栈的转化过程4.3.1 实现功能相同堆栈参数的输出事实只储存一个；第一层方法不同，他们的下一层若方法相同，则也可合并。如下图4.7，储存二三四层中方法相同的结点，但是若其父层的结点不合并，则该层的子结点方法若相同，也可合并。储存逻辑关系下的合并：图4.7 同层异堆栈转化的范例一实际解题下的合并：图4.8 同层异堆栈实际解题下的合并4.3.2 流程图的设计首先匹配同一层中第一层中的所有结点；匹配完成后，然后依次访问每个结点的所有子结点；匹配成功后，将其存储到合并层中以记录；访问完毕后指向下一层循环搜索。其中，若匹配成功，方法且不同，则储存到同一层中，以合并下一层中可以合并的结点；若方法相同，则储存到可合并层中记录可以合并的结点，然后再此储存到同一层中，以匹配下下层中可合并的结点。所以需要建立两个事实储存的模版，分别是可合并层与同一层。其中，可合并层是记录可以合并的结点；同一层是记录判断下一层中可合并结点的依据。具体流程图如下：图4.9同层异堆栈的转化流程图4.4同层同堆栈的转化过程4.4.1 实现功能相同堆栈参数的输出事实，若其方法相同，也可合并；同层的事实方法不同，若其子层方法相同，则还