第三章 搜索推理技术
第三章搜索推理技术
教学内容
本章在上一章的基础上研究问题求解的方法。包括早期搜索推理技术,如图搜索策略和消解原理;以及高级搜索推理技术,如规则演绎系统、产生式系统等。
教学重点
图搜索策略、消解原理、规则演绎系统、产生式系统。
教学难点
启发式搜索、规则双向演绎系统等。
教学方法
课堂教学为主,辅以恰当的实验。注意结合前面所学知识表示的基础内容,将其与问题求解方法融为一体。及时提问、收集学生学习情况。尽量使用实例和网络课程中的多媒体素材进行讲解。
教学要求
重点掌握一般图搜索策略和消解原理,掌握各种搜索方法和产生式系统原理,了解规则演绎系统的基本原理,对系统组织技术、不确定性推理和非单调推理等高级推理技术作一般性了解
3.1 图搜索策略
教学内容本节介绍图搜索的一般策略,作为各种图搜索技术的基础。
教学重点图搜索的一般过程、OPEN表和CLOSED表的概念。
教学难点 OPEN表和CLOSED表的物理意义。
教学方法课堂教学为主,通过提问彻底弄清图搜索的基本概念。
教学要求重点掌握图搜索一般策略,掌握OPEN表和CLOSE表的构成及作用。
提问图搜索是针对什么知识表示方法的问题求解方法?
1.何谓图搜索
图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。
2.图搜索算法中的几个重要名词术语
(1) OPEN表与CLOSE表
(2) 搜索图与搜索树
3.图搜索(GRAPHSEARCH)的一般过程
(1) 建立一个只含有起始节点S的搜索图G,把S放到一个叫做OPEN的未扩展节点表中。
(2) 建立一个叫做CLOSED的已扩展节点表,其初始为空表。
(3) LOOP:若OPEN表是空表,则失败退出。
(4) 选择OPEN表上的第一个节点,把它从OPEN表移出并放进CLOSED表中。称此节点
为节点n。
(5) 若n为一目标节点,则有解并成功退出,此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。
(6) 扩展节点n,同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n 的后继节点添入图G中。
(7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员,确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员,确定是否需要更改图G中通向它的每个后裔节点的指针方向。
(8) 按某一任意方式或按某个探试值,重排OPEN表。
(9) GO LOOP。
4.图搜索方法分析
图搜索过程的第8步对OPEN表上的节点进行排序,以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的(盲目搜索),也可以启发思想或其它准则为依据(启发式搜索)。搜索过程在找到目标节点时成功结束,这时,通过第7步设置的指针从目标节点向S回溯。当图中不再有未被扩展的非端节点时,搜索过程就以失败告终,在此情况下,问题无解。
提问什么是图搜索? 其中,重排OPEN表意味着什么,重排的原则是什么?
3.2 盲目搜索
教学内容介绍三种盲目搜索方法,即宽度优先搜索、深度优先搜索和等代价搜索。
教学重点盲目搜索的特点,宽度优先搜索。
教学难点等代价搜索中代价的概念。
教学方法以实例强化内容的学习,通过提问引导学生对三种方法的特点进行比较。
教学要求掌握盲目搜索的特点,比较三种盲目搜索方法的优缺点。
3.2.1 宽度优先搜索(breadth-first search)
1.定义
如果搜索是以接近起始节点的程度依次扩展节点的,那么这种搜索就叫做宽度优先搜索。
2.特点
这种搜索是逐层进行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。
3.宽度优先搜索算法
(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点,则求得一个解答)。
(2) OPEN是个空表,则没有解,失败退出;否则继续。
(3) 把第一个节点(节点n)从OPEN表移出,并把它放入CLOSED的扩展节点表中。
(4) 扩展节点n。如果没有后继节点,则转向上述第(2)步。
(5) 把n的所有后继节点放到OPEN表的末端,并提供从这些后继节点回到n的指针。
(6) 如果n的任一后继节点是目标节点,则找到一个解答,成功退出;否则转向(2)。
4.宽度优先搜索方法分析
宽度优先搜索是图搜索一般过程的特殊情况,将图搜索一般过程中的第(8)步具体化为本算法中的第(5)步,这实际是将OPEN表作为“先进先出”的队列进行操作。
宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径;这棵搜索树提供了所有存在的路径(如果没有路径存在,那么对有限图来说,我们就说该法失败退出;对于无限图来说,则永远不会终止)。
5.例
把宽度优先搜索应用于八数码难题时所生成的搜索树,这个问题就是要把初始棋局变为如下目标棋局的问题:
提问宽度优先搜索方法中OPEN表需要按什么方式进行操作? A.先进后出 B.先进先出
3.2.2 深度优先搜索(depth-first search)
1.定义
如果搜索时首先扩展最新产生的(即最深的)节点,这种搜索就叫做深度优先搜索。
2.特点
扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行,只有当搜索到达一个没有后裔的状态时,它才考虑另一条替代的路径。
3.深度界限
为了避免考虑太长的路径,往往给出一个节点扩展的最大深度——深度界限。任何节点如果达到了深度界限,那么都将把它们作为没有后继节点处理。
4.含有深度界限的深度优先搜索算法
请同学们课后自学,并回答课后思考题。
思考有界深度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径吗? 3.2.3 等代价搜索(depth-first search)
1.定义
宽度优先搜索可被推广用来解决寻找从起始状态至目标状态的具有最小代价的路径问题,这种推广了的宽度优先搜索算法叫做等代价搜索算法。
2.等代价搜索中的几个记号
起始节点记为S;
从节点i到它的后继节点j的连接弧线代价记为c(i,j);
从起始节点S到任一节点i的路径代价记为g(i)。
3.等代价搜索算法
请同学们课后认真阅读本算法,指出与宽度优先、深度优先算法有何特别之处。
4.等代价搜索方法分析
如果所有的连接弧线具有相等的代价,那么等代价算法就简化为宽度优先搜索算法。
思考试比较各种盲目搜索搜索方法的效率,找出影响算法效率的原因
3.3 启发式搜索
教学内容启发式搜索策略概述和有序搜索。启发式搜索弥补盲目搜索的不足,提高搜索效率。
教学重点启发式搜索策略、启发信息和有序搜索。
教学难点估价函数的设计、A*算法原理。
教学方法通过实例加深对原理的理解,鼓励同学扩大阅读范围。
教学要求掌握启发式搜索策略和估价函数的设计方法,了解A*算法原理。
3.3.1 启发式搜索策略和估价函数
1.为什么需要启发式搜索
盲目搜索效率低,耗费过多的计算空间与时间,这是组合爆炸的一种表现形式。
2.定义
进行搜索技术一般需要某些有关具体问题领域的特性的信息,把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。
3.启发式搜索策略
有关具体问题领域的信息常常可以用来简化搜索。一种利用启发信息的方法是应用某些准则来重新排列OPEN表中节点的顺序。然后,搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程,需要某些估算节点“希望”的量度,这种量度叫做估价函数(evaluation function)。
4.估价函数
为获得某些节点“希望”的启发信息,提供一个评定侯选扩展节点的方法,以便确定哪个节点最有可能在通向目标的最佳路径上。
f(n)——表示节点n的估价函数值。
建立估价函数的一般方法:试图确定一个处在最佳路径上的节点的概率;提出任意节点与目标集之间的距离量度或差别量度;或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。
3.3.2 有序搜索
1.定义
用估价函数f来排列GRAPHSEARCH第8步中OPEN表上的节点。应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点,这种搜索方法叫做有序搜索(ordered search)或最佳优先搜索(best-first search)。
尼尔逊(Nilsson)曾提出一个有序搜索的基本算法。估价函数f是这样确定的:一个节点的希望程序越大,其f值就越小。被选为扩展的节点,是估价函数最小的节点。
2.实质
选择OPEN表上具有最小f值的节点作为下一个要扩展的节点,即总是选择最有希望的节点作为下一个要扩展的节点。
3.有序状态空间搜索算法
(1) 把起始节点S放到OPEN表中,计算f(S)并把其值与节点S联系起来。
(2) 如果OPEN是个空表,则失败退出,无解。
(3) 从OPEN表中选择一个f值最小的节点i。若有几个节点合格,当其中有一个为目标节点时,则选择此目标节点,否则就选择其中任一个节点作为节点i。
(4) 把节点i从OPEN表中移出,并把它放入CLOSED的扩展节点表中。
(5) 如果i是个目标节点,则成功退出,求得一个解。
(6) 扩展节点i,生成其全部后继节点。对于i的每一个后继节点j:
(a) 计算f(j);
(b) 若j既不在OPEN表,又不在CLOSED表中,则将其加入OPEN表,并按f值排序,提供指向i的指针;
(c) 若j已在OPEN或CLOSED表中,则比较新的f(j)和以前计算过的值,若新值较小,用新值取代旧值,将j的父节点由原来的改为i,若j在CLOSED中将其移回OPEN表。
(7) 转向(2),即GO TO(2)。
4.有序搜索方法分析
宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对于宽度优先搜索,选择f(i)作为节点i的深度。对于等代价搜索,f(i)是从起始节点至节点i这段路径的代价。f的选择直接影响了有序搜索的效率,其选择涉及两个方面的内容:即时间和空间之间的折衷,以及能否保证有一个最优的解或任意解。
5.例
采用了简单的估价函数
f(n)=d(n)+W(n)。
其中:d(n)是搜索树中节点n的深度;W(n)用来计算对应于节点n的数据库中错放的棋子个数。因此,起始节点棋局的f值等于0+4=4。
3.3.3 A*算法
A*算法是一种有序搜索算法,其特点在于对估价函数的定义上。
1.几个记号
令k(ni,nj)表示任意两个节点ni和nj之间最小代价路径的实际代价(对于两节点间没有通路的节点,函数k没有定义)。于是,从节点n到某个具体的目标节点ti,某一条最小代价路径的代价可由k(n,ti)给出。令h*(n)表示整个目标节点集合{ti}上所有k(n,ti)中最小的一个,因此,h*(n)就是从n到目标节点最小代价路径的代价,而且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径(对于任何不能到达目标节点的节点n,函数h*没有定义)。
2.估价函数的定义
定义g*为g*(n)=k(S,n)
定义函数f*,使得在任一节点n上其函数值f*(n)就是从节点S到节点n的一条最佳路径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和,即
f*(n)=g*(n)+h*(n)
希望估价函数f是f*的一个估计,此估计可由下式给出:
f(n)=g(n)+h(n)
其中:g是g*的估计;h是h*的估计。对于g(n)来说,一个明显的选择就是搜索树中从S到n 这段路径的代价,这一代价可以由从n到S寻找指针时,把所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。这个定义包含了g(n)≥g*(n)。h*(n)的估计h(n)依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数W(n)所用的那种信息相似。把h叫做启发函数。
3.A*算法定义
定义1在GRAPHSEARCH过程中,如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的,则称该过程为A算法。
定义2在A算法中,如果对所有的x存在h(x)≤h*(x),则称h(x)为h*(x)的下界,它表示某种偏于保守的估计。
定义3采用h*(x)的下界h(x)为启发函数的A算法,称为A*算法。当h=0时,A*算法就变为有序搜索算法。
4.A*算法
A*算法描述参考教材。
提问由g*(n)和g(n)的定义知g*(n)≤g(n): A.对 B.错
思考试比较宽度优先、有界深度优先及有序搜索的搜索效率,并以实例数据加以说明
3.4 消解原理
教学内容消解原理是针对谓词逻辑知识表示的问题求解方法。本节内容主要包括子句集的求取、消解推理的规则和消解反演问题求解方法。
教学重点子句集的求取、消解推理的规则和消解反演问题求解方法。
教学难点消解反演的思想。
教学方法实例讲解,注重课堂练习。
教学要求重点掌握子句集的求解步骤和消解反演过程,掌握消解推理的规则。
消解原理的基础知识
(1) 谓词公式、某些推理规则以及置换合一等概念。
(2) 子句:由文字的析取组成的公式(一个原子公式和原子公式的否定都叫做文字)。
(3) 消解:当消解可使用时,消解过程被应用于母体子句对,以便产生一个导出子句。
例如,如果存在某个公理E1∨E2和另一公理～E2∨E3,那么E1∨E3在逻辑上成立。这就是消解,而称E1∧E3为E1∨E2和～E2∨E3的消解式(resolvent)。
3.4.1 子句集的求取
1.步骤
(1) 消去蕴涵符号
只应用∨和～符号,以～A∨B替换A=>B。
(2) 减少否定符号的辖域
每个否定符号～最多只用到一个谓词符号上,并反复应用狄?摩根定律。
(3) 对变量标准化
在任一量词辖域内,受该量词约束的变量为一哑元(虚构变量),它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替,而不改变公式的真值。合适公式中变量的标准化意味着对哑元改名以保证每个量词有其自己唯一的哑元。
(4) 消去存在量词
用Skolem函数代替存在的x,就可以消去全部存在量词,并写成:
(y)P[g(y),y]
从一个公式消去一个存在量词的一般规则是以一个Skolem函数代替每个出现的存在量词的量化变量,而这个Skolem函数的变量就是由那些全称量词所约束的全称量词量化变量,这些全称量词的辖域包括要被消去的存在量词的辖域在内。Skolem函数所使用的函数符号必须是新的,即不允许是公式中已经出现过的函数符号。例如:
(y)(x)P(x,y)被〔(y)P(g(y),y)〕代替,其中g(y)为一Skolem函数。
如果要消去的存在量词不在任何一个全称量词的辖域内,则用不含变量的Skolem函数即常量。例如,(x)P(x)化为P(A),其中常量符号A用来表示人们知道的存在实体。A必须是个新的常量符号,它未曾在公式中其它地方使用过。
(5) 化为前束形
把所有全称量词移到公式的左边,并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。
(6) 把母式化为合取范式任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。这种母式叫做合取范式。
(7) 消去全称量词
消去明显出现的全称量词。
(8) 消去连词符号∧
用{A,B}代替(A∧B),以消去明显的符号∧。反复代替的结果,最后得到一个有限集,其中每个公式是文字的析取。任一个只由文字的析取构成的合适公式叫做一个子句。
(9) 更换变量名称
可以更换变量符号的名称,使一个变量符号不出现在一个以上的子句中。
2.例
将下列谓词演算公式化为一个子句集
(x){P(x){(y)[P(y)P(f(x,y))]∧～(y)[Q(x,y)P(y)]}}
3.说明
并不是所有问题的谓词公式化为子句集都需要上述9个步骤。对于某些问题,可能不需要其中的一些步骤。
3.4.2 消解推理规则
1.消解式
令L1为任一原子公式,L2为另一原子公式;L1和L2具有相同的谓词符号,但一般具有不同的变量。已知两子句L1∨α和～L2∨β,如果L1和L2具有最一般合一者σ,那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β)σ。这个新子句叫做消解式。它是由取这两个子句的析取,然后消去互补对而得到的。
2.消解式求法
(1) 假言推理
(2) 合并
(3) 重言式
(4) 空子句(矛盾)
(5) 链式(三段论)
3.4.3 含有变量的消解式
为了对含有变量的子句使用消解规则,必须找到一个置换,作用于父辈子句使其含有互补文字。
3.4.4 消解反演求解过程
1.基本思想
把要解决的问题作为一个要证明的命题,其目标公式被否定并化成子句形,然后添加到命题公式集中去,把消解反演系统应用于联合集,并推导出一个空子句(NIL),产生一个矛盾,这说明目标公式的否定式不成立,即有目标公式成立,定理得证,问题得到解决,与数学中反证法的思想十分相似。
2.消解反演
反演求解的步骤
给出一个公式集S和目标公式L,通过反证或反演来求证目标公式L,其证明步骤如下:
(1) 否定L,得～L;
(2) 把～L添加到S中去;
(3) 把新产生的集合{～L,S}化成子句集;
(4) 应用消解原理,力图推导出一个表示矛盾的空子句NIL。
反演求解的正确性
设公式L在逻辑上遵循公式集S,那么按照定义满足S的每个解释也满足L。决不会有满
足S的解释能够满足～L的,所以不存在能够同时满足S与～L的解释。如果一个公式集不能被任一解释所满足,那么这个公式是不可满足的。因此,如果L在逻辑上遵循S,那么{～L,S}是不可满足的。由于空子句不可被满足,因此,如果L在逻辑上遵循S,那么由并集{～L,S}不断消解最后将产生空子句;反之,可以证明,如果从{～L,S}的子句消解得到空子句,那么L在逻辑上遵循S。
3.反演求解过程
步骤
(1) 把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。
(2) 按照反演树,执行和以前相同的消解,直至在根部得到某个子句止。
(3) 用根部的子句作为一个回答语句。
分析
答案求取涉及到把一棵根部有NIL的反演树变换为在根部带有可用作答案的某个语句的一颗证明树。由于变换关系涉及到把由目标公式的否定产生的每个子句变换为一个重言式,所以被变换的证明树就是一棵消解的证明树,其在根部的语句在逻辑上遵循公理加上重言式,因而也单独地遵循公理。因此被变换的证明树本身就证明了求取办法是正确的。
例:储蓄问题
前提:每个储蓄钱的人都获得利息。
结论:如果没有利息,那么就没有人去储蓄钱
思考应用消解反演求解如下问题:
“如果无论约翰(John)到哪里去,菲多(Fido)也就去那里,那么如果约翰在学校里,菲多在哪里呢?”
3.5 规则演绎系统
教学内容本节介绍规则演绎系统的定义及其三种推理方法:规则正向演绎系统、规则逆向演绎系统和规则双向演绎系统。
教学重点规则演绎系统的定义、正向推理和逆向推理过程。
教学难点双向演绎的匹配问题等。
教学方法课堂教学为主。通过比较揭示正向推理、逆向推理和双向推理的特点。
教学要求掌握规则演绎系统的定义和正向推理、逆向推理的过程,了解规则双向演绎系统。
规则演绎系统的定义
基于规则的问题求解系统运用下述规则来建立:
If→Then
在所有基于规则系统中,每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规则系统中,then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(rule based deduction system)。在这种系统中,通常称每个if部分为前项(antecedent),称每个then部分为后项(consequent)。
3.5.1 规则正向演绎系统
1.定义
正向规则演绎系统是从事实到目标进行操作的,也就是从if到then的方向进行推理的。
2.正向推理过程
(1) 事实表达式的与或形变换把事实表示为非蕴涵形式的与或形,作为系统的总数据库。具体变换步骤与前述化为子句形类似。
注意:我们不想把这些事实化为子句形,而是把它们表示为谓词演算公式,并把这些公式变换为叫做与或形的非蕴涵形式。
例:有事实表达式
(u)(v){Q(v,u)∧～[(R(v)∨P(v))∧S(u,v)]}
把它化为
Q(v,A)∧{[～R(v)∧～P(v)]∨～S(A,v)}
对变量更名标准化,使得同一变量不出现在事实表达式的不同主要合取式中,得:
Q(w,A)∧{[～R(v)∧～P(v)]∨～S(A,v)}
(2) 事实表达式的与或图表示
将上例与或形的事实表达式用与或图来表示,见图3.1。
图3.1 一个事实表达式的与或树表示
一般把事实表达式的与或图表示倒过来画,即把根节点画在最下面,而把其后继节点往上画。上节的与或图表示,就是按通常方式画出的,即目标在上面。
(3) 与或图的F规则变换
这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。把允许用作规则的公式类型限制为下列形式:
L=>W
式中:L是单文字;W为与或形的唯一公式。
将这类规则应用于与或图进行推演。假设有一条规则L=>W,根据此规则及事实表达式F(L),可以推出表达式F(W),产生一个含有F(W)表示的新图。该过程以极其有效的方式达到了用其它方法要进行多次消解才能达到的目的。
(4) 作为终止条件的目标公式
应用F规则的目的在于从某个事实公式和某个规则集出发来证明某个目标公式。在正向推理系统中,这种目标表达式只限于可证明的表达式,尤其是可证明的文字析取形的目标公式表达式。用文字集表示此目标公式,并设该集各元都为析取关系。
当正向演绎系统产生一个含有以目标节点作为终止的解图时,此系统就成功地终止。
3.5.2 规则逆向演绎系统
基于规则的逆向演绎系统,是从目标到事实的操作过程,即从then到if的推理过程。
2.逆向推理过程
(1) 目标表达式的与或形
逆向演绎系统能够处理任意形式的目标表达式。首先,采用与变换事实表达式同样的过程,把目标公式化成与或形。
(2) 与或图的B规则变换
B规则是建立在确定的蕴涵式基础上的,正如正向系统的F规则一样。不过,我们现在把这些B规则限制为
W=>L
形式的表达式。其中,W为任一与或形公式,L为文字,而且蕴涵式中任何变量的量词辖域为整个蕴涵式。
(3) 作为终止条件的事实节点的一致解图
逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。
提问逆向推理与正向推理的区别有哪些?
3.5.3 规则双向演绎系统
1.基于规则的正向演绎系统和逆向演绎系统的特点和局限性
正向演绎系统能够处理任意形式的if表达式,但被限制在then表达式为析取式。逆向演绎系统能够处理任意形式的then表达式,但被限制在if表达式为合取式。双向组合演绎系统具有正向和逆向两系统的优点,克服各自的缺点。
2.双向(正向和逆向)组合演绎系统的构成
正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成,并分别用F规则和B规则来修正。
3.终止条件
组合演绎系统的主要复杂之处在于其终止条件,终止涉及两个图结构之间的适当交接处。当用F规则和B规则对图进行扩展之后,匹配就可以出现在任何文字节点上。
在完成两个图间的所有可能匹配之后,目标图中根节点上的表达式是否已经根据事实图中根节点上的表达式和规则得到证明的问题仍然需要判定。只有当求得这样的一个证明时,证明过程才算成功地终止。若能够断定在给定方法限度内找不到证明时过程则以失败告终
3.6 产生式系统
教学内容本节介绍产生式系统的定义、组成和推理技术。
教学重点产生式系统与规则演绎系统的差别和产生式系统的组成。
教学难点产生式系统的控制策略等。
教学方法课堂教学和实验相结合。重点讲解原理,通过实验进一步领会系统的精髓。充分利用网络课程中的多媒体素材来表示抽象概念。
教学要求掌握产生式系统的组成结构,通过实践掌握产生式系统的设计和工作过程。
在基于规则系统中,每个if可能与某断言(assertion)集中的一个或多个断言匹配,then部分用于规定放入工作内存的新断言。当then部分用于规定动作时,称这种基于规则的系统为反应式系统(reaction system)或产生式系统(production system)。
提问产生式系统与规则演绎系统有什么区别?
3.6.1 产生式系统的组成
1.产生式系统的组成
产生式系统由3个部分组成,即总数据库(或全局数据库)、产生式规则和控制策略,如图3.2所示。
图3.2 产生式系统的主要组成
总数据库有时也被称作上下文,当前数据库或暂时存储器。总数据库是产生式规则的注意中心。产生式规则的左边表示在启用这一规则之前总数据库内必须准备好的条件。执行产生式规则的操作会引起总数据库的变化,这就使其他产生式规则的条件可能被满足。
产生式规则是一个规则库,用于存放与求解问题有关的某个领域知识的规则之集合及其交换规则。规则库知识的完整性、一致性、准确性、灵活性和知识组织的合理性,将对产生式系统的运行效率和工作性能产生重要影响。
控制策略为一推理机构,由一组程序组成,用来控制产生式系统的运行,决定问题求解过程的推理线路,实现对问题的求解。产生式系统的控制策略随搜索方式的不同可分为可撤回策略、回溯策略、图搜索策略等。
2.产生式系统的控制策略
控制策略的作用是说明下一步应该选用什么规则,通常从选择规则到执行操作分3步:匹配、冲突解决和操作。
(1) 匹配
在这一步,把当前数据库与规则的条件部分相匹配。如果两者完全匹配,则把这条规则称为触发规则。当按规则的操作部分去执行时,称这条规则为启用规则。被触发的规则不一定总是启用规则,因为可能同时有几条规则的条件部分被满足,这就要在解决冲突步骤中来解决这个问题。在复杂的情况下,在数据库和规则的条件部分之间可能要进行近似匹配。
(2) 冲突解决
当有一条以上规则的条件部分和当前数据库相匹配时,就需要决定首先使用哪一条规则,这称为冲突解决。
(3) 操作
操作就是执行规则的操作部分,经过操作以后,当前数据库将被修改。然后,其他的规则有可能被使用。
3.6.2 产生式系统的推理
1.正向推理
从一组表示事实的谓词或命题出发,使用一组产生式规则,用以证明该谓词公式或命题是否成立。
一般策略:先提供一批事实（数据）到总数据库中。系统利用这些事实与规则的前提相匹配,触发匹配成功的规则,把其结论作为新的事实添加到总数据库中。继续上述过程,直到没有可匹配的新规则,不再有新的事实加到总数据库中。
2.逆向推理
从表示目标的谓词或命题出发,使用一组产生式规则证明事实谓词或命题成立,即首先提出一批假设目标,然后逐一验证这些假设。
一般策略:首先假设一个可能的目标,然后由产生式系统试图证明此假设目标是否在总数据库中。若在总数据库中,则该假设目标成立;否则,若该假设为证据节点,则询问用户。若不是,则寻找结论部分包含该假设的那些规则,把它们的前提作为新的假设,并力图证明其成立。这样反复进行推理,直到所有目标均获证明或者所有路径都得到测试为止。
3.双向推理
双向推理的推理策略是同时从目标向事实推理和从事实向目标推理,并在推理过程中的某个步骤,实现事实与目标的匹配。
3.6.3 产生式系统举例
说明请同学们课后认真阅读本部分内容,并以此为参考进行实验准备!
思考规则演绎系统和产生式系统有哪几种推理方式?各自的特点为何
3.7 系统组织技术
教学内容系统组织技术属于高级搜索推理技术,能够用于求解比较复杂的系统。本节简要介绍三种系统组织技术:议程表法、黑板法和△极小搜索法。
教学重点系统组织技术如何实现模块之间的合作。
教学难点无要求。
教学方法课堂教学。
教学要求了解系统组织技术的基本原理。
3.7.1 议程表
1.定义
议程表(agenda)是一个系统能够执行的任务表列。与每个任务有关的有两件事,即提出该任务的理由和表示对该任务是有用的证据总权的评价。
2.模块间的合作
从组织大系统的观点看,议程表方法的意义在于它允许几个独立模块进行通讯,这样就使系统能够选出从各方面都有充分证据的任务。虽然各模块共同使用关于为什么要执行各项任务的证据,但一个模块并不需要了解其它模块如何工作,以及它们所包含的知识。这样,议程表方法便具有大系统中模块化的一切优点,而无相互隔离的缺点。
3.7.2 黑板法
1.定义
黑板法(the Blackboard Approach)首先是在HEARSAY-Ⅱ语音理解系统中发展起来的。它的思想比较简单。整个系统由一组称为知识资源(KS)的独立模块和一块黑板组成。这里,知识资源含有系统中专门领域的知识,而黑板则是一切KS可以访问的公用数据结构。
2.模块间的合作
当一个KS被激发时,它检查当时黑板上的内容,并应用其知识产生一个新的假设写到黑板上,直到完成任务为止。当时间表没有发现未解决的活动记录时,系统便停止执行。
3.7.3 Δ-极小搜索法
1.定义
黑板法(the Blackboard Approach)Δ值表示一假设的级别与参加竞争的最佳假设的级别之差,提供了一种选择最有希望假设的技术。
2.工作过程
一次接受一串输入,顺序地处理,使其形成一个关于输入的统一而相容的解释。Δ-极小法是这样来解决这类问题的:在适当的时刻,触发某KS,然后为它生成所有它认为是可能的假设,并赋给某个假设一种级别。由这些级别计算出的Δ值,表示一假设的级别与参加竞争的最佳假设的级别之差。而在该假设最后导致不相容时,再考虑参加竞争的另一假设
3.8 小结
本章所讨论的知识的搜索与推理是人工智能研究另一核心问题。
盲目搜索包括宽度优先搜索、深度优先搜索和等代价搜索等,其中,有界深度优先搜索在某种意义上讲,是具有一定的启发性的。从搜索效率看,一般说来,有界深度优先搜索较好,宽度优先搜索次之,深度优先搜索较差。有界深度优先搜索则可能丢失某些解。
启发式搜索主要讨论有序搜索(或最好优先搜索)和最优搜索A*算法。
在求解问题时,可把问题表示为一个有待证明的问题或定理,然后用消解原理和消解反演过程来证明。在证明时,采用推理规则进行正向搜索,希望能够使问题(定理)最终获得证明。另一种策略是采用反演方法来证明某个定理的否定是不成立的。
有些问题的搜索既可使用正向搜索,又可使用逆向搜索,还可以混合从两个搜索方向进行搜索,即双向搜索。当这两个方向的搜索边域以某种形式会合时,此搜索以成功而告终。
高级求解系统是知识推理和搜索的先进方法,它们比一般搜索方法具有更高的搜索效率,能够用于求解比较复杂的系统。
规则演绎系统采用if-then规则来求解问题。
与规则演绎系统有密切关系的是产生式系统,它由总数据库、产生式规则和控制策略3部
分组成的。产生式系统的推理也分为正向推理、逆向推理和双向推理3种形式。
系统组织技术首先将一个大系统或复杂系统中的知识划分为一组相对独立的模块,然后考虑各子模块间在求解时的合作问题。合作技术包括议程表法、黑板法和△-极小搜索法等。本章还讨论了两种推理技术,即不确定性推理和非单调推理。不确定性推理是研究复杂系统不完全性和不确定性的有力工具。缺省推理和正确性维持系统TMS是非单调推理的两种主要技术
搜索引擎营销案例分析
搜索引擎营销案例分析 文/盛漏托盘https://www.wendangku.net/doc/6e7634275.html, 很高兴在今天的会议上和大家分享一些知识。前面的嘉宾从战略的角度、策略的角度上分享了很多的经验，我感觉到受益匪浅，下面我从技术的角度上和大家分享一下。 中小网站搜索引擎友好设计：现在我们现在中国有1.75亿网民通过搜索引擎进行搜索网站，搜索引擎是一个非常重要的流量来源，我们分享的是SEO，这传入国内以来，有一个正反两面的争论，这个可以用作弊的方法做一个短暂的网站流量，搜索引擎优化是在确保用户体验的同时，以搜索引擎为中心的优化推广行为。搜索引擎优化主要包括三大部分：搜索引擎友好、外围环境优化，营销推广。 首先做SEO之前我们有做自己的网站要有一个准确的定位，你的网站是做什么的？你后面的营销活动、后面各种推广和宣传才能基于这个出发，我们的网站是用来做品牌宣传的，还是做企业的平台做形象展示的，孩或者是给用户服务的，我们以这个为目的做一些相应的推广和营销。 搜索引擎的网站设计：什么样的网站设计用户比较喜欢呢？主要分为几个小点： 一是网页静态化。现在有很多小型网站都是动态的，甚至里面包括很多特色的东西，像这些网址一旦参数超过三成、五成甚至于更多的情况下，可能会影响速度，网页静态化可以提高浏览速度，有利于搜索引擎蜘蛛高效率的爬行，提高并加快搜索引擎收录。我们使用静态化的方法，有限的方法就是常用的ASP、PHP、JSP等生态静态网页，这是网站中间都是实实在在存在的。如果这种方式实现比较困难，可以进行一些伪静态。 二是搜索引擎的不利因素。搜索引擎不利因素对网站危害很大。Flash虽然美观，交互性强，但长期危害着网站在搜索引擎中的表现。图片中的重要内容，Javascript等其他也有一些不利的因素。 三是网页代码规范。网页代码规范有助于Spider高效率爬行。我们可以让CSS与HTML 分离，尽量使用DIV+ CSS，这个最大的优点也就是代码比较简单，代码简单了搜索引擎搜索起来就越方便，搜索引擎喜欢这样的网页。把网页代码进行精简。在这种情况下使用搜索引擎的速度是不一样的。我们很多做页面编辑的人会发现，网页代码越精简越容易。 四是用户习惯与网页焦点。结合我前面说到的与网站的定位，不同的用户群体有不同的浏览习惯和对网页关注的焦点。我们要考虑到用户的这种习惯来进行，有很多网站喜欢在左边放导航，有的网站喜欢在右边放导航，而有些是以另外一些方式进行的。所以要分析目
图的深度优先遍历算法课程设计报告
合肥学院 计算机科学与技术系 课程设计报告 2013～2014学年第二学期 课程数据结构与算法 课程设计名称图的深度优先遍历算法的实现 学生姓名陈琳 学号1204091022 专业班级软件工程 指导教师何立新 2014 年9 月 一：问题分析和任务定义 涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法，并且以深度优先实现遍历的过程得到其遍历序列。
深度优先遍历图的方法是，从图中某顶点v 出发： （1）访问顶点v ； （2）依次从v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v 有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 二：数据结构的选择和概要设计 设计流程如图： 图1 设计流程 利用一维数组创建邻接表，同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图，最后用深度优先的方法来实现遍历。 图 2 原始图 1.从0开始，首先找到0的关联顶点3 2.由3出发，找到1；由1出发，没有关联的顶点。 3.回到3，从3出发，找到2；由2出发，没有关联的顶点。 4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。
所以最后顺序是0,3,1,2,4 三：详细设计和编码 1.创建邻接表和图 void CreateALGraph (ALGraph* G) //建立邻接表函数. { int i,j,k,s; char y; EdgeNode* p; //工作指针. printf("请输入图的顶点数n与边数e(以逗号做分隔符)：\n"); scanf("%d,%d",&(G->n),&(G->e)); scanf("%c",&y); //用y来接收回车符. for(s=0;s
《人工智能及其应用》(蔡自兴)课后习题答案第3章
第三章搜索推理技术 3-1什么是图搜索过程?其中，重排OPEN表意味着什么，重排的原则是什么? 图搜索的一般过程如下： (1) 建立一个搜索图G(初始只含有起始节点S)，把S放到未扩展节点表中（OPEN表）中。 (2) 建立一个已扩展节点表（CLOSED表），其初始为空表。 (3) LOOP：若OPEN表是空表，则失败退出。 (4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节 点n，它是CLOSED表中节点的编号 (5) 若n为一目标节点，则有解并成功退出。此解是追踪图G中沿着指针从n到S这条路径 而得到的(指针将在第7步中设置) (6) 扩展节点n，生成不是n的祖先的那些后继节点的集合M。将M添入图G中。 (7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一 个通向n的指针，并将它们加进OPEN表。 对已经在OPEN或CLOSED表上的每个M成员，确定是否需要更改通到n的指针方向。 对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。 (8) 按某一任意方式或按某个探试值，重排OPEN表。 (9) GO LOOP。 重排OPEN表意味着，在第(6)步中，将优先扩展哪个节点，不同的排序标准对应着不同的搜索策略。 重排的原则当视具体需求而定，不同的原则对应着不同的搜索策略，如果想尽快地找到一个解，则应当将最有可能达到目标节点的那些节点排在OPEN表的前面部分，如果想找到代价最小的解，则应当按代价从小到大的顺序重排OPEN表。 3-2 试举例比较各种搜索方法的效率。
搜索引擎模式案例分析
搜索引擎模式案例分析
搜索引擎模式案例分析 Google搜索引擎 Google的基本情况 谷歌（google）公司的介绍：Google（Google Inc.，NASDAQ：GOOG）是一家美国上市公司（公有股份公司），于1998年9月7日由里?佩奇（25岁）和谢尔盖?布林（24岁）在1998年用募集来的100万美元建立，以设计并管理一个互联网搜索引擎。Google公司的总部称作“Googleplex”，它位于加利福尼亚山景城。Google 目前被公认为是全球规模最大的搜索引擎，它提供了简单易用的免费服务，用户可以在瞬间得到搜索结果。Google属于全文搜索引擎，也是综合性的搜索引擎。不作恶（Don't be evil）是谷歌公司的一项非正式的公司口号，最早是由Gmail服务创始人在一次会议中提出。Google 2008年在全球的市场份额为62.4%，2007年Google在中国的市场份额为17.2%，2008年为20.7%， 2008年Google利润超过了217.9 亿美元。2012年5月，谷歌以125亿美元收购摩托罗拉移动。Google搜索引擎的价值网络以Google为中心，
始只要付极少的费用就可以刊登广告。而且，可以保证用户的每次付费。因为Google收费原则是点击付费，不点击不付费，默认点击在中国和波兰最低0.15元/次，在全球其他区域是最低5美分/次。 2003年，Google推出了比AdWords更为先进、技术也更复杂的AdSense广告模式，期望以会员的形式来吸引更多的网站加盟Google广告发布平台。 AdSense实际上相当于一个广告联盟。AdSense 可以在加盟者网站的内容网页上展示相关性较高的Google广告，并且这些广告不会过分夸张醒目。由于所展示的广告同用户在加盟者的网站上查找的内容相关，只要链接的广告被有效点击，加盟者还可以借此从Google处分得一部分广告收入。谷歌的在线广告业务是谷歌成为世界上最赚钱的公司之一。据2009年财年Google财报显示谷歌在这一年赚了236亿美元，净利润达65亿美元。目前谷歌的绝大多数收入来源于AdWords和AdSense这两项广告业务。
搜索引擎模式案例分析
搜索引擎模式案例分析 搜索引擎 的基本情况 谷歌（）公司的介绍：（ .，：）是一家美国上市公司（公有股份公司），于年月7日由里?佩奇（岁）和谢尔盖?布林（岁）在年用募集来的万美元建立，以设计并管理一个互联网搜索引擎。公司的总部称作“”，它位于加利福尼亚山景城。目前被公认为是全球规模最大的搜索引擎，它提供了简单易用的免费服务，用户可以在瞬间得到搜索结果。属于全文搜索引擎，也是综合性的搜索引擎。不作恶（' ）是谷歌公司的一项非正式的公司口号，最早是由服务创始人在一次会议中提出。年在全球的市场份额为，年在中国的市场份额为，年为， 年利润超过了亿美元。年月，谷歌以亿美元收购摩托罗拉移动。 搜索引擎的价值网络以为中心，涉及提供的搜索服务、服务、管家次广告主等等，它们的关系如下图所示。 商业模式
1.战略目标 ——要为互联网使用者提供网上最好的查询服务，促进全球信息的交流。 2.目标用户 1)全球网民——让人们能够更加快捷更加方便的获取和查找信息。 2)企业市场——助力企业内部信息整合，加强企业内部搜索；帮助企业实行网络营销 3.产品和服务 1)搜索服务、移动服务、分享与沟通服务、软件产品等， 2)搜索服务包括：网页搜索、图片搜索、视频搜索、音乐搜索、地图搜索、购物搜索、 博客搜索、大学搜索、生活搜索、图书搜索、学术搜索等。 4.赢利模式 1)付费搜索服务 的网页搜索服务保证了他在行业的领先地位。它通过向各大门户网站提供搜素技术。通过技术的部分使用权的转让收取费用。 2)在线广告业务 谷歌之前在上海建立全球唯一分析中国广告市场的研究中心，用于进行中国用户举动习惯的分析。
图的深度优先遍历实验报告
一．实验目的 熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。 二．实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 图的邻接表的存储表示： #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三．实验内容 编写LocateVex函数，Create函数，print函数，main函数，输入要构造的图的相关信息，得到其邻接表并输出显示。 四。实验步骤 1）结构体定义,预定义，全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20
广度优先搜索和深度优先搜索
有两种常用的方法可用来搜索图：即深度优先搜索和广度优先搜索。它们最终都会到达所有 连通的顶点。深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。 深度优先搜索： 深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进(到达叶子节点或受到深度限制)时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。 下面图中的数字显示了深度优先搜索顶点被访问的顺序。 "* ■ J 严-* 4 t C '4 --------------------------------- --- _ 为了实现深度优先搜索，首先选择一个起始顶点并需要遵守三个规则： (1) 如果可能，访问一个邻接的未访问顶点，标记它，并把它放入栈中。 (2) 当不能执行规则1时，如果栈不空，就从栈中弹出一个顶点。 (3) 如果不能执行规则1和规则2，就完成了整个搜索过程。 广度优先搜索： 在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。 在深度优先搜索中，算法表现得好像要尽快地远离起始点似的。相反，在广度优先搜索中， 算法好像要尽可能地靠近起始点。它首先访问起始顶点的所有邻接点，然后再访问较远的区 域。它是用队列来实现的。 下面图中的数字显示了广度优先搜索顶点被访问的顺序。 实现广度优先搜索，也要遵守三个规则: ⑴ 访问下一个未来访问的邻接点，这个顶点必须是当前顶点的邻接点，标记它，并把它插入到队列中。（2）如果因为已经没有未访问顶点而不能执行规则1
搜索引擎(百度)案例分析
实验一、搜索引擎（百度）案例分析 一、百度概况 问题1：用200字左右叙述百度概况？ 答：百度（Nasdaq简称：BIDU）是全球最大的中文搜索引擎，2000年1月由李彦宏、徐勇两人创立于北京中关村，致力于向人们提供“简单，可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”，象征着百度对中文信息检索技术的执著追求。这是一个充满朝气、求实坦诚的公司，以搜索改变生活，推动人类的文明与进步，促进中国经济的发展为己任，正朝着更为远大的目标而迈进。 二、商业模式分析 商业模式具体体现了电子商务项目现在如何获利以及在未来长时间内的计划。 （一）战略目标 问题1：百度的战略目标是什么？ 答：百度的目标是成为最优秀的互联网中文信息检索和传递技术提供商、成为中国网络技术企业在全球同行业中的优秀代表。 （二）目标用户 问题2：公司的客户有哪几类？各具有什么特点？ 答：（1）百度的目标用户,可以分为商业用户和普通用户两类。 （2）商业用户需求的是商品信息，所关注的是自己所需要商品的信息。 普通用户就是大量的在网上浏览的网民，需求的是准确信息。 （三）产品与服务 问题3：公司对各类用户分别提供哪些产品或服务？ 答：（1）网页搜索 作为最大的中文搜索引擎公司，百度致力于让网民便捷地获取信息。 （2）垂直搜索 除网页搜索外，百度还提供MP3、图片、视频、地图等多样化的搜索服务。 （3）社区产品 百度贴吧、知道、百科、空间等围绕关键词服务的社区化产品应运而生。 （4）电子商务 百度旗下电子商务交易平台为中国互联网电子商务用户提供专属服务。 （四）赢利模式 问题4：公司收入来源中，哪些对公司的利润水平具有关键性影响？ 答：（1）竞价排名 竞价排名广告是按照点击率收费，竞价较高的网站就会出现在较前位置。 （2）手机移动搜索 手机移动搜索，是指通过移动终端获取所需信息的搜索行为。 （3）固定排名 固定排名模式是指企业将按照在关键词搜索页面的排名依次出现。 （五）核心能力 核心能力是相对稀缺的资源和有特色的服务能力，它能够创造长期的竞争优
百度搜索引擎案例分析
百度搜索引擎案例分析
目录 一、基本情况 (2) （一）公司简介 (2) （二）发展历程 (2) （三）价值网络 (3) 二、商业模式 (4) （一）战略目标 (4) （二）目标用户 (4) （三）产品与服务 (5) （四）盈利模式 (8) 三、技术模式 (14) （一）基础服务技术 (14) （二）用户服务技术 (15) 四、经营模式 (16) （二）口碑式经营 (16) （三）本土化经营 (17) （四）全球化经营 (17) （五）营销、推广模式的长尾化 (17) （六）主题鲜明的促销模式 (18) （七）以渠道代理为主的分销策略 (18) 五、管理模式 (18) （一）组织管理 (18) （二）文化管理 (19) （三）创新管理 (19) （四）人力资源管理 (21) （五）服务管理 (22) （六）代理商管理 (22) （七）国际化管理 (23) 六、资本模式 (23) （一）创始人投资 (23) （二）风险投资 (24) （三）上市融资 (25) （四）并购 (25) 七、竞争者对比 (26) （一）Google公司简介及产品介绍 (27) （二）百度与谷歌的异同点 (27) （三）百度与谷歌的评价 (28) （四）小结 (30) 八、结论和建议 (30) （一）存在问题 (30) （二）改进建议 (31) （三）结束语 (34) 参考文献 (35)
一、基本情况 （一）公司简介 百度搜索引擎（.baidu.，首页如图1所示）属于综合搜索门户，是目前全球最大的中文搜索引擎。由李彦宏和徐勇2000年1月创立于北京中关村，致力于向人们提供“简单，可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案?元夕》词句“众里寻他千百度”，象征着百度对中文信息检索技术的执著追求。百度公司最初的创业团队不足十人。发展至今，在册员工数已超过万人。如今的百度，已成为蜚声海内外、最具影响力的中文网站之一。 图1 百度搜索引擎首页 （二）发展历程 2000年5月，作为搜索技术服务供应商，百度迎来了它的第一个客户——硅谷动力，之后一发不可收拾，百度的业务版图扩展到大江南北，迅速成为国内最主要的搜索技术供应商。 2001年8月，百度发布https://www.wendangku.net/doc/6e7634275.html,搜索引擎Beta版，从后台技术提供者转为面向公众独立提供搜索服务。推出一种全新的业务模式：竞价排名。这是百度的一个很大的转折点。同年10月22日，正式发布百度搜索引擎。
图的深度优先遍历和广度优先遍历
华北水利水电学院数据结构实验报告 20 10 ～20 11 学年第一学期2008级计算机专业 班级：107学号：200810702姓名：王文波 实验四图的应用 一、实验目的： 1．掌握图的存储结构及其构造方法 2．掌握图的两种遍历算法及其执行过程 二、实验内容： 以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。 提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。 三、实验要求： 1．各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。 2．C/ C++完成算法设计和程序设计并上机调试通过。 3．撰写实验报告，提供实验结果和数据。 4．写出算法设计小结和心得。 四、程序源代码： #include
{ int nData; QueueNode* next; }; struct QueueList { QueueNode* front; QueueNode* rear; }; void EnQueue(QueueList* Q,int e) { QueueNode *q=new QueueNode; q->nData=e; q->next=NULL; if(Q==NULL) return; if(Q->rear==NULL) Q->front=Q->rear=q; else { Q->rear->next=q; Q->rear=Q->rear->next; } } void DeQueue(QueueList* Q,int* e) { if (Q==NULL) return; if (Q->front==Q->rear) { *e=Q->front->nData; Q->front=Q->rear=NULL; } else { *e=Q->front->nData; Q->front=Q->front->next; } } //创建图 void CreatAdjList(Graph* G) { int i,j,k; edgenode* p1; edgenode* p2;
谷歌案例分析报告
Google搜索引擎案例分析报告 一、Google的基本情况 谷歌（google）公司的介绍：Google（Google Inc.，NASDAQ：GOOG）是一家美国上市公司（公有股份公司），于1998年9月7日由里?佩奇（25岁）和谢尔盖?布林（24岁）在1998年用募集来的100万美元建立，以设计并管理一个互联网搜索引擎。Google公司的总部称作“Googleplex”，它位于加利福尼亚山景城。Google 目前被公认为是全球规模最大的搜索引擎，它提供了简单易用的免费服务，用户可以在瞬间得到搜索结果。Google属于全文搜索引擎，也是综合性的搜索引擎。不作恶（Don't be evil）是谷歌公司的一项非正式的公司口号，最早是由Gmail服务创始人在一次会议中提出。Google 2008年在全球的市场份额为62.4%，2007年Google在中国的市场份额为17.2%，2008年为20.7%，2008年Google 利润超过了217.9 亿美元。2012年5月，谷歌以125亿美元收购摩托罗拉移动。 Google搜索引擎的价值网络以Google为中心，涉及Google提供的搜索服务、Google AdWords服务、管家次广告主等等，它们的关系如下图所示 二、商业模式 1.战略目标 ——要为互联网使用者提供网上最好的查询服务，促进全球信息的交流。 2.目标用户 全球网民——让人们能够更加快捷更加方便的获取和查找信息。 企业市场——助力企业内部信息整合，加强企业内部搜索；帮助企业实行网络营销3.产品和服务 搜索服务、移动服务、分享与沟通服务、软件产品等， 搜索服务包括：网页搜索、图片搜索、视频搜索、音乐搜索、地图搜索、购物搜索、博客搜索、大学搜索、生活搜索、图书搜索、学术搜索等。
图的深度优先搜索,广度优先搜索,代码
#include
《搜索引擎》教学案例分析
《搜索引擎》教学案例分析 作者：刘肖红资料来源：《南京市第十四中学》点击数：946 更新时间：2010-4-14 一、案例背景： 1、教材分析 搜索引擎为《信息技术基础》必须部分的第二章第二节网上获取信息的策略中的第三部分内容。 这节课的内容以培养学生从网络上获取信息的能力为主，因为信息获取能力是信息素养的一个重要组成部分，培养学生掌握利用网络获取信息的过程和方法，为学生的学习、生活和发展提供服务。同时注意引导学生形成自主学习意识，为必修模块的其他章节和选修模块开展多元化交流打下基础。 2、学时安排 1学时 3、适用年级 高中一年级 二、教学设计 1、教学目标 （一）、知识与技能： （1）了解搜索引擎的简单分类； （2）学会灵活运用贴切的搜索关键词进行信息的搜索； （3）培养学生运用因特网浏览、搜集信息的能力； （二）、过程与方法： （1）能够完成下载各类资源 （2）能选择网上获取信息的最佳途径，高效准确地获取信息。 （三）、情感态度与价值观： （1）培养学生主动探究知识和获取信息的兴趣。
（2）培养学生的团队合作精神。 2、教学重点和难点 教学重点： 运用贴切的搜索关键词进行信息的搜索； 教学难点： 掌握关键词搜索的技巧 3、、教学环境 连接因特网的多媒体网络机房。 4、学情分析 学生通过初中的学习对上网已熟悉，基本操作已掌握，但是对于搜索技巧的使用不太熟悉。针对这种情况，老师结合学生原有的知识基础加以归纳提升，使学生对搜索技巧的使用有进一步的掌握，不断提高自己的网络信息搜索水平。 5、教学策略 本节课的教学采用自主探索、协作学习与教师指导相结合。在课堂教学活动中，通过提出问题激发学生利用网络获取信息的学习欲望，采用自主探究和小组合作的学习方法，既可以让学生主动地探求知识，又可以让学生通过相互之间的协作交流，培养学生的合作精神。通过自主探索、协作学习，利用网上资源进行学习，从而掌握网络信息搜索的几种主要策略和技巧。 三、教与学过程描述： 【教学过程】 （一）、情境引入 师：大家都知道我们中国有一个最传统也是最隆重的一个节日，是什么节？春节。那你知道有关春节由来以及春节方面故事吗？现在网络技术正在飞速发展，我们可以借助网络来查询这么信息。那么，我们如何从因特网上得到这些信息呢？ 生：通过这些可激发学生的兴趣。 （二）、课程实施
第三章 搜索推理技术
第三章搜索推理技术 教学内容 本章在上一章的基础上研究问题求解的方法。包括早期搜索推理技术,如图搜索策略和消解原理;以及高级搜索推理技术,如规则演绎系统、产生式系统等。 教学重点 图搜索策略、消解原理、规则演绎系统、产生式系统。 教学难点 启发式搜索、规则双向演绎系统等。 教学方法 课堂教学为主,辅以恰当的实验。注意结合前面所学知识表示的基础内容,将其与问题求解方法融为一体。及时提问、收集学生学习情况。尽量使用实例和网络课程中的多媒体素材进行讲解。 教学要求 重点掌握一般图搜索策略和消解原理,掌握各种搜索方法和产生式系统原理,了解规则演绎系统的基本原理,对系统组织技术、不确定性推理和非单调推理等高级推理技术作一般性了解 3.1 图搜索策略 教学内容本节介绍图搜索的一般策略,作为各种图搜索技术的基础。 教学重点图搜索的一般过程、OPEN表和CLOSED表的概念。 教学难点 OPEN表和CLOSED表的物理意义。 教学方法课堂教学为主,通过提问彻底弄清图搜索的基本概念。 教学要求重点掌握图搜索一般策略,掌握OPEN表和CLOSE表的构成及作用。 提问图搜索是针对什么知识表示方法的问题求解方法? 1.何谓图搜索 图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。 2.图搜索算法中的几个重要名词术语 (1) OPEN表与CLOSE表 (2) 搜索图与搜索树 3.图搜索(GRAPHSEARCH)的一般过程 (1) 建立一个只含有起始节点S的搜索图G,把S放到一个叫做OPEN的未扩展节点表中。 (2) 建立一个叫做CLOSED的已扩展节点表,其初始为空表。 (3) LOOP:若OPEN表是空表,则失败退出。 (4) 选择OPEN表上的第一个节点,把它从OPEN表移出并放进CLOSED表中。称此节点
谷歌搜索引擎案例分析(新)
《市场营销学》非试卷考试试卷（A）卷 题目：Google公司搜索引擎案例 摘要 两位年轻的大学生依靠自己的力量，逐渐成为实业家，他们只专注于搜索行业，对于其他的一切不管不顾，开创了打破常规。年轻的Google成功了。如果从经济学角度来分析的话，Google这一品牌不仅成功了，而且还是一次惊人的成功----它不仅创造了巨大的经济利益，而且在其公司股票上市之后，又成功地从市场获得了更多的资本。 目录 一、市场分析 （1）企业的目标和任务 （2）市场现状和策略 （3）主要竞争对手及其优劣势 （4）营销外部环境分析 ①经济 ②法律法规 ③成本 ④竞争 ⑤技术 ⑥社会因素 （5）内部环境分析 ①优势 ②劣势 ③预期变化 二、营销策略 (1)营销目标/预期效果
(2)目标市场描述 (3)识别特征 (4)独特的需求、态度和行为 (5)市场定位 (6)营销组合描述 (7)产品/服务 (8)分销 (9)定价 (10)促销 三、行动策划案 (1)制定活动步骤 (2)职能 (3)具体安排 (4)评估流程 (5)成功的依据 (6)收集成功依据的方法
一、市场分析 （1）企业的目标和任务 从Google整体业务分布来看，搜索、广告、应用是google的三大核心目标业务。Google大约将70%的资源投入到了搜索与广告业务中。可以说，搜索是google的技术核心，广告是google的商业核心，而其应用是支撑其面向未来竞争的战略核心。整合全球的信息，建立一个完善的搜索引擎，使其为每个人所用，让所有人受益，为所有信息搜索者提供更准确的服务。 （2）市场现状和策略 Google成立于1997年，几年间迅速发展成为目前规模最大的搜索引擎，并向Yahoo、AOL等其他目录索引和搜索引擎提供后台网页查询服务。2009年，谷歌在美国网络搜索市场的占有率达到惊人的64.7%，而微软和雅虎加起来只有28.2%。目前谷歌每天处理的搜索请求高达2亿次以上，而且这一数字还在不断增长！Google营销策略：Google将巩固并扩大搜索领域的市场份额，互联网广告产业仍然还有增长的空间，Google继续加大投入力度。另一方面，它也在不断地进行各种尝试，拓展新的业务，力求提供多元服务满足客户多样化的需求。Google公司先后推出了本地化和个性化互联网搜索服务、电子邮件服务，并计划不久将推出即时通讯服务。 （3）主要竞争对手及其优劣势 在互联网业务领域，与谷歌展开最为激烈竞争的对手当属微软。过去数年中，微软一直在开展自家搜索和网络广告业务。尽管微软已为此投入了数十亿美元的资金，但目前这些努力尚未对谷歌构成实质性威胁。 优点：微软擅长于战略分析、商业模式，能够分析透每个细分产业的发展和商机。另外微软有很强大的分工和当责精神，能够把一个很大的项目拆分成小块，由少数的明星人物领头，带着大团队分批执行。
图深度优先搜索C++
#include
} cout<<"请输入顶点编号:"<
奇虎360搜索引擎案例分析报告
奇虎360案例分析报告 专业电子商务 班级 31504 姓名杨欣泽
1.案例基本情况汇总 1.1基本情况 360综合搜索，属于元搜索引擎，是搜索引擎的一种，是通过一个统一的用户界面帮助用户在多个搜索引擎中选择和利用合适的（甚至是同时利用若干个）搜索引擎来实现检索操作，是对分布于网络的多种检索工具的全局控制机制。而360搜索+，属于全文搜索引擎，是奇虎360公司开发的基于机器学习技术的第三代搜索引擎，具备“自学习、自进化”能力和发现用户最需要的搜索结果。 2012年8月16日，奇虎360推出综合搜索，360拥有强大的用户群和流量入口资源，这对其他搜索引擎将极具竞争力，该服务初期采用二级域名，整合了百度搜索、谷歌搜索内容，可实现平台间的快速切换。 360搜索主要包括新闻搜索、网页搜索、微博搜索、视频搜索、MP3搜索、图片搜索、地图搜索、问答搜索、购物搜索，通过互联网信息的及时获取和主动呈现，为广大用户提供实用和便利的搜索服务。 360综合搜索实际上它是提供一站式的实用工具综合查询入口，在国外，这类搜索被定义为“元搜索”，同时将信息聚合在一起实现网络工具化、个性化的发展需求；提升网络使用效率，让用户更快地从繁复的搜索系统里解放出来，让上网搜索更轻松有效。国外比较成功的类似网站有InfoSpace、Dogpile、Vivisimo等“元搜索”网站。 360综合搜索是360开放平台的组成部分，充分尊重用户的选择权，360综合搜索页面的导航菜单提供多搜索引擎切换，将多个不同搜索网站界面集成在一个浏览页面中，用户只要输入一次关键字就可以同时完成多次搜索，并实现快速的切换查看。 在分类栏目中，除360视频搜索之外，新闻、MP3、图片、地图及问答均来自百度，点击可自动跳转。 2012年9月21日，360综合搜索正式启动独立域名so，花了七位数美元购买，sou则为辅助域名。 2016年2月，360宣布，将“好搜搜索”重新更名为“360搜索”，域名也由“https://www.wendangku.net/doc/6e7634275.html,”切换为更易输入的“https://www.wendangku.net/doc/6e7634275.html,”，回归360母品牌，意味着360搜索将继续依托360母品牌的基础，在安全、可信赖等方面，继续形成差异化优势。
深度优先搜索算法DFS
深度优先搜索算法DFS = = = 1.首先选定图的类别（有向图、无向图），再选定图的存储结构，根据输入的顶点或者边建立图；并把相应的邻接表或者邻接矩阵输出； 2.根据已有的邻接矩阵或邻接表用递归方法编写深度优先搜索遍历算法，并输出遍历结果； [dfs.rar] - 深度优先搜索算法解决八码难题 [Draw1Doc.rar] - 简单的绘图程序,能画点,直线,多边形等,比较简单 = = = =这里的图的深度优先算法利用了栈来实现。 图的深度遍历原则： 1 如果有可能，访问一个领接的未访问的节点，标记它，并把它放入栈中。 2 当不能执行规则1 时，如果栈不为空，则从栈中弹出一个元素。 3 如果不能执行规则1 和规则2 时，则完成了遍历。 代码中的图使用的是Graph 图－邻接矩阵法来表示，其他的表示法请见：Graph 图－邻接表法 代码中的Stack为辅助结构，用来记载访问过的节点。栈的详细描述可以见：ArrayStack 栈，LinkedStack 栈。 Vertex表示图中的节点，其中包含访问，是否访问，清除访问标志的方法。 Graph.main：提供简单测试。代码可以以指定下标的节点开始作深度遍历。 代码比较简单，除了Graph.dsf(int i)深度优先遍历算法外没有过多注释。 = = = =深度优先搜索DFS 正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续汉下去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。 和宽度优先搜索类似，每当扫描已发现结点u的邻接表从而发现新结点v时，深度优先搜索将置v的先辈域π[v]为u。和宽度优先搜索不同的是，前者的先辈子图形成一棵树，而后者产生的先辈子图可以由几棵树组成，因为搜索可能由多个源顶点开始重复进行。因此深度优先搜索的先辈子图的定义也和宽度优先搜索稍有不同： Gπ=(V,Eπ),Eπ={(π[v],v)∈E:v∈V∧π[v]≠NIL} 深度优先搜索的先辈子图形成一个由数个深度优先树组成的深度优先森林。Eπ中的边称为树枝。 和宽度优先搜索类似，深度优先在搜索过程中也为结点着色以表示结点的状态。每个顶点开始均为白色，搜索中被发现时置为灰色，结束时又被置成黑色(即当其邻接表被完全检索之后)。这一技巧可以保证每一顶点搜索结束时只存在于一棵深度优先树上，因此这些树都是分离的。 除了创建一个深度优先森林外，深度优先搜索同时为每个结点加盖时间戳。每个结点v有两个时间戳：当结点v第一次被发现(并置成灰色)时记录下第一个时间戳d[v]，当结束检查v 的邻接表时(并置v为黑色)记录下第二个时间截f[v]。许多图的算法中都用到时间戳，他们对推算深度优先搜索进行情况是很有帮助的。 下列过程DFS记录了何时在变量d[u]中发现结点u以及何时在变量f[u]中完成对结点u的检
有向图的深度优先遍历
#include "stdio.h" #include "stdlib.h" int visited[20]; #define MAX_VERTER_NUM 20 typedef char VertexType; typedef struct ArcNode{ int adjver; struct ArcNode *nextarc; //InfoType *info; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTER_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; void GraphCreated(ALGraph *G) { int i,j,n;
ArcNode *p,*q; printf("请输入顶点个数和弧数：\n"); scanf("%d%d",&G->vexnum,&G->arcnum); for(i=0;i
- 人工智能-第三搜索推理技术
- 第3章 确定性推理技术
- (完整word版)人工智能习题答案搜索推理技术.docx
- 第三章 搜索推理技术解读
- (完整word版)人工智能习题答案搜索推理技术
- 第3章 搜索推理技术(自学)
- 搜索推理技术3与或树搜索
- 人工智能搜索推理技术
- 人工智能之(搜索推理技术1-图盲目搜索)
- 人工智能推理技术
- 人工智能(AI)及其应用-搜索推理技术
- 人工智能 搜索推理技术消解原理
- 人工智能习题&答案-第3章-搜索推理技术
- 第三章 搜索推理技术
- 人工智能推理技术综述
- 第3章 搜索推理技术
- 第三章 推理技术
- 智能控制第三章搜索推理技术优秀课件
- 经典人工智能技术—推理与搜索.pptx
- 经典人工智能技术—推理与搜索