人工智能 第二版 课件 马少平 第0-4章 绪论、搜索问题-不确定性推理

第〇章绪论0.1人工智能的诞生人类对人造智能的幻想诸葛亮的木牛流马一种运输工具，解决几十万大军的粮草运输问题指南车“robot”一词的来历源于1921年的一部捷克

舞台剧《罗素姆万能机器人》人工智能的诞生图灵1950年发表论文《计算机与智能》“模仿游戏”图灵测试预测50年之后可以建造出可以通过图灵测试的智能机器。苦于没有合适的工具直到电子计算机的问世人工智能的诞生1956年达特茅斯夏季讨论会上，首次提出人工智能约翰·麦肯锡组织了这次研讨会，提出人工智能约翰·麦肯锡研讨会的参加者达特茅斯大学人工智能的诞生讨论会上的成果展示定理证明模式识别计算机下棋……研究方向明确让机器具有智能名称？充满争议复杂信息处理？人工智能？机器智能？达特茅斯会议讨论的内容自动计算机（这里的自动指可编程）编程语言神经网络计算规模理论（指计算复杂性）自我改进（指机器学习）抽象随机性与创造性0.2人工智能发展简史人工智能诞生60多年了，经历过几次高潮和低谷人工智能发展的5个时代：初期时代知识时代特征时代数据时代大模型时代0.2.1初期时代定理证明程序“逻辑理论家”研制者：赫伯特·西蒙（司马贺）和艾伦•纽厄尔达特茅斯会议做演示证明了《数学原理》第二章52个定理中的38个定理改进后证明了第二章全部52个定理初期时代通用问题求解器（GPS：GeneralProblemSolver）试图从逻辑的角度构造一个可以解决多种问题的问题求解器可以解决任何形式化的符号问题初期时代计算机下棋图灵很早就对计算机下棋做过研究达特茅斯夏季讨论会上就演示过计算机下棋信息论的提出者香农早期发表过论文《计算机下棋程序》，提出了极小极大算法，还和图灵一起探讨过计算机下棋问题约翰·麦卡锡在50年代提出了α-β剪枝算法的雏形Edwards、Timothy于1961年、Brudno于1963年分别独立提出了α-β剪枝算法1963年一个采用该算法的跳棋程序，战胜了美国康涅狄格州的跳棋大师罗伯特·尼尔利1997年战胜国际象棋大师卡斯帕罗夫的深蓝采用的也是α-β剪枝算法初期时代机器翻译机器翻译也是当时的一个研究热点。当时把这个问题看得有些简单化，认为只要建造一个强大的电子词典，借助于计算机的强大计算能力，就可以解决世界范围内的语言翻译问题初期时代陷入困境由于对人工智能研究的困难认识不足，很快就陷入了困境一个笑话英俄-俄英翻译：Thespiritiswillingbutthefleshisweak.（心有余而力不足）Thevodkaisstrongbutmeatisrotten.（伏特加酒虽然很浓但肉是腐烂的）俄语英译俄俄译英精神、烈性酒知识就是力量0.2.2知识时代专家系统世界上第一个专家系统DENDRALMYCIN奠定了专家系统的基本结构让人工智能走向了实用知识工程主要研究内容知识表示与使用不确定性推理人为知识表示爱德华·费根鲍姆知识获取的瓶颈问题很多知识难于整理只可意会不可言传例：如何骑自行车？能否实现自动学习呢？机器学习的诞生多种机器学习方法统计机器学习方法走向了实用0.2.3特征时代统计机器学习让人工智能走出了低谷优化技术特征映射（浅层）……人为特征定义莱斯利·瓦利安特和朱迪亚·佩尔特征提取的瓶颈很难定义合适的特征必须是计算机能够使用的特征例：汉字识别偏旁部首？语音识别什么是特征？能否自动抽取特征呢？从原始数据中抽取特征0.2.4数据时代深度学习（神经网络）2006年辛顿教授在《科学》期刊上发表论文提出深度学习两个标志性事件：语音识别ImageNet图像识别表示学习自动特征抽取不同层次的抽象特征特征映射（深层）……将人工智能推向了高潮杨立顿、辛顿和本吉奥新的问题如何实现知识与数据的融合？文本：知识的承载既是数据又是知识知识隐藏与数据之中0.2.5大模型时代ChatGPT的出现4大能力1大缺陷强大的语言理解能力强大的语言生成能力强大的交互能力强大的多任务求解能力一个重大缺陷：幻觉两大关键技术动态词向量注意力机制让人工智能上了一个新的台阶共同特点如何描述问题人工智能=描述+算法描述：说明问题，告诉计算机做什么算法：将智能问题转化为计算问题0.3什么是人工智能？由于智能的复杂性，很难给出统一的人工智能的定义帕特里克·温斯顿教授的定义：人工智能就是研究如何使计算机做过去只有人才能做的智能工作我们的定义：人工智能是探讨用计算机模拟人类智能行为的科学人工智能的本质：人工智能是研究如何制造出人造的智能机器或系统，来模拟人类智能活动的能力，以延伸人们智能的科学人工智能系统五要素算据算力算法算者算景AI系统年夜饭0.4图灵测试与中文屋子问题如何知道一个系统是否具有智能呢？1950年图灵发表论文《计算机与智能》提出了著名的“图灵测试”模仿游戏通过标准测试5分钟，超过30%的测试者误把机器当作人正确理解图灵测试误解1：将机器在某一方面的能力超过人类认作是通过了图灵测试误解2：将超过30%的测试者误把机器当作人类，理解为机器的回答中超过30%的内容与人类一致就通过了图灵测试。中文屋子问题通过图灵测试就一定具有智能吗？哲学家希尔勒对此提出质疑罗杰•施安克的故事理解程序“一个人进入餐馆并订了一份汉堡包。当汉堡包端来时发现被烘脆了，此人暴怒地离开餐馆，没有付帐或留下小费。”“一个人进入餐馆并订了一份汉堡包。当汉堡包端来后他非常喜欢它，而且在离开餐馆付帐之前，给了女服务员很多小费。”作为对“理解”故事的检验，可以向计算机询问，在每一种情况下，此人是否吃了汉堡包。中文屋子问题哲学家希尔勒提出中文屋子问题两个问题：行为模拟还是机理模拟考查的粒度问题0.5人工智能的发展方向人工智能存在的问题依靠大量的数据训练人工智能存在的问题不是理解而是猜测人工智能存在的问题人工智能存在的问题对抗样本人工智能存在的问题对围棋系统KataGo的攻击KataGo是一个类似于AlphaGo的围棋系统一个很弱的围棋AI通过诱导KataGo犯错的方式，以77%的胜率战胜KataGo人工智能的“阿喀琉斯之踵”目前的人工智能可能就存在这样的“死穴”一旦这些“死穴”被利用，就可能会带来不可预测的灾难性后果冥河第三代人工智能张钹院士提出第三代人工智能第一代：知识驱动以专家系统、知识工程为代表的基于知识的人工智能第二代：数据驱动以统计机器学习、深度学习为代表的基于数据的人工智能第三代人工智能第二代第三代数据充分数据不充分信息完全信息不完全信息确定信息不确定静态环境动态环境单一任务复合任务不安全安全不可信可信不可靠可靠不可扩展可扩展适应求解的任务存在的问题需要解决的问题达到的目标人工智能充满了挑战人工智能充满了希望第一章搜索问题内容： 状态空间的搜索问题。搜索方式：盲目搜索启发式搜索关键问题： 如何利用知识，尽可能有效地找到问题的解（最佳解）。42搜索问题（续1）S0Sg43搜索问题（续2）讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。441.1回溯策略例：皇后问题45()46()Q((1,1))47()QQ((1,1))((1,1)(2,3))48()Q((1,1))((1,1)(2,3))49()QQ((1,1))((1,1)(2,3))((1,1)(2,4))50()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))51()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))52()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))53()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))54()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))55()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))56()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))57()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))58递归的思想从前有座山……

