人工智能技术导论

人工智能技术导论第1页，共187页，2023年，2月20日，星期日参考书《人工智能》马少平、朱小燕编著，清华大学出版社《人工智能及其应用》蔡自兴、徐光祐编著，清华大学出版社

ArtificialIntelligenceANewSynthesis(人工智能)NilsJ.Nilsson第2页，共187页，2023年，2月20日，星期日第一章人工智能概述人工智能的概念人工智能的研究途经与方法人工智能的分工领域人工智能的基本技术人工智能的发展概括第3页，共187页，2023年，2月20日，星期日什么是人工智能人工智能(ArtificialIntelligence)是指由计算机实现的人造智能。作为一门学科，人工智能可定义为：人工智能是一门研究如何构造智能机器（智能计算机）或智能系统，使它能模拟、延伸、扩展人类智能的学科人工智能是一门交叉边缘学科，与人工智能有关的学科有：计算机科学、数学、语言学、神经生理学、神经心理学、脑科学、认知科学、逻辑学、控制论等第4页，共187页，2023年，2月20日，星期日什么是人的智能智能是人脑的属性和产物。智能具有的主要特征：A、具有感知能力。通过视觉、听觉、触觉、味觉和嗅觉感知外部世界。B、具有记忆与思维能力。记忆能存储由感知器官感知到的外部信息以及由思维所产生的知识。思维用于对记忆的信息进行处理。思维可分为逻辑思维和形象思维。C、具有学习能力及自适应能力。D、具有行为能力。发现规律应用规律分析问题解决问题图灵测试中文屋子问题（约翰·希尔勒）第5页，共187页，2023年，2月20日，星期日为什么要研究人工智能现有计算机系统的局限性。智能低下、缺乏自学习、自适应、自优化能力。人类智能的局限性。学习能力因人而异、学习速度慢、效率低。信息化社会的迫切要求。第6页，共187页，2023年，2月20日，星期日人工智能的目标近期目标：使现有的电子数字计算机能模拟人类的部分智能行为。远期目标：制造智能计算机，使计算机具有看、听、说等感知和交互能力、具有联想、推理、理解、学习等高级思维能力，还要有分析问题、解决问题和发明创造的能力。深蓝（32CPU，200万次/秒，200万个棋局）第7页，共187页，2023年，2月20日，星期日人工智能的表现形式智能软件智能设备智能网络智能计算机智能机器人智能体(Agent)(艾真体)第8页，共187页，2023年，2月20日，星期日人工智能的研究途径与方法结构模拟（神经计算、生理学派、连接主义）模拟人脑的神经网络结构实现智能。主要特征：1、通过神经元之间的并行协同作用实现信息处理，具有并行性、动态性、全局性。2、通过神经元间分布式的物理联接存储信息。联想记忆、容错性。3、通过神经元间连接强度的动态调整实现自学习和自适应功能。4、善于模拟人类的形象思维过程。第9页，共187页，2023年，2月20日，星期日人工智能的研究途径与方法功能模拟（符号主义、心理学派、逻辑学派）以人脑的心理模型为基础，将问题或知识表示成某种逻辑网络，采用符号推演的方法，实现搜索、推理和学习等功能。主要特征：1、立足于逻辑运算和符号操作，适合于模拟人的逻辑思维过程。2、知识用显式的符号表示，容易表达人的心理模型。3、现有的数字计算机可以方便地实现高速的符号处理。4、能与传统的符号数据库进行链接，易于模块化。5、以知识为基础。第10页，共187页，2023年，2月20日，星期日人工智能的研究途径与方法行为模拟（行为主义、进化主义、控制论学派）基于感知-行为模型的研究途径和方法。模拟人在控制过程中的智能活动和行为特征：自寻优、自适应、自组织、自学习。强调智能系统与环境的交互，认为智能取决于感知和行动,智能行为可以不要知识。智能只有放在环境中才是真正的智能，智能的高低体现在对环境的适应性上Brooks，机器虫第11页，共187页，2023年，2月20日，星期日人工智能的分支领域基于脑功能模拟的领域划分1、机器感知（信息输入）。使计算机具有类似于人的感知能力，能通过“感知”直接从外界获取信息，是对人的感知的模拟及延伸。机器视觉、机器听觉。相关学科：模式识别（语音识别、图像识别）。信息->电信号序列->预处理->提取特征->模式匹配2、机器联想。基于内容的联想，与具体存储位置无关。联想存储技术。3、机器推理。又称为计算机推理、自动推理，是人工智能的核心课题之一。推理：从一些已知判断（前提）推出一个新判断（结论）的思维过程。演绎推理、归纳推理、类比推理确定性推理、不确定性推理基于概率逻辑的或然推理(随机性)、基于模糊逻辑的似然推理(模糊性)串行推理、并行推理第12页，共187页，2023年，2月20日，星期日人工智能的分支领域4、机器学习。使机器自己获取知识。对人类已有知识的获取、对客观规律的发现、对自身行为的修正。机器学习分为：机械学习、指导学习、解释学习、类比学习、示例学习、发现学习等。这些属于符号学习。另外还有神经网络学习。5、机器理解。图形理解（物景分析）、自然语言理解。理解是感知的延伸和深化。6、机器行为（机器人行动规划）。智能机器人的核心技术，反映了机器人的智能水平解决问题依靠规划功能确定行动步骤和动作序列任务：在一个特定的工作区域中自动生成从初始状态到目标状态的动作序列、运动路径和轨迹的控制程序第13页，共187页，2023年，2月20日，星期日人工智能的分支领域基于研究途径和实现技术的领域划分1、符号智能以符号知识为基础，通过符号推理进行问题求解知识工程(知识获取、知识表示、知识管理、知识运用、知识库系统)、符号处理2、计算智能以数据为基础，通过数值计算进行问题求解人工神经网络、进化计算(遗传算法、遗传程序设计、进化规划、进化策略)、模糊技术、人工生命第14页，共187页，2023年，2月20日，星期日人工智能的分支领域基于应用领域的领域划分1、难题求解难题的概念路径规划、组合优化、天气预报、股市分析、市场预测、机器博弈NP(NondeterministicPolynomial)和NPC(NondeterministicPolynomialComplete)问题难题求解技术能促进人工智能其他领域的发展2、自动定理证明自然演绎法、判定法、定例证明器、计算机辅助证明四色问题(1976.6,K.Appeel)。3、自动程序设计超级编译系统自动程序综合和自动程序验证。第15页，共187页，2023年，2月20日，星期日人工智能的分支领域4、自动翻译。机器翻译。自然语言理解。一边站着一个人他想起来了5、智能控制1965，KS.FU(傅京孙)提出将启发式推理规则用于学习控制系统6、智能管理。人工智能与管理科学、系统工程和计算机技术的结合。7、智能决策。人工智能应用于决策支持系统。8、智能通讯。在通讯的各个环节和层次上实现智能化。如网控、转接、信息转换等。使通讯网随时运行于最佳状态。9、智能仿真。仿真是在三种类型知识-描述性知识、目的性知识和处理知识的基础上产生另一种形式的知识-结论性知识。10、智能CAD。人工智能应用于CAD的设计自动化、智能交互、智能图形学、自动数据采集方面。11、智能CAI。人工智能应用于CAI：自动生成各种问题与练习、自动选择与调整教学内容和进度、自动生成答案、自然语言理解能力、不断改善教学策略。第16页，共187页，2023年，2月20日，星期日人工智能的分支领域基于应用系统的领域划分1、专家系统。基于人类专家知识的程序系统。能模拟专家的思维方式。2、知识库系统。3、智能数据库系统。传统数据库系统+人工智能。4、智能机器人系统。具备感知、思维、人-机通讯和运动能力。第17页，共187页，2023年，2月20日，星期日人工智能的分支领域基于计算机系统结构的领域划分1、智能操作系统。并行性、分布性和智能性。2、智能多媒体系统。人工智能与多媒体技术的有机结合。3、智能计算机系统。4、智能网络系统。模糊和神经网络技术应用于网络的业务量预测和控制、资源动态分配、动态路由选择等方面。第18页，共187页，2023年，2月20日，星期日人工智能的分支领域基于实现工具与环境的领域划分1、智能软件工具。人工智能程序设计语言，如表处理语言LISP、逻辑程序设计语言PROLOG、面向对象程序设计语言Smalltalk等。知识表示语言FRL、OPS5。专家系统工具、知识工程工具等。2、智能硬件平台。直接支持智能系统开发和运行的机器硬件。第19页，共187页，2023年，2月20日，星期日人工智能的分支领域基于体系结构的领域划分集中式人工智能（个体智能）分布式人工智能（群体智能）个体智能的组合或叠加DPS（分布式问题求解），自顶向下MAS（多智能体系统），自底向上第20页，共187页，2023年，2月20日，星期日人工智能的基本技术推理技术。推理是智能的核心。推理以逻辑为基础。基于谓词逻辑的自然演绎推理和归结反演推理。基于非标准逻辑如多值逻辑、模态逻辑、时态逻辑、模糊逻辑、非单调逻辑的推理。搜索技术。人工智能的基本技术。许多智能活动的过程，都可以看作或抽象为一个“问题求解”过程。“问题求解”就是在问题空间中进行搜索的过程。盲目搜索、启发式搜索。神经网络搜索。知识表示与知识库技术。知识表示是指知识在计算机中的表示方式。知识表示要符合知识的逻辑结构和物理结构，并适合于计算机存储和处理。知识库由知识构成。知识的组织、管理、维护和优化。第21页，共187页，2023年，2月20日，星期日人工智能的基本技术归纳技术。机器自动提取概念、获取知识、发现规律的技术。归纳技术与知识获取和机器学习密切相关。基于符号处理的归纳和基于神经网络的归纳。数据库知识发现（KDD,KnowledgeDiscoveryinDatabase)和数据挖掘(DataMining)技术。联想技术。联想记忆，联想存储。第22页，共187页，2023年，2月20日，星期日人工智能的发展概况孕育期（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年，世界上第一台电子计算机诞生。第23页，共187页，2023年，2月20日，星期日人工智能的发展概况人工智能学科的产生（1956年）

