人工智能总结

⼈⼯智能重点总结

第⼀章：发展简史（此处为简答题）1.⼈⼯智能的萌芽（1956年以前）

1936年，图灵创⽴了⾃动机理论（后⼈称为图灵机），提出⼀个理论计算机模型，为电⼦计算机设计奠定了基础，促进了⼈⼯智能，特别是思维机器的研究。

麦克洛克和⽪茨于1943年提出“拟脑模型”是世界上第⼀个神经⽹络模型（MP模型），开创了从结构上研究⼈类⼤脑的途径。1948年维纳发表《控制论—关于动物与机器中的控制与通信的科学》，不但开创了近代控制论，⽽且为⼈⼯智能的控制学派树⽴了⾥程碑。

1、古希腊伟⼤的哲学家思想家亚⾥⼠多德的主要贡献是为形式逻辑奠定了基

础。形式逻辑是⼀切推理活动的最基本的出发点。在他的代表作《⼯具论》中，就给出了形式逻辑的⼀些基本规律，如⽭盾律、排中律，并且实际上已经提到了同⼀律和充⾜理由律。此外亚⾥⼠多得还研究了概念、判断问题，以及概念的分类和概念之间的关系判断问题的分类和它们之间的关系。其最著名的创造就是提出⼈⼈熟知的三段论。2、英国的哲学家、⾃然科学家 Bacon（培根）（1561-1626），他的主要贡献是系统地给出了归纳法，成为和 Aristotle 的演绎法相辅相成的思维法则。

Bacon 另⼀个功绩是强调了知识的作⽤。 Bacon 的著名警句是\"知识就是⼒量\"。3、德国数学家、哲学家 Leibnitz（莱布尼茨）（16-1716），他提出了关于数

理逻辑的思想，把形式逻辑符号化，从⽽能对⼈的思维进⾏运算和推理。他曾经做出了能进⾏四则运算的⼿摇计算机4、英国数学家、逻辑学家 Boole（布尔）（1815-18），他初步实现了布莱尼茨的思维符号化和数学化的思想，提出了⼀种崭新的代数系统--布尔代数。5、美籍奥地利数理逻辑学家Godel（哥德尔）（1906-1978），他证明了⼀阶谓词

的完备性定理；任何包含初等数论的形式系统，如果它是⽆⽭盾的，那么⼀定是不完备的。此定理的意义在于，⼈的思维形式化和机械化的某种极限，在理论上证明了有些事是做不到的。

6、英国数学家 Turing(图灵)（1912-19）,1936 年提出了⼀种理想计算机的

数学模型（图灵机），1950 年提出了图灵试验，发表了\"计算机与智能\"的论⽂。当今世界上计算机科学最⾼荣誉奖励为\"图灵奖\"。名词解释：名词解释：图灵试验。当⼀个⼈与⼀个封闭房间⾥的⼈或者机器交谈时，如果他不能分辨⾃⼰问题的回答是计算机还是⼈给出时，则称该机器是具有智能的。以往该试验⼏乎是衡量机器⼈⼯智能的唯⼀标准，但是从九⼗年始，现代⼈⼯智能领域的科学家开始对此试验提出异议：反对封闭式的，机器完全⾃主的智能；提出与外界交流的，⼈机交互的智能。

7、美国数学家Mauchly，1946 发明了电⼦数字计算机 ENIAC

8、美国神经⽣理学家 McCulloch，建⽴了第⼀个神经⽹络数学模型。从某种意

义上可以说近代⼈⼯智能的发展，⾸先是从⼈⼯神经⽹络研究开始的。但是由于某种原因，神经⽹络的研究⼀度进⼊低潮。详细内容参见第六章《⼈⼯神经元⽹络》

9、美国数学家 Shannon（⾹农）,1948 年发表了《通讯的数学理论》，标志着\"信息论\"的诞⽣。

10、美国数学家、计算机科学家 McCarthy，⼈⼯智能的早期研究者。1956

年，他和其他⼀些学者联合发起召开了世界上第⼀次⼈⼯智能学术⼤会，在他的提议下，会上正式决定使⽤⼈⼯智能这个词来概括这个研究⽅向。