从前有座山……

从前有座山……59递归的思想（续）当前状态目标状态g60一个递归的例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}NULLpLIST12361回溯搜索算法 BACKTRACK（DATA）

DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。62回溯搜索算法递归过程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);4, LOOP:IFNULL(RULES)RETURNFAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R,DATA);8, PATH:=BACKTRACK(RDATA);9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);63存在问题及解决办法解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态问题：深度问题死循环问题64回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：从初始到当前的状态表（逆向） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。65回溯搜索算法11, DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);66回溯搜索算法1（续）9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);67一些深入的问题失败原因分析、多步回溯QQ68一些深入问题（续）回溯搜索中知识的利用 基本思想(以皇后问题为例)： 尽可能选取划去对角线上位置数最少的。QQQQ3223691.2图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。

70一些基本概念节点深度： 根节点深度=0

其它节点深度=父节点深度+1012371一些基本概念（续1）路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。72一些基本概念（续1）扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。73一般的图搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);74一般的图搜索算法（续）7,标记和修改指针：

ADD(mj,OPEN),并标记mj到n的指针； 计算是否要修改mk、ml到n的指针； 计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；75节点类型说明…...…...…...…...…...mjmkml76修改指针举例123456s77修改指针举例（续1）123456s78123456修改指针举例（续2）s79123456修改指针举例（续3）s801.3无信息图搜索过程深度优先搜索宽度优先搜索81深度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目标在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GOLOOP;82231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标83深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法84宽度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G:=ADD(mi,G);7,IF目标在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),