1956年夏季，McCarthy,Minsky,Lochester,Shannon,More,Samuel,Selfridge,Solomonff,Newell,Simon等十人在Dartmouth大学召开历时两个多月的研讨会，讨论机器智能的有关问题。由McCarthy提出“人工智能”一词，人工智能从此成为一门学科。第24页，共187页，2023年，2月20日，星期日人工智能的发展概况符号主义AI发展概况1、形成（1956-1965）（人工智能的推理期。结构良好问题。搜索策略和算法）（1）、1956年，Samuel的跳棋程序。1959,1962（2）、定理证明方面，1956年Newell等的逻辑理论机（LT）程序；1958年，王浩的工作；1965年，Robinson提出的消解原理。（3）、模式识别方面，1959年Selfridge的模式识别程序；1965年Roberts编制了可以分辨积木构造的程序。（4）、问题求解方面。1960年，Newell的通用问题求解(GPS)程序。（5）、1960年，McCarthy研制成功LISP语言。第25页，共187页，2023年，2月20日，星期日人工智能的发展概况人工智能的知识期（1965-70年代末）（1）、专家系统方面。1965年，Feigenbaum的专家系统DENDRAL，1968年投入使用。DENDRAL对知识表示、存储、获取和推理的技术为以后的专家系统的建造树立了榜样，对AI的发展产生了深刻的影响。之后著名的专家系统有：医学专家系统MYCIN，地质勘探专家系统PROSPECTOR，计算机配置专家系统R1等。（2）、1969年，国际人工智能联合会议(IJCAI)召开。1970年，“ArtificialIntelligence”杂志创刊。（3）、1977年，Feigenbaum在第五届国际人工智能会议上，提出了“知识工程”的概念。发展期（20世纪80年代后）专家系统与知识工程在理论、技术和应用方面都有长足的进步和发展。出现了多专家系统、大型专家系统、微专家系统、分布式专家系统等。智能管理信息系统、智能决策支持系统、智能控制系统等。第26页，共187页，2023年，2月20日，星期日人工智能的发展概况连接主义途径发展概况1、1943年，神经生理学家McCulloch和Pitts提出M-P神经元模型。1944年，Hebb提出Hebb学习规则。2、1957年，Rosenblatt提出Perceptron单层神经网络模型。1962年，Widrow提出自适应线性元件Adaline。应用于天气预报、电子线路板分析、人工视觉等。3、1969年，Minsky和Papert发表《Perceptrons》，证明了单层人工神经网络无法实现一个简单的异或逻辑函数XOR，把神经网络的研究带入低谷。4、在低谷期，KohonenGrossberg和Anderson等人仍坚持研究，取得了一些有价值的结果。5、20世纪80年代中期以后，神经网络研究复苏，掀起了新一轮研究热潮。1986年，Hopfield网络成功应用于TSP问题。1986年Rumelhart提出BP算法，解决了多层人工神经元网络的学习问题。1987年6月，第一届国际神经网络大会（IJCNN）召开，盛况空前。目前，NN与专家系统、知识工程成为AI的两个主流方向。NN在智能控制、信号处理、最优化、知识工程等领域都有成功应用。第27页，共187页，2023年，2月20日，星期日当前发展趋势1、传统以符号处理为中心的人工智能与神经网络的结合。神经网络：识别联想学习适应，负责对外界的感知和交互专家系统：判断推理搜索，负责高层的决策与控制2、新理论、新技术的出现。Fuzzy,GeneticAlgorithm,Chaos,Artificiallife,SoftComputing,ComputationalIntelligence,Roughset,DataMining,Knowledgediscoveryindatabase,Datawarehouse,SituatedAI,Agent-baseddistributedAI