参加⼤会的有 Minsky, Rochester, Shannon, Moore, Samuel, Selfridge, Solomonff, Simon, Newell 等数学家、⼼理学家、神经⽣理学家、计算机科学家。McCarthy 也被尊为\"⼈⼯智能之⽗\"。

2.⼈⼯智能的形成（1956-1969年）

费根鲍姆于1968年研究成功第⼀个专家系统DENDRAL，⽤于质谱仪分析有机化合物的分⼦结构。1969年召开了第⼀届国际⼈⼯智能会议，标志着⼈⼯智能作为⼀门独⽴学科登上国际学术舞台。1970年《⼈⼯智能国际杂志》创刊。◆50年代初开始有了符号处理，搜索法产⽣。

⼈⼯智能的基本⽅法是逻辑法和搜索法。最初的搜索应⽤于机器翻译、机器定理证明、跳棋程序等。

◆60年代Simon由试验得到结论：⼈类问题的求解是⼀个搜索的过程，效果与启发式函数有关。叙述了智能系统的特点：智能表⽰、智能推理、智能搜索。◆Nilson发表了A*算法（搜索⽅法）◆McCarthy建⽴了⼈⼯智能程序设计语⾔Lisp◆1965年Robinson提出了归结原理。

◆1968年Quillian提出了语义⽹络的知识表⽰⽅法

◆1969年Minsky出了⼀本书\"感知机\"，给当时的神经⽹络研究结果判了死刑3.⼈⼯智能的发展（1970年以后）

费根鲍姆1972-1976年成功开发MYCIN医疗专家系统，⽤于抗⽣素药物治疗1987年在美国召开第⼀届神经⽹络国际会议，并发起成⽴国际神经⽹络学会（INNS）

19年⾸次召开了中国⼈⼯控制联合会议（CJCAI）

◆70年代，⼈⼯智能开始从理论⾛向实践，解决⼀些实际问题。同时很快就发现问题：归结法费时、下棋赢不了全国冠军、机器翻译⼀团糟。此时，以Feigenbaum 为⾸的⼀批年轻科学家改变了战略思想，1977年提出了知识⼯程的概念，开展了以知识为基础的专家咨询系统研究与应⽤。著名的专家系统有：

DENDRAL化学分析专家系统（斯坦福⼤学1968）；MACSYMA符号数学专家系统（⿇省理⼯1971）；

MYCIN诊断和治疗细菌感染性⾎液病的专家咨询系统（斯坦福⼤学1973）；

CASNET(Causal ASsciational Network)诊断和治疗青光眼的专家咨询系统（拉特格尔斯（Rutgers）⼤学70年代中）；CADUCEUS(原名INTERNIST)医疗咨询系统（匹兹堡⼤学）；HEARSAY I 和II语⾳理解系统（卡内基-梅隆⼤学）；PROSPECTOR地质勘探专家系统（斯坦福⼤学1976）；XCON计算机配置专家系统（卡内基-梅隆⼤学1978）。

应该说，知识⼯程和专家系统是近⼗余年来⼈⼯智能研究中最有成就的分⽀之⼀。

◆80年代，⼈⼯智能发展达到阶段性的顶峰。87,年世界⼤会有6－7千⼈参加。硬件公司有上千个。Lisp硬件、Lisp机形成产品。同时，在专家系统及其⼯具越来越商品化的过程中，国际软件市场上形成了⼀门旨在⽣产和加⼯知识的新产业--知识产业。

◆同年代，1986年Rumlhart领导的并⾏分布处理研究⼩组提出了神经元⽹络的反向传播学习算法，解决了神经⽹络分类能⼒有限这⼀根本问题。从此，神经⽹络的研究进⼊新的⾼潮。

◆90年代，计算机发展趋势为⼩型化、并⾏化、⽹络化、智能化。⼈⼯智能技术逐渐与数据库、多媒体等主流技术相结合，并融合在主流技术之中，旨在使计算机更聪明、更有效、与⼈更接近。⼆、三⼤学派：

