第五章-人工智能语言与问题求解课件

－人工智能语言与问题求解主要内容学习人工智能语言了解人工智能语言使用人工智能语言用搜索解决问题搜索及其类型盲目搜索宽度优先搜索深度优先搜索启发式搜索与博弈人工智能语言概述1、什么是人工智能语言人工智能语言是一类适应于人工智能和知识工程领域的、具有符号处理和逻辑推理能力的计算机程序设计语言。能够用它来编写程序求解非数值计算、知识处理、推理、规划、决策等各种复杂的智能问题。人工智能语言概述2、人工智能语言的特点•具有符号处理能力；•适合于结构化程序设计，容易编程；•具有递归和回溯的功能；•具有人机交互能力；•适合于推理；•能够融合过程与数据结构，具有模式匹配机制。与其他语言的关系：都可以用来帮助人们解决问题。人工智能语言概述3、人工智能语言的种类Prolog：以谓词逻辑为基础，使计算机能够进行归结演绎TurboProlog、VisualPrologLISP：其程序是由一组函数组成，程序的执行过程就是一系列的函数调用和求值的过程其他：Smalltalk是一种面向对象的语言，其中所涉及的类、对象和继承等概念，与人工智能特别是知识表示和知识库具有天然的联系。TurboProlog的交互环境窗口VisualProlog的交互环境窗口

