智能控制基础：第二章 智能控制的知识工程基础

第二章

智能控制的知识工程基础

第二章智能控制的知识工程基础

2.1

引言

2.2

知识的基本概念

2.3

知识的表示

2.4

知识的获取

2.5知识的处理符号信息处理、启发式程序设计、知识表示、自动推理、机器学习和决策智能控制研究需采用的相关技术：对实际环境或过程进行组织，即决策和规划，实现广义问题求解。智能控制的核心任务：2.1引言

2.2知识的基本概念2.2.1

什么是知识2.2.2

知识的分类人类智能活动是获取和运用知识计算机要有智能就必须有知识知识必须要存储到计算机

2.2.1什么是知识

知识是人们在长期生活、社会实践、科学研究和实验中积累起来的对客观世界的认识和总结，然后将实践中获得的信息关联在一起，也就构成了知识。

简言之，知识是把有关信息关联在一起所形成的信息结构。应用最多的关联形式是“IF-THEN”形式，它反映了信息间的某种因果关系。知识、规则、数据、信息之间的关系

智能活动：是人类获取知识并运用知识的过程。知识：是智能的基础。人类大量的要使计算机具有智能的话，就必须使计算机具有获取知识和运用知识的能力知识、规则、数据、信息之间的关系

规则：把关联起来的知识称为规则。事实或原子事实：把不与其他信息关联的信息称为事实或原子事实。

数据：描述客观事物的属性、数量、位置以及相互关系。是信息的载体和表示。它可以是数，也可以是字符串。信息：是数据在特定场合下的具体含义，或是数据的语义。知识、规则、数据、信息之间的关系同一个数据在不同的场合可能代表不同的信息同一个信息在不同的场合也可以用不同的数据表示

要使计算机具有智能，模拟人的智能活动，就必须使它有知识。而知识只有用适当的模式表示出来才能存储到计算机中去。

知识的基本属性有：真理性、相对性、相容性、不完全性、模糊性、可表达性、可存储性、可传递性和可处理性。

2.2.2知识的分类共性知识（常识性知识）个性知识（领域性知识）

按知识的使用范围分类按知识的功能分类按知识的确定性分类按知识结构及表现形式分类过程性知识事实性知识(描述性知识)控制性知识确定性知识不确定性知识逻辑型知识形象型知识数学、物理控制理论这是温控装置不精确真、假正处于升温过程开大蒸气阀人类经验树2.3知识的表示

知识必须以适当的形式表示出来才便于在计算机中存储、检索、使用和修改等。

知识的表示

知识表示是一种计算机可接受的对人类智能行为的描述。它是一种符号模型的约定，将人类知识通过一个符号模型映射到计算机中。

知识表示法（知识表示模式/技术）状态空间表示法一阶谓词逻辑表示法时序逻辑表示法产生式表示法语义网络表示法Petri网络表示法定性模型知识表示法可视知识模型表示法神经网络知识表示法不确定性（模糊）知识表示法…….框架表示法

2.3.1状态空间表示法

状态、操作和状态空间的概念状态空间图示法

状态、操作和状态空间的概念

状态：描述某些事物中各不同事物间的差异，而引入的一种最小变量的有序组合。状态、操作和状态空间的概念其中，是状态变量，用于表示事物的某一特征，也可称为特征量。如：脸像、指纹。

状态、操作和状态空间的概念操作：能够引起状态中某些分量发生变化，从而使一个状态转移为另一个状态。

状态、操作和状态空间的概念状态空间：描述全部可能状态及其相互关系的三重序元<S,F,G>。

S是事物可能的初始状态集合F是操作集合G是可能的目标状态集合

状态空间图示法

用右向图来表示状态空间。

状态空间图示法

把状态集合映射为结点集合。操作所引起的状态转移映射为标注该操作的有向边。问题求解通过操作从初始结点到目标结点寻找一条有效的途径。

2.3.2一阶谓词表示法

取值为真或假的句子称为命题。（1）12>5;（2）3是12的约数;（3）0.5是整数;（4）X>5.（5）今天上课点名吗？（6）把门关上（7）10000000是一个好大的数啊!疑问句、祈使句、感叹句、开语句都不是命题。在命题演算中，对下述论断无法判断其正确性。“苏格拉底三段论”：所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。

2.3.2一阶谓词表示法在谓词演算中，命题可分为谓词和个体两部分。谓词：用于刻划个体的性质、状态或个体间的关系，用大写字母表示。个体：表示某个独立存在的事物或某个抽象的概念，用小写字母表示。谓词的一般形式是：其中P是谓词，有n个个体，称之为n元谓词。例如：（1）李明是学生；（2）张亮比陈华高；（3）陈华坐在张亮与李明之间。

