人工智能技术—知识表示推理与搜索分解学习教案

1、人工智能技术人工智能技术知识知识(zh shi)表示推理与表示推理与搜索分解搜索分解第一页，共78页。索技术宜用问题带出内容，通过问题引发学生思考：“这样的问题机器能解决吗？可以怎么做？”以增加兴趣。第1页/共77页第二页，共78页。(jizh)来产生智力行为的经典人工智能技术主要以符号表示、符号处理为实现智能的主要手段，推理和搜索是其中的核心技术第2页/共77页第三页，共78页。第3页/共77页第四页，共78页。问题：斑马在哪个房间问题：斑马在哪个房间(fngjin)中？哪个房间中？哪个房间(fngjin)中的人喝水？中的人喝水？第4页/共77页第五页，共78页。房间号12345颜色国籍香烟

2、饮料宠物挪威人牛奶(ni ni)咖啡(kfi)库尔斯马英国人水橘子汁西班牙幸运狗茶乌克兰日本人国会温斯顿切斯菲尔德蜗牛狐狸斑马3.挪威人住在左边第一间房里6.挪威人住在蓝房间旁边14.中间房间的人喝牛奶12.绿房间中的人喝咖啡14.绿房间在白房间的左边1.英国人在红房间中4.黄房间中的人在抽库尔斯牌香烟11.抽库尔斯牌烟的房间在有匹马的房间隔壁8.抽幸运香烟的人喝橘子汁9.乌克兰人喝茶2.西班牙人有一条狗8.抽幸运牌香烟的人喝橘子汁9.乌克兰人喝茶10.日本人抽国会牌香烟7.抽温斯顿牌香烟的人有一只蜗牛5.抽切斯菲尔德牌香烟的人的是养了一只狐狸的人的邻居机器真的能自动完机器真的能自动完成这样的

3、推理吗？成这样的推理吗？第5页/共77页第六页，共78页。求 解第6页/共77页第七页，共78页。笛卡尔莱布尼茨自动证明的提出笛卡尔、莱布尼茨（17世纪）萌发(mngf)了用机械系统实现定理证明的想法把一类数学问题当作一个整体，建立统一的证明过程，按照规定的程序步骤机械地进行下去，在有限步骤之后判断出定理的正确性 第7页/共77页第八页，共78页。希尔伯特希尔伯特20世纪初，在他的名著几何基础中给出了一条可以对一类几何命题进行(jnxng)判定的定理。希尔伯特对命题的要求太高，当时仅能解决很少的一类几何定理的机器证明，却是历史上第一个关于某类几何命题的机械化检验方法的定理。第8页/共77页第九

4、页，共78页。塔斯基塔斯基（波兰）1950年，证明了：“一切初等几何和初等代数范围的命题都可以用机械方法(fngf)判定”为几何定理的机器证明开拓了一条利用代数方法(fngf)的途径方法(fngf)太复杂，即使用高速计算机也证明不了稍难的几何定理第9页/共77页第十页，共78页。艾伦.纽厄尔纽厄尔,西蒙和肖1956年, 发表了论文逻辑理论机(LTM)认为LTM不仅是计算机智力的有力证明，也是人类认知本质的证明1957年开发了最早的AI程序设计语言IPL语言1960年，成功地合作开发了“通用问题(wnt)求解系统” GPS (General Problem Solver)赫伯特.西蒙第10页/共

5、77页第十一页，共78页。王浩美籍华裔王浩（19211995）数学家、逻辑学家、计算机科学家、哲学家。简历生于山东济南市1943年毕业于西南联合大学数学系1945年毕业于清华大学(qn hu d xu)研究生院哲学系1948年获哈佛大学哲学博士学位1954-1956年在牛津大学任高级教职1961-1967年任哈佛大学教授1967-1991年任洛克菲勒大学逻辑学教授20世纪50年代初当选美国科学院院士及不列颠科学院外籍院士。第11页/共77页第十二页，共78页。王浩美籍华裔王浩（19211995）l953年起开始计算机理论与机器证明的研究。他敏锐地感觉到被认为过分讲究形式的精确又十分繁琐而无任何

