人工智能教案.

人工智能及其应用ArtificialIntelligence:PrinciplesandApplications总复习第1章绪论1、重点掌握人工智能的几种定义。2、掌握目前人工智能的三个主要学派及其认知观。3、一般了解人工智能的主要研究范围和应用领域。定义2人工智能(学科)人工智能(学科)是计算机科学中涉及研究、设计和应用智能机器的一个分支。它的近期主要目标在于研究用机器来模仿和执行人脑的某些智力功能，并开发相关理论和技术。定义3人工智能(能力)人工智能(能力)是智能机器所执行的通常与人类智能有关的智能行为，如判断、推理、证明、识别、感知、理解、通信、设计、思考、规划、学习和问题求解等思维活动。人工智能的三大学派及其认知观：(1)符号主义认为人工智能起源于数理逻辑。(2)连接主义认为人工智能起源于仿生学，特别是对人脑模型的研究。(3)行为主义认为人工智能起源于控制论。第2章知识表示方法重点掌握用状态空间法、问题归约法、谓词逻辑法、语义网络法、框架表示法来描述问题，解决问题；2.1状态空间法许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。2.1状态空间法状态空间法三要点(1)状态（state）：表示问题解法中每一步问题状况的数据结构；(2)算符（operator）：把问题从一种状态变换为另一种状态的手段；(3)状态空间方法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。2.1状态空间法由上可知，对一个问题的状态描述，必须确定3件事：(1)该状态描述方式，特别是初始状态描述；(2)操作符集合及其对状态描述的作用；(3)目标状态描述的特性。例2：(分油问题)有A、B、C三个不带刻度的瓶子，分别能装8kg,5kg和3kg油。如果A瓶装满油，B和C是空瓶，怎样操作三个瓶，使A中的油平分两份？(假设分油过程中不耗油)解：第一步：定义问题状态的描述形式：设Sk=(b,c)表示B瓶和C瓶中的油量的状态。其中：b表示B瓶中的油量。c表示C瓶中的油量。初始状态集：S={(0,0)}目标状态集：G={(4,0)}第二步：定义操作符：操作：把瓶子倒满油，或把瓶子的油倒空。f1：从A瓶往B瓶倒油，把B瓶倒满。f2：从C瓶往B瓶倒油，把B瓶倒满。f3：从A瓶往C瓶倒油，把C瓶倒满。f4：从B瓶往C瓶倒油，把C瓶倒满。f5：从B瓶往A瓶倒油，把B瓶倒空。f6：从B瓶往C瓶倒油，把B瓶倒空。f7：从C瓶往A瓶倒油，把C瓶倒空。f8：从C瓶往B瓶倒油，把C瓶倒空。第三步：求解过程：0,33,02,3f1f10,05,31,31,00,15,13,34,04,35,25,30,00,20,32,05,0f1f3f4f7f8f6f5f3f1f4f7f5f3f2f8f3f8f3f2f5f8f3f8f7f7f6f1f4f7f4f5f1f7f1f1f1f7f5f5f7f5f6f7f5f1f3f3f1：从A瓶往B瓶倒油，把B瓶倒满。f2：从C瓶往B瓶倒油，把B瓶倒满。f3：从A瓶往C瓶倒油，把C瓶倒满。f4：从B瓶往C瓶倒油，把C瓶倒满。f5：从B瓶往A瓶倒油，把B瓶倒空。f6：从B瓶往C瓶倒油，把B瓶倒空。f7：从C瓶往A瓶倒油，把C瓶倒空。f8：从C瓶往B瓶倒油，把C瓶倒空。由上述状态空间图，可见从初始状态(0,1)到目标状态(4,0)的任何一条通路都是问题的一个解。其中：{f1,f4,f7,f6,f1,f4,f7}是算符最少的解之一。例：设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？解：第一步：定义问题状态的描述形式：设Sk=(M,C,B)表示传教士和野人在河右岸的状态。其中：M表示传教士在右岸的人数。C表示野人在右岸的人数。B用来表示船是不是在右岸。(B=1表示在右岸，B=0表示在左岸)。初始状态集：S={(3,3,1)}目标状态集：G={(0,0,0)}第二步：定义算符。算符R(i,j)表示划船将i个传教士和j个野人送到左岸的操作。算符L(i,j)表示划船从左岸将i个传教士和j个野人带回右岸的操作。由于过河的船每次最多载两个人，所以i+j≤2。这样定义的算符集F中只可能有如下10个算符。F：R(1,0),R(2,0),R(1,1),R(0,1),R(0,2)L(1,0),L(2,0),L(1,1),L(0,1),L(0,2)第三步：求解过程。1,1,02,2,13,1,10,2,03,0,0R(2,0)L(2,0)R(1,1)L(1,1)L(0,1)R(0,1)L(2,0)R(2,0)2,2,03,3,13,2,13,2,03,1,0L(0,2)R(0,2)R(0,1)L(0,1)L(1,0)R(1,0)L(0,1)R(0,1)L(1,1)R(1,1)L(0,2)R(0,2)1,1,10,0,00,1,00,1,10,2,1R(0,1)L(1,0)L(0,1)R(0,1)R(1,0)L(1,0)R(0,1)L(0,1)R(1,1)L(1,1)R(0,2)L(0,2)0,3,1R(0,2)L(0,2)由上述状态空间图，可见从初始状态(3,3,1)到目标状态(0,0,0)的任何一条通路都是问题的一个解。其中：{R(1,1),L(1,0),R(0,2),L(0,1),R(2,0),L(1,1),R(2,0),L(0,1),R(0,2),L(1,0),R(1,1)}是算符最少的解之一。2.2问题归约法问题归约法的概念已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。该方法也就是从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。2.2问题归约法问题归约法的组成部分（1）一个初始问题描述；（2）一套把问题变换为子问题的操作符；（3）一套本原问题描述。2.3谓词逻辑法一阶谓词逻辑表示法适于表示确定性的知识。它具有自然性、精确性、严密性及易实现等特点。2.3谓词逻辑法用一阶谓词逻辑法表示知识的步骤如下：（1）定义谓词及个体，确定每个谓词及个体的确切含义。（2）根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值。（3）根据所要表达的知识的语义，用适当的连接符号将各个谓词连接起来，形成谓词公式。例1：设有下列事实性知识：张晓辉是一名计算机系的学生，但他不喜欢编程序。李晓鹏比他父亲长得高。请用谓词公式表示这些知识。（1）定义谓词及个体。Computer(x):x是计算机系的学生。Like(x,y):x喜欢y。Higher(x,y):x比y长得高。这里涉及的个体有：张晓辉(zhangxh),编程序(programming),李晓鹏(lixp)，以及函数father(lixp)表示李晓鹏的父亲。第二步：将这些个体代入谓词中，得到Computer(zhangxh),~Like(zhangxh,programming),Higher(lixp,father(lixp))第三步：根据语义，用逻辑联结词将它们联结起来，就得到了表示上述知识的谓词公式。Computer(zhangxh)∧~Like(zhangxh,programming)Higher(lixp,father(lixp))例2：设有下列语句，请用相应的谓词公式把它们表示出来：（1）人人爱劳动。（2）自然数都是大于零的整数。（3）西安市的夏天既干燥又炎热。（4）喜欢读《三国演义》的人必读《水浒》。（5）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。（6）他每天下午都去打篮球。解：（1）人人爱劳动。定义谓词如下：Man(x):x是人。Love(x,y):x爱y。（x)(Man(x)→Love(x,劳动））（2）自然数都是大于等于零的整数。定义谓词如下：N(x):x是自然数。I(x):x是整数。GZ(x):x大于等于零。（x)(N(x)→(GZ(x）∧I(x))）(3)西安市的夏天既干燥又炎热。定义谓词：SUMMER(x):x处于夏天。DRY(x):x很干燥。HOT(x):x很炎热。SUMMER(Xi’an)→DRY(Xi’an)∧HOT(Xi’an)（4）喜欢读《三国演义》的人必读《水浒》。定义谓词：MAN(x)：x是人。LIKE(x,y)：x喜欢读y。(x)(MAN(x)∧LIKE(x,《SANGUOYANYI》)→LIKE(x,《SHUIHU》))（5）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。定义谓词：MAN(x):x是人。LIKE(x,y):x喜欢y。Meihua表示梅花，Juhua表示菊花，(x)(MAN(x)∧LIKE(x,Meihua))∧(y)(MAN(y)∧LIKE(y,Juhua))∧(z)(MAN(z)∧(LIKE(z,Meihua)∧LIKE(z,Juhua)))（6）他每天下午都去打篮球。定义谓词及个体：设TIME(x):x是下午。PLAY(x,y):x去打y，Liming表示李明，Basketball表示足球，则:（x）TIME(x)PLAY(Liming,Basketball)2.4语义网络法语义网络是1968年J.R.Quillian在研究人类联想记忆时提出的心理学模型。2.4语义网络法语义网络的概念语义网络是通过概念及其语义关系来表示知识的一种结构化网络图，它由节点和弧线或链线组成，节点用来表示各种概念、事物、属性、情况、动作、状态等，每个节点可以带有若干个属性，以表征其所代表的对象的特性。弧线用于表示节点间的关系，其上的标注则表示被连接的两个节点间的某种语义联系或语义关系。2.4语义网络法语义网络表示知识的方法及步骤（a）确定问题中的所有对象以及各对象的属性。（b）确定所讨论对象间的关系。（c）语义网络中，如果节点间的联系是ISA/AKO，则下层节点对上层节点的属性具有继承性。整理同一层节点的共同属性，并抽出这些属性，加入上层节点中，以免造成属性信息的冗余。（d）将各对象作为语义网络的一个节点，而各对象间的关系作为网络中各节点间的弧，连接形成语义网络。节点可代表一个事物或一个具体概念，也可代表某种情况、事件或某一动作。当节点表示某种事件或某一动作时，可以从该节点引出一组向外的弧，用于指出事件的因果或动作的主体及客体。例1、用一个语义网络表示下列命题。(1)树和草都是植物；(2)树和草是有根有叶的；(3)水草是草，且长在水中；(4)果树是树，且会结果；(5)苹果树是果树中的一种，它结苹果。分析：问题涉及的对象有：植物、树、草、水草、果树、苹果树各对象的属性分别为：树和草的属性：有根、有叶；水草的属性：长在水中；果树的属性：会结果；苹果树的属性：结苹果。植物苹果树水草果树草树AKOAKOAKOAKOAKO有根有叶有根有叶会结果结苹果长在水中例：用语义网络表示下列知识：猎狗是一种狗，而狗是一种动物。狗除了动物的有生命、能吃食物、有繁殖能力、能运动外，还有以下特点：身上有毛、有尾巴、四条腿；猎狗的特点是吃肉、奔跑速度快、能狩猎、个头大；而狮子狗也是一种狗，它的特点是吃饲料、身体小、奔跑速度慢、不咬人、供观赏。解题分析（1）本知识涉及的对象有4个：猎狗、狮子狗、狗、动物。猎狗和狮子狗都是一种狗，除了它们本身的属性外，具有狗的一般特性：身上有毛、有尾巴、四条腿。而狗是一种动物，动物所具有的属性它也具有。（2）猎狗与狗之间是一种类属关系，狗和动物之间也是一种类属关系，它们都可以用AKO表示。（3）整理各对象节点之间的属性，使上层节点所具有的属性不在下层节点中标出。（4）将各对象作为一个节点，而它们之间的关系作为弧，得到如下图所示