并标记mj到n的指针;9,GOLOOP;8523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标823418765486宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法87渐进式深度优先搜索方法目的解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。思想 首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所以分支为止。881.4启发式图搜索利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解89希望：引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。90基本思想定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。911，启发式搜索算法A（A算法）评价函数的格式：

f(n)=g(n)+h(n) f(n)：评价函数

h(n)：启发函数92符号的意义g*(n)：从s到n的最短路径的耗散值h*(n)：从n到g的最短路径的耗散值f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值93A算法1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi}, 计算f(n,mi):=g(n,mi)+h(mi);

94A算法（续） ADD(mj,OPEN),标记mj到n的指针；

IFf(n,mk)<f(mk)THENf(mk):=f(n,mk), 标记mk到n的指针； IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml),

标记ml到n的指针, ADD(ml,OPEN);7,OPEN中的节点按f值从小到大排序；8,GOLOOP；95…...…...…...…...…...mjmkmlnab96Closed表Open表97一个A算法的例子定义评价函数：

f(n)=g(n)+h(n) g(n)为从初始节点到当前节点的耗散值

h(n)为当前节点“不在位”的将牌数

283164751238476598h计算举例 h(n)=42

831

64751234576

8992831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标1234561002，最佳图搜索算法A*（A*算法）在A算法中，如果满足条件：

h(n)≤h*(n)

则A算法称为A*算法。101A*条件举例8数码问题h1(n)=“不在位”的将牌数h2(n)=将牌“不在位”的距离和2

831

64751234576

8将牌1：1将牌2：1将牌6：1将牌8：2102A*算法的性质A*算法的假设

设ni、nj是任意两个节点，有：

C(ni,nj)>

其中

为大于0的常数几个等式

f*(s)=f*(t)=h*(s)=g*(t)=f*(n)

其中s是初始节点，t是目标节点，n是s到t的最佳路径上的节点。103A*算法的性质（续1）定理1.1： 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。104A*算法的性质（续2）引理1.1： 对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)>f*(s)。105A*算法的性质（续3）引理1.2：

A*结束前，OPEN表中必存在f(n)≤f*(s)。存在一个节点n，n在最佳路径上。f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)106A*算法的性质（续3）定理1.2： 对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。引理1.1：A*如果不结束，则OPEN中所有的n有f(n)>f*(s)引理1.2：在A*结束前，必存在节点n，使得f(n)≤f*(s)所以，如果A*不结束，将导致矛盾。107A*算法的性质（续4）推论1.1：

OPEN表上任一具有f(n)<f*(s)的节点n，最终都将被A*选作扩展的节点。

由定理1.2，知A*一定结束，由A*的结束条件，OPEN表中f(t)最小时才结束。而

f(t)≥f*(t)＝f*(s)

所以f(n)<f*(s)的n，均被扩展。得证。108A*算法的性质（续5）定理1.3(可采纳性定理)： 若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。109可采纳性的证明由定理1.1、1.2知A*一定找到一条路径结束设找到的路径s→t不是最佳的（t为目标）则：f(t)=g(t)>f*(s)由引理1.2知结束前OPEN中存在f(n)≤f*(s)的节点n，所以

f(n)≤f*(s)<f(t)因此A*应选择n扩展，而不是t。与假设A*选择t结束矛盾。得证。注意：A*的结束条件110A*算法的性质（续6）推论1.2：

A*选作扩展的任一节点n，有f(n)≤f*(s)。由引理2.2知在A*结束前，OPEN中存在节点n’，f(n’)≤f*(s)设此时A*选择n扩展。如果n＝n’，则f(n)≤f*(s)，得证。如果n≠n’，由于A*选择n扩展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得证。111A*算法的性质（续7）定理1.4：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n)>h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。简写：如果h2(n)>h1(n)(目标节点除外)，则A1扩展的节点数≥A2扩展的节点数112A*算法的性质（续7）注意：