CommonLISP了解Prolog谓词逻辑－Prolog的理论基础谓词：用来描述对象的状态、性质及对象之间关系的词。逻辑：事物间的因果关系。例如：小明喜欢(打)羽毛球关系对象1对象2喜欢小明羽毛球likexiaomingbadmintonlike(xiaoming,badminton)Prolog语言的基本特点Prolog语言是一种智能型的描述语言，用传统的高级语言求解问题，程序员必须写出求解问题的全部过程细节，即告诉计算机如何求解问题，用Prolog语言求解问题，只需要程序员告诉计算机求解的问题是什么。Prolog语言接近于自然语言，语句种类少，只有事实，规则和目标三种语句，易于学习和掌握。用Prolog语言中的事实和规则可方便地表达知识，元逻辑操作使得存取、管理以及处理知识更加方便、灵活。程序与数据统一。逻辑性强。Prolog语句采用逻辑表达形式，所以易于保证Prolog程序的正确性。Prolog程序的执行以归结院里为基础自动地实现对问题的求解，从而使它具有超越传统高级语言的功能。了解PrologProlog的基本语句事实：表示对象的状态、性质或对象之间的关系。p(x,y,…）.其中的P是谓词，它描述事物的性质或事物间关系；参数x，y，代表事物。likes(xiaofang,badminton).Prolog的基本语句规则：表示对象之间的因果关系、蕴涵关系或对应关系。p(x,y,…):-q(x,y,…).friend(X,xiaohua):-likes(X,pingpong).结论前提形式名称构成与作用备注P(x,y，…规则头定义谓词p参数可以是常量或变量：-连接符表示“如果”q(x,y,…)规则体由一条或多条语句构成，语句间用“，”分隔；q是谓词“,”表示并且，参数可以是常量或变量.结束符表示一条规则结束Prolog的规则说明假设用parallel(x,y)表示直线x平行于直线y，则可用下图表示一条平行线定理：Parallel(x,y):-parallel(x,z),parallel(y,z)规则头如果规则体并且Prolog规则表示的例子Prolog的基本语句查询（Query）又称为目标：是用户向计算机提出的问题。查询语句可以写入程序之中，也可以在运行程序之后在输入计算机。Prolog查询语句的一般形式：Goal:p(x,y,…）形式名称构成与作用备注Goal:系统提示符提示用户输入查询语句P（x,y,…）语句查询由一条或多条事实语句构成，语句间用“，”分隔，其中没一条语句成为一个子目标。“，”表示“并且”，“而且”.语句结束符用“.”构成，标志一条语句结束。例如：我们已经知道这样一组事实和规则：Play(zhangqiang,baseball).play(zhangqiang,basketball).Play(wangming,x):-play(zhangqiang,x).常量/变量查询语句查询答案常量Goal:play(zhangqiang,basketball)./*张强打棒球吗*/Yes/*是的*/变量Goal:play(wangming,x)./*王明打什么球*/X=baseball/*王明打棒球*/X=basketball/*张强打篮球*/Prolog语言的内部谓词Write(x1,x2,…xn）是把项xi的值显示在屏幕上；Nl的功能是换行；Readln（x）的功能是从键盘上读取一个字符串并约束给变量x；了解PrologProlog的运行机理例化：在Prolog中若变量X还没有值，则称之为自由变量，一旦变量X取得了一个值，则称之为约束变量，或者说X被某一个值例化了。friend(X,xiaohua).在X有值以前它是自由变量，若X=xiaoming，则X被xiaoming例化了匹配：当两个谓词的名称相同，参数的个数、类型相同，并且还满足某些条件时，则这两个谓词可以匹配。friend(X,xiaohua)friend(xiaoming,xiaohua)当X是自由变量时，上面两个谓词friend是可以匹配的。了解PrologProlog的运行机理搜索与回溯走迷宫以上这种走不通再返回去寻找另一条路的方式，称为回溯

了解PrologProlog求解问题的过程首先从目标出发，不断地进行例化、匹配，有时还要进行回溯，直到目标被完全满足或不能满足时为止。了解Prolog简单的Prolog程序likes(xiaofang，badminton)./*以下2行是一组事实*/likes(xiaoming，pingpong).

friend(X,xiaohua):-likes(X,pingpong)./*本行是规则*/?-friend(X,xiaohua)./*本行是目标*/输出结果：X=xiaoming使用PrologProlog的使用方法TurboPrologVisualPrologTurboProlog的使用TurboProlog的基本语法

constants <常量说明语句> /*<注释>*/ domains <领域说明语句> database <数据库说明语句> predicates <谓词说明语句> clauses <子句语句> goal <目标语句>TurboProlog的程序示例domains

name,thing=symbolpredicates

likes(name,thing)

friend(name,thing)clauses

likes(xiaofang,badminton).

likes(xiaoming,pingpong).

friend(X,xiaohua):-likes(X,pingpong).

goal

friend(X,xiaohua),write(X,"isxiaohua'sfriend.").用TurboProlog进行数值计算例1从键盘输入2个整数，求两数之和。程序：goal

readint(X),/*输入一个整数给X*/

readint(Y),/*输入一个整数给Y*/Z=X+Y,

write(X,"+",Y,"=",Z),nl./*输出计算结果Z*/用TurboProlog求解阶乘问题例2阶乘问题:n!=n*(n-1)*(n-2)*…*3*2*1汉诺塔问题例3：传说在古代印度的贝拿勒斯圣庙里，安放了一块黄铜板，板上插了三根宝石柱，在其中一根宝石柱上，自上而下按由小到大的顺序串有64个金盘子。要求将这64个盘子从柱1移到柱3。在移动时必须遵照以下规则：a) 一次只能移一个盘子；b) 盘子只能在三个柱子上存放；c) 大盘任何时候不能放在小盘上面。问应该如何移动？

汉诺塔问题的求解思路若设定盘子的数目为N：第1步：将柱1上的N-1个盘子从柱1移到柱2上（可借助柱3）；第2步：将柱1上剩下的一个盘子从柱1直接移到柱3上；第3步：将柱2上的N-1个盘子从柱2移到柱3上（可借助柱1）。汉诺塔问题的求解程序搜索及其类型1、什么是搜索人工智能所要解决的问题大部分不具备明确的解题步骤，而只能是利用已有的知识一步一步地摸索前进。

根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称之为搜索。搜索及其类型2、可以用搜索解决的问题8数码问题猴子和香蕉问题旅行商问题走迷宫博弈问题规划问题…………搜索及其类型3、常用的搜索技术盲目搜索又称无信息/穷举式搜索，只能按照预先规定的搜索控制策略进行搜索，没有任何中间信息来改变这些控制策略。具有盲目性，效率不高，不便于复杂问题的求解。具体可以分为宽度优先搜索和深度优先搜索两种。启发式搜索在搜索求解过程中，根据问题本身的特性或搜索过程中所产生的一些与问题有关的启发性信息，指导搜索朝着最有希望的推理方向前进，加速问题的求解过程并找到最优解。盲目搜索宽度优先搜索基本思想从初始节点So开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。它是一种先生成的节点先扩展的搜索方法。课件演示8数码问题的宽度优先搜索过程盲目搜索宽度优先搜索示例求解八数码问题宽度优先搜索示例8数码问题的宽度优先搜索树盲目搜索深度优先搜索深度优先搜索中，搜索树是从树根开始一枝一枝逐渐生成的。它是一种后生成的节点先扩展的搜索方法。基本思想：从初始节点So开始，在其子节点中选择一个节点进行考察，若不是目标节点，则再在该子节点的子节点中选择一个节点进行考察，如果该子节点可以扩展，则扩展该子节点，依次向下搜索，在搜索树的每一层始终先只扩展一个子节点，如此一直向下搜索，直到某个子节点既不是目标节点又不能继续扩展时，才从当前节点返回上一级节点，沿另一方向又继续前进。盲目搜索深度优先搜索示例求解八数码问题（课件演示）深度优先搜索示例8数码问题的深度优先搜索树盲目搜索有界深度优先搜索在深度优先搜索的基础上，给出了搜索树深度限制，当从初始节点出发沿某一分枝扩展到一限定深度时，就不能再继续向下扩展，而只能改变方向继续搜索。算法示例

八数码问题(课件演示)启发式搜索启发式搜索是指在控制性知识中增加关于被解问题和相应任务的某些特性，利用启发性信息来确定节点的生成、扩展和搜索顺序，指导搜索朝着最有希望的方向前进的一类搜索方法。

启发式搜索的特点大多是深度优先搜索的改进，即尽量沿着最有希望的路径，向深度方向小范围前进；在有多条路可走时，会给出该走哪条路径的建议，从而指导搜索过程朝最有利的方向前进；利用问题求解的先验知识，使之尽快找到问题的解；可采用估值的方法进行搜索指导；生成的状态空间小、搜索时间短且效率高、控制性好，易于使问题得到解。启发式搜索启发性信息的类型有效地帮助确定扩展节点的信息，即用于决定应先扩展哪一个节点，以免盲目扩展。有效地帮助决定哪些后继节点应被生成的信息，即用于决定应生成哪些后继节点，以免盲目地生成过多无用节点。能决定在扩展一个节点时哪些节点应从搜索树上删除的信息，即用于决定应删除哪些无用节点，以免造成时空浪费。估价函数用来估价节点重要性的函数

f(n)=g(n)+h(n)g(n)是从初始节点So到节点n的已经实际付出的代价；h(n)是从节点n到目标节点Sg的最优路径的估计代价

启发式搜索示例设估价函数为f(n)=g(n)+h(n)，其中g(n)表示节点n的搜索深度，h(n)表示节点n与目标节点两个棋局之间位置不相同的棋子数。每个节点左边的蓝色数字表示其估价值。博弈与启发式搜索博弈诸如下棋、打牌、战争等一类竞争性的智能活动。其中最简单的一种称为双方完备博弈。博弈树当某一方当前有多个行动方案可供选择时，他总是选择对自己最为有利而对对方最为不利的那个行动方案。当轮到A方走棋时，则可供A方选择的若干个行动方案之间是“或”的关系。轮到B方走棋时，B方也有若干个可供选择的行动方案，但此时这些行动方案对A方来说它们之间是“与”的关系。使用与或图（与或树）来表示博弈过程，叫做博弈树。博弈与启发式搜索博弈树的特点博弈的初始格局是初始节点。在博弈树中，“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系，对方扩展的节点之间是“与”关系。双方轮流扩展节点。博弈与启发式搜索极大极小分析法设博弈的双方分别为A和B，然后为其中的一方（如A）寻找一个最优行动方案。为了找到当前的最优行动方案，需要对各个方案可能产生的结果进行比较，并计算可能的得分。为了计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。当端节点的估值计算出来后，再推算父节点的得分。如果一个行动方案能获得最大的倒推值，那么它就是当前最好的行动方案。博弈与启发式搜索一字棋问题的求解课件演示：一字棋博弈与启发式搜索一字棋问题的求解思路设A的棋子用“a”表示，B的棋子用“b”表示。并设棋局为P，估价函数为e（P），其中：（1）若P是A获胜的棋局，则e（P）=＋∞。（2）若P是B获胜的棋局，则e（P）=-∞。（3）若P是胜负未定的棋局，则e（P）=e（+P）-e（-P）。其中e（+P）表示棋局上有可能使a成一线的数目；e（-P）则表示棋局上有可能使b成一线的数目。博弈与启发式搜索一字棋的极大极小搜索（第一回合）博弈与启发式搜索一字棋的极大极小搜索

人工智能

是一门交叉学科

脑科学认知科学心理学语言学逻辑学哲学计算机科学人工智能什么是人工智能人工智能的定义可以分为两部分，即“人工”和“智能”。关于什么是“智能”？智能需要具备的特征？具有感知能力（系统输入）:

机器视觉，机器听觉，图像语音识别……具有记忆与思维能力：思维是智能的根本原因，思维是一个动态的过程。思维分为：逻辑思维，形象思维和顿悟思维。具有学习能力及自适应能力：适应环境的变换、积累经验的能力

具有行为能力（系统输出）：对外界的智能化反应早期判断是否有智能的方法———图灵测试英国数学家阿兰·图灵(AlanTuring)提出了现称为“图灵测试”(TuringTest)的方法。简单来讲,图灵测试的做法是:让一位测试者分别与一台计算机和一个人进行交谈(当时是用电传打字机),而测试者事先并不知道哪一个是人,哪一个是计算机。如果交谈后测试者分不出哪一个被测者是人,哪一个是计算机,则可以认为这台被测的计算机具有智能。

Turing测试存在的问题“图灵测试”没有规定问题的范围和提问的标准仅反映了结果的比较，无涉及思维过程没指出是什么人争论：通过了图灵检验的电脑就具备思维能力了么？测试主持人被测机器被测人中文屋子约翰·西尔勒的中文屋子假设是说:有一台计算机阅读了一段故事并且能正确回答相关问题,这样这台计算就通过了图灵测试。而西尔勒设想将这段故事和问题改用中文描述(因为他本人不懂中文),然后将自己封闭在一个屋子里,代替计算机阅读这段故事并且回答相关问题。描述这段故事和问题的一连串中文符号只能通过一个很小的缝隙被送到屋子里。西尔勒则完全按照原先计算机程序的处理方式和过程(如符号匹配、查找、照抄等)对这些符号串进行操作,然后把得到的结果即问题答案通过小缝隙送出去。西尔勒也得到了问题的正确答案。西尔勒认为尽管计算机用这种符号处理方式也能正确回答问题,并且也可通过图灵测试,但仍然不能说计算机就有了智能。

人工智能的发展概况

1.形成期（1956--1970年）AI诞生于一次历史性的聚会(Dartmouth人工智能夏季研讨会)时间：1956年夏季地点：美国达特茅斯(Dartmouth)大学目的：为使计算机变得更“聪明”，或者说使计算机具有智能发起人：麦卡锡(J.McCarthy），Dartmouth的年轻数学家、计算机专家，后为MIT教授明斯基(M.L.Minsky），哈佛大学数学家、神经学家，后为MIT教授洛切斯特(N.Lochester)，IBM公司信息中心负责人香农(C.E.Shannon)，贝尔实验室信息部数学研究员会议结果：由麦卡锡提议正式采用了“ArtificialIntelligence”这一术语人工智能的发展概况2.形成期（1956----1970年）其他开创性贡献1958年，美籍华人数理逻辑学家王浩在IBM-740计算机上仅用了3-5分钟就证明了《数学原理》命题演算全部220条定理。1965年，费根鲍姆(E.A.Feigenbaum)开始研究化学专家系统DENDRAL，用于质谱仪分析有机化合物的分子结构。1969年召开了第一届国际人工智能联合会议（InternationalJointConferenceonAI，IJCAI），标志着人工智能作为一门独立学科登上了国际学术舞台。此后IJCAI每两年召开一次。1970年《InternationalJournalofAI》创刊。人工智能的发展概况3.暗淡期（1966----1974年）失败的预言给人工智能的声誉造成重大伤害“20年内，机器将能做人所能做的一切”---------1965在博弈方面：塞缪尔的下棋程序在与世界冠军对弈时，5局败了4局。在定理证明方面：发现鲁宾逊归结法的能力有限。当用归结原理证明两个连续函数之和还是连续函数时，推了10万步也没证出结果。在机器翻译方面：发现并不那么简单，甚至会闹出笑话。例如，把“心有余而力不足”的英语句子翻译成俄语，再翻译回来时竟变成了“酒是好的，肉变质了”在问题求解方面：对于不良结构，会产生组合爆炸问题。在神经生理学方面：研究发现人脑有1011-12以上的神经元，在现有技术条件下用机器从结构上模拟人脑是根本不可能的。在英国，剑桥大学的詹姆教授指责“人工智能研究不是骗局，也是庸人自扰”。从此，形势急转直下，在全世界范围内人工智能研究陷入困境、落入低谷。

人工智能的发展概况

4.知识应用期（1970----1988年）整个20世纪80年代，专家系统和知识工程在全世界得到了迅速发展。专家系统为企业等用户赢得了巨大的经济效益。在开发专家系统过程中，许多研究者获得共识，即人工智能系统是一个知识处理系统，而知识获取、知识表示和知识利用则成为人工智能系统的三大基本问题。同时出现新的问题：专家系统本身所存在的应用领域狭窄、缺乏常识性知识、知识获取困难、推理方法单一、没有分布式功能、不能访问现存数据库等问题被逐渐暴露出来。人工智能的发展概况

5.集成发展期（1986年以来）1997年5月11日，由IBM研制的超级计算机“深蓝”首次击败了国际象棋特级大师卡斯帕洛夫。2000年，中国科学院计算所开发出知识发现系统MSMiner。该系统是一种多策略知识发现平台，能够提供快捷有效的数据挖掘解决方案，提供多种知识发现方法。2011年，IBM超级电脑“沃森”亮相美国最受欢迎的智力竞赛节目《危险边缘》战胜该节目两位最成功的选手。人工智能研究形成了三大学派符号主义连接主义行为主义符号主义又称：逻辑主义、心理学派或计算机学派符号主义的实现基础是纽威尔和西蒙提出的物理符号系统假设。该学派认为：人类认知和思维的基本单元是符号，而认知过程就是在符号表示上的一种运算。它认为人是一个物理符号系统,计算机也是一个物理符号系统,因此,我们就能够用计算机来模拟人的智能行为,即用计算机的符号操作来模拟人的认知过程。这种方法的实质就是模拟人的左脑抽象逻辑思维，通过研究人类认知系统的功能机理，用某种符号来描述人类的认知过程，并把这种符号输入到能处理符号的计算机中，就可以模拟人类的认知过程，从而实现人工智能。可以把符号主义的思想简单的归结为“认知即计算”。连接主义又称：仿生学派或生理学派原理：神经网络及神经网络间的连接机制与学习算法。起源：源于仿生学，特别是人脑模型的研究。学派代表：卡洛克、皮茨、Hopfield、鲁梅尔哈特等。连结主义基本理论认为思维基元是神经元，而不是符号处理过程。认为人脑不同于电脑，并提出连结主义的大脑工作模式，用于取代符号操作的电脑工作模式。行为主义又称：进化主义或控制论学派原理：控制论及感知—动作型控制系统认为智能不需要知识、不需要表示、不需要推理；