1、符号主义(Symbolicism)，⼜称为逻辑主义(Logicism)、⼼理学派(Psychlogism)或计算机学派(Computerism)，其原理主要

为物理符号系统(即符号操作系统)假设和有限合理性原理。符号主义学派认为：⼈⼯智能源于数学逻辑。

代表性成果：是启发式程序LT逻辑理论家，证明了3数学定理，表明我们可以应⽤计算机研究⼈的思维过程，模拟⼈类智能活动。

代表⼈物：纽厄尔、肖·西蒙和尼尔逊。

2、联结主义(Connectionism)，⼜称为仿⽣学派(Bionicsism)或⽣理学派(Physiologism)，其原理主要为神经⽹络及神经⽹络间的连接机制与学习算法。

这⼀学派认为：⼈⼯智能源于仿⽣学，特别是⼈脑模型的研究

代表性成果： 1943年由麦克洛奇和⽪兹提出的形式化神经元模型，即M-P模型代表⼈物：麦克洛奇、⽪兹、霍普菲尔特、鲁梅尔哈特

3、⾏为主义(Actionism)，⼜称进化主义(Evolutionism)或控制论学派(Cyberneticsism)，其原理为控制论。这⼀学派认为：⼈⼯智能源于控制论

代表性成果：布鲁克斯的六⾜机器⼈，它被看做新⼀代的“控制论动物”，是⼀个基于感知——动作模式的模拟昆⾍⾏为的控制系统。

代表⼈物：布鲁克斯第⼆章知识表⽰

1.状态空间（在搜索那⾥考⼀个⼤题）

了解个三元状态（S，F，G），其中S:初始状态集, F：操作符集合

G：⽬标状态集合（这⾥只⽤了解个⼤概就可以了，详细在搜索部分介绍）2.问题归约（只考⼀个名词解释）解树：由可解节点构成，并且由这些可解节点可推出初始节点（对应初始问题）为可解节点的⼦树称为解树3.谓词表⽰法（会在第⼆道⼤题中考4-5个应⽤）

⽤谓词公式表⽰知识时，需要⾸先定义谓词，然后再⽤连接词把有关的谓词连接起来，形成⼀个谓词公式表达⼀个完整的意义。

例题设有下列知识：①刘欢⽐他⽗亲出名。

②⾼扬是计算机系的⼀名学⽣，但他不喜欢编程。为了⽤谓词公式表⽰上述知识，⾸先需要定义谓词：BIGGER(x,y) : x⽐y出名

COMPUTER ( x ) : x 是计算机系的LIKE (x, y ) : x 喜欢y

解答：此时可⽤谓词公式把上述知识表⽰为:

○1BIGGER ( liuhuan, father ( liuhuan ))（个⼈觉得那个father 函数最好也定义下，保险⼀点）○2COMPUTER(gaoyang)∧?LIKE(gaoyang, programing)总结：（上⾯的例题应该就是考试的形式）

A)⾸先必须知道什么是合取、析取、蕴含、否定以及两种量词的⽤法B)全称量词后⾯跟蕴含，存在量词后⾯跟合取

C)必须先定义（切记），再表⽰。⼀般步骤为

1>提取谓词，使⽤类似于P（x，y）：谓词内容的格式定义谓词2>⽤连接词和量词加以表⽰

D)置换和合⼀那会⽤就OK了。只会在归结演绎推理那块最后的证明时⽤⼀下，不理解的话看那个“黄书”P81中那个反演树⾥⽤到的置换。

4.语义⽹络（会考画图题）只考⼆元关系⽹络

例题⼩燕是⼀只燕⼦，燕⼦是鸟；巢-1是⼩燕的巢，巢-1是巢中的⼀个。”

注意：

A）语义⽹络中不会考量词、继承、匹配

B）就根据题⽬所描述的写，不要蛋疼的写什么⼩明ISA ⼈ISA 动物ISA ⽣物……题⽬上怎么说怎么写就可以（⽼师原话）5.框架表⽰（只有概念题）