一阶谓词中的基本概念基本要素：常量、变量、函数、谓词、联接词、量词用谓词逻辑表示状态和操作。

例：关于积木世界的问题。

基本要素常量：具体的特定的个体变量：抽象的、泛指的个体函数：由其他事物所确定的事物联接词：联接谓词的逻辑符号量词：分为全称量词和存在量词

一阶谓词中的联接词

：否定词（非）(非P)

：合取词（与）(P与Q)

：析取词（或）(P或Q)

：蕴含词（条件）(如果P，则Q)

：双蕴含词（等价）(P当且仅当Q)PQP

QP

Q

PP→QTTTTFTFTTFTTTFTFFFFFFFTT实质蕴含：P→Q=

P

Q如果拉登没死，则股市天天大涨蕴含怪论：P

→（Q→P

）

P

→（P→Q

）如果P为真，则由任何命题Q可推出P如果P为假，则P可以蕴含任何Q质疑：“任何命题蕴含真命题”证明“2+2=5蕴含雪是白的”直觉：有些命题彼此无关，不能相互蕴含，实质蕴含没有考虑这种情况挑战罗素：已知：假命题2+2=5

证明：罗素与某主教是一个人罗素证明：假设2+2=5，又∵2+2=4,∴4=5

两边减1得：3=4，2=3，1=2∴罗素与某主教是一个人断言得证

一阶谓词中的联接词由联接词构成的谓词称为复合谓词公式，联接词的优先级别是，，，，。

一阶谓词中的量词

：全称量词，表示所有个体中的全体。：存在量词，表示存在某一些。

x(P(x))表示对于所有个体，谓词P(x)成立。

x(P(x))表示存在某些个体，谓词P(x)成立。位于量词后面的单个谓词或复合谓词称为量词的辖域，辖域内与量词同名的变元称为约束变元，不受约束的称为自由变元。用谓词表示知识时，需要先定义谓词，指出每个谓词的含义，然后用联接词把有关的谓联接起来，形成一个谓词公式，表示一个完整的意义。

关于积木世界的问题BACACB初始状态目标状态

关于积木世界的问题定义谓词：ON(x,y):表示x在y上CLEAR(x):表示x顶上是空的ONTABLE(x):表示x在桌子上HOLDING(x):表示手里拿着xHANDEMPTY:表示手是空的大写字母表示谓词

关于积木世界的问题以上谓词中，x和y是个体，个体域为A，B和C。

关于积木世界的问题初始状态QS：CLEAR(C)CLEAR(B)ONTABLE(A)ONTABLE(B)ON(C，A)HANDEMPTYBAC

关于积木世界的问题目标状态Qg：ONTABLE(C)ON(B，C)ON(A，B)CLEAR(A)HANDEMPTYACB

关于积木世界的问题操作1：PICKUP(x):拿起xP.D:CLEAR(x),ONTABLE(x),HANDEMPTYA:HOLDING(x)

关于积木世界的问题操作2：PUTDOWN(x):放x在桌上P.D:HOLDING(x)A:CLEAR(x),ONTABLE(x),HANDEMPTY

关于积木世界的问题操作3：STACK(x,y):把x放在y上P.D:CLEAR(y),HOLDING(x)A:ON(x,y),CLEAR(x),HANDEMPTY

关于积木世界的问题操作4：UNSTACK(x,y):把x从y上拿开P.D:ON(x,y),CLEAR(x),HANDEMPTYA:CLEAR(y),HOLDING(x)

关于积木世界的问题操作序列：UNSTACK(C,A)PUTDOWN(C)PICKUP(B)STACK(B，C)PICKUP(A)STACK(A，B)BACACB例：设个体域是整数集合，请利用给出的谓词将下列命题符号化。

N(e)：e是自然数

P(e)：e是素数

Q(e)：e是偶数

E(e1,e2)：e1=e2

L(e1,e2)：e1

e2

D(e1,e2)：e1

e2

a)凡素数均为自然数。

x(P(x)

N(x))b)没有最大的素数。

x(P(x)

y(P(y)

L(y,x)))c)有些自然数不是素数。

x(N(x)

P(x))d)并非所有的素数都不是偶数。

x(P(x)

Q(x))

一阶谓词表示法