6、实际用处的数理逻辑，可以在计算机领域发挥极好的作用。1959年，采用“王浩算法”用计算机证明了罗素 、 怀海德的巨著数学原理中的几百条有关(yugun)命题逻辑的定理，仅用了 9 分钟（vs 10年），宣告了用计算机进行定理证明的可能性，第一次明确提出“走向数学的机械化”。第12页/共77页第十三页，共78页。美籍华裔(huy)王浩1983 年，获国际人工智能联合会 “数学定理机械证明里程碑奖”，表彰他在数学定理机械证明研究领域的开创性贡献。1972年以后，王浩数次回国讲学。1985年兼任北京大学教授；1986年兼任清华大学教授。新中国成立之初，公开发表演说表示对新中国的支持。1972年回国时

7、曾受周恩来总理的接见。1973年撰写了访问中国的沉思，赞美新中国，被报纸与杂志广泛刊载。为此，他受到了许多攻击。他热爱祖国和中华民族的精神值得人们学习与称道。第13页/共77页第十四页，共78页。1977年，美国年轻的数学家阿佩尔等在高速电子计算机上耗费 1200 小时的计算时间，证明了著名的“四色定理” ，人类百年悬而未决的疑问最终(zu zhn)被圆满解决了。这一成就轰动一时，成为机器定理证明的一个典范。第14页/共77页第十五页，共78页。1951年回到祖国，任北京大学数学系的教授1956年与华罗庚、钱学森同台领取国家自然科学奖一等奖；38岁时当选为中国科学院学部委员1993年获得陈嘉庚

8、数理科学奖1994年获首届求是(qi sh)科技基金会杰出科学家奖1997 年获Herbrand自动推理杰出成就奖2001年获国家最高科学技术奖第15页/共77页第十六页，共78页。1985 年发表论文“关于代数方程组的零点”吴文俊消元法，即“吴氏公式”。2010年5月4日，国际小行星中心发布公报通知国际社会，将国际永久编号为第7683号的小行星永久命名为“吴文俊星”。第16页/共77页第十七页，共78页。第17页/共77页第十八页，共78页。第18页/共77页第十九页，共78页。第19页/共77页第二十页，共78页。事实事实(shsh)规则规则人类的推理可以理解语义人类的推理可以理解语义机器

9、如何进行这样类似的推理？机器如何进行这样类似的推理？需要将推理的过程与理解分割开，将其形式化需要将推理的过程与理解分割开，将其形式化结论只是穿着不同衣服的同一个人约尔第20页/共77页第二十一页，共78页。PQ：如果 P 那么 Q结论： Q这个过程(guchng)不需要直觉和解释第21页/共77页第二十二页，共78页。第22页/共77页第二十三页，共78页。识适合于表示事物的状态、属性、概念等，也可用来表示事物间确定的因果关系第23页/共77页第二十四页，共78页。t1,t2,.,tn是项，则P(t1,t2,.,tn) 是一个原子公式，其他任何表达式都不是原子公式第24页/共77页第二十五页，

10、共78页。(a)(b)(c)第25页/共77页第二十六页，共78页。第26页/共77页第二十七页，共78页。第27页/共77页第二十八页，共78页。鲁滨逊美国数学家鲁滨逊提出消解原理（1965年）基本的出发点：要证明(zhngmng)一个命题为真都可以通过证明(zhngmng)其否命题为假来得到将多样的推理规则简化为一个消解第28页/共77页第二十九页，共78页。P QP RQ R消解式消解式亲本亲本(qn bn)子句子句消解式是亲本子句消解式是亲本子句的逻辑的逻辑(lu j)结论结论消解只能在仅含否定和析取联接词的公式（子句）间进行必须先把公式化成规范的形式（范式，子句集）析取联接词，类似析