在定理1.4中，评价指标是“扩展的节点数”，也就是说，同一个节点无论被扩展多少次，都只计算一次。113定理1.4的证明使用数学归纳法，对节点的深度进行归纳（1）当d(n)＝0时，即只有一个节点，显然定理成立。（2）设d(n)≤k时定理成立。（归纳假设）（3）当d(n)=k+1时，用反证法。设存在一个深度为k＋1的节点n，被A2扩展，但没有被A1扩展。而由假设，A1扩展了n的父节点，即n已经被生成了。因此当A1结束时，n将被保留在OPEN中。114定理1.4的证明（续1）所以有：f1(n)≥f*(s)

即：g1(n)+h1(n)≥f*(s)所以：h1(n)≥f*(s)-g1(n)另一方面，由于A2扩展了n，有f2(n)≤f*(s)即：h2(n)≤f*(s)–g2(n)(A)由于d(n)=k时，A2扩展的节点A1一定扩展，有

g1(n)≤g2(n)(因为A2的路A1均走到了)所以：h1(n)≥f*(s)-g1(n)≥f*(s)–g2(n)(B)比较A、B两式，有h1(n)≥h2(n)，与定理条件矛盾。故定理得证。115对h的评价方法平均分叉树 设共扩展了d层节点，共搜索了N个节点，则:

其中，b*称为平均分叉树。b*越小，说明h效果越好。实验表明，b*是一个比较稳定的常数，同一问题基本不随问题规模变化。116对h的评价举例例：8数码问题，随机产生若干初始状态。使用h1：

d=14,N=539, b*=1.44;d=20,N=7276， b*=1.47；使用h2：

d=14,N=113, b*=1.23; d=20,N=676, b*=1.27117A*的复杂性一般来说，A*的算法复杂性是指数型的，可以证明，当且仅当以下条件成立时：

abs(h(n)-h*(n))≤O(log(h*(n))) A*的算法复杂性才是非指数型的，但是通常情况下，h与h*的差别至少是和离目标的距离成正比的。1183，A*算法的改进问题的提出： 因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。119s(10)A(1)B(5)C(8)G目标631118一个例子：OPEN表CLOSED表s(10)s(10)A(7)B(8)C(9)A(7)s(10)B(8)C(9)G(14)A(5)C(9)G(14)C(9)G(12)B(7)G(12)A(4)G(12)G(11)B(8)s(10)A(5)B(8)s(10)C(9)A(5)s(10)B(7)C(9)s(10)A(4)B(7)C(9)s(10)120出现多次扩展节点的原因在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。s(10)A(1)B(5)C(8)G目标631118121解决的途径对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展。122改进的条件可采纳性不变不多扩展节点不增加算法的复杂性123对h加以限制定义：一个启发函数h，如果对所有节点ni和nj，其中nj是ni的子节点，满足

h(ni)-h(nj)≤c(ni,nj) h(t)=0

或

h(ni)≤c(ni,nj)+h(nj) h(t)=0

则称h是单调的。h(ni)ninjh(nj)c(ni,nj)124h单调的性质定理1.5： 若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。 即：当A*选n扩展时，有g(n)=g*(n)。125定理1.5的证明设n是A*扩展的任一节点。当n＝s时，定理显然成立。下面考察n≠s的情况。设P＝(n0=s,n1,n2,…,nk=n)是s到n的最佳路径P中一定有节点在CLOSED中，设P中最后一个出现在CLOSED中的节点为nj，则nj+1在OPEN中。126定理1.5的证明（续1）由单调限制条件，对P中任意节点ni有：

h(ni)≤C(ni,ni+1)+h(ni+1)

g*(ni)+h(ni)≤g*(ni)+C(ni,ni+1)+h(ni+1)由于ni、ni+1在最佳路径上，所以：

g*(ni+1)=g*(ni)+C(ni,ni+1)带入上式有：

g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)从i=j到i=k-1应用上不等式，有：

g*(nj+1)+h(nj+1)≤g*(nk)+h(nk)即：f(nj+1)≤g*(n)+h(n)

注意：(nj在CLOSED中，nj+1在OPEN中)127定理1.5的证明（续2）重写上式：f(nj+1)≤g*(n)+h(n)另一方面，A*选n扩展，必有：

f(n)=g(n)+h(n)≤f(nj+1)比较两式，有：

g(n)≤g*(n)但已知g*(n)是最佳路径的耗散值，所以只有：g(n)=g*(n)。得证。128h单调的性质（续）定理1.6： 若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。即f(ni)≤f(nj)。