1>框架：我们⽆法把过去的经验⼀⼀都存在脑⼦⾥，⽽只能以⼀个通⽤的数据结构的形式存储以往的经验。这样的数据结构称为框架

2>框架的构成：

框架通常由描述事物的各个⽅⾯的槽组成，每个槽可以拥有若⼲个侧⾯，⽽每个侧⾯⼜可拥有若⼲个值。⼀个框架的⼀般结构如下：<框架名>

<槽1><侧⾯11><值111>…<侧⾯12><值121>……<槽2><侧⾯21><值211>………

<槽n><侧⾯n1><值n11>……

<侧⾯nm><值nm1>…

3>⼀个框架系统（我觉得应该不会考这个，保险起见所以放上来了）下图所⽰为表⽰⽴⽅体的⼀个视图的框架。图中，最⾼层的框架，⽤isa槽说明它是⼀个⽴⽅体，并由region槽指⽰出它所拥有的3个可见⾯A、B、E。⽽A、B、E⼜分别⽤3个框架来具体描述。⽤must be槽指⽰出它们必须是⼀个平⾏四边形。为了能从各个不同的⾓度来描述物体，可以对不同⾓度的视图分

别建⽴框架，然后再把它们联系起来组成⼀个框架系统。下图所⽰的就是从3个不同的⾓度来研究⼀个⽴⽅体的例⼦

6.过程、剧本表⽰不考第三章经典逻辑推理

3.1归结演绎推理（问题求解&证明）

定理证明即证明P→Q(?P ∨Q)的永真性。根据反证法，只要证明其否定(P ∧?Q) 不可满⾜性即可。

海伯伦(Herbrand)定理为⾃动定理证明奠定了理论基础；鲁滨逊(Robinson)提出的归结原理使机器定理证明成为现实。在谓词逻辑中，把原⼦谓词公式及其否定统称为⽂字。如：P(x)， ?P(x,f(x))， Q(x,g(x)) ，任何⽂字的析取式称为⼦句，不包含任何⽂字的⼦句称为空⼦句。3.1.1化简⼦句集

(1) 合取范式：C1 ∧C2 ∧C 3… ∧Cn (2) ⼦句集: S= {C1 ,C2 ,C3… ,Cn}

(3) 任何谓词公式F 都可通过等价关系及推理规则化为相应的⼦句集S 。 ◆ ⼦句集的性质：

(1)⼦句集中⼦句之间是合取关系。 (2)⼦句集中的变元受全称量词的约束。 ◆ 把谓词公式化成⼦句集的步骤：1) 利⽤等价关系消去“→”和“?” 例如公式可等价变换成

2) 利⽤等价关系把“?”移到紧靠谓词的位置上上式经等价变换后

3) 重新命名变元，使不同量词约束的变元有不同的名字上式经变换后 4) 消去存在量词

a.存在量词不出现在全称量词的辖域内，则只要⽤⼀个新的个体常量替换受该量词约束的变元。

b.存在量词位于⼀个或者多个全称量词的辖域内，此时要⽤Skolem 函数f(x 1,x 2,…,x n )替换受该存在量词约束的变元。上式中存在量词(?y)及(?z)都位于(?x)的辖域内，所以需要⽤Skolem 函数替换，设替换y 和z 的Skolem 函数分别是f(x)和g(x)，()(()(,)()((,)(,)))

x y P x y y Q x y R x y ??→??→()(()(,)()((,)(,)))x y P x y y Q x y R x y ∨∨()(()(,)()((,)(,)))x y P x y y Q x y R x y ∨?∧?()(()(,)()((,)(,)))x y P x y z Q x z R x z ∨?∧?()((,())((,())(,())))x P x f x Q x g x R x g x ??∨∧?则替换后得到

5) 把全称量词全部移到公式的左边 6) 利⽤等价关系把公式化为Skolem 标准形Skolem 标准形的⼀般形式是

其中，M 是⼦句的合取式，称为Skolem 标准形的母式。上式化为Skolem 标准形后得到：7) 消去全称量词