也称一阶谓词逻辑表示法，用一阶谓词逻辑表示人们在问题求解时的逻辑演绎推理过程。例：关于海豚的定理证明形式

关于海豚的定理证明形式已知：

①无论什么动物，能阅读即识字②海豚不识字③某些海豚有智能证明：某人或动物有智能却不能阅读

关于海豚的定理证明形式定义谓词：R(x):动物x能阅读L(x):动物x能识字D(x):x是海豚I(x):x有智能X是个体，域是每个人或动物

关于海豚的定理证明形式已知：F1:(

x)(R(x)→L(x))F2:(

x)(D(x)→L(x))F3:(x)(D(x)I(x))G:(

x)(I(x)R(x))(F1

F2F3)

→G是永真公式证明：将已知条件,求证结论的反化成子句集

①～R(x)∨L(x)

②～D(y)∨～L(y)

③D(a)

④I(a)

⑤～I(z)∨R(z)（结论的否定）

⑥～L(a)......2,3归结｛a/y｝

⑦～R(a)......1,6归结｛a/x｝

⑧R(a)......4,5归结｛a/z｝

⑨□......7,8归结

2.3.3时序逻辑表示法

将时间及其次序关系引入谓词表达式之中，利用谓词逻辑的概念和方法，便构成了时序逻辑知识模型。

例：Holds(u1,t1)Holds(u2,t2)After(t2,t1)After(t3,t2)Holds(y,t3)

2.3.4产生式表示法

又称为规则或产生式规则。通常用于表示具有因果关系的知识。基本形式为：

IFPTHENQ或P

Q

（前提条件）

（结论或动作）产生式系统反映领域知识一种类似于缓冲器的数据结构，存放问题求解过程中的各种当前信息。如初始状态、推理的中间结论、最终结论等匹配、冲突解决、操作

2.3.5语义网络知识表示法

语义网络（SematicNetwork)是通过概念及其语义关系来表达知识的一种网络图，由节点和连接节点的弧构成。其基础是一种三元组结构（节点1、弧、节点2）。

（下层概念）（上层概念）是一种（弧）（节点）（节点）狗狗猎

结构（节点1，弧，节点2）节点：表示各种事物、概念、情况、属性、动作、状态、地点等。弧：表示各种语义联系，指明所连接节点的某种关系。语义网络除可表达事实外，还可表达规则。一条产生式规则R：IFATHENB，可表示成一个语义网络规则如下：当多个三元组综合在一起表达时，就可得到一个语义网络。BAR语义网络可以描述事物间复杂的语义关系图书馆语义网络1）分类关系——事物间类属关系张杰是一个读者，师大附中是一个单位，图书馆是一种建筑2）聚集关系——下层概念是上层概念的一个方面或一个部分阅览室是图书馆的一部分3）推论关系——一个概念可由另一个概念推出校园像公园推出风景美丽4）时间、位置关系校园在芙蓉山脚下5）相近关系校园像公园6）属性关系阅览室能开放，阅览室有读者

2.3.6框架知识表示法人工智能专家、minsky在1975年提出框架理论基本观点：人脑中已存储有大量事物的典型情境，也就是人们对这些事物的一种认识，这些典型情境是以一个称作框架的基本知识结构存储在记忆中的。当人面临新的情境时，就从记忆中选择一个合适的框架，这个框架是以前记忆的一个知识空框，而其具体内容依新的情境而改变。通过对这个空框的细节加工、修改和补充，形成对新的事物情境的认识，而这种认识的新框架又可记忆于人脑中，以丰富人的知识。

举例：组装电脑，你需要了解硬件的细节，如：CPU的型号，价格，硬盘，大小，内存，大小显示器，型号，大小……

你的头脑中很快建立了关于计算机硬件组成的基本框架。框架的组成：一个框架由若干个“槽”的结构组成，每一个槽又可以根据实际情况拥有若干个侧面，每个侧面也可以再拥有若干个侧面。在一个框架系统中，一般含有多个框架，为了区别这些不同的框架，需要分别给它们赋予不同名字，称为框架名。同样，对于不同的槽和侧面也需要给予相应的槽名和侧面名。框架的一般形式

<框架名>槽名1：侧面名11：值111，值112

侧面名12：值121，值122

……

槽名2：侧面名21：值211，值212

侧面名22：值221，值222

……

槽名n：侧面名n1：值n11，值n12

侧面名n2：值n21，值n22框架表示知识实例：描述本科生情况的具体框架：

框架名：<本科生>

姓名：性别：年龄：院系：专业：课程：