129定理1.6的证明由单调限制条件，有：

h(ni)–h(nj)≤C(ni,nj)=f(ni)-g(ni)=f(nj)-g(nj)

f(ni)-g(ni)-f(nj)+g(nj)≤C(ni,nj)=g(ni)+C(ni,nj)

f(ni)-g(ni)-f(nj)+g(ni)+C(ni,nj)≤C(ni,nj)

f(ni)-f(nj)

≤0，得证。130h单调的例子8数码问题：h为“不在位”的将牌数

1 h(ni)-h(nj)=0 (nj为ni的后继节点)-1 h(t)=0 c(ni,nj)=1

满足单调的条件。 131对算法加以改进一些结论：OPEN表上任以具有f(n)<f*(s)的节点定会被扩展。A*选作扩展的任一节点，定有f(n)≤f*(s)。132改进的出发点OPEN=(…

…

…

…)f*(s)f值小于f*(s)的节点f值大于等于f*(s)的节点fm：到目前为止已扩展节点的最大f值，用fm代替f*(s)133修正过程A1,OPEN:=(s),f(s)=g(s)+h(s),fm:=0;2,LOOP:IFOPEN=()THENEXIT(FAIL);3,NEST:={ni|f(ni)<fm} IFNEST≠()THENn:=NEST中g最小的节点

ELSEn:=FIRST(OPEN), fm:=f(n);4,…,8:同过程A。134s(10)A(1)B(5)C(8)G目标631118前面的例子：OPEN表CLOSED表fms(0+10)s(0+10)10A(6+1)B(3+5)C(1+8)s(0+10)C(1+8)10A(6+1)B(2+5)s(0+10)C(1+8)B(2+5)10A(3+1)s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0)135h的单调化方法如果令：

f(n)=max(f(n的父节点),g(n)+h(n))

则容易证明，这样处理后的h是单调的。136IDA*算法(IterativeDeepeningA*)基本思想：回溯与A*的结合算法简介（非严格地）

1，设初始值f0；

2，集合S＝NULL；

3，用回溯法求解问题，如果节点n的f值大于f0，则将该节点放入集合S中，并回溯；

4，如果在3中找到了解，则结束；

5，如果3以失败结束，则f0＝S中节点的最小f值；

6，返回到2。137知识的灵活应用例：如何转动，使得每个扇区数字和为12。13551441332523123122552342543433分析：阴影部分数字和：48

直径部分数字和：24

转45°改变阴影部分转90°改变直径部分但不改变阴影部分转180°改变扇区部分但不改变阴影部分也不改变直径部分1384，其他的搜索算法爬山法（局部搜索算法）139其他的搜索算法（续1）随机搜索算法动态规划算法 如果对于任何n，当h(n)=0时，A*算法就成为了动态规划算法。140动态规划st第一阶段第二阶段第三阶段第四阶段第五阶段1415，搜索算法实用举例汉字识别后处理一个例子我钱线载哦栽哉裁劣绥 优仍们仿伦奶砧犯扔妨 要耍密穷安壁驻努窑垂 扳报叔嵌奴振技寂叙蔽 奋夯杏蚕香脊秀吞吝番 精猜指洁括治捐活冶桔 种神衬祥科钟拌样拎补

142汉字识别后处理二元语法时：为常量用识别信度代替问题变为求最大143第二章谓词逻辑与归结推理概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理归结推理命题逻辑谓词逻辑Skolem标准形、子句集基本概念谓词逻辑归结原理合一和置换、控制策略数理逻辑命题逻辑归结Herbrand定理第二章谓词逻辑与归结推理概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制概述归结原理由J.A.Robinson由1965年提出。与演绎法(deductiveinference)完全不同，新的逻辑演算(inductiveinference)算法。一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题。

第二章谓词逻辑与归结推理概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理第二章谓词逻辑与归结推理概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理命题逻辑的归结法命题逻辑基础：定义：合取式：p与q，记做pΛ

q析取式：

p或q，记做p∨

q蕴含式：如果p则q，记做p→

q等价式：p当且仅当q，记做p<=>

q

。。。。。。命题逻辑基础定义：若A无成假赋值，则称A为重言式或永真式；若A无成真赋值，则称A为矛盾式或永假式；若A至少有一个成真赋值，则称A为可满足的；析取范式：仅由有限个简单合取式组成的析取式。合取范式：仅由有限个简单析取式组成的合取式。命题逻辑基础基本等值式24个(1)交换率：p∨q<=>q