8) 对变元更名，使不同⼦句中的变元不同名.上式化为9) 消去合取词，就得到⼦句集3.1.2替换的定义

推论1 设C 1与C 2是⼦句集S 中的两个⼦句，C 12是它们的归结式。若⽤C 12代替C 1和C 2后得到新⼦句集S 1，则由S 1的不可满⾜性可推出原⼦句集S 的不可满⾜性，即：S 1的不可满⾜性S 的不可满⾜性

推论2 设C 1与C 2是⼦句集S 中的两个⼦句，C 12是它们的归结式。若把C 12加⼊S 中得到新⼦句集S 2，则S 与S 2在不可满⾜的意义上是等价的，即：S 2的不可满⾜性S 的不可满⾜性

推论1及推论2保证了我们可以⽤归结的⽅法来证明⼦句集S 的不可满⾜性。为了要证明⼦句集S 的不可满⾜性，只要对其中可进⾏归结的⼦句()()()

P Q R P Q P R ∨∧?∨∧∨12()()()n x x x M ()(((,())(,()))((,())(,())))

x P x f x Q x g x P x f x R x g x ??∨∧?∨?((,())(,()))((,())(,()))P x f x Q x g x P y f y R y g y ?∨∧?∨?(,())(,())(,())(,())P x f x Q x g x P y f y R y g y ?∨?∨?

进⾏归结，并把归结式加⼊⼦句集S，或者⽤归结式替换它的亲本⼦句，然后对新⼦句集(S1或者S2)证明不可满⾜性就可以了。如果经过归结能得到空⼦句，则⽴即可得原⼦句集S是不可满⾜的结论。

在命题逻辑中，对不可满⾜的⼦句集S，归结原理是完备的。即，若⼦句集不可满⾜，则必然存在⼀个从S到空⼦句的归结演绎；若存在⼀个从S到空⼦句的归结演绎，则S⼀定是不可满⾜的。3.1.3归结

◆命题逻辑中的归结原理

定义4.9 若P是原⼦谓词公式，则称P与?P为互补⽂字。在命题逻辑中，P为命题。

定义4.10 设C1与C2是⼦句集中的任意两个⼦句。如果C1中的⽂字L1与C2中⽂字L2互补，那么从C1和C2中分别消去L1和L2，并将两个⼦句中余下的部分析取，构成⼀个新⼦句C12，则称这⼀过程为归结。称C12为C1和C2的归结式，C1和C2为C12的亲本⼦句。

例4.9 设C1=?P∨Q, C2=?Q∨R, C3=PC1与C2归结得到：C12=?P∨RC12与C3归结得到：C123=R◆谓词逻辑中的归结原理

在谓词逻辑中，由于⼦句中含有变元，所以不能像命题逻辑那样直接消去互补⽂字，⽽需要先⽤最⼀般合⼀对变元进⾏代换，然后才能进⾏归结。

例如,设有两个⼦句

C1=P(x)∨Q(x), C2= ?P(a)∨R(y)

由于P(x)与P(a)不同，所以C1与C2不能直接进⾏归结。但是若⽤最⼀般合⼀σ={a/x}

对两个⼦句分别进⾏代换：C1σ=P(a)∨Q(a) C2σ= ?P(a)∨R(y)就可对它们进⾏归结，得到归结式：Q(a)∨R(y)

◆ 归结反演及其⽰例*

如欲证明Q 为P 1,P 2,…,P n 的逻辑结论，只需证(P 1∧P 2∧…∧P n )∧?Q

是不可满⾜的，或证明其⼦句集是不可满⾜的。⽽⼦句集的不可满⾜性可⽤归结原理来证明。应⽤归结原理证明定理的过程称为归结反演。

设F 为已知前提的公式集，Q 为⽬标公式(结论)，⽤归结反演证明Q为真的步骤是： a) 否定Q ，得到?Q ；

b) 把?Q 并⼊到公式集F 中，得到{F, ?Q}; c) 把公式集{F, ?Q}化为⼦句集S;d) 应⽤归结原理对⼦句集S 中的⼦句进⾏归结，并把每次归结得到

