人工智能重点总结41344.docx

《人工智能重点总结41344.docx》由会员分享，可在线阅读，更多相关《人工智能重点总结41344.docx（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、人工智能重点总结第一章：发展简史（此处为简答题）1.人工智能的萌芽（1956年以前）1936年，图图灵创立了自自动机理论（后后人称为图灵灵机），提出出一个理论计计算机模型，为为电子计算机机设计奠定了了基础，促进进了人工智能能，特别是思思维机器的研研究。麦克洛克和皮茨茨于19433年提出“拟脑模型”是世界上第第一个神经网网络模型（MMP模型），开开创了从结构构上研究人类类大脑的途径径。1948年维纳纳发表控制制论关于动物与与机器中的控控制与通信的的科学，不不但开创了近近代控制论，而而且为人工智智能的控制学学派树立了里里程碑。1、 古希腊伟大的哲哲学家思想家家亚里士多德德的主要贡献献是为形式逻逻辑

2、奠定了基基础。形式逻逻辑是一切推推理活动的最最基本的出发发点。在他的的代表作工工具论中，就就给出了形式式逻辑的一些些基本规律，如如矛盾律、排排中律，并且且实际上已经经提到了同一一律和充足理理由律。此外外亚里士多得得还研究了概概念、判断问问题，以及概概念的分类和和概念之间的的关系判断问问题的分类和和它们之间的的关系。其最最著名的创造造就是提出人人人熟知的三三段论。2、 英国的哲学家、自自然科学家 Baconn（培根）（11561-11626），他他的主要贡献献是系统地给给出了归纳法法，成为和 Aristtotle 的演绎法相相辅相成的思思维法则。BBacon 另一个功绩绩是强调了知知识的作用。

3、Baconn 的著名警警句是知识识就是力量。3、 德国数学家、哲哲学家 Leeibnittz（莱布尼尼茨）（16646-17716），他他提出了关于于数理逻辑的的思想，把形形式逻辑符号号化，从而能能对人的思维维进行运算和和推理。他曾曾经做出了能能进行四则运运算的手摇计计算机4、 英国数学家、逻逻辑学家 BBoole（布布尔）（18815-18864），他他初步实现了了布莱尼茨的的思维符号化化和数学化的的思想，提出出了一种崭新新的代数系统统-布尔代代数。5、 美籍奥地利数理理逻辑学家GGodel（哥哥德尔）（11906-11978），他他证明了一阶阶谓词的完备备性定理；任任何包含初等等数论的形式

4、式系统，如果果它是无矛盾盾的，那么一一定是不完备备的。此定理理的意义在于于，人的思维维形式化和机机械化的某种种极限，在理理论上证明了了有些事是做做不到的。6、 英国数学家 TTuringg(图灵)（11912-11954）,1936 年提出了一一种理想计算算机的数学模模型（图灵机机），19550 年提出出了图灵试验验，发表了计算机与智智能的论文文。当今世界界上计算机科科学最高荣誉誉奖励为图图灵奖。名名词解释：名名词解释：图图灵试验。当当一个人与一一个封闭房间间里的人或者者机器交谈时时，如果他不不能分辨自己己问题的回答答是计算机还还是人给出时时，则称该机机器是具有智智能的。以往往该试验几乎乎是衡

5、量机器器人工智能的的唯一标准，但但是从九十年年代开始，现现代人工智能能领域的科学学家开始对此此试验提出异异议：反对封封闭式的，机机器完全自主主的智能；提提出与外界交交流的，人机机交互的智能能。7、 美国数学家Maauchlyy，19466 发明了电电子数字计算算机 ENIIAC 8、 美国神经生理学学家 McCCullocch，建立了了第一个神经经网络数学模模型。从某种种意义上可以以说近代人工工智能的发展展， 首先是是从人工神 经网络研究究开始的。但但是由于某种种原因，神经经网络的研究究一度进 入入低潮。详细细内容参见第第六章人工工神经元网络络 9、 美国数学家 Shannnon（香农农）,1