∨p

；

pΛq<=>qΛp

结合率：(p∨q)∨

r<=>p∨(q∨r); (pΛq)Λ

r<=>pΛ(qΛr)分配率：p∨(qΛ

r)<=>(p∨q)Λ(p∨r)

；

pΛ(q∨

r)<=>(pΛq)∨(pΛr)

命题逻辑基础基本等值式（1）摩根率:～

(p∨q)

<=>～

pΛ

～

q

；

～

(pΛq)

<=>～

p∨

～

q

吸收率:p∨(pΛq)<=>p

；

pΛ(p∨q)<=>p

同一律:p∨0

<=>p

；

pΛ1

<=>p

蕴含等值式:p→

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q

命题例命题：能判断真假（不是既真又假）的陈述句。

简单陈述句描述事实、事物的状态、关系等性质。例如：1．

1+1=22．

雪是黑色的。3．

北京是中国的首都。4．

到冥王星去渡假。

判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一。以上的例子都是陈述句，第4句的真值现在是假，随着人类科学的发展，有可能变成真，但不管怎样，真值是唯一的。因此，以上4个例子都是命题。而例如：1．

快点走吧！

2．

到那去？

3．

x+y>10

等等句子，都不是命题。命题表示公式（1）将陈述句转化成命题公式。如：设“下雨”为p，“骑车上班”为q，，1．“只要不下雨，我骑自行车上班”。～p

是q的充分条件， 因而，可得命题公式：～p→q2．“只有不下雨，我才骑自行车上班”。～p

是q的必要条件， 因而，可得命题公式：q→～p命题表示公式（2）例如：1．

“如果我进城我就去看你，除非我很累。” 设：p，我进城，q，去看你，r，我很累。 则有命题公式：～r→(p→q)。2．“应届高中生，得过数学或物理竞赛的一等奖， 保送上北京大学。” 设：p，应届高中生，q，保送上北京大学上学，

r，是得过数学一等奖。t，是得过物理一等奖。 则有命题公式公式：p

∧(r∨t)→

q。

命题逻辑的归结法基本单元：简单命题（陈述句）例：

命题：A1、A2、A3

和B求证：A1ΛA2ΛA3成立，则B成立，即：A1ΛA2ΛA3→B反证法：证明A1ΛA2ΛA3Λ～B是矛盾式（永假式）

命题逻辑的归结法建立子句集合取范式：命题、命题和的与，如：

PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命题（元素）的集合例：命题公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}

命题逻辑的归结法归结式消除互补对，求新子句→得到归结式。如子句：C1,C2， 归结式：R(C1,C2)=C1ΛC2

注意：C1ΛC2→R(C1,C2)

，反之不一定成立。命题逻辑的归结法归结过程

将命题写成合取范式求出子句集对子句集使用归结推理规则归结式作为新子句参加归结归结式为空子句□，S是不可满足的（矛盾），原命题成立。（证明完毕）谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。命题逻辑归结例题（1）例题，证明公式：(P→Q)→(～Q→～P)证明：（1）根据归结原理，将待证明公式转化成待归结命题公式：

(P→Q)∧～(～Q→～P)（2）分别将公式前项化为合取范式：

P→Q＝～P∨Q

结论求～后的后项化为合取范式： ～(～Q→～P)＝～(Q∨～P)＝～Q∧P

两项合并后化为合取范式： （～P∨Q）∧～Q∧P

（3）则子句集为：

{～P∨Q，～Q，P}命题逻辑归结例题（2）子句集为： {～P∨Q，～Q，P}（4）对子句集中的子句进行归结可得：1.

～P∨Q2.

～Q3.

P4.

Q， （1，3归结）5.

， （2，4归结）

由上可得原公式成立。第二章谓词逻辑与归结推理概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理第二章谓词逻辑与归结推理概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理谓词归结原理基础一阶逻辑基本概念个体词：表示主语的词谓词：刻画个体性质或个体之间关系的词量词：表示数量的词谓词归结原理基础

小王是个工程师。

8是个自然数。 我去买花。 小丽和小华是朋友。其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词“是朋友”表示两个个体词之间的关系。谓词归结原理基础一阶逻辑公式及其解释个体常量：a,b,c个体变量：x,y,z谓词符号：P,Q,R量词符号：

,

谓词归结原理基础例如：（1）所有的人都是要死的。（2）

有的人活到一百岁以上。在个体域D为人类集合时，可符号化为：（1）