的归结式都并⼊S 中。如此反复进⾏，若出现了空⼦句，则停⽌归结，此时就证明了Q 为真。例4.12 已知

求证：G 是F 的逻辑结论。 证明：⾸先把F 和?G 化为⼦句集：

然后进⾏归结： (6)?A(x,y)∨?B(y) 由(1)与(3)归结，{f(x)/z} (7)?B(b) 由(4)与(6)归结，{a/x,b/y} (8)NIL由(5)与(7)归结

所以G 是F 的逻辑结论。 上述归结过程如下图归结树所⽰。:()(()((,)())()(()(,))):()()()()((,)())F x y A x y B y y C y D x y

G x C x x y A x y B y ??∧→?∧??→??→?{(,)()(()),(,)()(,())}{(),(,),()}F A x y B y C f x A x y B y D x f xG C z A a b B b =?∨?∨?∨?∨?=?

◆应⽤归结原理求取问题的答案及其⽰例

归结时，并不要求把⼦句集中所有的⼦句都⽤到。在归结过程中，⼀个⼦句可以多次被⽤来进⾏归结。求解的步骤：

1.把已知前提⽤谓词公式表⽰出来，并且化为相应的⼦句集。设该⼦句集的名字为S。

2.把待求解的问题也⽤谓词公式表⽰出来，然后把它否定并与谓词Answer构成析取式。Answer是⼀个为了求解问题⽽专设的谓词。3.把此析取式化为⼦句集，并且把该⼦句集并⼊到⼦句集S中，得到⼦句集S`。

4.对S`应⽤归结原理进⾏归结。

5.若得到归结式Answer，则答案就在Answer中。

例4.16设A,B,C三⼈中有⼈从不说真话，也有⼈从不说假话。某⼈向这三⼈分别提出同⼀个问题：谁是说谎者？A答：“B和C都是说谎者”；B 答：“A和C都是说谎者”；C答：“A和B中⾄少有⼀个是说谎者”。求谁是⽼实⼈，谁是说谎者？解：设⽤T(x)表⽰x说真话。T(C)∨T(A)∨T(B)T(C)∨?T(A)∨?T(B)T(A)→?T(B)∧?T(C)T(A)→T(B)∨T(C)T(B)→?T(A)∧?T(C)T(B)→T(A)∨T(C)T(C)→?T(A)∨?T(B)T(C)→T(A)∧T(B)

把上述公式化成⼦句集，得到S：(1)?T(A)∨?T(B)(2)?T(A)∨?T(C)

(3)T(C)∨T(A)∨T(B)(4)?T(B)∨?T(C)(5)?T(C)∨?T(A)∨?T(B)(6) T(A)∨T(C)(7)T(B)∨T(C)

下⾯先求谁是⽼实⼈。把?T(x)∨Ansewer(x)并⼊S得到S1。即多⼀个⼦句：(8)?T(x)∨Ansewer(x)应⽤归结原理对S1进⾏归结：(9)?T(A)∨T(C) (1)和(7)归结(10)T(C) (6)和(9)归结(11)Ansewer(C) (8)和(10)归结所以C是⽼实⼈，即C从不说假话。下⾯证明A不是⽼实⼈，即证明?T(A)。

对?T(A)进⾏否定，并⼊S中，得到⼦句集S2，即S2⽐S多如下⼦句：(8)?(?T(A)), 即T(A)

应⽤归结原理对S2进⾏归结：(9)?T(A)∨T(C) (1)和(7)归结(10)?T(A) (2)和(9)归结(11)NIL (8)和(10)归结

所以A不是⽼实⼈。同样可以证明B也不是⽼实⼈。◆应⽤归结原理的练习1.设已知：

（1）如果x是y的⽗亲，y是z的⽗亲，则x是z的祖⽗；（2）每个⼈都有⼀个⽗亲。

试⽤归结演绎推理证明：对于某⼈u，⼀定存在⼀个⼈v，v是u的祖⽗。