6、9448 年发表表了通讯的的数 学理论论 ，标志志着信息论论的诞生。10、 美国数学家、计计算机科学家家 McCaarthy，人人工智能的早早期 研究者者。19566 年，他和和其他一些学学者联合发起起召开了世界界上第 一次次人工智能学学术大会，在在他的提议下下，会上正式式决定使用人人工 智能这这个词来概括括这个研究方方向。 参加加大会的有 Minskky, Roochestter, SShannoon, Mooore, Samueel, Seelfriddge, SSolomoonff, Simonn, Newwell 等等数学家、 心理学家、 神经生 理理学家、计算算机科学家。MMcCar

7、tthy 也被被尊为人工工智能之父。2.人工智能的的形成（19956-19969年）费根鲍姆于19968年研究究成功第一个个专家系统DDENDRAAL，用于质质谱仪分析有有机化合物的的分子结构。1969年召开开了第一届国国际人工智能能会议，标志志着人工智能能作为一门独独立学科登上上国际学术舞舞台。1970年人人工智能国际际杂志创刊刊。 50年代初初开始有了符符号处理，搜搜索法产生。人工智能的基本方法是逻辑法和搜索法。最初的搜索应用于机器翻译、机器定理证明、跳棋程序等。 60年代Simon由试验得到结论：人类问题的求解是一个搜索的过程，效果与启发式函数有关。叙述了智能系统的特点：智能表示、智能推

8、理、智能搜索。 Nilson发表了A* 算法（搜索方法） McCarthy建立了人工智能程序设计语言Lisp 1965年Robinson提出了归结原理。 1968年Quillian提出了语义网络的知识表示方法 1969年Minsky出了一本书感知机，给当时的神经网络研究结果判了死刑3.人工智能的的发展（19970年以后后）费根鲍姆19772-19776年成功开开发MYCIIN医疗专家家系统，用于于抗生素药物物治疗1987年在美美国召开第一一届神经网络络国际会议，并并发起成立国国际神经网络络学会（INNNS）1989年首次次召开了中国国人工控制联联合会议（CCJCAI） 70年代，人人工智能开始

9、始从理论走向向实践，解决决一些实际问问题。同时很很快就发现问问题：归结法法费时、下棋棋赢不了全国国冠军、机器器翻译一团糟糟。此时，以以Feigeenbaumm为首的一批批年轻科学家家改变了战略略思想，19977年提出出了知识工程程的概念，开开展了以知识识为基础的专专家咨询系统统研究与应用用。著名的专专家系统有：DENNDRAL化化学分析专家家系统（斯坦坦福大学19968）；MACSSYMA符号号数学专家系系统（麻省理理工19711）；MMYCIN诊诊断和治疗细细菌感染性血血液病的专家家咨询系统（斯斯坦福大学11973）；CASSNET(CCausall ASscciatioonal NNetw

10、orrk)诊断和和治疗青光眼眼的专家咨询询系统（拉特特格尔斯（RRutgerrs）大学770年代中）；CADDUCEUSS(原名INNTERNIIST)医疗疗咨询系统（匹匹兹堡大学）；HEAARSAY I 和III语音理解系系统（卡内基基-梅隆大学学）；PPROSPEECTOR地地质勘探专家家系统（斯坦坦福大学19976）；XCONN计算机配置置专家系统（卡卡内基-梅隆隆大学19778）。应该说，知知识工程和专专家系统是近近十余年来人人工智能研究究中最有成就就的分支之一一。 80年代代，人工智能能发展达到阶阶段性的顶峰峰。87,889年世界大大会有677千人参加。硬硬件公司有上上千个。Liis

11、p硬件、LLisp机形形成产品。同同时，在专家家系统及其工工具越来越商商品化的过程程中，国际软软件市场上形形成了一门旨旨在生产和加加工知识的新新产业-知知识产业。 同年代，11986年RRumlhaart领导的的并行分布处处理研究小组组提出了神经经元网络的反反向传播学习习算法，解决决了神经网络络分类能力有有限这一根本本问题。从此此，神经网络络的研究进入入新的高潮。 90年代，计算机发展趋势为小型化、并行化、网络化、智能化。人工智能技术逐渐与数据库、多媒体等主流技术相结合，并融合在主流技术之中，旨在使计算机更聪明、更有效、与人更接近。二、三大学派：1、符号主义(Symboolicissm)，又称