等。第28页，共187页，2023年，2月20日，星期日第二章基于谓词逻辑的机器推理谓词、函词、量词个体：研究对象中可以独立存在的具体的或抽象的客体。个体用个体常元或个体变元表示，如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))。第29页，共187页，2023年，2月20日，星期日一些命题的表示凡是人都有名字x(M(x)N(x))不存在最大的整数x(G(x)y(G(y)D(x,y))

x(G(x)y(G(y)D(y,x))对所有的自然数，均有X+Y>Xxy(N(x)N(y)S(x,y,x))某些人对某些食物过敏xy(M(x)F(y)G(x,y))第30页，共187页，2023年，2月20日，星期日谓词公式项的定义：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，AB，AB，AB，AB，xA，xA也是谓词公式；3、只有有限次地应用步骤1，2形成的符号串才是谓词公式。辖域：xA和xA中，x称为量词的指导(作用)变元，A称为x的辖域。辖域中与该量词的指导变元相同的变元称为约束变元，其它变元(如果存在的话)称为自由变元。例、xP(x)；x(H(x)G(x,y))；xA(x)B(x)约束变元的改名

：两个规则第31页，共187页，2023年，2月20日，星期日部分逻辑蕴含式（p59-p60)析取三段论：

A(AB)B假言推理（分离规则）：A(AB)B拒取式：B(AB)A假言三段论：(AB)(BC)AC二难推论:(AB)

(AC)(BC)C全称指定规则US(UniversalSpecification)：xA(x)A(y)，y是个体域中任一确定元素。存在指定规则ES(ExistentialSpecification)：xA(x)A(c)，c是个体域中某一确定元素。全称推广规则UG(UniversalGeneralization)：A(y)xA(x)，y是个体域中任一确定元素。存在推广规则EG(UniversalGeneralization)：A(c)xA(x)，c是个体域中某一确定元素。第32页，共187页，2023年，2月20日，星期日自然演绎推理以谓词公式的等价式及推理定律为基础进行的推理称为自然演绎推理。例见教材p61。推理过程是一个符号变换过程，类似于人们使用自然语言进行推理的思维过程。推理与谓词公式的含义无关，是一种形式推理。自然演绎推理在机器上实施比较困难推理规则太多应用规则需要很强的模式识别能力中间结论的指数递增第33页，共187页，2023年，2月20日，星期日子句集定义1

原子谓词公式及其否定称为文字；若干个文字的一个析取式称为一个子句；由r个文字组成的子句称为r-文字子句，1-文字子句称为单元子句，不含任何文字的子句称为空子句，记为□或NIL。定义2

对一个谓词公式G，通过一定的步骤得到的子句集合S称为G的子句集。第34页，共187页，2023年，2月20日，星期日子句集（1）、利用等价式ABAB和AB(AB)(BA)消去联结词“”和“”。（2）、缩小否定联结词的作用范围，使其仅作用于原子公式。可利用下列等价式：

AA；(AB)

AB，(AB)AB；xA(x)xA(x)，xA(x)xA(x)（3）、重新命名变元名，使不同量词约束的变元有不同的名字。（4）、消去存在量词。若存在量词不在全称量词的辖域内，则用一个常量符号替换该存在量词辖域中的相应约束变元。这样的常量称为Skolem常量；若该存在量词在一个或多个全称量词的辖域内，则用这些全称量词指导变元的一个函数替换该存在量词约束的变元。这样的函数称为Skolem函数。例如x1x2•••xnyP(x1,x2,…,xn,y)中y可用Skolem函数f(x1,x2,…,xn)替换为x1x2•••xnP(x1,x2,…,xn,f(x1,x2,…,xn))。第35页，共187页，2023年，2月20日，星期日子句集（5）、把全称量词全部移到公式的左边。（6）、把全称量词后面的公式利用等价关系A(BC)

(AB)(AC)化为子句的合取式，得到的公式称为Skolem标准形。Skolem标准形的一般形式为x1x2•••xnM，其中M是子句的合取式。（7）、消去全称量词。（8）、对变元更名，使子句间无同名变元。（9）、消去合取词，以子句为元素组成的集合称为谓词公式的子句集。例：把如下谓词公式化为子句集。x{yP(x,y)y[Q(x,y)R(x,y)]}第36页，共187页，2023年，2月20日，星期日子句集求解过程x{yP(x,y)y[Q(x,y)R(x,y)]}1)x{yP(x,y)y[Q(x,y)R(x,y)]}2)x{yP(x,y)y[Q(x,y)

R(x,y)]}3)x{yP(x,y)z[Q(x,z)R(x,z)]}4)x{P(x,f(x))[Q(x,g(x))R(x,g(x))]}5)P(x,f(x))[Q(x,g(x))R(x,g(x))]6)[P(x,f(x))Q(x,g(x))](P(x,f(x))R(x,g(x))]7)[P(x,f(x))Q(x,g(x))](P(y,f(y))R(y,g(y))]8){P(x,f(x))Q(x,g(x))，(P(y,f(y))R(y,g(y))}定理1谓词公式G不可满足当且仅当其子句集S不可满足。子句集S是不可满足的是指其全部子句的合取式是不可满足的。第37页，共187页，2023年，2月20日，星期日命题逻辑中的归结原理要证明在前提P下结论Q成立，即是证明PQ永真，这只须证明PQ不可满足。根据定理1，只须证明PQ的子句集不可满足。由于子句之间是合取关系，只要有一个子句不满足，则整个子句集不可满足。由于空子句是不可满足的，所以如果子句集中包含空子句，则该子句集是不可满足的。若子句集中不包含空子句，则可通过Robinson提出的归结原理对子句集进行归结，归结过程保证子句集的不可满足性不变。一旦归结出空子句，则证明结束。因此，归结原理把定理的证明化为子句集中归结出空子句的过程。第38页，共187页，2023年，2月20日，星期日命题逻辑中的归结原理定义４、设L是一个文字，则称L与L为互补文字。定义５、设C1、C2是命题逻辑中的两个子句，C1

中有文字L1

，C２中有文字L２，且L1与L２互补，从C1，C２中分别删除L1

，L２，再将剩余部分析取起来，构成的新子句C1２称为C1与C2的归结式（消解式），C1，C2称为C1２的亲本子句。C1=PQR,C2=QS,C1２

=PRS定理２、归结式C1２是其亲本子句C1与C2的逻辑结论。推论、设C1，C2是子句集S的两个子句，C1２是它们的归结式，则（１）若用C1２代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性。即 S1不可满足S不可满足２）若把C1２加入到S中，得到新子句集S２，则S２与S在不可满足意义上是等价的。即 S2不可满足

S不可满足第39页，共187页，2023年，2月20日，星期日命题逻辑中的归结原理例、用归结原理证明R是P,(PQ)R，(SU)Q，U的逻辑结果。求子句集P,(PQ)R,(SU)Q,U,RP,(PQ)R,(SU)Q,U,RP,PQR,SQ,UQ,U,R(子句集)归结演绎PQRRPQPQPQQUQUUU□第40页，共187页，2023年，2月20日，星期日替换与合一问题的提出谓词逻辑和命题逻辑中使用归结原理的差别C1=P(x)Q(x),C2=P(a)R(y)C1’=P(a)Q(a),C2’=P(a)R(y)定义６一个替换(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)。基替换(t1,t2,…,tn均不含变元)、空替换ε例：｛a/x,g(c)/y,f(g(b))/z}，{g(y)/x,f(x)/y}第41页，共187页，2023年，2月20日，星期日替换与合一定义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))定义８设＝{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}第42页，共187页，2023年，2月20日，星期日替换与合一定义９设S={

F1,

F2,…,

Fn}是一个原子谓词公式集，若存在一个替换，使得F1＝