11、取联接词，类似“或或”第29页/共77页第三十页，共78页。R SRS例2：如果(rgu)今天不下雨，我就去你家 PQ今天没有下雨 PP Q第30页/共77页第三十一页，共78页。Man (x) Mortal “”怎么办？ 化为子句集化为子句集 置换与合一置换与合一如果(rgu)能消去“”，Man (x) 和Man (Socrates)也不能构成互补对，形式不一样，怎么办？第31页/共77页第三十二页，共78页。(xin tn)，也不允许变元xi循环出现在另一个tj中a/x,f(b)/y,w/z f(a)/x, b/y, t/x g(y)/x,f(x)/ys=z/x,w/y =P(x,f(y)

12、,B) s =P(z,f(w),B)第32页/共77页第三十三页，共78页。若s为Fi的任一合一者，又存在某个置换s，使得 s=gs则称g为Fi的最一般(最简单的)合一者，记作mgu。mgu is unique F=P(x,f(y),B) s=A/x,B/y g=B/y s=A/x gs=s第33页/共77页第三十四页，共78页。由子句构成的集合称为子句集例：P（x）Q(x) , P（x，f(x)）Q(x,g(x) 第34页/共77页第三十五页，共78页。Px) (= x)P(Px) (= x)P(QP Q)(PQP Q)(P$=第35页/共77页第三十六页，共78页。4)消去存在量词(具体化

13、 Skolemnizing)，两种情况：存在量词不在全称量词的辖域内用新的个体常量替换受存在量词约束(yush)的变元 存在量词在全称量词的辖域内 Skolem函数，即具体化函数 x)Q(x)( x)P(x)($y)Q(y)( x)P(x)($)a(Q)x(P)x()y(Q)y()x(P)x($)y,x,.,x,x(P)y)(x).(x)(x(n21n21$)x,.,x,x(f ,x,.,x,x(P)x).(x)(x()n21n21n21)x,.,x,x(f ,x,.,x,x(P)x).(x)(x()n21n21n21第36页/共77页第三十七页，共78页。第37页/共77页第三十八页，共78

14、页。一阶谓词(wi c)逻辑的消解式设C1与C2是两个没有相同变元的子句，L1和L2分别是C1和C2中的文字，若是L1和L2的最一般合一者，则称C12=(C1 - L1)(C2 - L2) 为C1和C2的二元消解式，L1和L2为消解式上的文字第38页/共77页第三十九页，共78页。化成(hu chn)范式；应用消解原理，不断求消解式，直到得到一个表示矛盾的空子句第39页/共77页第四十页，共78页。 Happy(x) x是快乐(kuil)的 Read(x) x能看书 Exciting(x) x过着激动人心的生活第40页/共77页第四十一页，共78页。Read(Liming)Poor(Limin

15、g)“快乐的人过着激动人心的生活” (z) (Happy(z)Exciting(z)目标“李明过着激动人心的生活”的否定 Exciting(Liming)第41页/共77页第四十二页，共78页。的否定)第42页/共77页第四十三页，共78页。Exciting(Liming)Happy(z)Exciting(z)Happy(Liming)Happy(x)Smart(x)Happy(x)Poor(Liming)Smart(Liming)Read(y)Smart(y )Poor(Liming)Read(Liming)Poor(Liming)Read(Liming)Read(Liming) NILLi

16、ming/zLiming/xLiming/y第43页/共77页第四十四页，共78页。第44页/共77页第四十五页，共78页。第45页/共77页第四十六页，共78页。求解的手段(shudun)多种多样其中搜索技术是问题求解的主要手段(shudun)之一问题表示解的搜索第46页/共77页第四十七页，共78页。12384567初始状态81324567目标状态如何将棋盘从某一初始状态变成最后的目标(mbio)状态？第47页/共77页第四十八页，共78页。49怎样(znyng)找到两点之间的最短路径呢？问题有了，可问题有了，可怎么让计算机怎么让计算机知道这些问题知道这些问题呢？呢？第48页/共77页第四

17、十九页，共78页。状态(zhungti)第49页/共77页第五十页，共78页。状态(zhungti)空间图第50页/共77页第五十一页，共78页。第51页/共77页第五十二页，共78页。状态：问题在某一时刻所处的“位置”，“情况”等根据问题所关心的因素，一般用向量形式表示(biosh)，每一位表示(biosh)一个因素0：右岸1：左岸(zu n)初始状态：(0, 0, 0)目标状态：(3, 3, 1)哪些操作能导致状态哪些操作能导致状态变化？变化？状态可有多种表示方法：(左岸传教士数, 右岸传教士数, 左岸野人数, 右岸野人数, 船的位置)或(左岸传教士数, 左岸野人数, 船的位置)第52页/

18、共77页第五十三页，共78页。rl Move-2c-lr Move-2c-rl Move-2m-lrMove-2m-rl Move-1c-lrMove-1c-rl Move-1m-lr Move-1m-rl第53页/共77页第五十四页，共78页。MC第54页/共77页第五十五页，共78页。有信息(xnx)搜索（启发式搜索）宽度优先搜索深度优先搜索A算法A*算法图的一般搜索策略第55页/共77页第五十六页，共78页。状态：(城市名)算子(sun z)：常德益阳益阳常德益阳汨罗益阳宁乡益阳娄底？必须记住哪些点走过了必须记住下一步还可以走哪些点深度深度(shnd)优先搜索优先搜索必须记住从目标返回的

19、路径第56页/共77页第五十七页，共78页。必须(bx)记住哪些点走过了必须记住(j zh)下一步还可以走哪些点必须记住从目标返回的路径第57页/共77页第五十八页，共78页。第58页/共77页第五十九页，共78页。第59页/共77页第六十页，共78页。图策略开始(kish)把S放入OPEN表OPEN表为空表？把第一个节点(ji din)(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表，提供返回节点n的指针修改指针方向重排OPEN表失败成功是是否否第60页/共77页第六十一页，共78页。第61页/共77页第六十二页，共78页。1238456712384567（目

20、标状态）（初始状态）操作(cozu): 空格上移，空格下移，空格左移，空格右移第62页/共77页第六十三页，共78页。1238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345宽度优先(yuxin)搜索树1 2384567271345612384567123845671238456712384567232425262782212384567123845671 238456712 3845671238456712

21、38456712384567141516171819202112384567第63页/共77页第六十四页，共78页。12384567123845671238456712384567123845671 2384567123845671238456741238567深度优先(yuxin)搜索树(深度约束=4)123845671238456712384567123845671 238456713456278能否预先知道下能否预先知道下一步应选择谁？一步应选择谁？第64页/共77页第六十五页，共78页。第65页/共77页第六十六页，共78页。第66页/共77页第六十七页，共78页。1964年，尼尔逊提

22、出一种算法以提高最短路径搜索的效率，被称为(chn wi)A1算法1967年，拉斐尔改进了A1算法，称为(chn wi)A2算法尼尔逊拉斐尔第67页/共77页第六十八页，共78页。从起始状态(zhungti)到当前状态(zhungti)x的代价从当前状态x到目标状态的估计代价（启发函数）虽提高了算法效率，但不能保证找到最优解虽提高了算法效率，但不能保证找到最优解第68页/共77页第六十九页，共78页。1968年，彼得.哈特对A算法进行了很小的修改，并证明了当估价函数满足一定的限制(xinzh)条件时，算法一定可以找到最优解估价函数满足一定限制(xinzh)条件的算法称为A*算法f (x) = g (x) + h (x)A*算法的限制算法的限制(xinzh)条件条件大于0不大于x到目标的实际代价彼得.哈特第69页/共77页第七十页，共78页。谁更接