12、称为逻辑主义义(Logiicism)、心理学派派(Psycchlogiism)或计计算机学派(Compuuterissm)，其原原理主要为物物理符号系统统(即符号操操作系统)假假设和有限合合理性原理。符号主义学派认认为： 人工智智能源于数学学逻辑。代表性成果： 是启发式式程序LT逻逻辑理论家，证证明了38条条数学定理，表表明我们可以以应用计算机机研究人的思思维过程，模模拟人类智能能活动。代表人物：纽厄厄尔、肖西蒙和尼尔尔逊。2、联结主义(Conneectionnism)，又又称为仿生学学派(Bioonicsiism)或生生理学派(PPhysioologissm)，其原原理主要为神神经网络及神神

13、经网络间的的连接机制与与学习算法。这一学派认为： 人工智智能源于仿生生学，特别是是人脑模型的的研究代表性成果： 1943年年由麦克洛奇奇和皮兹提出出的形式化神神经元模型，即即M-P模型型代表人物： 麦克洛奇奇、皮兹、霍普菲尔特特、鲁梅尔哈特特3、行为主义(Actioonism)，又称进化化主义(Evvolutiionismm)或控制论论学派(Cyyberneeticsiism)，其其原理为控制制论。这一学派认为： 人工智智能源于控制制论代表性成果： 布鲁鲁克斯的六足足机器人，它它被看做新一一代的“控制论动物物”，是一个基基于感知动作模式的的模拟昆虫行行为的控制系系统。代表人物： 布布鲁克斯第二

14、章 知识表表示1. 状态空间（在搜搜索那里考一一个大题）了解个三元状态态（S，F，GG），其中SS:初始状态态集, F：操作符集合合G：目标状态集集合（这里只只用了解个大大概就可以了了，详细在搜搜索部分介绍绍）2. 问题归约（只考考一个名词解解释）解树：由可解节节点构成，并并且由这些可可解节点可推推出初始节点点（对应初始问题题）为可解节节点的子树称称为解树3. 谓词表示法（会会在第二道大大题中考4-5个应用）用谓词公式表示示知识时，需需要首先定义义谓词，然后后再用连接词词把有关的谓谓词连接起来来，形成一个个谓词公式表表达一个完整整的意义。例题 设有下列列知识： 刘欢欢比他父亲出出名。 高扬扬是

15、计算机系系的一名学生生，但他不喜喜欢编程 。 为了用用谓词公式表表示上述知识识，首先需要要定义谓词： BIGGGER(xx,y) : x比比y出名 COMMPUTERR ( x ) : xx 是计算机机系的 LIKKE (x, y ) : x 喜喜欢 y解答：此时可用用谓词公式把把上述知识表表示为: BIGGGER ( liuhuuan, ffatherr ( liiuhuann )（个个人觉得那个个fatheer函数最好也定义义下，保险一一点） COOMPUTEER(gaooyang)LIKEE(gaoyyang, progrramingg)总结：（上面的的例题应该就就是考试的形形式）A)

16、首先必须知道什什么是合取、析析取、蕴含、否否定以及两种种量词的用法法B) 全称量词后面跟跟蕴含，存在在量词后面跟跟合取C) 必须先定义（切切记），再表表示。一般步步骤为1提取谓词，使使用类似于 P（x，yy）：谓词内内容 的格格式定义谓词词2用连接词和和量词加以表表示D)置换和合一一那会用就OOK了。只会会在归结演绎绎推理那块最最后的证明时时用一下，不不理解的话看看那个“黄书”P81中那那个反演树里里用到的置换换。4. 语义网络（会考考画图题）只考二元关系网网络例题 小燕是一一只燕子，燕燕子是鸟；巢巢-1是小燕燕的巢，巢-1是巢中的的一个。”注意：A） 语义网络中不会会考量词、继继承、匹配B）

17、 就根据题目所描描述的写，不不要蛋疼的写写什么小明 ISA 人人 ISA 动物 ISSA 生物 题目上上怎么说怎么么写就可以（老老师原话） 5. 框架表示（只有有概念题）1框架：我们们无法把过去去的经验一一一都存在脑子子里，而只能能以一个通 用的数据结结构的形式存存储以往的经经验。这样的的数据结构称称为 框架2框架的构成成：框架通常由描述述事物的各个个方面的槽组组成，每个槽槽可以拥有若若干个侧面，而而每个侧面又又可拥有若干干个值。一个个框架的一般般结构如下： 3一个框架系系统（我觉得得应该不会考考这个，保险险起见所以放放上来了）下图所示为为表示立方 体的一个视视图的框架。图图中，最高层层的框架