F2＝…＝

Fn，则称为S的一个合一(Unifier)，并称S为可合一的。一个公式集的合一一般不唯一定义10设是公式集S的一个合一，如果对S的任何一个合一，都存在一个替换，使得＝·，则称为S的一个最一般合一(MostGeneralUnifier)，简称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}，使得＝·第43页，共187页，2023年，2月20日，星期日替换与合一定义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}第44页，共187页，2023年，2月20日，星期日替换与合一设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=Sk{tk/xk}，k+1=k·{tk/xk}，k=k+1，然后转步(2)(5)算法停止，S的最一般合一不存在第45页，共187页，2023年，2月20日，星期日替换与合一求S={P(a,x,f(g(y))),P(z,h(z,u),f(u))}的MGUk=0S0=S,0=,D0={a,z}1=0·{a/z}={a/z}S1=S0{a/z}={P(a,x,f(g(y))),P(a,h(a,u),f(u))}k=1D1={x,h(a,u)}2=1·{h(a,u)/x}={a/z}·{h(a,u)/x}={a/z,h(a,u)/x}S2=S1{h(a,u)/x}={P(a,h(a,u),f(g(y))),P(a,h(a,u),f(u))}第46页，共187页，2023年，2月20日，星期日替换与合一S2=S1{h(a,u)/x}={P(a,h(a,u),f(g(y))),P(a,h(a,u),f(u))}k=2D2={g(y),u}3=2·{g(y)/u}={a/z,h(a,g(y))/x,g(y)/u}S3=S2{g(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=3S3为单元素集，所以3为所求的S的MGU说明：MGU可能是不唯一的，如Dk={xk,yk}时第47页，共187页，2023年，2月20日，星期日谓词逻辑中的归结原理定义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)归结原理：C1C2(C1-{L1})(C2-{L2})第48页，共187页，2023年，2月20日，星期日谓词逻辑中的归结原理归结时的注意事项谓词的一致性.名称不一致的谓词不能归结P(x)，R(x)不能归结常量的一致性.含有不同常量的谓词不能归结P(a,…)，

P(b,…)不能归结变量与函数P(x,x,…)，P(x,f(x),…)不能归结P(x,x,…)，P(x,f(y),…)能归结不能同时消去两个互补对PQ与P

Q不能同时消去第49页，共187页，2023年，2月20日，星期日归结反演归结反演：应用归结原理证明定理的过程若F为已知前提的公式集，Q为结论，用归结反演证明Q为真的步骤是：（1）、否定Q，得到Q；（2）、把Q并入到公式集F中，得到{F,Q}；（3）、把公式集{F,Q}化为子句集S；（4）、应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，直到出现空子句，就证明了Q为真。定理5（归结原理的完备性）、如果子句集S是不可满足的，则必存在一个由S推出空子句的归结序列。第50页，共187页，2023年，2月20日，星期日归结反演举例例：自然数都是大于零的整数；所有整数不是偶数就是奇数；偶数除以2是整数。求证：所有自然数不是奇数就是其一半为整数的数。证明：前提：F1

：x(N(x)GZ(x)I(x))N(x)：x是自然数

F2

：x(I(x)E(x)O(x))GZ(x)：x>0I(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))归结：（8）I(c)((2),(5),c/y)（9）I(c)E(c)((3),(6),c/z)（10）E(c)((8),(9))（11）I(h(c))((4),(10),c/u)（12）((7),(11))第51页，共187页，2023年，2月20日，星期日应用归结原理求解应用归结原理求取问题答案的步骤把已知前提用谓词公式表示出来，并化为子句集S把待求解问题也用谓词公式表示出来，然后把它的否定与谓词ANS构成析取式。ANS的变元应与问题的变元完全一致把此析取式化为子句集，并把该子句集并入S中得到子句集S‘对S‘应用归结原理进行归结若得到归结式ANS，则答案就在ANS中第52页，共187页，2023年，2月20日，星期日应用归结原理求解例：设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)第53页，共187页，2023年，2月20日，星期日应用归结原理求解化为子句集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)因此C是老实人。无论如何归结，推不出ANS(A),ANS(B)第54页，共187页，2023年，2月20日，星期日归结策略归结反演的一般过程。步1将子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，则归结成功，结束。步3若CLAUSES表中存在可归结的子句对，则归结之，并将归结式并入CLAUSES表，转步２；步4归结失败，退出。穷举算法（广度优先策略）第一轮：将原子句集S中的子句两两归结，产生的归结式集合记为S1，再将S1并入CLAUSES表；第二轮：将新的CLAUSES表，即SS1中的子句与S1中的子句两两归结，产生的归结式集合记为S2，再将S2并入CLAUSES；第三轮：将新的CLAUSES表即SS1S2中的子句与S2中的子句两两归结，…。如此下去，直到出现空子句。第55页，共187页，2023年，2月20日，星期日归结策略例1设有如下的子句集，用穷举算法归结如下：S：（1）PQ