2.张某被盗，派出五个侦察员去调查。研究案情时，侦察员A 说“赵与钱中⾄少有⼀⼈作案”；侦察员B 说“钱与孙中⾄少有⼀⼈作案”；侦察员 C 说“孙与李中⾄少有⼀⼈作案”；侦察员 D 说“赵与孙中⾄少有⼀⼈与此案⽆关”；侦察员 E 说“钱与李中⾄少有⼀⼈与此案⽆关”。如果这五个侦察员的话都是可信的，试⽤归结演绎推理求出谁是盗窃犯。

3.2不确定性------只考模糊理论◆简单模糊推理

知识中只含有简单条件，且不带可信度因⼦的模糊推理称为简单模糊推理。

合成推理规则：对于知识IF x is A THEN y is B

⾸先构造出A与B之间的模糊关系R，然后通过R与证据的合成求出结论。如果已知证据是x is A’

且A与A’可以模糊匹配，则通过下述合成运算求取B’：B’=A’?R如果已知证据是y is B’

且B与B’可以模糊匹配，则通过下述合成运算求出A’：A’=R?B’模糊集的运算

模糊集上的运算主要有：包含、交、并、补等等。 1. 包含运算定义2.14 设A ，B ∈F (U)，若对任意u ∈U ，都有µB (u )≤µA (u )

成⽴，则称A 包含B ，记为 。 2. 交、并、补运算定义2.15 设A ，B ∈F (U)，以下为扎德算⼦例2.9 设U={u 1,u 2,u 3}，

A=0.3/u 1+0.8/u 2+0.6/u 3 B=0.6/u 1+0.4/u 2+0.7/u 3则：

A ∩B=(0.3∧0.6)/u 1+(0.8∧0.4)/u 2+(0.6∧0.7)/u 3=0.3/u 1+0.4/u 2+0.6/u 3

A ∪B=(0.3∨0.6)/u 1+(0.8∨0.4)/u 2+(0.6∨0.7)/u 3=0.6/u 1+0.8/u 2+0.7/u 3

A=(1-0.3)/u 1+(1-0.8)/u 2+(1-0.6)/u 3=0.7/u 1+0.2/u 2+0.4/u 3

3.3搜索--⼴度优先、深度优先、全局择优三选⼀

B A ?:()max{(),()}()():()min{(),()}()():()1()A B A B A B u UA B A B A B u U

A A A

B u u u u u A B u u u u u A u u µµµµµµµµµµµµ∈∈?==∨==∧?=- 状态空间搜索策略

盲⽬搜索⼴度优先搜索深度优先搜索有界深度优先搜索

代价树的⼴度优先搜索代价树的深度优先搜索局部择优搜索全局择优搜索

状态空间的⼀些基本概念

1)很多问题的求解过程都可以看作是⼀个搜索过程。问题及其求解过程可以⽤状态空间表⽰法来表⽰。2)状态空间⽤“状态”和“算符”来表⽰问题。状态

状态⽤以描述问题在求解过程中不同时刻的状态，⼀般⽤⼀个向量表⽰：SK=(Sk0,Sk1,…)算符

使问题从⼀个状态转变为另⼀个状态的操作称为算符。在产⽣式系统中，⼀条产⽣式规则就是⼀个算符。状态空间

由所有可能出现的状态及⼀切可⽤算符所构成的集合称为问题的状态空间。3)采⽤状态空间求解问题，可以⽤下⾯的⼀个三元组表⽰：(S,F,G)

其中S是问题初始状态的集合；F是算符的集合；G是⽬标状态的集合。

采⽤状态空间表⽰⽅法，⾸先要把问题的⼀切状态都表⽰出来，其次要定义⼀组算符。

问题的求解过程是⼀个不断把算符作⽤于状态的过程。如果在使⽤某个算符后得到的新状态是⽬标状态，就得到了问题的⼀个解。这个解

就是从初始状态到⽬标状态所采⽤算符的序列。使⽤算符最少的解称为最优解。

对任何⼀个状态，可使⽤的算符可能不⽌⼀个。这样由⼀个状态所⽣成的后继状态就可能有多个。此时⾸先对哪⼀个状态进⾏操作，就取决于搜索策略。◆OPEN表和CLOSE表