xP(x)，其中P(x)表示x是要死的。（2）

xQ(x),其中Q(x)表示x活到一百岁以上。在个体域D是全总个体域时，引入特殊谓词R(x)表示x是人，可符号化为：（1）

x（R(x)→P(x)）,

其中，R(x)表示x是人；P(x)表示x是要死的。（2）

x（R(x)∧Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百岁以上。

谓词归结原理基础量词否定等值式：～(

x

）

M（x）<=>（

y

）～

M（y）～(

x

）

M（x）<=>（

y

）～

M（y）量词分配等值式：(

x

）(

P（x）ΛQ（x）)<=>(

x

）

P（x）Λ(

x

）

Q（x）(

x

）(

P（x）∨

Q（x）)<=>(

x

）

P（x）∨

(

x

）

Q（x）消去量词等值式：设个体域为有穷集合（a1,a2,…an）(

x

）

P（x）<=>P（a1

）ΛP（a2

）Λ…ΛP（an

）(

x

）P（x）<=>P（a1

）∨

P（a2

）∨

…

∨

P（an

）谓词归结原理基础量词辖域收缩与扩张等值式：(

x

）(

P（x）∨Q)<=>(

x

）

P（x）∨Q(

x

）(

P（x）ΛQ)<=>(

x

）

P（x）ΛQ

(

x

）(

P（x）→Q)<=>(

x

）

P（x）→Q

(

x

）(Q

→P（x）)<=>Q

→(

x

）

P（x）(

x

）(

P（x）∨Q)<=>(

x

）

P（x）∨Q(

x

）(

P（x）ΛQ)<=>(

x

）

P（x）ΛQ

(

x

）(

P（x）→Q)<=>(

x

）

P（x）→Q

(

x

）(Q

→P（x）)<=>Q

→(

x

）

P（x）谓词归结子句形(Skolem标准形)SKOLEM标准形前束范式

定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。谓词归结子句形(Skolem标准形)即：把所有的量词都提到前面去，然后消掉所有量词

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)约束变项换名规则：(Qx

）

M（x）<=>（Qy

）

M（y）(Qx

）

M（x,z）<=>（Qy

）

M（y,z）谓词归结子句形(Skolem标准形)

量词消去原则： 消去存在量词“

”，略去全程量词“

”。 注意：左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，改写成为常量。

谓词归结子句形(Skolem标准形)

Skolem定理： 谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。SKOLEM标准形定义： 消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。谓词归结子句形(Skolem标准形)例:将下式化为Skolem标准形： ～(

x)(

y)P(a,x,y)→(

x)(～(

y)Q(y,b)→R(x))解：第一步，消去→号，得： ～(～(

x)(

y)P(a,x,y))∨(

x)(～～(

y)Q(y,b)∨R(x))第二步，～深入到量词内部，得：

(

x)(

y)P(a,x,y)∨(

x)((

y)Q(y,b)∨R(x))第三步，变元易名，得

(

x)((

y)P(a,x,y)∨(u)(v)(Q(v,b)∨R(u))第四步，存在量词左移，直至所有的量词移到前面，得：

(

x)(

y)(u)(v)P(a,x,y)∨(Q(v,b)∨R(u))由此得到前述范式谓词归结子句形(Skolem标准形)

第五步，消去“

”（存在量词），略去“

”全称量词 消去(

y)，因为它左边只有(

x)，所以使用x的函数f(x)代替之，这样得到：

(

x)(

z)(P(a,x,f(x))∧～Q(z,b)∧～R(x))

消去(

z)，同理使用g(x)代替之，这样得到：

(

x)(P(a,x,f(x))∧～Q(g(x),b)∧～R(x))

则，略去全称变量，原式的Skolem标准形为：

P(a,x,f(x))∧～Q(g(x),b)∧～R(x)

谓词归结子句形子句与子句集文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。子句集S的求取：

G→SKOLEM标准形 →消去存在变量 →以“，”取代“Λ”，并表示为集合形式。谓词归结子句形

G是不可满足的<=>S是不可满足的G与S不等价，但在不可满足得意义下是一致的。

定理： 若G是给定的公式，而S是相应的子句集，则G是不可满足的<=>S是不可满足的。

注意：G真不一定S真，而S真必有G真。 即：S=>G谓词归结子句形G=G1ΛG2ΛG3Λ…ΛGn

的子句形G的字句集可以分解成几个单独处理。

有SG=S1US2US3U…USn

则SG

与S1US2US3U…USn在不可满足得意义上是一致的。 即SG

不可满足<=>S1US2US3U…USn不可满足求取子句集例(1)例：对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：

P(x,y)表示x是y的父亲

Q(x,y)表示x是y的祖父

ANS(x)表示问题的解答求取子句集例(2)对于第一个条件，“如果x是y的父亲，y又是z的父亲，则x是z的祖父”，一阶逻辑表达式如下：

A1：(

x)(

y)(

z)(P(x,y)∧P(y,z)→Q(x,z)) SA1：～P(x,y)∨～P(y,z)∨Q(x,z)对于第二个条件：“每个人都有父亲”，一阶逻辑表达式：

A2：(

y)(

x)P(x,y) SA2：P(f(y),y)对于结论：某个人是它的祖父

B：(

x)(

y)Q(x,y)

否定后得到子句：～（(

x)(

y)Q(x,y)）∨ANS(x) S～B：～Q(x,y)∨ANS(x)则得到的相应的子句集为：{SA1，SA2，S～B}第二章谓词逻辑与归结推理概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理第二章谓词逻辑与归结推理概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理归结原理归结原理正确性的根本在于，找到矛盾可以肯定不真。方法：和命题逻辑一样。但由于有函数，所以要考虑合一和置换。

置换置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。定义： 置换是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，x1,x2,…,xn是互不相同的变量，t1,t2,…,tn是不同于xi的项（常量、变量、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中。例如

{a/x，c/y，f(b)/z}是一个置换。

{g(y)/x，f(x)/y}不是一个置换，

置换的合成设

＝{t1/x1,t2/x2,…,tn/xn}，

＝{u1/y1,u2/y2,…,un/yn}，是两个置换。 则

与

的合成也是一个置换，记作

·

。它是从集合

{t1·

/x1,t2·

/x2,…,tn·

/xn,u1/y1,u2/y2,…,un/yn}

中删去以下两种元素：当ti

=xi时，删去ti

/xi(i=1,2,…,n);

当yi

{x1,x2,…,xn}时，删去uj/yj(j=1,2,…,m)

最后剩下的元素所构成的集合。合成即是对ti先做

置换然后再做

置换，置换xi置换的合成例：设：

＝{f(y)/x,z/y}，

＝{a/x,b/y,y/z}，求

与

的合成。解：先求出集合

{f(b/y)/x,(y/z)/y,a/x,b/y,y/z}＝{f(b)/x,y/y,a/x,b/y,y/z}

其中，f(b)/x中的f(b)是置换

作用于f(y)的结果；y/y中的y是置换

作用于z的结果。在该集合中，y/y满足定义中的条件i，需要删除；a/x，b/y满足定义中的条件ii，也需要删除。最后得

·

＝{f(b)/x，y/z}合一合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。定义：设有公式集F＝{F1，F2，…，Fn}，若存在一个置换

，可使F1

＝F2

＝…=Fn

，则称

是F的一个合一。同时称F1，F2，...，Fn是可合一的。

例： 设有公式集F＝{P(x,y,f(y)),P(a,g(x),z)}，则

＝{a/x,g(a)/y,f(g(a))/z}是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。

归结原理归结的注意事项：谓词的一致性，P()与Q()，不可以常量的一致性，P(a,…)与P(b,….)，不可以 变量，P(a,….)与P(x,…)，可以变量与函数，P(a,x,….)与P(x,f(x),…)，不可以；是不能同时消去两个互补对，P∨Q与～P∨～Q的空，不可以先进行内部简化（置换、合并）

归结原理归结的过程写出谓词关系公式→用反演法写出谓词表达式→SKOLEM标准形→子句集S→对S中可归结的子句做归结→归结式仍放入S中，反复归结过程→得到空子句

▯得证例题“快乐学生”问题假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。

解：先将问题用谓词表示如下：R1:“任何通过计算机考试并获奖的人都是快乐的”

(

x)((Pass(x,computer)∧Win(x,prize))→Happy(x))R2:“任何肯学习或幸运的人都可以通过所有考试”

(

x)(

y)(Study(x)∨Lucky(x)→Pass(x,y))R3:“张不肯学习但他是幸运的” ～Study(zhang)∧Lucky(zhang)R4:“任何幸运的人都能获奖”

(

x)(Luck(x)→Win(x,prize))结论：“张是快乐的”的否定～Happy(zhang)例题“快乐学生”问题由R1及逻辑转换公式:P∧W→H=～（P∧W）∨H，可