18、，用用isa槽说说明它是一个个立方体，并并由regiion槽指示示出它所拥有有的3个可见见面A、B、EE。而A、BB、E又分别别用3个框架架来具体描述述。用musst be槽槽指示出它们们必须是一个个平行四边形形。为了能从从各个不同的的角度来描述述物体，可以以对不同角度度的视图分别别建立框架，然然后再把它们们联系起来组组成一个框架架系统。下图图所示的就是是从3个不同同的角度来研研究一个立方方体的例子 6.过程、剧本本表示不考第三章经典逻逻辑推理3.1归结演绎绎推理（问题题求解&证明明）定理证明即证明明PQ(PQ)的永真性性。根据反证证法，只要证证明其否定(PQ) 不可可满足性即可可。海伯伦(H

19、errbrandd)定理为自自动定理证明明奠定了理论论基础；鲁滨滨逊(Robbinsonn)提出的归归结原理使机机器定理证明明成为现实。在谓词逻辑中，把把原子谓词公公式及其否定定统称为文字字。如：P(x)， P(xx,f(x)， Q(x,g(x) ，任何文字的的析取式称为为子句，不包包含任何文字字的子句称为为空子句。 3.1.1化简简子句集(1) 合取范范式：C1 C2 C3 Cn (2) 子句集集: S= C1 ,CC2 ,C33 ,Cnn(3)任何谓谓词公式F都可通过等等价关系及推推理规则化为为相应的子句句集S。u 子句集的性质质：(1)子句集中中子句之间是是合取关系。(2)子句集中中的变

20、元受全全称量词的约约束。u 把谓词公式化成成子句集的步步骤：1) 利用等价关系消消去“”和“” 例如公式可等价变换成成2) 利用等价关系把把“”移到紧紧靠谓词的位位置上上式经等价变变换后 3) 重新命名变元，使使不同量词约约束的变元有有不同的名字字上式经变换后后4) 消去存在量词a.存在量词词不出现在全全称量词的辖辖域内，则只只要用一个新新的个体常量量替换受该量量词约束的变变元。b.存在量词词位于一个或或者多个全称称量词的辖域域内，此时要要用Skollem函数f(x1,x2,xn)替换受该存存在量词约束束的变元。上式中存在量量词($y)及($z)都位于(x)的辖域内内，所以需要要用Skolle

21、m函数替替换，设替换换y和z的Skoleem函数分别别是f(x)和g(x)，则则替换后得到到5) 把全称量词全部部移到公式的的左边6) 利用等价关系把把公式化为SSkolemm标准形Skolem标标准形的一般般形式是其中，M是子句句的合取式，称称为Skollem标准形形的母式。上上式化为Skkolem标标准形后得到到：7) 消去全称量词8) 对变元更名，使使不同子句中中的变元不同同名.上式化为9) 消去合取词，就就得到子句集集3.1.2替换换的定义推论1 设C11与C2是子句集S中的两个子子句，C12是它们的的归结式。若若用C12代替C1和C2后得到新子子句集S1，则由S1的不可满足足性可推出

22、原原子句集S的不可满足足性，即：S1的不可满足足性S的不可满足足性推论2 设C11与C2是子句集S中的两个子子句，C12是它们的的归结式。若若把C12加入S中得到新子子句集S2，则S与S2在不可满足足的意义上是是等价的，即即：S2的不可满足足性S的不可满足足性推论1及推论22保证了我们们可以用归结结的方法来证证明子句集SS的不可满足足性。为了要证明子句句集S的不可满足足性，只要对对其中可进行行归结的子句句进行归结，并并把归结式加加入子句集SS，或者用归归结式替换它它的亲本子句句，然后对新新子句集(SS1或者S2)证明不可满满足性就可以以了。如果经经过归结能得得到空子句，则则立即可得原原子句集S

