人工智能技术导论

人工智能技术导论（第二版人工智能技术导论（第二版)廉师友 编著参考书u人工智能马少平、朱小燕编著，清华大学出版社u人工智能及其应用蔡自兴、徐光祐编著，清华大学出版社u Artificial Intelligence A New Synthesis(人工智能)Nils J.Nilsson 第一章 人工智能概述u人工智能的概念u人工智能的研究途经与方法u人工智能的分工领域u人工智能的基本技术u人工智能的发展概括什么是人工智能u人工智能(Artificial Intelligence)是指由计算机实现的人造智能。作为一门学科，人工智能可定义为：人工智能是一门研究如何构造智能机器（智能计算机）或智能系统，使它能模拟、延伸、扩展人类智能的学科u人工智能是一门交叉边缘学科，与人工智能有关的学科有：计算机科学、数学、语言学、神经生理学、神经心理学、脑科学、认知科学、逻辑学、控制论等什么是人的智能u智能是人脑的属性和产物。智能具有的主要特征：A、具有感知能力。通过视觉、听觉、触觉、味觉和嗅觉感知外部世界。B、具有记忆与思维能力。记忆能存储由感知器官感知到的外部信息以及由思维所产生的知识。思维用于对记忆的信息进行处理。思维可分为逻辑思维和形象思维。C、具有学习能力及自适应能力。D、具有行为能力。u发现规律 应用规律 分析问题 解决问题u图灵测试u中文屋子问题（约翰希尔勒）为什么要研究人工智能u现有计算机系统的局限性。智能低下、缺乏自学习、自适应、自优化能力。u人类智能的局限性。学习能力因人而异、学习速度慢、效率低。u信息化社会的迫切要求。人工智能的目标u近期目标：使现有的电子数字计算机能模拟人类的部分智能行为。u远期目标：制造智能计算机，使计算机具有看、听、说等感知和交互能力、具有联想、推理、理解、学习等高级思维能力，还要有分析问题、解决问题和发明创造的能力。u深蓝（32CPU，200万次/秒，200万个棋局）人工智能的表现形式u智能软件u智能设备u智能网络u智能计算机u智能机器人u智能体(Agent)(艾真体)人工智能的研究途径与方法u结构模拟（神经计算、生理学派、连接主义）模拟人脑的神经网络结构实现智能。主要特征：1、通过神经元之间的并行协同作用实现信息处理，具有并行性、动态性、全局性。2、通过神经元间分布式的物理联接存储信息。联想记忆、容错性。3、通过神经元间连接强度的动态调整实现自学习和自适应功能。4、善于模拟人类的形象思维过程。人工智能的研究途径与方法u功能模拟（符号主义、心理学派、逻辑学派）以人脑的心理模型为基础，将问题或知识表示成某种逻辑网络，采用符号推演的方法，实现搜索、推理和学习等功能。主要特征：1、立足于逻辑运算和符号操作，适合于模拟人的逻辑思维过程。2、知识用显式的符号表示，容易表达人的心理模型。3、现有的数字计算机可以方便地实现高速的符号处理。4、能与传统的符号数据库进行链接，易于模块化。5、以知识为基础。人工智能的研究途径与方法u行为模拟（行为主义、进化主义、控制论学派）基于感知-行为模型的研究途径和方法。模拟人在控制过程中的智能活动和行为特征：自寻优、自适应、自组织、自学习。强调智能系统与环境的交互，认为智能取决于感知和行动,智能行为可以不要知识。智能只有放在环境中才是真正的智能，智能的高低体现在对环境的适应性上Brooks，机器虫人工智能的分支领域u基于脑功能模拟的领域划分1、机器感知（信息输入）。使计算机具有类似于人的感知能力，能通过“感知”直接从外界获取信息，是对人的感知的模拟及延伸。机器视觉、机器听觉。相关学科：模式识别（语音识别、图像识别）。信息-电信号序列-预处理-提取特征-模式匹配2、机器联想。基于内容的联想，与具体存储位置无关。联想存储技术。3、机器推理。又称为计算机推理、自动推理，是人工智能的核心课题之一。v推理：从一些已知判断（前提）推出一个新判断（结论）的思维过程。v演绎推理、归纳推理、类比推理v确定性推理、不确定性推理v基于概率逻辑的或然推理(随机性)、基于模糊逻辑的似然推理(模糊性)v串行推理、并行推理人工智能的分支领域4、机器学习。使机器自己获取知识。v对人类已有知识的获取、对客观规律的发现、对自身行为的修正。v机器学习分为：机械学习、指导学习、解释学习、类比学习、示例学习、发现学习等。这些属于符号学习。另外还有神经网络学习。5、机器理解。图形理解（物景分析）、自然语言理解。理解是感知的延伸和深化。6、机器行为（机器人行动规划）。v智能机器人的核心技术，反映了机器人的智能水平v解决问题依靠规划功能确定行动步骤和动作序列v任务：在一个特定的工作区域中自动生成从初始状态到目标状态的动作序列、运动路径和轨迹的控制程序人工智能的分支领域u基于研究途径和实现技术的领域划分1、符号智能v以符号知识为基础，通过符号推理进行问题求解v知识工程(知识获取、知识表示、知识管理、知识运用、知识库系统)、符号处理2、计算智能v以数据为基础，通过数值计算进行问题求解v人工神经网络、进化计算(遗传算法、遗传程序设计、进化规划、进化策略)、模糊技术、人工生命人工智能的分支领域u基于应用领域的领域划分1、难题求解v难题的概念v路径规划、组合优化、天气预报、股市分析、市场预测、机器博弈vNP(Nondeterministic Polynomial)和NPC(Nondeterministic Polynomial Complete)问题v难题求解技术能促进人工智能其他领域的发展2、自动定理证明v自然演绎法、判定法、定例证明器、计算机辅助证明v四色问题(1976.6,K.Appeel)。3、自动程序设计v超级编译系统v自动程序综合和自动程序验证。人工智能的分支领域4、自动翻译。机器翻译。自然语言理解。v一边站着一个人v他想起来了5、智能控制v1965，KS.FU(傅京孙)提出将启发式推理规则用于学习控制系统6、智能管理。人工智能与管理科学、系统工程和计算机技术的结合。7、智能决策。人工智能应用于决策支持系统。8、智能通讯。在通讯的各个环节和层次上实现智能化。如网控、转接、信息转换等。使通讯网随时运行于最佳状态。9、智能仿真。仿真是在三种类型知识-描述性知识、目的性知识和处理知识的基础上产生另一种形式的知识-结论性知识。10、智能CAD。人工智能应用于CAD的设计自动化、智能交互、智能图形学、自动数据采集方面。11、智能CAI。人工智能应用于CAI：自动生成各种问题与练习、自动选择与调整教学内容和进度、自动生成答案、自然语言理解能力、不断改善教学策略。人工智能的分支领域u基于应用系统的领域划分1、专家系统。基于人类专家知识的程序系统。能模拟专家的思维方式。2、知识库系统。3、智能数据库系统。传统数据库系统+人工智能。4、智能机器人系统。具备感知、思维、人-机通讯和运动能力。人工智能的分支领域u基于计算机系统结构的领域划分1、智能操作系统。并行性、分布性和智能性。2、智能多媒体系统。人工智能与多媒体技术的有机结合。3、智能计算机系统。4、智能网络系统。模糊和神经网络技术应用于网络的业务量预测和控制、资源动态分配、动态路由选择等方面。人工智能的分支领域u基于实现工具与环境的领域划分1、智能软件工具。人工智能程序设计语言，如表处理语言LISP、逻辑程序设计语言PROLOG、面向对象程序设计语言Smalltalk等。知识表示语言FRL、OPS5。专家系统工具、知识工程工具等。2、智能硬件平台。直接支持智能系统开发和运行的机器硬件。人工智能的分支领域u基于体系结构的领域划分集中式人工智能（个体智能）分布式人工智能（群体智能）v个体智能的组合或叠加vDPS（分布式问题求解），自顶向下vMAS（多智能体系统），自底向上人工智能的基本技术u推理技术。推理是智能的核心。推理以逻辑为基础。基于谓词逻辑的自然演绎推理和归结反演推理。基于非标准逻辑如多值逻辑、模态逻辑、时态逻辑、模糊逻辑、非单调逻辑的推理。u搜索技术。人工智能的基本技术。许多智能活动的过程，都可以看作或抽象为一个“问题求解”过程。“问题求解”就是在问题空间中进行搜索的过程。盲目搜索、启发式搜索。神经网络搜索。u知识表示与知识库技术。知识表示是指知识在计算机中的表示方式。知识表示要符合知识的逻辑结构和物理结构，并适合于计算机存储和处理。知识库由知识构成。知识的组织、管理、维护和优化。人工智能的基本技术u归纳技术。机器自动提取概念、获取知识、发现规律的技术。归纳技术与知识获取和机器学习密切相关。基于符号处理的归纳和基于神经网络的归纳。数据库知识发现（KDD,Knowledge Discovery in Database)和数据挖掘(Data Mining)技术。u联想技术。联想记忆，联想存储。人工智能的发展概况u孕育期（1956年之前）1、公元前，Aristotle提出形式逻辑的一些主要定律，三段论至今仍是演绎推理的基本依据。2、培根（1561-1626）曾系统地提出了归纳法。提出“知识就是力量”3、德国数学家Leibniz（1646-1716）提出了万能符号和推理计算的思想，为数理逻辑的产生和发展奠定了基础。4、英国逻辑学家Boole（1815-1864）创立了布尔代数，在思维法则一书中首次用符号语言描述了思维活动的基本推理法则。5、英国数学家Turing于1936年提出理想计算机的数学模型，即图灵机。Turing测试。6、1943年，McCulloch 和 Pitts提出M-P神经元模型。7、1946年，世界上第一台电子计算机诞生。人工智能的发展概况u人工智能学科的产生（1956年）1956年夏季，McCarthy,Minsky,Lochester,Shannon,More,Samuel,Selfridge,Solomonff,Newell,Simon等十人在Dartmouth大学召开历时两个多月的研讨会，讨论机器智能的有关问题。由McCarthy提出“人工智能”一词，人工智能从此成为一门学科。人工智能的发展概况u符号主义AI发展概况1、形成（1956-1965）（人工智能的推理期。结构良好问题。搜索策略和算法）v（1）、1956年，Samuel的跳棋程序。1959,1962v（2）、定理证明方面，1956年Newell等的逻辑理论机（LT）程序；1958年，王浩的工作；1965年，Robinson提出的消解原理。v（3）、模式识别方面，1959年Selfridge的模式识别程序；1965年Roberts编制了可以分辨积木构造的程序。v（4）、问题求解方面。1960年，Newell的通用问题求解(GPS)程序。v（5）、1960年，McCarthy研制成功LISP语言。人工智能的发展概况人工智能的知识期（1965-70年代末）v（1）、专家系统方面。1965年，Feigenbaum的专家系统DENDRAL，1968年投入使用。DENDRAL对知识表示、存储、获取和推理的技术为以后的专家系统的建造树立了榜样，对AI的发展产生了深刻的影响。之后著名的专家系统有：医学专家系统MYCIN，地质勘探专家系统PROSPECTOR，计算机配置专家系统R1等。v（2）、1969年，国际人工智能联合会议(IJCAI)召开。1970年，“Artificial Intelligence”杂志创刊。v（3）、1977年，Feigenbaum在第五届国际人工智能会议上，提出了“知识工程”的概念。发展期（20世纪80年代后）专家系统与知识工程在理论、技术和应用方面都有长足的进步和发展。出现了多专家系统、大型专家系统、微专家系统、分布式专家系统等。智能管理信息系统、智能决策支持系统、智能控制系统等。人工智能的发展概况u连接主义途径发展概况1、1943年，神经生理学家McCulloch 和Pitts提出M-P神经元模型。1944年，Hebb提出Hebb学习规则。2、1957年，Rosenblatt提出Perceptron单层神经网络模型。1962年，Widrow提出自适应线性元件Adaline。应用于天气预报、电子线路板分析、人工视觉等。3、1969年，Minsky和Papert发表Perceptrons，证明了单层人工神经网络无法实现一个简单的异或逻辑函数XOR，把神经网络的研究带入低谷。4、在低谷期，Kohonen Grossberg和Anderson等人仍坚持研究，取得了一些有价值的结果。5、20世纪80年代中期以后，神经网络研究复苏，掀起了新一轮研究热潮。1986年，Hopfield网络成功应用于TSP问题。1986年Rumelhart提出BP算法，解决了多层人工神经元网络的学习问题。1987年6月，第一届国际神经网络大会（IJCNN）召开，盛况空前。目前，NN与专家系统、知识工程成为AI的两个主流方向。NN在智能控制、信号处理、最优化、知识工程等领域都有成功应用。当前发展趋势u1、传统以符号处理为中心的人工智能与神经网络的结合。神经网络：识别 联想 学习 适应，负责对外界的感知和交互专家系统：判断 推理 搜索，负责高层的决策与控制u2、新理论、新技术的出现。Fuzzy,Genetic Algorithm,Chaos,Artificial life,Soft Computing,Computational Intelligence,Rough set,Data Mining,Knowledge discovery in database,Data warehouse,Situated AI,Agent-based distributed AI 等。第二章 基于谓词逻辑的机器推理谓词、函词、量词个体个体：研究对象中可以独立存在的具体的或抽象的客体。个体用个体常元或个体变元表示，如x,y,z,a,b,c,等。谓词谓词：描述个体性质及个体之间相互关系的词。如P、Q、R，等。例、命题“2是素数”中，2是个体，“是素数”是谓词。可表示为P(2).函词函词（函数）：某些个体是其它个体的函数，描述这种关系的词称为函词。例、命题“小李的父亲是医生”可表示为Doctor(father(Li).量词量词：存在量词“”；全称量词“”。例、“任何实数的平方都非负”可表示为 x(R(x)N(s(x)。“存在偶素数”可表示为 x(E(x)P(x)。一些命题的表示u凡是人都有名字 x(M(x)N(x)u不存在最大的整数x(G(x)y(G(y)D(x,y)x(G(x)y(G(y)D(y,x)u对所有的自然数，均有X+YXx y(N(x)N(y)S(x,y,x)u某些人对某些食物过敏 x y(M(x)F(y)G(x,y)谓词公式项的定义项的定义：1、个体常元和个体变元是项；2、设f是n元函词符号，t1,t2,tn是项，则f(t1,t2,tn)是项。3、只有有限次使用1，2得到的符号串才是项。原子公式原子公式：P是n元谓词，t1,t2,(tn是项，则P(t1,t2,tn)称为原子谓词公式(原子公式)(原子)。谓词公式谓词公式：1、原子公式是谓词公式；2、若A、B是谓词公式，则 A，A B，A B，A B，A B，xA，xA也是谓词公式；3、只有有限次地应用步骤1，2形成的符号串才是谓词公式。辖域辖域：xA 和 xA中，x称为量词的指导(作用)变元，A称为x的辖域。辖域中与该量词的指导变元相同的变元称为约束变元，其它变元(如果存在的话)称为自由变元。例、xP(x)；x(H(x)G(x,y)；xA(x)B(x)约束变元的改名约束变元的改名：两个规则部分逻辑蕴含式（p59-p60)析取三段论：A(A B)B假言推理（分离规则）：A(A B)B拒取式：B(A B)A假言三段论：(A B)(BC)A C二难推论:(A B)(A C)(BC)C全称指定规则US(Universal Specification)：xA(x)A(y)，y是个体域中任一确定元素。存在指定规则ES(Existential Specification)：xA(x)A(c)，c是个体域中某一确定元素。全称推广规则UG(Universal Generalization)：A(y)xA(x)，y是个体域中任一确定元素。存在推广规则 EG(Universal Generalization)：A(c)xA(x)，c是个体域中某一确定元素。自然演绎推理u以谓词公式的等价式及推理定律为基础进行的推理称为自然演绎推理。例见教材p61。u推理过程是一个符号变换过程，类似于人们使用自然语言进行推理的思维过程。u推理与谓词公式的含义无关，是一种形式推理。u自然演绎推理在机器上实施比较困难推理规则太多应用规则需要很强的模式识别能力中间结论的指数递增子句集u定义定义1 原子谓词公式及其否定称为文字文字；若干个文字的一个析取式称为一个子句子句；由r个文字组成的子句称为r-文文字子句字子句，1-文字子句称为单元子句单元子句，不含任何文字的子句称为空子句空子句，记为或NIL。u定义定义2 对一个谓词公式G，通过一定的步骤得到的子句集合S称为G的子句集子句集。子句集（1）、利用等价式A B A B和 A B (A B)(B A)消去联结词“”和“”。（2）、缩小否定联结词的作用范围，使其仅作用于原子公式。可利用下列等价式：A A；(AB)A B，(A B)A B；xA(x)x A(x)，xA(x)x A(x)（3）、重新命名变元名，使不同量词约束的变元有不同的名字。（4）、消去存在量词。若存在量词不在全称量词的辖域内，则用一个常量符号替换该存在量词辖域中的相应约束变元。这样的常量称为Skolem常量；若该存在量词在一个或多个全称量词的辖域内，则用这些全称量词指导变元的一个函数替换该存在量词约束的变元。这样的函数称为Skolem函数。例如x1 x2 xnyP(x1,x2,xn,y)中y可用Skolem函数f(x1,x2,xn)替换为x1 x2 xnP(x1,x2,xn,f(x1,x2,xn)。子句集（5）、把全称量词全部移到公式的左边。（6）、把全称量词后面的公式利用等价关系A(B C)(AB)(A C)化为子句的合取式，得到的公式称为Skolem标准形标准形。Skolem标准形的一般形式为x1 x2 xnM，其中M是子句的合取式。（7）、消去全称量词。（8）、对变元更名，使子句间无同名变元。（9）、消去合取词，以子句为元素组成的集合称为谓词公式的子句集。例：把如下谓词公式化为子句集。例：把如下谓词公式化为子句集。xyP(x,y)yQ(x,y)R(x,y)子句集求解过程求解过程 x yP(x,y)yQ(x,y)R(x,y)u1)xyP(x,y)yQ(x,y)R(x,y)u2)xyP(x,y)yQ(x,y)R(x,y)u3)xyP(x,y)zQ(x,z)R(x,z)u4)xP(x,f(x)Q(x,g(x)R(x,g(x)u5)P(x,f(x)Q(x,g(x)R(x,g(x)u6)P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)u7)P(x,f(x)Q(x,g(x)(P(y,f(y)R(y,g(y)u8)P(x,f(x)Q(x,g(x)，(P(y,f(y)R(y,g(y)u定理定理1 谓词公式G 不可满足当且仅当当且仅当其子句集S不可满足。子句集S是不可满足的是指其全部子句的合取式是不可满足的。命题逻辑中的归结原理u要证明在前提P下结论Q成立，即是证明P Q永真，这只须证明P Q不可满足。u根据定理1，只须证明P Q的子句集不可满足。由于子句之间是合取关系，只要有一个子句不满足，则整个子句集不可满足。u由于空子句是不可满足的，所以如果子句集中包含空子句，则该子句集是不可满足的。u若子句集中不包含空子句，则可通过Robinson提出的归结原理对子句集进行归结，归结过程保证子句集的不可满足性不变。一旦归结出空子句，则证明结束。u因此，归结原理把定理的证明化为子句集中归结出空子句的过程。命题逻辑中的归结原理定义定义、设L是一个文字，则称L与L为互补文字互补文字。定义定义、设C1、C2是命题逻辑中的两个子句，C1 中有文字L1，C 中有文字L，且L1与L互补，从C1，C中分别删除L1，L，再将剩余部分析取析取起来，构成的新子句C1称为C1与C2的归结式归结式（消解式），C1，C2称为C1的亲本子句亲本子句。C1=PQ R,C2=Q S,C1=P R S定理定理、归结式C1是其亲本子句C1与C2的逻辑结论。推论推论、设C1，C2是子句集S的两个子句，C1是它们的归结式，则（）若用C1代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性。即S1不可满足S不可满足）若把C1加入到S中，得到新子句集S，则S与S在不可满足意义上是等价的。即S2不可满足 S不可满足命题逻辑中的归结原理u例、用归结原理证明例、用归结原理证明R是是P,(P Q)R，(S U)Q，U的逻辑结果。的逻辑结果。u求子句集P,(PQ)R,(SU)Q,U,RP,(P Q)R,(S U)Q,U,RP,P Q R,S Q,U Q,U,R (子句集)u归结演绎P Q R R P Q P Q P QQ U Q U U U 替换与合一u问题的提出谓词逻辑和命题逻辑中使用归结原理的差别C1=P(x)Q(x),C2=P(a)R(y)C1=P(a)Q(a),C2=P(a)R(y)u定义 一个替换替换(Substitution)是形如t1/x1,t2/x2,tn/xn 的有限集合，其中t1,t2 ,tn 是项(替换的分子)，x1,x2,xn是互不相同的个体变元(替换的分母)。ti/xi表示用ti代换xi。ti与xi不同，xi也不能循环循环出现在tj中(j=1,2,n)。u基替换基替换(t1,t2 ,tn 均不含变元)、空替换空替换u例：a/x,g(c)/y,f(g(b)/z ，g(y)/x,f(x)/y替换与合一u定义7 设t1/x1,t2/x2,tn/xn 是一个替换，E是一个表达式，把E中出现的所有个体变元xi都用ti 替换，记为E，得到的结果称为E在下的替换实例替换实例(Instance)。Eg：E=P(x,y,g(z),a/x,f(b)/y,c/z，E=P(a,f(b),g(c)u定义 设t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,um/ym 是两个替换，则将集合t1 /x1,t2 /x2,tn /xn，u1/y1,u2/y2,um/ym 中符合下列条件的两种情形删除：ti /xi，当ti xi ui/yi，当yi x1,x2,xn 得到的集合仍是一个替换，称为与的复合复合或乘积乘积，记为 例:设=f(y)/x,z/y=a/x,b/y,y/z =f(b)/x,y/y,a/x,b/y,y/z=f(b)/x,y/z替换与合一u定义 设S=F1,F2,Fn 是一个原子谓词公式集，若存在一个替换，使得F1 F2 Fn，则称为S的一个合一合一(Unifier)，并称S为可合一的。一个公式集的合一一般不唯一u定义10 设是公式集S的一个合一，如果对S的任何一个合一，都存在一个替换，使得 ，则称为S的一个最一般合一最一般合一(Most General Unifier)，简称MGU 设S=P(u,y,g(y),P(x,f(u),z),有=u/x,f(u)/y,g(f(u)/z 对其它某个合一,如=a/x,f(a)/y,g(f(a)/z,a/u，可找到替换=a/u，使得 替换与合一u定义11 设S是一个非空的具有相同相同谓词名的原子公式集，从S中各公式的左边第一个项开始，同时向右比较，每一组不都相同的项的差异部分组成的集合称为S的差异集差异集。公式集S=P(a,x,f(g(y),P(z,h(z,u),f(u)的差异集为a,z,x,h(z,u),g(y),u 替换与合一u设S为一非空有限具有相同谓词名的原子谓词公式集，求S的MGU的算法：(1)令k=0,Sk=S,k=（表示空替换）(2)若Sk只含有一个谓词公式，则算法停止，k就是要求的最一般合一(3)求Sk的差异集Dk(4)若Dk中存在元素 xk 和 tk，其中xk是变元，tk是项且xk不在tk中出现，则置Sk+1=Sktk/xk，k+1=ktk/xk，k=k+1，然后转步(2)(5)算法停止，S的最一般合一不存在替换与合一u求S=P(a,x,f(g(y),P(z,h(z,u),f(u)的MGUk=0vS0=S,0=,D0=a,zv1=0a/z=a/zvS1=S0a/z=P(a,x,f(g(y),P(a,h(a,u),f(u)k=1vD1=x,h(a,u)v2=1h(a,u)/x=a/z h(a,u)/x=a/z,h(a,u)/xvS2=S1h(a,u)/x=P(a,h(a,u),f(g(y),P(a,h(a,u),f(u)替换与合一vS2=S1h(a,u)/x=P(a,h(a,u),f(g(y),P(a,h(a,u),f(u)k=2vD2=g(y),uv3=2g(y)/u=a/z,h(a,g(y)/x,g(y)/uvS3=S2g(y)/u=P(a,h(a,g(y),f(g(y),P(a,h(a,g(y),f(g(y)=P(a,h(a,g(y),f(g(y)k=3vS3为单元素集，所以3为所求的S的MGU说明：MGU可能是不唯一的，如Dk=xk,yk时谓词逻辑中的归结原理u定义12 设C1,C2是两个没有相同变元的子句，L1,L2分别是C1,C2中的两个文字，如果L1与L2有最一般合一，则子句C12=(C1-L1)(C2-L2)，称作C1和C2的二元归结式二元归结式(二元消解式二元消解式)。C1和C2称为C12的亲本亲本子句子句，L1，L2称为消解文字消解文字。例：C1=P(x)Q(x),C2=P(a)R(y),C12=Q(a)R(y)说明：当子句内部有可合一的文字时，应在归结前进行合一，使子句最简例：C1=P(x)P(f(a)Q(x)，则C1=P(f(a)Q(x)u归结原理：C1 C2(C1-L1)(C2-L2)谓词逻辑中的归结原理u归结时的注意事项谓词的一致性.名称不一致的谓词不能归结v P(x)，R(x)不能归结不能归结常量的一致性.含有不同常量的谓词不能归结vP(a,)，P(b,)不能归结不能归结变量与函数vP(x,x,)，P(x,f(x),)不能归结不能归结vP(x,x,)，P(x,f(y),)能归结能归结不能同时消去两个互补对vP Q 与 P Q 不能同时消去不能同时消去归结反演u归结反演：应用归结原理证明定理的过程u若F为已知前提的公式集，Q为结论，用归结反演证明Q为真的步骤是：（1）、否定Q，得到Q；（2）、把Q并入到公式集F中，得到F,Q；（3）、把公式集F,Q化为子句集S；（4）、应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，直到出现空子句，就证明了Q为真。u定理5（归结原理的完备性完备性）、如果子句集S是不可满足的，则必存在一个由S推出空子句的归结序列。归结反演举例例：自然数都是大于零的整数；所有整数不是偶数就是奇数；偶数除以例：自然数都是大于零的整数；所有整数不是偶数就是奇数；偶数除以2是整是整数。求证：所有自然数不是奇数就是其一半为整数的数。数。求证：所有自然数不是奇数就是其一半为整数的数。证明：前提：F1：x(N(x)GZ(x)I(x)N(x)：x是自然数是自然数 F2：x(I(x)E(x)O(x)GZ(x)：x0 I(x)：x是整数是整数 F3：x(E(x)I(h(x)E(x)：x是偶数是偶数 O(x)：x是奇数是奇数 结论：G：x(N(x)O(x)I(h(x)h(x)：half(x)F1、F2、F3 及G 化为子句集：（1）N(x)GZ(x)（2）N(y)I(y)（3）I(z)E(z)O(z)（4）E(u)I(h(u)（5）N(c)（6）O(c)（7）I(h(c)应用归结原理求解u应用归结原理求取问题答案的步骤把已知前提用谓词公式表示出来，并化为子句集S把待求解问题也用谓词公式表示出来，然后把它的否定与谓词谓词ANS构成析取式。ANS的变元应与问题的变元完全一致把此析取式化为子句集，并把该子句集并入S中得到子句集S对S应用归结原理进行归结若得到归结式ANS，则答案就在ANS中应用归结原理求解u例：设A、B、C三人中有人从不说真话，也有人从不说假话，某人向这三人分别提出同一个问题：谁是说谎者？谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个是说谎者”。问：谁是老实人？解、设T(x)表示x说真话。如果A说的是真话，则有：T(A)T(B)T(C)如果A说的是假话，则有：T(A)T(B)T(C)。同理，对B和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(A)T(B)T(C)4)T(B)T(C)5)T(A)T(B)T(C)6)T(C)T(A)7)T(C)T(B)把T(x)ANS(x)并入S8)T(x)ANS(x)9)T(A)ANS(C)(8,6,C/x)10)T(B)ANS(C)(7,8,C/x)11)T(B)ANS(C)(9,1)12)ANS(C)(10,11)归结策略 u归结反演的一般过程。步1将子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，则归结成功，结束。步3若CLAUSES表中存在可归结的子句对，则归结之，并将归结式并入CLAUSES表，转步；步4归结失败，退出。u穷举算法（广度优先策略）第一轮：将原子句集S中的子句两两归结，产生的归结式集合记为S1，再将S1并入CLAUSES表；第二轮：将新的CLAUSES表，即S S1中的子句与S1中的子句两两归结，产生的归结式集合记为S2，再将S2并入CLAUSES；第三轮：将新的CLAUSES表即S S1 S2中的子句与S2中的子句两两归结，。如此下去，直到出现空子句。归结策略例1 设有如下的子句集，用穷举算法归结如下：S：（1）PQ （2）PQ （3）P Q （4）P QS1：（5）Q (1),(2)（6）P (1),(3)（7）Q Q (1),(4)（8）P P (1),(4)（9）Q Q (2),(3)（10）P P (2),(3)（11）P (2),(4)（12）Q (3),(4)S2：（13）P Q (1),(7)（14）P Q (1),(8)归结策略（15）P Q (1),(9)（16）P Q (1),(10)（17）Q (1),(11)（18）P (1),(12)（19）Q (2),(6)（20）PQ (2),(7)（21）PQ (2),(8)（22）PQ (2),(9)（23）PQ (2),(10)（24）P (2),(12)（25）P (3),(5)（26）P Q (3),(7)（27）P Q (3),(8)（28）P Q (3),(9)（29）P Q (3),(10)（30）Q (3),(11)（31）P (4),(5)（32）Q (4),(6)（33）P Q (4),(7)（34）P Q (4),(8)（35）P Q (4),(9)（36）P Q (4),(10)（37）Q (5),(7)（38）Q (5),(9)（39）(5),(12)归结策略u定义：设C1，C2是两个子句，若存在替换，使得C1 C2，则称子句C1类含类含C2。P(x)类含P(a)Q(y)P(x)类含P(a)u删除策略。在归结过程中可随时删除以下子句：（1）、含有纯文字的子句。v纯文字纯文字是指在子句中无补文字的文字。vP(x)Q(x,y)R(x)，P(a)Q(u,v)，Q(b,z)，P(w)v解释：永远无法得到空子句（2）、含有永真式的子句；v解释：对子句集的不可满足性不起作用（3）、被子句集中别的子句类含的子句。v解释：C=P(x)替换后得C=P(a)，D=P(a)Q(y)归结策略u使用删除策略，例1可简化为：（1）PQ （7）P (2),(4)（2）PQ （8）Q (3),(4)（3）P Q （9）(5),(8)（4）P Q（5）Q (1),(2)（6）P (1),(3)u删除策略的特点：删除策略的思想是及早删除无用字句，以避免无效归结，缩小搜索空间。删除策略是完备完备的。一个归结策略是完备的，是指对于不可满足的子句集，使用该策略进行归结，最终必导出空子句。归结策略u支持集策略支持集支持集：目标公式的否定的子句集支持集策略：每次归结时，两个亲本子句中至少要有一个是目标公式否定的子句或其后裔。支持集策略的特点：v支持集策略实际是一种目标制导目标制导的反向反向推理。v支持集策略是完备的。u线性归结策略在归结过程中，除第一次归结可都用初始子句集S中的子句外，其它的各次归结至少要有一个亲本子句是前次归结的结果。线性归结策略的特点：完备、高效、与别的策略兼容。归结策略u归结策略的类型简化性策略v思想：尽量简化子句和子句集，以减少和避免无效归结。v缺点：额外开销(eg:检验、真值计算)限制性策略v思想：缩小搜索范围，提高搜索效率有序性策略v思想：给子句安排一定的顺序，一边尽快推出空子句u归结反演的一般算法步1将子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，则归结成功，结束。步3按某种策略在CLAUSES表中寻找可归结的子句对，若存在则归结之，并将归结式并入CLAUSES表，转步；步4归结失败，退出。第四章 图搜索技术u搜索：根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程。u应用：结构不良问题，无成熟算法；或有算法，但问题复杂，如博弈u图：由节点和有向边组成的网络u图的分类：或图(状态图、直接图)与或图状态图u状态图的概念迷宫问题八数码难题/华容道问题u以上问题的本质：在某个有向图中寻找目标或路径，该有向图称为状态空间图状态空间图或状态图状态图。u状态状态是描述问题求解过程中任一时刻的状况。引起状态中某些分量发生变化，从而使问题从一个状态变为另一个状态的操作、规则、变换称为算符算符。问题求解就是寻找一个从初始状态到目标状态的算符序列的过程。问题求解过程可描述为一个有向图，其中的节点节点代表状态，边边表示状态转换之间的算符。2 31 8 47 6 51 2 38 47 6 5状态图搜索u搜索树：搜索过程中经过的节点和边按原图的连接关系构成一个树型的有向图，称为搜索树。u搜索方式树式搜索：记录搜索过程中所经过的所有节点和边线式搜索：记录当前认为是所找路径上的节点和边v不可回溯(随机碰撞式搜索)v可回溯 (穷举式搜索)u两种方式下路径的获得树式搜索：反向求解线式搜索：搜索线本身状态图搜索u搜索策略盲目搜索(无向导)：按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。启发式搜索(有向导)：在搜索过程中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。u按搜索范围的扩展顺序不同广度优先搜索深度优先搜索搜索算法uCLOSED表和OPEN表u树式搜索算法步1 把初始节点放入OPEN表；步2 检查OPEN表，若为空，则问题无解，退出；步3 移出OPEN表中第一个节点N并放入CLOSED表中，并编号为n;步4 考察节点N是否为目标节点，若是，则搜索成功，退出；步5 若N不可扩展，则转步2；步6 扩展节点N，生成所有子节点，对这组子节点作如下处理：v（1）、如果有节点N的先辈节点，则删除；v（2）、如果有已存在于OPEN表的节点，也删除；但删除之前要比较其返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原指向父节点的指针，使其指向新的父节点。v（3）、如果有已存在于CLOSED表中的节点，则作与（2）同样的处理，并且再将其移出CLOSED表，放入OPEN表重新扩展；v（4）、对其余子节点，配上指向父节点n的指针后放入OPEN表，对OPEN表按某种搜索策略排序后转步2。搜索算法u不回溯的线式搜索步1 把初始节点S0放入CLOSED表中；步2 令N=S0；步3 若N是目标节点，则搜索成功，结束;步4 若N不可扩展，则搜索失败，退出。步5 扩展N，选取一个未在CLOSED表中出现的子节点N1放入CLOSED表中，令N=N1，转步3。u可回溯的线式搜索步1 把初始节点S0放入CLOSED表中；步2 令N=S0；步3 若N是目标节点，则搜索成功，结束;步4 若N不可扩展，则移出CLOSED表的末端节点Ne，若Ne=S0，则搜索失败，退出。否则，以CLOSED表新的末端节点Ne作为N,即令N=Ne，转步4步5 扩展N，选取一个未在CLOSED表中出现的子节点N1放入CLOSED表中，令N=N1，转步3。穷举式搜索u广度优先搜索：优先在同一级节点中考察，只有当同一级节点扩展完以后，才扩展下一级节点。u广度优先搜索算法：步1 把初始节点S0放入OPEN表中；步2 若OPEN表为空，则搜索失败，退出；步3 取OPEN表中前面第一个节点N放入CLOSED表中；步4 若目标节点Sg=N，则搜索成功，结束;步5 若N不可扩展，则转步2。步6 扩展N，将其所有子节点配上指向N的指针依次放入OPEN表的尾尾部部，转步2。(OPEN表为一个队列表为一个队列)u例、解八数码问题。初始状态例、解八数码问题。初始状态(2，3，1，8，4，7，6，5)，目标状态，目标状态(1，2，3，8，4，7，6，5)2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目标82 3 41 8 7 6 54穷举式搜索u深度优先搜索：在搜索的每一层，始终只扩展一个节点，不断地向纵深前进，直到不能再前进时，才从当前节点返回到上一级节点，延另一节点又继续前进。u深度优先搜索算法：步1 把初始节点S0放入OPEN表中；步2 若OPEN表为空，则搜索失败，退出；步3 取OPEN表中前面第一个节点N放入CLOSED表中；步4 若目标节点Sg=N，则搜索成功，结束;步5 若N不可扩展，则转步2。步6 扩展N，将其所有子节点配上指向N的返回指针依次放入OPEN表的首部首部，转步2。(OPEN表为一个堆栈表为一个堆栈)穷举式搜索u广度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低u深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解最坏情况时，搜索空间等同于穷举是一个通用的与问题无关的方法穷举式搜索u有界深度优先搜索：搜索深度限制。当深度优先搜索到一定深度后，就不在向纵深搜索，而是改变方向继续搜索。u有界深度搜索算法步1 把初始节点S0放入OPEN表中，置S0的深度d(S0)=0；步2 若OPEN表为空，则搜索失败，退出；步3 取OPEN表中前面第一个节点N放入CLOSED表中；步4 若目标节点Sg=N，则搜索成功，结束;步5 若N的深度d(N)=dm，或者N无子节点，则转步2。步6 扩展N，将其所有子节点Ni配上指向N的返回指针后依次放入OPEN表的前部，置d(Ni)=d(N)+1，转步2。启发式搜索u问题的提出穷举法的局限性组合爆炸：梵塔问题，博弈：国际象棋10120，围棋10761u启发性信息（1）、用于扩展节点的选择的信息；（2）、用于生成节点的选择的信息；（3）、用于删除节点的选择的信息。Eg：八数码问题u启发函数用来估计搜索树上节点X与目标节点Sg接近程度的函数，记为h(x).启发式搜索算法u(1)全局择优搜索算法：步1 把初始节点S0放入OPEN表中，计算h(S0)；步2 若OPEN表为空，则搜索失败，退出；步3 取OPEN表中前面第一个节点N放入CLOSED表中；步4 若目标节点Sg=N，则搜索成功，结束;步5 若N不可扩展，则转步2。步步6 扩展N，计算每个子节点x的函数值h(x)，并将所有子节点配上指向N的返回指针放入OPEN表中，再对OPEN表中的所有子节点所有子节点按其函数值大小以升序排序，转步2。Eg:八数码问题 P95u(2)局部择优搜索扩展节点后仅对N的子节点按启发函数值排序后放入OPEN的首部。(问题：优秀个体的后代未必优秀)加权状态图搜索u加权状态图与代价树Eg:交通图加权状态图的搜索要增加权值的计算与传播过程，并且要由权值来确定节点的扩展顺序。代价：g(xj)=g(xi)+c(xi,xj);g(S0)=0.u分支界限法：相当于启发式搜索中的全局择优搜索，不过用代价函数代替启发函数。u最近择优法：相当于启发式搜索中的局部择优搜索，不过用代价函数代替启发函数。启发式搜索的A算法和A*算法u估价函数f(x)=g(x)+h(x);其中g(x)是代价函数，h(x)是启发函数。或定义为：f(x)=d(x)+h(x);d(x)是x的深度g(x),h(x)对搜索的影响u最小代价搜索uA算法步1 把附有f(S0)的初始节点S0放入OPEN表中；步2 若OPEN表为空，则搜索失败，退出；步3 取OPEN表中前面第一个节点N放入CLOSED表中；步4 若目标节点Sg=N，则搜索成功，结束;步5 若N不可扩展，则转步2。启发式搜索的A算法和A*算法步6 扩展N，计算每个子节点x的估价函数值f(x)，并对这组子节点作如下处理：v（1）考察是否有已在OPEN表或CLOSED表中存在的节点；若有，则再考察其中有无N的先辈节点，若有则删除之；对于其余节点，也删除之，但由于它们又被第二次生成，因而需考虑是否修改已经存在于 OPEN表或CLOSED表中的这些节点及其后裔的返回指针和f(x)值，修改原则是“抄f(x)值小的路走”；v（2）对其余子节点配上指向N的返回指针后放入OPEN表中，并对OPEN表按f(x)值以升序排序，转步2。v 可以看出，A算法是树式搜索算法加估价函数f(x)的一种启发式搜索算法。启发式搜索的A算法和A*算法uA算法加上限制：对所有节点x均有h(x)h*(x)。其中h*(x)是从节点x到目标节点的最小代价。h(x)为启发式函数。u由Nilsson提出u定理1 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。u定理2 对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。u定理3(可采纳性定理)：若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。状态图问题求解u问题的状态图表示状态：节点；记录、对象、规则：边；数据对(x,y)，条件语句(if x y)，一个问题的状态图表示为一个三元组(S,F,G)S:初始状态集；G:目标状态集；F:状态转换规则集合u迷宫问题的状态图表示 P99u显式状态图u八数码问题的状态图表示 P100u隐式状态图uTSP问题与或图u与或图的引入u本质：复杂问题分解为简单问题u与或树 与或图u状态图和与或图的关系目标目标初始节点与或图u解树：问题的求解路径构成的树。u本原问题：直接可解的简单问题。u终止节点：本原问题对应的节点。u端节点：无子节点的节点。终止节点一定是端节点，反之不成立。u与节点：子节点之间是“与”关系的节点。u或节点：子节点之间是“或”关系的节点。与或图搜索u搜索特点：边扩展边判断u可解判断终止节点是可解节点一个与节点可解，当且仅当其子节点全部可解一个或节点可解，只要其子节点中至少一个可解u不可解判断非终止节点的端节点是不可解节点一个与节点不可解，只要其子节点中至少一个不可解一个或节点可解，当且仅当其子节点全部不可解u盲目搜索(穷举(广度/深度)，盲目碰撞)，启发式搜索与或树搜索u步1 把初始节点S0放入OPEN表中；u步2 取OPEN表中第一个节点N放入CLOSED表中；u步3 若节点N可扩展，则做下列工作：1.扩展N，将其所有子节点配上指向父节点N的指针后放入OPEN表；2.考察这些子节点中是否有终止节点。若有，则标记它们为可解节点，并将它们也放入CLOSED表，然后由它们的可解返回推断其先辈节点的可解性，并对其中的可解节点进行标记。如果初始节点也被标记为可解节点，则搜索成功，结束。3.删去OPEN表中那些具有可解先辈的节点（因为其先辈节点已经可解，故已无考察节点的必要），转步2。u步4 若N不可扩展，则做下列工作：1.标记N为不可解节点，然后由它的不可解返回推断其先辈节点的可解性，并对其中的不可解节点进行标记。如果初始节点也被标记为不可解节点，则搜索失败，退出。2.删去OPEN表中那些具有不可解先辈的节点（因为其先辈节点已不可解，没必要再考察这些节点），转步2。P112.例例4.16启发式与或树搜索u最优解树最优解树：代价最小的解树称为最优解树。u有序搜索有序搜索：每次确定欲扩展的节点时，先往前多看几步。计算一下扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩展。u解树的代价(树根的代价)：自下而上逐层计算u代价的计算方法：设g(x)表示节点x的代价，c(x,y)表示节点x到其子节点y的代价（即边xy的代价），则若x是终止节点，g(x)=0；若x是或节点，g(x)=min1 i nc(x,yi)+g(yi)若x是与节点：和代价法和代价法：g(x)=1 i nc(x,yi)+g(yi)最大代价法最大代价法：g(x)=max1 i nc(x,yi)+g(yi)对非终止端节点x，g(x)=P113.例例4.17希望树u定义启发函数来估算子节点的代价u节点扩展后需重新计算u希望树是在不断变化的，但总是包含初始节点u希望树的定义初始节点S0在希望树T中如果节点x在希望树T中，则一定有v如果x是具有子节点y1，y2，yn的“或”节点，则具有min1 i nc(x,yi)+g(yi)值的那个子节点yi也应在T中v如果x是与节点，则它的全部子节点都应在T中与或树的有序搜索过程u是一个不断选择修正希望树的过程u算法如下：步1 把初始节点S0放入OPEN表中步2 求出希望树T，即根据当前搜索树中节点的代价g求出以S0为根的希望树T步3 依次把OPEN表中T的端节点N选出放入CLOSED表中步4 若节点N是终止节点，则做下列工作v1.标记N为可解节点v2.对T应用可解标记过程，把N的先辈节点中的可解节点都标记为可解节点v3.若初始节点S0能被标记为可解节点，则T就是最优解树，成功退出v4.否则，从OPEN表中删去具有可解先辈的所有节点与或树的有序搜索过程步5 若N不是终止节点且不可扩展(不可解不可解)，则做下列工作v1.标记N为不可解节点v2.对T应用不可解标记过程，把N的先辈节点中的不可解节点都标记为不可解节点v3.若初始节点S0也被标记为不可解节点，则失败退出v4.否则，从OPEN表中删去具有不可解先辈的所有节点步6 若N不是终止节点，但它可扩展，则做下列工作v1.扩展节点N，产生N的所有子节点v2.把这些子节点都放入OPEN表中，并为每一个子节点配置指向父节点N的指针v3.计算这些子节点的g值及其先辈节点的g值步7 转步2P115.例例4.18博弈树搜索u“二人零和、全信息、非偶然”博弈：（1）、对垒的A、B双方轮流采取行动。结局有三种情况：A方胜，B方败；A方败，B方胜；双方平局。（2）、对垒过程中，任何一方都了解当前的格局和过去的历史。（3）、任何一方都要选取对自己最有利而对对方最不利的对策。不存在碰运气的偶然因素。u博弈树的概念描述博弈过程的与或树u博弈树的特点（1）、博弈的初始格局是初始节点。（2）、在博弈树中，“或”节点和“与”节点是逐层交替出现逐层交替出现的。自己一方扩展的节点是“或”的关系，对方扩展的节点之间是“与”的关系。（3）、所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