（2）PQ

（3）PQ

（4）

PQS1：（5）Q[(1),(2)]

（6）P[(1),(3)]

（7）QQ[(1),(4)]

（8）PP[(1),(4)]

（9）QQ[(2),(3)]

（10）PP[(2),(3)]

（11）P[(2),(4)]

（12）Q[(3),(4)]S2：（13）P

Q[(1),(7)]（14）P

Q[(1),(8)]第56页，共187页，2023年，2月20日，星期日归结策略（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）PQ[(3),(7)]（27）PQ[(3),(8)]（28）PQ[(3),(9)]（29）PQ[(3),(10)]（30）Q[(3),(11)]（31）

P[(4),(5)]（32）Q[(4),(6)]（33）PQ[(4),(7)]（34）PQ[(4),(8)]（35）PQ[(4),(9)]（36）PQ[(4),(10)]（37）Q[(5),(7)]（38）Q[(5),(9)]（39）□[(5),(12)]第57页，共187页，2023年，2月20日，星期日归结策略定义：设C1，C2是两个子句，若存在替换，使得C1C2

，则称子句C1类含C2

。

P(x)类含P(a)Q(y)P(x)类含P(a)删除策略。在归结过程中可随时删除以下子句：（1）、含有纯文字的子句。纯文字是指在子句中无补文字的文字。{P(x)Q(x,y)R(x)，

P(a)Q(u,v)，

Q(b,z)，

P(w)}解释：永远无法得到空子句（2）、含有永真式的子句；解释：对子句集的不可满足性不起作用（3）、被子句集中别的子句类含的子句。解释：C=P(x)替换后得C=P(a)，D=P(a)Q(y)第58页，共187页，2023年，2月20日，星期日归结策略使用删除策略，例1可简化为：（1）PQ（7）