2.3.6框架知识表示法框架网络把多个相互关联的框架连接起来组成框架网络。可以用语义网络的形式表示，每个节点代表一个框架。注：

究竟采用哪一种表示模式，没有统一的标准。在确定一个知识表示模式时，首先应考虑的是它能否充分地表示领域知识。

2.4知识的获取

人工智能或知识工程系统中，通过非自动方式或自动方式实现计算机从知识源获取知识的过程。知识源包括专家、书本、数据库和人的经验等。

知识的获取目的

通过计算机对人类专家的丰富知识高速度地加以收集、整理，并在此基础上建立各种高性能的知识系统，以帮助人类解决那些单独依靠人难以解决或解决起来太慢、效率太低的各种问题。2.4.1

非自动知识获取2.4.2自动知识获取

2.4.1非自动知识获取

非自动知识获取是指知识是通过知识工程师和知识编辑器传授给知识库的。知识编辑器是一类程序设计系统，包括语法检查、一致性检查、自动薄记、知识抽取等功能。知识库领域专家知识编辑器知识工程师非自动知识获取2.4.2自动知识获取

全自动知识获取是让计算机直接从环境中获取全部信息。包括机器感知（主要是计算机视觉和听觉）、机器识别和机器学习等。环境机器感知机器学习机器识别知识库全自动知识获取模型

机器感知

机器感知接受外部环境的信息（语言、文字、图像等），经过感知系统的初步处理后，可以得到一些简单的事实性知识。

机器识别系统

信息的分类知识信息的特征信息的结构知识

机器学习系统（提供更高层次知识）

根据环境信息形成概念归纳推理文法推断假设猜想科学发现

学习系统的基本模型

学习是系统积累经验以改善其性能的过程，是知识的获取与改进，是事物规律的发现过程。也就是，学习是一个有特定目的的知识获取过程。

学习系统的基本模型学习系统内在行为：获取知识、积累经验、发现规律学习系统外部表现：改进性能、适应环境、实现系统的自我完善

学习系统的基本模型

学习系统是指，一个系统能够从某个过程或环境的未知特征中学到有关信息，并且能把学到的信息用于未来的估计、分类、决策或控制，以便改进系统的性能。

学习系统的基本模型环境学习环节工作环节知识库系统的外界信息源。有关环境的信息数据存在数据库中，它处于在线学习时是可变的，属于短期记忆范畴。代表知识信息（学习成果），用于存储或记忆系统通过学习所获得的各种知识。分长期和中期记忆两部分。学习系统的核心。是对环境信息进行搜索、控制和逻辑思维。通过比较、抽象、概括、综合、推理等，以产生、修改与补充知识。是智能系统的知识产生器。用于处理系统面临的现实问题，如组合调度。从工作环节到学习环节必须有反馈信息，以便学习环节决定是否进行再学习。

学习系统的分类

机械式学习系统类比学习系统示例学习系统发现式学习系统指导学习系统

机械式学习系统（RoteLearning)又称记忆学习。是一种最简单、最基本的学习方法，无推理过程，是从特殊到特殊的学习过程。通过从知识库中检索相应的知识，直接求解问题。

机械式学习系统输入：输出：存储联想对：

类比学习系统(AnalogyLearning)在两个相似域之间进行类比。源域S：目标域T：

类比学习系统(AnalogyLearning)当出现{s′,t′}，已经发现s′具有特性P，则可类比地归纳出t′具有特性Q。

示例学习系统

（LearningfromExamples)是从许多示例中得出事物的特性或一般规律的一种学习方法。是从特殊到一般的学习过程。

示例学习系统

（LearningfromExamples)示例的质量要求它能准确地反映实际问题的情况，因为它是学习的基础，只有正确的示例才有可能得出正确的知识。

发现式学习系统

（DiscoveringLearning)又称猜想-验证式学习。首先对历史经验进行分析总结，提出猜想，然后有意识地设计实验以验证猜想。包括归纳与演绎、综合与分析、联想与设计。在示例学习中，示例经环境严格挑选，没有干扰信息。发现式学习由环境提供的是未经挑选的，信息是一种随机多干扰信息。由学习环节对信息提纯，以发现新概念。

应用谓词，将下述推理符号化。每个学生或者聪明或者勤奋；所有勤奋的人都将有所作为；但并非所有学生都将有所作为。所以，一定有些学生是聪明的。

[解]令：个体域Ｉ是人的集合。

S(e):e是学生；A(e):e聪明；