23、是不可满足足的结论。在命题逻辑中，对对不可满足的的子句集S，归结原理理是完备的。即即，若子句集集不可满足，则则必然存在一一个从S到空子句的的归结演绎；若存在一个个从S到空子句的的归结演绎，则则S一定是不可可满足的。3.1.3归结结u 命题逻辑中的归归结原理定义4.9 若若P是原子谓词词公式，则称称P与P为互补文文字。在命题题逻辑中，PP为命题。定义4.10 设C1与C2是子句集中中的任意两个个子句。如果果C1中的文字L1与C2中文字L2互补，那么么从C1和C2中分别消去去L1和L2，并将两个个子句中余下下的部分析取取，构成一个个新子句C12，则称这这一过程为归归结。称C12为C1和C2的归结式

24、，CC1和C2为C12的亲本子子句。例4.9 设设C1=PQ, C2=QR, C3=PC1与C2归结结得到：C12=PRC12与C3归归结得到：CC123=Ru 谓词逻辑中的归归结原理在谓词逻辑中，由由于子句中含含有变元，所所以不能像命命题逻辑那样样直接消去互互补文字，而而需要先用最最一般合一对对变元进行代代换，然后才才能进行归结结。例如,设有两个个子句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)就可对它们进行行归结

25、，得到到归结式：Q(a)R(y)u 归结反演及其示示例*如欲证明Q为PP1,P2,Pn的逻辑结论论，只需证(P1P2Pn)Q是不可满足的，或或证明其子句句集是不可满满足的。而子子句集的不可可满足性可用用归结原理来来证明。 应用归结原理证证明定理的过过程称为归结结反演。 设F为已知前提提的公式集，Q为目标公式(结论)，用归结反演证明Q为真的步骤是：a) 否定Q，得到Q；b) 把Q并入到公公式集F中，得到FF, Q;c) 把公式集F, Q化化为子句集SS;d) 应用归结原理对对子句集S中的子句进进行归结，并并把每次归结结得到的归结结式都并入SS中。如此反反复进行，若若出现了空子子句，则停止止归结，

26、此时时就证明了QQ为真。例4.12 已已知求证：G是F的的逻辑结论。证明：首先把FF和G化为子句句集：然后进行归结：(6)A(xx,y)B(y)由(1)与(3)归结，f(x)/z(7)B(bb)由(4)与(6)归结，a/x,b/yy(8)NIL由(5)与(7)归结所以G是F的逻逻辑结论。上述归结过程如如下图归结树树所示。u 应用归结原理求求取问题的答答案及其示例例 归结时，并不要要求把子句集集中所有的子子句都用到。 在归结过程中，一一个子句可以以多次被用来来进行归结。求解的步骤：1. 把已知前提用谓谓词公式表示示出来，并且且化为相应的的子句集。设设该子句集的的名字为S。2. 把待求解的问题题也

27、用谓词公公式表示出来来，然后把它它否定并与谓谓词Answwer构成析析取式。Annswer是是一个为了求求解问题而专专设的谓词。3. 把此析取式化为为子句集，并并且把该子句句集并入到子子句集S中，得到子子句集S。4. 对S应用归结结原理进行归归结。5. 若得到归结式AAnswerr，则答案就就在Answwer中。例4.16 设设A,B,CC三人中有人人从不说真话话，也有人从从不说假话。某某人向这三人人分别提出同同一个问题：谁是说谎者者？A答：“B和C都是说谎者者”；B答：“A和C都是说谎者者”；C答：“A和B中至少有一一个是说谎者者”。求谁是老老实人，谁是是说谎者？解：设用T(xx)表示x说真