P[(2),(4)]（2）PQ（8）Q[(3),(4)]（3）PQ（9）□[(5),(8)]（4）

PQ（5）Q[(1),(2)]（6）P[(1),(3)]删除策略的特点：删除策略的思想是及早删除无用字句，以避免无效归结，缩小搜索空间。删除策略是完备的。一个归结策略是完备的，是指对于不可满足的子句集，使用该策略进行归结，最终必导出空子句。第59页，共187页，2023年，2月20日，星期日归结策略支持集策略支持集：目标公式的否定的子句集支持集策略：每次归结时，两个亲本子句中至少要有一个是目标公式否定的子句或其后裔。支持集策略的特点：支持集策略实际是一种目标制导的反向推理。支持集策略是完备的。线性归结策略在归结过程中，除第一次归结可都用初始子句集S中的子句外，其它的各次归结至少要有一个亲本子句是前次归结的结果。线性归结策略的特点：完备、高效、与别的策略兼容。第60页，共187页，2023年，2月20日，星期日归结策略归结策略的类型简化性策略思想：尽量简化子句和子句集，以减少和避免无效归结。缺点：额外开销(eg:检验、真值计算)限制性策略思想：缩小搜索范围，提高搜索效率有序性策略思想：给子句安排一定的顺序，一边尽快推出空子句归结反演的一般算法步1将子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，则归结成功，结束。步3按某种策略在CLAUSES表中寻找可归结的子句对，若存在则归结之，并将归结式并入CLAUSES表，转步２；步4归结失败，退出。第61页，共187页，2023年，2月20日，星期日第四章图搜索技术搜索：根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程。应用：结构不良问题，无成熟算法；或有算法，但问题复杂，如博弈图：由节点和有向边组成的网络图的分类：或图(状态图、直接图)与或图第62页，共187页，2023年，2月20日，星期日状态图状态图的概念迷宫问题八数码难题/华容道问题以上问题的本质：在某个有向图中寻找目标或路径，该有向图称为状态空间图或状态图。状态是描述问题求解过程中任一时刻的状况。引起状态中某些分量发生变化，从而使问题从一个状态变为另一个状态的操作、规则、变换称为算符。问题求解就是寻找一个从初始状态到目标状态的算符序列的过程。问题求解过程可描述为一个有向图，其中的节点代表状态，边表示状态转换之间的算符。2318476512384765第63页，共187页，2023年，2月20日，星期日状态图搜索搜索树：搜索过程中经过的节点和边按原图的连接关系构成一个树型的有向图，称为搜索树。搜索方式树式搜索：记录搜索过程中所经过的所有节点和边线式搜索：记录当前认为是所找路径上的节点和边不可回溯(随机碰撞式搜索)可回溯(穷举式搜索)两种方式下路径的获得树式搜索：反向求解线式搜索：搜索线本身第64页，共187页，2023年，2月20日，星期日状态图搜索搜索策略盲目搜索(无向导)：按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。启发式搜索(有向导)：在搜索过程中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。按搜索范围的扩展顺序不同广度优先搜索深度优先搜索第65页，共187页，2023年，2月20日，星期日搜索算法CLOSED表和OPEN表树式搜索算法步1把初始节点放入OPEN表；步2检查OPEN表，若为空，则问题无解，退出；步3移出OPEN表中第一个节点N并放入CLOSED表中，并编号为n;步4考察节点N是否为目标节点，若是，则搜索成功，退出；步5若N不可扩展，则转步2；步6扩展节点N，生成所有子节点，对这组子节点作如下处理：（1）、如果有节点N的先辈节点，则删除；（2）、如果有已存在于OPEN表的节点，也删除；但删除之前要比较其返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原指向父节点的指针，使其指向新的父节点。（3）、如果有已存在于CLOSED表中的节点，则作与（2）同样的处理，并且再将其移出CLOSED表，放入OPEN表重新扩展；（4）、对其余子节点，配上指向父节点n的指针后放入OPEN表，对OPEN表按某种搜索策略排序后转步2。第66页，共187页，2023年，2月20日，星期日搜索算法不回溯的线式搜索步1把初始节点S0放入CLOSED表中；步2令N=S0