B(e):e勤奋；C(e):e将有所作为。符号化为：

x(S(x)(A(x)B(x)))，x(B(x)C(x))，

x(S(x)C(x))，x(S(x)A(x))

2.5知识的处理运用知识的过程称为推理过程。推理是指依据一定的规则从已有的事实推出结论的过程。其中的规则称为控制策略。

知识的处理智能系统是以知识为基础的系统，它根据已有的知识和事实去求解当前的问题。也叫基于知识的推理。推理由程序实现，称为推理机。

知识的处理推理是按某种策略从一个或几个已知判断推出另一个判断的思维过程。

知识的处理推理所依据的判断叫前提，包括知识库中的领域知识及问题的初始证据。由前提推出的新判断叫结论。推理存在一个置信度转移的过程。2.5.1

推理的方式与分类2.5.2推理控制策略2.5.3

状态空间的搜索策略

2.5.1推理的方式与分类

演绎推理归纳推理非单调推理

演绎推理（DeductionReasoning)前提与结论之间有蕴含关系的推理，或前提与结论之间有必然联系的推理。即结论蕴含在已知的判断之中，是一种由一般到个别的推理。

演绎推理（DeductionReasoning)

或例：已知：每个学术会的成员都是工人并且是专家，有些成员是青年人。求证：有的成员是青年专家。证明：定义谓词：

F(x):x是学术会成员G(x):x是专家H(x):

x是工人R(x):x是青年人归纳推理（InductiveReasoning)指由个别事物或现象推出该类事物或现象一般性知识的过程。常用方法有枚举法、类比法、统计法等。

非单调推理（Non-monotousReasoning)在信息或知识不完全的情况下，假设某些命题成立并进行推理。在推理过程中，如果发现原假设不正确，就撤销原假设以及由此得出的结论，重新按新情况进行推理。非单调推理（Non-monotousReasoning)新事实或新知识的加入，不但没有扩充可推出的命题，反面必须删除一些原先推出的命题。常用的非单调推理为默认推理。默认推理：

α(x):mβ1(x),…mβm(x)w(x)

α(x):前提条件，β(x)缺省条件,w(x)是结论，m表示相容。当前提与缺省条件相容或不矛盾时，结论可信。例：已知x是一只鸟，正常情况下推断或相信x能飞，用默认逻辑表述：鸟(x):m会飞(x)会飞(x)

根据常规，鸟t会飞，如果得知鸟t受伤或是只鸵鸟，则推断是不可信的。得出一个新的理论：理论＝规则＋事实鸟(x):m会飞(x)会飞(x)，鸵鸟(x)→~会飞(x);

导致原有逻辑结论发生改变。

2.5.2推理控制策略

正向推理（数据驱动推理）

反向推理（目标驱动推理）

正反向混合推理解决知识的选择与应用的顺序问题

正向推理正向推理是事实驱动。过程是从问题所有可能的初始证据（事实）开始，正向使用规则，通过匹配每条知识的前提，识别出所有可用的知识而形成一个可用知识集（冲突集），然后以某种冲突求解方式在冲突集中选取一条知识。这条知识的使用又会得出新的事实。新的事实和原有事实又引起知识库中新的知识匹配，从而继续问题的求解，直至达到某一状态。若问题的结论已包含在所产生的事实中，则说明问题有解，否则无解或已给出所有解。例：已知：初始事实是有毛发、会吃肉、有斑点，现在要求专家系统判断这是什么动物？IF该动物用乳汁哺育幼子=trueTHEN哺乳动物=trueIF该动物有毛发=trueTHEN哺乳动物=trueIF该动物会吃肉=trueTHEN食肉动物=trueIF哺乳动物=trueAND该动物是反刍动物=trueTHEN蹄类动物=trueIF哺乳动物=trueAND食肉动物=trueAND有暗斑点=trueTHEN该动物是金钱豹=true…………

根据上面事实，匹配成功了三条规则：规则2被激活，增加新事实：哺乳动物规则3被激活，增加新事实：食肉动物规则５被激活，增加新事实：金钱豹得出结论：该动物是金钱豹

反向推理反向推理是目标驱动。过程是首先从提出目标假设开始，然后从知识库中找出其结论部分能与假设相匹配的所有知识，得到一个可用的知识集。若可用知识集为空集，则推理失败。若可用知识集非空，则从可用知识集中选取一条验证前提部分。若验证成功，就从目标或假设集中找出该知识的结论，且由该知识计算出可信度放入上下文。若该知识中的某一前提被用户或上下文否定，则该知识的结论部分不能被这条知识所验证，可以返回到可用知识集中重新选择一条可用知识。当所有知识都不能验证成功时，该结论应从假设目标中删除，直到上下文中含有原提出的目标或假设。这说明问题有解，当所有目标都测试过，而上下文中找不到原提出的目标或假设时，则说明该问题无解。证据节点：不能作为其他规则结论的假设。