OPEN表⽤于存放刚⽣成的节点。对于不同的搜索策略，节点在OPEN 表中的排列顺序是不同的。

CLOSE表⽤于存放将要扩展的节点。对⼀个节点的扩展是指：⽤所有可适⽤的算符对该节点进⾏操作，⽣成⼀组⼦节点

◆搜索的⼀般过程

1.把初始节点S0放⼊OPEN表，并建⽴⽬前只包含S0的图，记为G；2.检查OPEN表是否为空，若为空则问题⽆解，退出；

3.把OPEN表的第⼀个节点取出放⼊CLOSE表，并计该节点为n；4.考察节点n是否为⽬标节点。若是，则求得了问题的解，退出；5.扩展节点n，⽣成⼀组⼦节点。把其中不是节点n先辈的那些⼦节点记做集合M，并把这些⼦节点作为节点n的⼦节点加⼊G中；6.针对M中⼦节点的不同情况，分别进⾏如下处理：

1)对于那些未曾在G中出现过的M成员设置⼀个指向⽗节点（即节点n）的指针，并把它们放⼊OPEN表；（不在OPEN表）2)对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向⽗节点的指针；（在OPEN表中）

3)对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向⽗节点的指针；（在CLOSE表中）7.按某种搜索策略对OPEN表中的节点进⾏排序；8.转第2步。◆⼀些说明

⼀个节点经⼀个算符操作后⼀般只⽣成⼀个⼦节点。但适⽤于⼀个节点的算符可能有多个，此时就会⽣成⼀组⼦节点。这些⼦节点中

可能有些是当前扩展节点的⽗节点、祖⽗节点等，此时不能把这些先辈节点作为当前扩展节点的⼦节点。

⼀个新⽣成的节点，它可能是第⼀次被⽣成的节点，也可能是先前已作为其它节点的⼦节点被⽣成过，当前⼜作为另⼀个节点的⼦节

点被再次⽣成。此时，它究竟应选择哪个节点作为⽗节点？⼀般由原始节点到该节点的代价来决定，处于代价⼩的路途上的那个节点就作为该节点的⽗节点。

在搜索过程中，⼀旦某个被考察的节点是⽬标节点就得到了⼀个解。该解是由从初始节点到该⽬标节点路径上的算符构成。

如果在搜索中⼀直找不到⽬标节点，⽽且OPEN表中不再有可供扩展的节点，则搜索失败。

通过搜索得到的图称为搜索图，搜索图是状态空间图的⼀个⼦集。由搜索图中的所有节点及反向指针所构成的集合是⼀棵树，称为搜索树。根据搜索树可给出问题的解。◆盲⽬搜索⼴度优先搜索

⼴度优先搜索按照“先扩展出的节点先被考察”的原则进⾏搜索；基本思想

从初始节点S0开始，逐层地对节点进⾏扩展并考察它是否为⽬标节点。在第n层的节点没有全部扩展并考察之前，不对第n＋1层的节点进⾏扩展。

OPEN表中节点总是按进⼊的先后顺序排列，先进⼊的节点排在前⾯，后进⼊的排在后⾯。⼴度优先搜索过程

1)把初始节点S0放⼊OPEN表。

2)如果OPEN表为空，则问题⽆解，退出。

3)把OPEN表的第⼀个节点（记为节点n）取出放⼊CLOSE表。4)考察节点n是否为⽬标节点。若是，则求得了问题的解，退出。

5)若节点n不可扩展，则转第2步。

6)扩展节点n，将其⼦节点放⼊OPEN表的尾部，并为每⼀个⼦节点都配置指向⽗节点的指针，然后转第2步。

⼴度优先搜索的本质是，以初始节点为根节点，在状态空间图中按照⼴度优先的原则，⽣成⼀棵搜索树

优点：总可以得到解，且是路径最短的解。缺点：盲⽬、效率低。重排九宫的⼴度优先搜索

深度优先搜索----考有界深度优先搜索的可能性很⼤