28、话。T(C)T(A)T(B)T(C)T(A)T(B)T(A)TT(B)T(C)T(A)TT(B)T(C)T(B)TT(A)T(C)T(B)TT(A)T(C)T(C)TT(A)T(B)T(C)TT(A)T(B)把上述公式化成成子句集，得得到S：(1)T(AA)T(B)(2)T(AA)T(C)(3)T(C)T(A)T(B)(4)T(BB)T(C)(5)T(CC)T(A)T(B)(6) T(AA)T(C)(7)T(B)T(C)下面先求谁是老老实人。把T(x)Ansewwer(x)并入S得到S1。即多一个个子句：(8)T(xx)Ansewwer(x)应用归结原理对对S1进行归结结：(9)T(AA)T(

29、C)(1)和(7)归结(10)T(CC) (6)和(9)归结(11)Anssewer(C)(8)和(10)归结结所以C是老实人人，即C从不说假话话。下面证明A不是是老实人，即即证明T(A)。对T(A)进进行否定，并并入S中，得到子子句集S2，即S2比S多如下子句句：(8)(TT(A), 即T(A)应用归结原理对对S2进行归结：(9)T(AA)T(C) (1)和(7)归结(10)T(A) (2)和(9)归结(11)NILL (8)和(10)归结结所以A不是老实实人。同样可可以证明B也不是老实实人。u 应用归结原理的的练习1. 设已知： （1）如果x是是y的父亲，y是z的父亲，则则x是z的祖父；

30、（2）每个人都都有一个父亲亲。 试用归结演绎推推理证明：对对于某人u，一一定存在一个个人v，v是u的祖父。 2. 张某被盗，公安安局派出五个个侦察员去调调查。研究案案情时，侦察察员 A 说“赵与钱中至至少有一人作作案”；侦察员 BB 说“钱与孙中至至少有一人作作案”；侦察员 CC 说“孙与李中至至少有一人作作案”；侦察员 DD 说“赵与孙中至至少有一人与与此案无关”；侦察员 EE 说“钱与李中至至少有一人与与此案无关”。如果这五五个侦察员的的话都是可信信的，试用归归结演绎推理理求出谁是盗盗窃犯。3.2不确定性性-只考模糊糊理论u 简单模糊推理知识中只含有简简单条件，且且不带可信度度因子的模糊糊

31、推理称为简简单模糊推理理。合成推理规则：对于知识IF x iis A THEN y is B首先构造出A与与B之间的模糊糊关系R，然后通过过R与证据的合合成求出结论论。如果已知证据是是x is A且A与A可以以模糊匹配，则则通过下述合合成运算求取取B：B=ARR如果已知证据是是y is B且B与B可以以模糊匹配，则则通过下述合合成运算求出出A：A=RBu 模糊集的运算模糊集上的运算算主要有：包包含、交、并并、补等等。1. 包含运算定义2.14 设A，BF(U)，若对对任意uU，都有B(u)A(u)成立，则称A包包含B，记为 。2. 交、并、补运算算定义2.15 设A，BF(U)，以下下为扎德算

32、子子例2.9 设UU=u1,u2,u3，A=0.3/uu1+0.8/u2+0.6/u3B=0.6/uu1+0.4/u2+0.7/u3则：AB=(0.30.6)/u1+(0.880.4)/u2+(0.660.7)/u3 =0.3/u1+0.4/u2+0.6/u3 AB=(0.30.6)/u1+(0.880.4)/u2+(0.660.7)/u3 =0.6/u1+0.8/u2+0.7/u3 A=(1-00.3)/uu1+(1-00.8)/uu2+(1-00.6)/uu3 =0.7/u1+0.2/u2+0.4/u33.3搜索-广度优先、深深度优先、全全局择优三选选一u 状态空间的一些些基本概念1) 很

33、多问题的求解解过程都可以以看作是一个个搜索过程。问问题及其求解解过程可以用用状态空间表表示法来表示示。2) 状态空间用“状状态”和“算符”来表示问题题。状态状态用以描述问问题在求解过过程中不同时时刻的状态，一一般用一个向向量表示：SK=(Sk00,Sk1,)算符使问题从一个状状态转变为另另一个状态的的操作称为算算符。在产生生式系统中，一一条产生式规规则就是一个个算符。状态空间由所有可能出现现的状态及一一切可用算符符所构成的集集合称为问题题的状态空间间。3) 采用状态空间求求解问题，可可以用下面的的一个三元组组表示：(S,F,G)其中S是问题初初始状态的集集合；F是算算符的集合；G是目标状状态的

34、集合。采用状态空间表表示方法，首首先要把问题题的一切状态态都表示出来来，其次要定定义一组算符符。问题的求解过程程是一个不断断把算符作用用于状态的过过程。如果在在使用某个算算符后得到的的新状态是目目标状态，就就得到了问题题的一个解。这这个解就是从从初始状态到到目标状态所所采用算符的的序列。使用用算符最少的的解称为最优优解。对任何一个状态态，可使用的的算符可能不不止一个。这这样由一个状状态所生成的的后继状态就就可能有多个个。此时首先先对哪一个状状态进行操作作，就取决于于搜索策略。u OPEN表和CCLOSE表表OPEN表用于于存放刚生成成的节点。对对于不同的搜搜索策略，节节点在OPEEN表中的排排