正反向混合推理

先根据数据库中的原始数据，通过正向推理帮助系统提出假设，再运用反向推理，进一步寻求支持假设的证据，如此反复，直到得出结论或不再有新的事实加到数据库为止。是压缩空间，提高搜索效率的有效途径。

2.5.3状态空间的搜索策略对于结构不良或非结构化的问题，不存在成熟的求解算法可供利用，只能一步步地摸索前进。这种不断搜寻前进方向求解问题的过程称为搜索

状态空间的搜索策略状态空间隐式图的基本搜索：盲目搜索（宽度/深度优先搜索策略）启发式搜索

状态空间隐式图搜索在不断的搜索过程中，产生新的状态空间，逐步地生成问题的状态空间图，即采用隐式存储。这种状态空间的生成过程就称为隐式图搜索。

状态空间隐式图搜索首先把问题的初始状态作为当前状态，选择适用的算符对其进行操作，生成一组子状态（子节点），然后检查目标状态是否在其中出现，若出现，则搜索成功，找到了问题的解，若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符为止。基本思想：

状态空间隐式图搜索过程OPEN：存放等待扩展的结点的表

CLOSED：存放已扩展的结点的表

(标注部分已生成的状态空间，可得到解径)

状态空间隐式图搜索过程

初始状态结点S0放入OPEN表中；从OPEN表中取出第一个结点N放到CLOSED表中；

状态空间隐式图搜索过程

(3)若N可扩展，则扩展结点N产生其所有子结点Ni，将Ni放入OPEN表中，并按控制性知识对OPEN表中所有结点排序，把最有希望在解径上的结点放在第一位置上；

状态空间隐式图搜索过程(4)测试刚生成的结点Ni中是否有目标结点Sg，若Sg已生成，则搜索成功；(5)若Sg尚未生成，则返回到(2)，搜索进入循环过程，直到OPEN表为空，搜索失败。

状态空间隐式图搜索过程扩展节点N即是对操作集合F中的每个操作的前提部分与结点N的状态描述进行匹配，并执行所有被N满足的操作fi，定义获得的由新状态描述所对应的结点分别为N的子结点。例：用状态空间搜索法求解走迷宫问题。设用Si表示各个格子的状态，把入口、出口、每一个格子都作为节点。设向上、向下、向左、向右的算符分别为U、D、L、R，应用状态空间搜索，得到搜索图。从入口到出口有很多条通道，每条通道都是问题的一个解，其中最短的路径长度是5，由5个算符组成：

S0S4S5S8S9Sg

盲目搜索只是按预定的控制策略进行搜索，没有考虑到问题的特性，具有盲目性，效率较低，一般只适于求解比较简单的问题。

宽度优先搜索（广度优先搜索）从初始节点S0开始，逐层地对节点进行扩展，并考察它是否为目标节点，在对第n层的节点没有全部扩展并考察完以前，不对第n+1层的节点进行扩展。

宽度优先搜索（广度优先搜索）节点顺序：S0，S1，S2，S3，…每次新生成的结点从尾部放入表，而已有结点从头部取出，即先进先出，后进后出。例：用宽度优先搜索策略求解重排九宫问题。在3*3的方格棋盘上放置1、2、3、4、5、6、7、8共8个棋子，初始状态为s0，目标状态为sg。

规则：（1）在移动时，只允许把位于空格上、下、左、右的邻近棋子移入空格（2）棋子移入空格的次序是由空格左边开始，沿顺时针方向移动，即每一层都按空格左移、上移、右移、下移的顺序进行（3）不允许斜方向移动，不允许返回

解的路径是：1（s0

）381626（sg

）

深度优先搜索从初始节点S0开始，在其子节点中选择一个节点进行考察，若不是目标节点，则在该节点的子节点中选择一个节点进行考察，一直如此向下搜索。

深度优先搜索（有界深度）OPEN表中，后生成的节点优先扩展，即后进先出。为了克服陷入无穷分支死循环的问题，提出了有界深度优先搜索方法。例：用深度优先搜索策略求解重排九宫问题。在3*3的方格棋盘上放置1、2、3、4、5、6、7