；步3若N是目标节点，则搜索成功，结束;步4若N不可扩展，则搜索失败，退出。步5扩展N，选取一个未在CLOSED表中出现的子节点N1放入CLOSED表中，令N=N1，转步3。可回溯的线式搜索步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。第67页，共187页，2023年，2月20日，星期日穷举式搜索广度优先搜索：优先在同一级节点中考察，只有当同一级节点扩展完以后，才扩展下一级节点。广度优先搜索算法：步1把初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出；步3取OPEN表中前面第一个节点N放入CLOSED表中；步4若目标节点Sg=N，则搜索成功，结束;步5若N不可扩展，则转步2。步6扩展N，将其所有子节点配上指向N的指针依次放入OPEN表的尾部，转步2。(OPEN表为一个队列)例、解八数码问题。初始状态(2，3，1，8，4，7，6，5)，目标状态(1，2，3，8，4，7，6，5)第68页，共187页，2023年，2月20日，星期日23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标8234187654第69页，共187页，2023年，2月20日，星期日穷举式搜索深度优先搜索：在搜索的每一层，始终只扩展一个节点，不断地向纵深前进，直到不能再前进时，才从当前节点返回到上一级节点，延另一节点又继续前进。深度优先搜索算法：步1把初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出；步3取OPEN表中前面第一个节点N放入CLOSED表中；步4若目标节点Sg=N，则搜索成功，结束;步5若N不可扩展，则转步2。步6扩展N，将其所有子节点配上指向N的返回指针依次放入OPEN表的首部，转步2。(OPEN表为一个堆栈)第70页，共187页，2023年，2月20日，星期日穷举式搜索广度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解最坏情况时，搜索空间等同于穷举是一个通用的与问题无关的方法第71页，共187页，2023年，2月20日，星期日穷举式搜索有界深度优先搜索：搜索深度限制。当深度优先搜索到一定深度后，就不在向纵深搜索，而是改变方向继续搜索。有界深度搜索算法步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。第72页，共187页，2023年，2月20日，星期日启发式搜索问题的提出穷举法的局限性组合爆炸：梵塔问题，博弈：国际象棋10120，围棋10761启发性信息（1）、用于扩展节点的选择的信息；（2）、用于生成节点的选择的信息；（3）、用于删除节点的选择的信息。Eg：八数码问题启发函数用来估计搜索树上节点X与目标节点Sg接近程度的函数，记为h(x).第73页，共187页，2023年，2月20日，星期日启发式搜索算法(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:八数码问题P95(2)局部择优搜索扩展节点后仅对N的子节点按启发函数值排序后放入OPEN的首部。(问题：优秀个体的后代未必优秀)第74页，共187页，2023年，2月20日，星期日加权状态图搜索加权状态图与代价树Eg:交通图加权状态图的搜索要增加权值的计算与传播过程，并且要由权值来确定节点的扩展顺序。代价：g(xj)=g(xi)+c(xi,xj);g(S0)=0.分支界限法：相当于启发式搜索中的全局择优搜索，不过用代价函数代替启发函数。最近择优法：相当于启发式搜索中的局部择优搜索，不过用代价函数代替启发函数。第75页，共187页，2023年，2月20日，星期日启发式搜索的A算法和A*算法估价函数f(x)=g(x)+h(x);其中g(x)是代价函数，h(x)是启发函数。或定义为：f(x)=d(x)+h(x);d(x)是x的深度g(x),h(x)对搜索的影响最小代价搜索A算法步1把附有f(S0)的初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出；步3取OPEN表中前面第一个节点N放入CLOSED表中；步4若目标节点Sg=N，则搜索成功，结束;步5若N不可扩展，则转步2。第76页，共187页，2023年，2月20日，星期日启发式搜索的A算法和A*算法步6扩展N，计算每个子节点x的估价函数值f(x)，并对这组子节点作如下处理：（1）考察是否有已在OPEN表或CLOSED表中存在的节点；若有，则再考察其中有无N的先辈节点，若有则删除之；对于其余节点，也删除之，但由于它们又被第二次生成，因而需考虑是否修改已经存在于OPEN表或CLOSED表中的这些节点及其后裔的返回指针和f(x)值，修改原则是“抄f(x)值小的路走”；（2）对其余子节点配上指向N的返回指针后放入OPEN表中，并对OPEN表按f(x)值以升序排序，转步2。可以看出，A算法是树式搜索算法加估价函数f(x)的一种启发式搜索算法。第77页，共187页，2023年，2月20日，星期日启发式搜索的A算法和A*算法A算法加上限制：对所有节点x均有h(x)h*(x)。其中h*(x)是从节点x到目标节点的最小代价。h(x)为启发式函数。由Nilsson提出定理1对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。定理2对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。定理3(可采纳性定理)：若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。第78页，共187页，2023年，2月20日，星期日状态图问题求解问题的状态图表示状态：节点；记录、对象、……规则：边；数据对(x,y)，条件语句(ifx…y…)，……一个问题的状态图表示为一个三元组(S,F,G)S:初始状态集；G:目标状态集；F:状态转换规则集合迷宫问题的状态图表示 P99显式状态图八数码问题的状态图表示 P100隐式状态图TSP问题第79页，共187页，2023年，2月20日，星期日与或图与或图的引入本质：复杂问题分解为简单问题与或树 与或图状态图和与或图的关系目标目标初始节点第80页，共187页，2023年，2月20日，星期日与或图解树：问题的求解路径构成的树。本原问题：直接可解的简单问题。终止节点：本原问题对应的节点。端节点：无子节点的节点。终止节点一定是端节点，反之不成立。与节点：子节点之间是“与”关系的节点。或节点：子节点之间是“或”关系的节点。第81页，共187页，2023年，2月20日，星期日与或图搜索搜索特点：边扩展边判断可解判断终止节点是可解节点一个与节