35、列顺序是不不同的。CLOSE表用用于存放将要要扩展的节点点。对一个节节点的扩展是是指：用所有有可适用的算算符对该节点点进行操作，生生成一组子节节点u 搜索的一般过程程1. 把初始节点S00放入OPENN表，并建立立目前只包含含S0的图，记为为G；2. 检查OPEN表表是否为空，若若为空则问题题无解，退出出；3. 把OPEN表的的第一个节点点取出放入CCLOSE表表，并计该节节点为n；4. 考察节点n是否否为目标节点点。若是，则则求得了问题题的解，退出出；5. 扩展节点n，生生成一组子节节点。把其中中不是节点nn先辈的那些些子节点记做做集合M，并把这些些子节点作为为节点n的子节点加加入G中；6.

36、 针对M中子节点点的不同情况况，分别进行行如下处理：1) 对于那些未曾在在G中出现过的的M成员设置一一个指向父节节点（即节点点n）的指针，并并把它们放入入OPEN表；（不在OPPEN表）2) 对于那些先前已已经在G中出现过的的M成员，确定定是否需要修修改它指向父父节点的指针针；（在OPPEN表中）3) 对于那些先前已已在G中出现并且且已经扩展了了的M成员，确定定是否需要修修改其后继节节点指向父节节点的指针；（在CLOOSE表中）7. 按某种搜索策略略对OPENN表中的节点点进行排序；8. 转第2步。u 一些说明 一个节点经一个个算符操作后后一般只生成成一个子节点点。但适用于于一个节点的的算符可

37、能有有多个，此时时就会生成一一组子节点。这这些子节点中中可能有些是是当前扩展节节点的父节点点、祖父节点点等，此时不不能把这些先先辈节点作为为当前扩展节节点的子节点点。 一个新生成的节节点，它可能能是第一次被被生成的节点点，也可能是是先前已作为为其它节点的的子节点被生生成过，当前前又作为另一一个节点的子子节点被再次次生成。此时时，它究竟应应选择哪个节节点作为父节节点？一般由由原始节点到到该节点的代代价来决定，处处于代价小的的路途上的那那个节点就作作为该节点的的父节点。 在搜索过程中，一一旦某个被考考察的节点是是目标节点就就得到了一个个解。该解是是由从初始节节点到该目标标节点路径上上的算符构成成。

38、 如果在搜索中一一直找不到目目标节点，而而且OPENN表中不再有有可供扩展的的节点，则搜搜索失败。 通过搜索得到的的图称为搜索索图，搜索图图是状态空间间图的一个子子集。由搜索索图中的所有有节点及反向向指针所构成成的集合是一一棵树，称为为搜索树。根根据搜索树可可给出问题的的解。u 盲目搜索 广度优先搜索广度优先搜索按按照“先扩展出的的节点先被考考察”的原则进行行搜索；n 基本思想从初始节点S00开始，逐层层地对节点进进行扩展并考考察它是否为为目标节点。在在第n层的节点没没有全部扩展展并考察之前前，不对第nn1层的节点进进行扩展。n OPEN表中节节点总是按进进入的先后顺顺序排列，先先进入的节点点

39、排在前面，后后进入的排在在后面。n 广度优先搜索过过程1) 把初始节点S00放入OPENN表。2) 如果OPEN表表为空，则问问题无解，退退出。3) 把OPEN表的的第一个节点点（记为节点点n）取出放入入CLOSEE表。4) 考察节点n是否否为目标节点点。若是，则则求得了问题题的解，退出出。5) 若节点n不可扩扩展，则转第第2步。6) 扩展节点n，将将其子节点放放入OPENN表的尾部，并并为每一个子子节点都配置置指向父节点点的指针，然然后转第2步。n 广度优先搜索的的本质是，以以初始节点为为根节点，在在状态空间图图中按照广度度优先的原则则，生成一棵棵搜索树n 优点：总可以得得到解，且是是路径最

