1、第2章 人工智能基础机器人足球比赛不仅仅起源于人工智能的发展、依赖于人工智能的理论和技术，而且以促进人工智能的发展为主要目的之一。目录 2.1 知识与推理 2.2 搜索2.1 知识知识与推理与推理主要内容：1.什么是知识？2.什么是知识表示？3.如何表示知识？常用知识表示和推理数据、信息、知识 数据是信息的载体和表示 信息是数据在特定场合下的含义，或数据的语义，是对客观事物的一般性描述 知识是对信息进行加工所形成的对客观世界规律性的认识。是经过精简、塑造、解释、选择和转换的信息 是由特定领域的描述、关系和过程组成。知识的类型 按知识的作用范围分：1常识性知识2领域性知识 按知识的作用分：1 事
2、实性知识2 过程性知识3 控制性知识4 元知识 人们描述客观世界的数据、信息、知识等具有如下的金字塔型层次结构。噪声数据信息知识元知识什么是知识表示？知识表示是对知识的一种描述，或者说是将知识编码为一组计算机可以接受的数据结构的过程。衡量标准：可实现性、表示能力、可利用性、可组织性、可维护性、自然性常用的知识表示法与推理 谓词逻辑表示法 产生式表示法 语义网络表示法 面向对象表示法 框架表示法 脚本表示谓词逻辑(predicate logic)一、逻辑基础二、谓词逻辑表示法三、谓词逻辑表示的特性一、逻辑基础 命题:一个陈述句称为断言.凡是有真假意义的断言称为命题.命题的意义通常称为真值，它有真
3、假两种情况.例子:南京是江苏的省会城市。（T）南京是江西的省会城市。（F）谓词 谓词可分为：谓词名与个体两个部分。个体表示某个独立存在的事物或者某个抽象的概念，谓词名用于刻画个体的性质、状态或个体之间的关系。一般形式:P(x1,x2,xn).其中，P为谓词名，x1,x2,xn为个体，个体可以是变量、变元、函数，个体取值范围称为个体域.例子:Man(x)函数 定义（函数）设D是个体域,f:Dn D是一个映射，则称f是D上的一个n元函数，记作：F(x1,x2,xn)例子:father(x,y)连接词和量词连接词1.“非”“否定”2.“合取”3.“析取”4.“条件”“蕴含”5.“双条件”量词1.:全
4、称量词x:所有x,每个x;2.:存在量词x:存在一个x;二、谓词逻辑表示法 对事物的状态、属性、概念等事实性知识，通常可以用否定、析取或合取符号连接起来的谓词公式表示；对事物间的关系通常用蕴含式表示三、谓词逻辑表示的特性 自然 精确 严密 容易实现 知识表示能力差 存在组合爆炸 系统效率低小结问题 你认为什么是逻辑？逻辑解决什么问题？如何用逻辑表示守门员相关状态知识？产生式表示法内容一、产生式表示的基本方法及特性二、产生式系统的基本结构三、产生式系统的基本过程四、产生式系统的类型五、产生式系统的特点一、产生式表示的基本方法及特性事实可看作是一个断言。常用三元组表示 确定性知识可用一个多元组:（
5、对象，属性，值）或（关系，对象1，对象2）来表示。如（snow,color,white）：”雪的颜色是白的1、事实2、规则、规则 规则描述事物间的因果关系。规则的产生式表示形式称为产生式规则，简称规则，或产生式 形式:条件 行动 前提 结论“ifthen”例如：所有人会死甲是人甲会死 规则与蕴涵式的主要区别：规则表示的知识或匹配可以是不确定的，而蕴涵式只能表示确定性知识，并且匹配要求是确定的。:=:=|:=|二、产生式系统的基本结构 产生式系统产生式系统：把一组产生式放在一起，并让它们相互配合，协同作用以求解问题的系统称为产生式系统。基本结构包括三个部分：综综合数据库合数据库(global d
6、atabase)规规则库则库(set of rules)控控制系统制系统(control system)1、综合数据库 也称事实库事实库，存放已知的事实和推导出的中间事实;说明 具体实现时，用DBMS和文件等都可以。数据是广义的，可以是常量、变量、谓词、图像等。2、规则库存放所有规则的集合这些规则描述了问题领域中的一般性知识设计时注意：1.有效的表达领域内的过程性知识2.对知识进行合理的组织与管理3、控制机构 控制机构完成的工作有：匹配综合数据库中已知事实与规则条件部分；多于一条规则匹配成功时，选择哪条规则执行(点燃)；如何将匹配规则的结论部分放入综合数据库（是直接添加到数据库中，还是替换其中
7、的某些东西）；决定系统何时终止；综合数据库产生式规则控制机制三、产生式系统的基本过程产生式系统的问题求解步骤产生式系统的问题求解步骤：1.将已知的事实放入综合数据库；2.检查规则库中是否存在未使用过的规则，若有执行3，否则转53.检查规则库中未使用的规则中是否有其前提可与综合数据库中已知事实相匹配的规则，若有则从中选择一个，否则转6.4.执行当前规则，并对规则作上标记，规则的结论放入综合数据库；如该规则的结论是一些操作，则执行这些操作产生式系统的基本过程（续）5.检查综合数据库中是否包含了该问题的解，若包含，问题求解结束，否则转26.当规则库中还有未使用的规则，但不能和已知事实相匹配时，要求用
8、户进一步提供关于该问题的事实，若能提供，转2，否则终止问题求解7.若知识库中不再有未使用的规则，终止问题求解四、产生式系统的类型 按推理方向分：正向、逆向、双向 按规则库的性质及结构分类：可交换、可分解、可恢复五、产生式系统的特点 自然性：模块性：有效性 清晰性：规则分为左半部分和右半部分；左半部分是条件，右半部分是结论；效率不高 不能表达具有结构性的知识 prolog例子 根据声音，判断动物。框架(frame)表示法一、框架理论二、框架和实例框架三、框架系统四、框架系统的推理过程一、框架理论框架理论：人们对现实世界中各种事物的认识都是以一种类似于框架的结构存储在记忆中的。当遇到一个新事物时，
9、就从记忆中找到一个合适的框架，并根据其细节加以修改、补充，从而形成对这个新事物的认识 人们不可能把过去的经验全部存放在脑子里，而只是以一种通用的数据形式把它们存储起来，当新情况发生时，只要把新的数据加入到该通用的数据结构中便可以形成一个具体的实体，这样通用的数据结构称为框架。框架是知识的基本单位，把一组有关的框架连接起来便可形成一个框架系统。对于一个框架，当人们把观察或认识到的具体细节填入后，就得到了该框架的一个具体实例，框架的这种具体实例被称为实例框架。二、框架和实例框架 在一个框架系统中，一般都含有多个框架，一个框架通常由若干个槽组成，每一个槽又可以根据实际情况拥有若干个侧面，每个侧面也可
10、以拥有若干个侧面值。槽名a:侧面名a1 值a1v1,值a1v2,侧面名an 值anv1,值anv2槽名x:侧面名x1 值x1v1,约束：约束条件1 约束条件n 框架名：书名：单位（字符串）作者：表明对作者框架的调用 出版社：版权：单位（年）条件：年2000 框架名：姓名：单位（姓，名）电邮：单位（字符串）对于一个框架，当把具体信息添入其槽或侧面后，就得到一个该框架的实例框架。如：书名：Extreme Programing Explained 作者：出版社：版权：2002三、框架系统/网络1.框架系统的基本结构2.框架系统的表示3.框架系统的预定义槽名框架系统的基本结构 框架系统的基本结构是通过
11、诸如框架之间的横向或纵向联系来实现。由于一个框架的槽值或侧面值可以是另一框架的名字，这在框架之间建立起了一种联系，这种联系称为框架之间的横向联系。如前面关于“书”的例子。当用框架来表示那种具有演绎关系的知识结构时，下层框架与上层框架之间具有一种继承关系，这种具有继承关系的框架之间的联系称为纵向联系。当下层框架对上层框架具有继承关系时，可以在下层框架中增加一个“继承”槽，其槽值为上层框架的框架名。如描述“学生”信息，可以先定义“人”的基本信息：框架名 姓名：单位（姓，名）性别：范围（男，女）身份证号：框架名 继承：入学时间：单位（年，月）学制：单位（年）学号：单位（年，班级代号，班内学号）框架系
12、统的表示 由以上分析可知，框架系统是由框架之间的纵向、横向联系所形成的一种复杂结构。框架系统的预定义槽名 在框架系统中，框架之间的联系实际上是通过在槽中填入相应的框架名来实现的，至于框架之间究竟为何种关系，是由槽名来指定的。在框架系统中通常定义了一些标准槽名，称这些槽名为系统预定义槽名。常用的预定义槽名有以下几种：1、ISA槽：用来指出一个具体事物与其抽象概念间的类属关系。一般的说，“ISA”槽所指出的联系都具有继承性，即下层框架可以继承上层框架所描述的属性或值。框架名 姓名：单位（姓，名）性别：范围（男，女）框架名 Is-a：入学时间：单位（年，月）学制：单位（年）2、AKO槽：用来指出事物
13、间的抽象概念上的类属关系。用作为下层框架的槽名时，其槽值为上层框架的框架名。它表示该下层框架表示的事物比其上层框架更具体。如“大中专学生”框架名 AKO：特点：有专业3、subclass槽：用来指出子类和类之间的类属关系。当它用作某下层框架的槽时，表示该下层框架是其上层框架的一个子类。如“大学生”框架名 subclass：高考成绩：4、instance槽:用来建立的AKO逆关系。当用它作为上层框架的槽时，可用来指出它的下一层框架有哪些。如“大中专学生”框架名 AKO：instance：，特点：有专业5、part-of槽：用于指出“部分”与“全体”关系。前4种槽描述的都是上、下层框架之间的类属关
14、系，它们之间具有共同特征，且具有继承性。而part-of槽仅是指出下层框架为上层框架的子结构，它们之间一般不具有共同特征，也不具有继承性。6、Infer槽用于指出两个框架所描述事物间的逻辑物理关系；7、possible-reason槽用来把某个结论与可能的原因联系起来；如框架名：已知条件1：地面湿 已知条件2：没人洒水 infer：可信度：0.8框架名：可能结论:天下雨 possible-reason:8、similar槽用于指出两个框架所描述事物之间的相似关系。9、其他四、框架系统的推理过程 系统主要由两个部分组成：由框架网络构成的知识库；由一组程序构成的框架推理机 在框架系统中，推理主要是
15、通过对框架的匹配与填槽来实现的。当需要求解问题时，首先要把该问题用框架表示出来。然后再把它与知识库中已有的框架进行匹配，找出一个或多个侯选框架，并在这些框架引导下进一步获取附加信息，填充尽量多的槽值，建立一个描述当前情况的实例框架。框架的匹配 匹配度方法：首先求出两个框架匹配的匹配度，然后再用该匹配度与预先设定的框架匹配阈值进行比较，若能满足阈值条件就认为两个框架可匹配，否则为不可匹配。匹配度是指当前框架所描述的属性与已知框架可匹配的程度。充分与必要条件法：“充分条件”“必要条件”槽，如果必要条件不满足，就认为这两个框架不可匹配。规定属性值变化范围方法：只要一个具体事物的属性值落在规定的范围内
16、，就认为这个属性是匹配的。功能属性描述方法：在外形属性描述的基础上，给出功能属性描述框架推理（深度优先、自顶向下）1.把用户要求解的问题形成一个初始问题框架，并将已知的知识添入到相应槽中有些槽是空的。2.把框架网络的根框架作为当前框架，即以根框架作为搜索推理的起点。3.把问题框架与当前框架进行匹配，如果匹配成功，转4步进行添槽，否则转5步搜索下一个框架。4.添槽后，检查问题框架是否已包含了问题的解，若已包含，转7步，否则转5步5把当前框架的Instance槽的槽值找一个尚未进行匹配的子框架。若有这样的子框架，则把该子框架作为当前框架，转3进行匹配及添槽操作；若没有这样的子框架，则转6进行回溯6
17、由把当前框架的AKO槽的槽值找它的父框架。如该父框架不是根框架，则把该父框架作为当前框架并转5；否则，需要另选一个根框架重复进行上述推理过程，如没有合适的根框架可选，问题无解。7如问题的解具有不确定性，则根据采用的不确定性知识表示方法计算解的不确定性度量，成功地结束推理过程。return语义网络表示法一、基本概念二、事物和概念的表示三、情况和动作的表示四、逻辑关系的表示五、语义网络的推理过程六、语义网络表示法的特征一、基本概念1.语义网络2.基本的语义关系语义网络 语义网络是一种用实体及其语义关系来表示知识的有向图。其中，结点代表实体，表示各种事物、概念、情况、属性等；弧代表语义关系，表示它所
18、连结的两个实体之间的语义联系。一个语义基元可用如下三元组：（结点1，弧，结点2）来表示。如（a,R,b）可表示：abR基本的语义关系 从功能上将，语义网络可以描述任何事物间的任意复杂关系。但这种描述是通过把许多基本的语义关系关联到一起来实现的。下面给出一些常用的基本语义关系：1分类关系：是指具有共同属性的不同事物间的类属关系、成员关系或实例关系。它体现的是“具体与抽象”、“个体与集体”的概念。它的一个最主要的特征是属性的继承性，处在具体层的结点可以继承所有抽象层结点的所有属性。常用的类属关系有：A-Kind-of:“是一种”A-Member-of:“是一员”Is-a：“是一个”2聚集关系：如果
19、下层概念是其上层概念的一个或者一个部分，是指具有组织或结构特征的“部分与整体”之间的关系。它和类属关系的最主要区别是包含关系一般不具备继承性。常用的包含关系有：Part-of：“是一部分”Composed-of3属性关系：是指事物和其属性的之间的关系。常用的属性关系有：Have：“有”Can:“能”“会”4时间关系：是指不同事件在其发生时间方面的先后次序关系。常用的时间关系有：Before：“在前”After:“在后”5位置关系：是指不同事物在位置之间的关系。常用的位置关系有：Located-on：“在上面”Located-under：“在下面”6相近关系：是指不同事物在形状、内容等方面相似或
20、接近。常用的相近关系有：Similar-to：“相似”Near-to：“接近”7推论关系：是指从一个概念推出另一个概念的语义关系。例如：天下雨地面湿推出二、事物和概念的表示1.用语义网络表示一元关系2.用语义网络表示二元关系3.用语义网络表示多元关系所谓一元关系是指可以用一元谓词P(x)来表示的关系。其中，个体x为实体，谓词P说明实体的性质、属性等。用语义网络表示一元关系 通常表示一元关系的方法是：用结点1表示实体，用结点2表示实体的性质或属性等，用弧表示结点1和结点2之间的语义关系。如“动物能运动”：动物运动能用语义网络表示二元关系 通常表示二元关系的方法是：用结点1表示实体，用结点2表示实
21、体，用弧表示结点1和结点2之间的关系。如“鸟是一种动物”：鸟动物是一种用语义网络表示多元关系 当用语义网络表示多元关系时，一般采用增加关系结点的办法。如“北京位于沈阳和郑州之间”：这是一种“在和之间”的三元关系。沈阳郑州位置关系北京边界1居中边界2三、情况和动作的表示1.情况的表示2.事件和动作的表示情况的表示 用语义网络表示情况时，需要设立一个情况结点。该结点有一组向外引出的弧，用于指出不同的情况。如“小张很认真地学习计算机网络课程”，若不加情况结点：小张计算机网络学习课程是一门小张学习情况学习者计算机网络学习对象课程是一门很认真学习态度事件和动作的表示 用语义网络表示事件或动作时，也需要建
22、立一个事件结点。事件结点也有一些向外引出的弧，用于指出动作的主体和客体。如前的“小张在学习日语”小张学习日语主体客体四、逻辑关系的表示1.合取与析取的表示2.量词的表示合取与析取的表示 例：学习班的学员有教师、有学生、有男、有女。要用语义网络来表示这个问题，首先要分析学员的不同情况：男教师、女教师；男学生、女学生则可以表示为：学员ABCD部分部分与状态或或教师学生男女量词的表示对存在量词，可以直接用“是一种”、“是一个”等这样的语义关系来表示。例题：每个学生都有一本教材 这个问题的语义网络如下图所示。GS是一个概念结点，它表示具有全称量化的一般事件。g 是一个具体例子，如本例所提到的事实。s
23、是一个全称变量，表示任意一个学生。h 是一个存在变量，表示某一种所有权。b 是一个存在变量，表示某一本教材。这样，s、h、b之间就构成了一个子空间，它表示对每个学生s都存在一种所有权h和一本教材b。弧“F”表示它（g）所代表的子空间及其具体形式。GSgIs-ashb所有者所有对象F学生Is-a教材Is-a所有权A-Kind-ofreturn五、语义网络的推理过程语义网络问题求解系统主要由2部分所组成：由语义网络构成的知识库用于问题求解的推理机构语义网络的推理过程主要有：1、继承2、匹配3、网络演绎继承所谓继承是指把对事物的描述从抽象结点传递到具体结点。继承的一般过程为：1.建立一个结点表，用来
24、存放待求解结点和所有以Is-a、A-Kind-of等继承弧与此结点相连的那些结点。初始情况下，表中只有待求解结点。2.检查表中的第一个结点是否有继承弧。若有，就把该弧所指的所有结点放入结点表的末尾，记录这些结点的所有属性，并从结点表中删除第一个结点。若没有，直接从结点表中删除第一个结点3.重复2，直到结点表为空。此时，记录下的所有属性都是待求解结点记录下来的属性。例子 结点表1(Man)结点2（含属性）(Student;Walk)结点表3 (Smith;Walk,Learn)ManwalkCanStudentIs-aLearnCanSmithIs-a23Age匹配所谓匹配就是在知识库的语义网络
25、中寻找 与待求问题相符的语义网络模式。其主要的过程：1.根据待求问题的要求构造一个网络片段，该网络片段中有些结点或弧的标识是空的，称为问询处，它反映的是待求解的问题。2.根据该语义片段到知识库中去寻找所需要的信息。3.当待求解问题的网络片段与知识库中的某语义网络片段相匹配时，则与询问处相匹配的事实就是该问题的解。语义网络演绎 带有逻辑推理语义关系的语义网络称为推理网络。Infer Possible-Reason弧六、语义网络表示法的特征 结构性 自然性 自索引性：语义网络把各结点之间的联系以明确、简洁的方式表示出来，通过与某一结点的弧可以很容易的找出该结点有关的信息，而不必查找整个知识库。非严
26、格性 复杂性面向对象表示法1.面向对象的知识表示：对象、消息、方法、封装；类、类层次、继承性2.面向对象表示法的特点：封装性、模块性、继承性、易维护性:=(ID,DS,MS,MI)ID:对象标识符DS：对象数据结构MS：对象方法集合，MI：对象的消息接口ROBOCUP的对象信息脚本（script）表示 用一组槽来表示某些事件的发生序列，就像剧本中的序列一样 组成：开场条件、角色、道具、场景、结果 故事理解：理解故事情节2.2 搜索 搜索是人工智能的一个基本问题，是推理不可分割的一部分。一个问题的求解过程就是搜索过程，所以搜索实际上是求解问题的一种方法。搜索概述 搜索的基本概念 人类的思维过程，
27、可以看作是一个搜索的过程。我们曾经遇到过很多有趣的智力游戏问题，比如传教士和野人问题：有三传教士和三个野人过河，河岸上只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会有危险。你能不能找出一种安全的渡河方法呢？如果要作这个游戏，在每一次渡河之后，都会有几种渡河方案供你选择，究竟哪种方案才有利于在满足题目所规定的约束条件下顺利过河呢？人工智能要解决的问题大多数是结构不良或者非结构的问题，对这样的问题一般不存在成熟的求解算法，而只能利用已有的知识一步步地摸索着前进。在这个过程中，存在着如何寻找一条推理路线，使得付出的代价尽可能地少，而问题又能够得到解决
28、。我们称寻找这样路线的过程为搜索。搜索的分类 根据在问题求解过程中是否运用启发性知识，搜索可分为盲目搜索和启发式搜索。盲目搜索是按预定的控制策略进行，在搜索的过程中所获得的信息不用来改进控制策略的一种搜索。由于搜索总是按预先规定的路线进行，没有考虑问题本身的特性，这种方法缺乏对问题求解的针对性，需要进行全方位的搜索，而没有选择最优的搜索途径，因此，这种搜索具有盲目性，效率较低。启发式搜索是在搜索中加入了与问题有关的启发式信息，用来指导搜索朝着最有希望的方向前进，加速问题的求解过程，并找到最优解。状态空间法 状态空间法的基本思想：用“状态”和“操作”来表示或求解问题。问题是用“状态”和“操作”来
29、表示，问题求解过程是用“状态空间”来表示的。状态是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：Sk=Sk0,Sk1,。在这种状态中，当对每一个分量都给予确定的值时，就得到了一个具体的状态。操作，也称算符，它是把问题一个状态变换为另一种状态的手段。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。状态空间用来描述一个问题的全部状态以及这些状态之间的相互关系。状态空间法基本过程：首先为问题选择适当的“状态”及“操作”的形式化描述方法；然后从某个初始状态出发，每次使用一个“操作”，递增的建立起操作序列，直到达到目标状态为止；此时，由初始状态到目标状态所使用的算符序列就是该问
30、题的一个解。八数码难题 在3*3的方格棋盘上，分别放置了标有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0,目标状态为Sg。可以使用的操作有：空格左移、上移、下移、右移状态 任一时刻,综合数据库的情况;237 51486A，B，C，D（c,a,b,0,0）状态空间 状态空间 所有可能的状态的全体.237 51486586 12743124 65783状态转移 初始状态 目标状态 状态转移 规则237 51486237 45186搜索(search)路径 状态序列 搜索 寻找从初始状态到目标状态的路径;S0Sg搜索问题状态空间237 5148612384765搜索不是检索237 514
31、8612384765搜索与检索的区别 状态是否动态生成;检索:静态;在数据库中检索某人的纪录;搜索:动态生成;下棋难点237 5148612384765状态空间搜索步骤 状态空间搜索实际上就是对有向图的搜索。先把问题的初始状态当作当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了该问题的解；若没有出现，则按照某种搜索策略从已生成的子节点中选择一个作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或没有可供扩展的节点为止。状态空间搜索算法（准备）若要讨论状态空间搜索的一般算法，需要：Open表和Closed表这样两个数据结构
32、。其中，Open表用于存放还没有扩展的节点，因此，Open表称为未扩展的节点表。Closed表用于存放已经扩展或将要扩展的节点，因此，Closed称为已扩展的节点表。用S0表示问题的初始状态，G表示搜索过程所得到的搜索图，M表示当前扩展节点新生成的且不为自己先辈的子节点集。算法(simple version)1建立一个只有起始节点S0组成的图G,把S0放到OPEN表中；2建立一个CLOSED表，置为空；3While(!NULL(OPEN)a)从OPEN表中取出（并删除）第一个节点n放入 CLOSED表。b)如果n是目标节点，成功结束；c)扩展节点n，把n的后继加入G中；d)把n的后继加入OPE
33、N表中,并建立它们到n的指针；e)对OPEN表中的节点排序；4返回FAIL；例子SOPENCLOSES 123 S 1,2,3 S 2,1,3 S 451,3 S,2 1,3,4,5 S,2 3,1,4,5 S,2 1,4,5 S,2,3 61,4,5,6 S,2,3 状态空间图的一般搜索算法：1、把初始节点S0放入Open表中，并建立目前仅包含S0的图G；2、检查是否为空，若为空，则问题无解，失败退出；3、把Open表的第一个节点取出放入Closed表中，并记该节点为节点n；4、考察节点n是否为目标节点，若是则得到问题的解，成功退出；5、扩展节点n,生成一组子节点。把这组节点中不为节点n先辈
34、的子节点记入集合M,并把这些节点作为节点n的子节点加入G中。6、针对中子节点的不同情况，分别处理如下（1-3）：1.对那些没有在G中出现过的M成员设置一个指向其父节点的指针，并把它放入Open表中。2.对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改指向其父节点的指针。3.对原来已在G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。7、按某种策略对Open表中节点排序。8、转第2步。示例如下：2S13451,2,3 S 3,1,2 S OPENCLOSES 4,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,
35、3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1414,10,11,9,7,5,2 S,3,4,6,8,1,12,13 2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 14OPEN表中的节点修改指针2S131,2,3 S 3,1,2 S OPEN
36、CLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S
37、,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSED表中的节点修改指针2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSED表中节点(8)的后裔(10)修改指针算法说明 各种搜索策略的主要区别在于对Open表中节点
38、排序的不同；一旦被考察的节点是目标节点时,算法成功结束;算法结束后，将生成一个图G，称为搜索图搜索图。同时由于每个节点都有一个指针指向父节点，这些指针指向的节点构成G的一个支撑树，称为搜索树搜索树。修改指针:找最优解；检查新产生的节点以前是否产生过，计算量较大;2S134567891011121314搜索图2S1324567891011121314搜索树状态空间盲目搜索 无须重新安排OPEN表的搜索叫做无信息搜索或盲目搜索，它包括宽度优先搜索、深度优先搜索和等代价搜索等。盲目搜索只适用于求解比较简单的问题。一、宽度优先搜索 宽度优先搜索(breadth-first search)又称为广度优先
39、搜索，是一种盲目搜索策略。其基本思想是，从初始节点开始，向下逐层对节点进行依次扩展，并考察它是否为目标节点，在对下层节点进行扩展（或搜索）之前，必须完成对当前层的所有节点的扩展。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。二、深度优先搜索 另一种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。在深度优先搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。我们定义节点的深度如下：(1)起始节点(即根节点)的深度为0。(2)任何其他节点的深度等于其父辈节点的深度加1。三、等代价搜索 在等代价搜索算
40、法中，把从节点i到其后继节点j的连接弧线代价记为c(i,j)，把从起始节点s到任一节点i的路径代价记为g(i)。在搜索树上，假设g(i)也是从起始节点s到节点i的最少代价路径上的代价，因为它是惟一的路径。等代价搜索方法以g(i)的递增顺序扩展其节点，状态空间启发式搜索 前面我们讨论的各种搜索策略的一个共同的特点就是它们的搜索路线是事先决定好的，没有利用被求解问题的任何特性信息，在决定要扩展的节点时，没有考虑该节点到底是否可能出现在解的路径上，也没有考虑它是否有利于问题的求解以及所求的解是否为最优解，这样的搜索策略具有很大的盲目性。如果能够找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节
41、点加以扩展，那么，搜索效率将会大为提高。在许多情况下，能够通过检测来确定合理的顺序。本节所介绍的搜索方法就是优先考虑这类检测，称这类搜索为启发式搜索(heuristically search)或有信息搜索(informed search)。一、启发式搜索策略和估价函数 我们用f(n)表示节点n的估价函数，则f(n)可以为任意函数。如f(n)可以表示节点n处于最佳路径的概率，也可以表示节点n到目标节点的距离。一般来说，估价一个节点价值必须考虑两方面的因素：已经付出的代价和将要付出的代价。二、最佳优先搜索 最佳优先搜索(best-first search)又称为有序搜索(ordered searc
42、h)，它总是选择最有希望的节点作为下一个要扩展的节点，而这种最有希望的节点是按估价函数f(n)的值来挑选的，一般估价函数的值越小，它的希望程度就越大。根据习惯，我们把OPEN表上的节点按照它们估价函数值的递增顺序排列。根据推测，某个具有低的估价值的节点较有可能处在最佳路径上。最佳优先搜索算法：（1）把起始节点s放到OPEN表中，计算其估价值f(s)。（2）如果OPEN是个空表，则失败退出，无解。（3）从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。（4）把节点i从OPEN表中移出，并把它放入CLOSED
43、表中。（5）如果i是个目标节点，则成功退出，求得一个解。（6）扩展节点i，生成其全部后继节点。对于i的每一个后继节点j：(a)计算f(j)。(b)如果j既不在OPEN表中，也不在CLOSED表中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。(c)如果j已在OPEN表或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小，则(i)以此新值取代旧值。(ii)从j指向i，而不是指向它的父辈节点。(iii)如果节点j在CLOSED表中，则把它移回OPEN表。（7）转向（2），即GOTO（2）。与/或
44、树搜索 与/或树是不同于状态空间法的另外一种用于表示问题及求解过程的形式化方法，通常用于表示比较复杂的问题求解。与/或树搜索的目标是寻找解树，从而求得原始问题的解。如果在搜索的某一时刻，通过可解标示过程可确定初始节点是可解的，则由初始节点及其下属的可解节点就构成了解树。如果在某时刻被选为扩展的解点不可扩展，并且它不是终止节点，则此节点就是不可解节点。此时可应用不可解标示过程确定初始节点是否为不可解节点，如果可以肯定初始节点是不可解节点，则搜索失败，否则继续扩展节点。与/或树的盲目搜索 对于与/或树的盲目搜索，通常有宽度优先搜索、深度优先搜索和有界深度优先搜索等。因篇幅所限，我们这里仅介绍与/或
45、树的宽度优先搜索算法。与/或树的宽度优先搜索1、把初始节点S0放入Open表中；2、把Open表的第一个节点取出放入Closed表中，并记该节点为节点n；3、若节点n可扩展，则做下列工作：扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针；考察这些子节点是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点或先辈节点中可解节点进行标记。如初始节点S0被标记为可解节点，得到解树，成功退出。如不能确定为S0可解节点，则从Open表中删除具有可解先辈的节点；转第2步4、如果节点不可扩展，则做下列工作：标记节点n 为不可解节点；用不可解标记过程对节点n的先辈节点中不可解节点进行标记。如初始节点S0被标记为不可解节点，原问题无解而失败退出。如不能确定S0为不可解节点，则从Open表中删除具有不可解先辈的节点；转第2步