40、短的的解。缺点：盲目、效率率低。n 重排九宫的广度度优先搜索 深度优先搜索-考有有界深度优先先搜索的可能能性很大深度优先搜索按按照“后扩展出的的节点先被考考察”的原则进行行搜索；n 深度优先搜索与与广度优先搜搜索的唯一区区别是：广度度优先搜索是是将节点n的子节点放放入到OPEEN表的尾部部，而深度优优先搜索是把把节点n的子节点放放入到OPEEN表的首部部。 n 深度优先搜索过过程1) 把初始节点S00放入OPENN表。2) 如果OPEN表表为空，则问问题无解，退退出。3) 把OPEN表的的第一个节点点（记为节点点n）取出放入入CLOSEE表。4) 考察节点n是否否为目标节点点。若是，则则求得了

41、问题题的解，退出出。5) 若节点n不可扩扩展，则转第第2步。6) 扩展节点n，将将其子节点放放入OPENN表的首部，并并为每一个子子节点都配置置指向父节点点的指针，然然后转第2步。n 深度优先搜索的的本质：以初初始节点为根根节点，在状状态空间图中中按照深度优优先的原则，生生成一棵搜索索树。n 重排九宫的深度度优先搜索 有界深度优先搜搜索：n 基本思想对深度优先搜索索引入搜索深深度的界限（设设为dm），当搜索索深度达到了了深度界限，而而仍未出现目目标节点时，就就换一个分支支进行搜索。n 搜索过程1) 把初始节点S00放入OPENN表中，置S0的深度d(SS0)=0。2) 如果OPEN表表为空，则

42、问问题无解，退退出。3) 把OPEN表的的第一个节点点（记为节点点n）取出放入入CLOSEE表。4) 考察节点n是否否为目标节点点。若是，则则求得了问题题的解，退出出。5) 若节点n的深度度d(n)=dm，则转转第2步（此时节节点n位于CLOSSE表，但并并未进行扩展展）。 6) 若节点n不可扩扩展，则转第第2步。7) 扩展节点n，将将其子节点放放入OPENN表的首部，为为每一个子节节点都配置指指向父节点的的指针，将每每一个子节点点的深度设置置为d(n)+1，然后后转第2步。n 重排九宫的有界界深度优先搜搜索（设深度度界限dm=4）u 启发式搜索启发式搜索采用用问题自身的的特性信息，以以指导搜

43、索朝朝着最有希望望的方向前进进。这种搜索索针对性较强强，因而效率率较高。 启发性信息与估估价函数：n 可用于指导搜索索过程，且与与具体问题有有关的信息称称为启发性信信息。n 用于评估节点重重要性的函数数称为估价函函数。其一般般形式为：f(x) = g(x)+h(x)n 其中g(x)表表示从初始节节点S0到节点x的代价；h(x)是从节节点x到目标节点点Sg的最优路径径的代价的估估计，它体现现了问题的启启发性信息。h(x)称为启发函数。n g(x) 有利利于搜索的完完备性，但影影响搜索的效效率。h(xx)有利于提提高搜索的效效率，但影响响搜索的完备备性。 全局择优搜索全局择优搜索按按照“哪个节点到

44、到目标节点的的估计代价小小就先考察哪哪个节点”的原则进行行搜索；广度优先搜索、代代价树的广度度优先搜索是是全局择优搜搜索的特例。 n 基本思想每当要选择下一一个节点进行行考察时，全全局择优搜索索每次总是从从OPEN表的的全体节点中中选择一个估估价值最小的的节点。n 搜索过程1) 把初始节点S00放入OPENN表，计算f(S0)。2) 如果OPEN表表为空，则问问题无解，退退出。3) 把OPEN表的的第一个节点点（记为节点点n）取出放入入CLOSEE表。4) 考察节点n是否否为目标节点点。若是，则则求得了问题题的解，退出出。5) 若节点n不可扩扩展，则转第第2步。6) 扩展节点n，用用估价函数ff(x)计算算每个子节点点的估价值，并并为每一个子子节点都配置置指向父节点点的指针。把把这些子节点点都送入OPPEN表中，然然后对OPEEN表中的全全部节点按估估价值从小至至大的顺序进进行排序，然然后转第2步。n 重排九宫问题的的全局择优搜搜索树设估价函数为：f(x)=d(x)+h(x)其中，d(x)表示节点x的深度，h(x)表示节节点x的格局与目目标节点格局局不相同的牌牌数。