人工智能-第4章 与或图搜索

《人工智能》教学大纲 课程名称：人工智能 英语名称：Artificial Intelligence 课程代码：130234 课程性质：专业必修 学分学时数： 5/80 适用专业：计算机应用技术 修（制）订人： 修（制）订日期：2009年2月 审核人： 审核日期： 审定人： 审定日期： 一、课程的性质和目的 （一）课程性质 人工智能是计算机科学理论基础研究的重要组成部分，人工智能课程是计算机科学技术专业的专业拓展选修课。

通过本课程的学习使学生了解人工智能的提出、几种智能观、重要研究领域，掌握人工智能求解方法的特点。

掌握人工智能的基本概念、基本方法，会用知识表示方法、推理方法和机器学习等方法求解简单问题等。

（二）课程目的 1、基本理论要求： 课程介绍人工智能的主要思想和基本技术、方法以及有关问题的入门知识。

要求学生了解人工智能的主要思想和方法。

2、基本技能要求： 学生在较坚实打好的人工智能数学基础（数理逻辑、概率论、模糊理论、数值分析）上，能够利用这些数学手段对确定性和不确定性的知识完成推理；在理解Herbrand 域概念和Horn 子句的基础上，应用Robinson 归结原理进行定理证明；应掌握问题求解（GPS ）的状态空间法，能应用几种主要的盲目搜索和启发式搜索算法（宽度优先、深度优先、有代价的搜索、A 算法、A*算法、博弈数的极大—极小法、α―β剪枝技术）完成问题求解；并能熟悉几种重要的不确定推理方法，如确定因子法、主观Bayes 方法、D —S 证据理论等，利用数值分析中常用方法进行正确计算。

3、职业素质要求：结合实战，初步理解和掌握人工智能的相关技术。

二、教学内容、重（难）点、教学要求及学时分配 第一章：人工智能概述（2学时）……………………………………………………………………装……订……线…………………………………………………………………………………………………………… …………………………1、讲授内容：（1）人工智能的概念（2）人工智能的研究途径和方法（3）人工智能的分之领域（4）人工智能的基本技术（5）人工智能的发展概况2、教学要求：了解：研究途径和方法、人工智能的分之领域、基本技术和发展概况。

只有一个孤独的影子，她，倚在栏杆上；她有眼，才从青春之梦里醒过来的眼还带着些朦胧睡意，望着这发狂似的世界，茫然地像不解这人生的谜。

她是时代的落伍者了，在青年的温馨的世界中，她在无形中已被摈弃了。

她再没有这资格，心情，来追随那些站立时代前面的人们了！在甜梦初醒的时候，她所有的惟有空虚，怅惘；怅惘自己的黄金时代的遗失。

咳！苍苍者天，既已给与人们的生命，赋与人们创造社会的青红，怎么又吝啬地只给我们仅仅十余年最可贵的稍纵即逝的创造时代呢？。

4.6 习题练习1 一元线性回归模型函数的几何意义是什么？一元线性回归求解就是拟合直线系数W和b的最佳估计值，使得预测值Y的误差最小。

只要这两个系数确定了，直线方程也就确定了，就可以把要预测的值X代入方程求得对应的Y值。

练习2 解释和分析梯度下降算法的原理。

梯度下降法的基本思想可以类比为一个下山的过程,可以类比为一个下山的过程，假设这样一个场景∶一个人被困在山上，需要从山上下来(找到山的最低点，也就是山谷)。

但此时山上的浓雾很大，导致可视度很低。

因此，下山的路径就无法确定，他必须利用自己周围的信息去找到下山的路径。

这个时候，他就可以利用梯度下降算法来帮助自己下山。

具体来说就是，以他当前所处的位置为基准，寻找这个位置最陡峭的地方，然后朝着山的高度下降最多的地方走，(同理，如果我们的目标是上山，也就是爬到山顶，那么此时应该是朝着最陡峭的方向往上走)。

然后每走一段距离，都反复采用同一个方法，最后就能成功的抵达山谷。

梯度下降示意图原理：在微积分里面，对多元函数的参数求偏导数，把求得的各个参数的偏导数以向量的形式写出来，就是梯度。

比如函数f(x,y), 分别对x,y 求偏导数，求得的梯度向量就是(∂f ∂x ,∂f ∂y)T ，梯度向量的几何意义就是函数变化增加最快的地方。

具体来说，对于函数f(x,y),在点(x0,y0)，沿着梯度向量的方向就是(∂f ∂x 0,∂f ∂y 0)T 的方向是f(x,y)增加最快的地方。

或者说，沿着梯度向量的方向，更加容易找到函数的最大值。

反过来说，沿着梯度向量相反的方向，也就是−(∂f ∂x 0,∂f ∂y 0)T 的方向，梯度减少最快，也就是更加容易找到函数的最小值。

练习3 说明逻辑回归的Sigmod 函数原理是什么？ Sigmod 函数：x ex -+=11)(SSigmod 函数图像：Sigmod 函数可以将任意实数映射到（0, 1）之间，比较适合做二分类。

逻辑回归的输入是线性回归的输出，将Sigmoid 函数作用于线性回归的输出得到输出结果。

《人工智能》课程教学大纲《人工智能》课程教学大纲一、课程基本信息开课单位课程名称开课对象学时/学分先修课程课程简介：人工智能是计算机科学的重要分支，是研究如何利用计算机来模拟人脑所从事的感知、XXX人工智能课程类别课程编码开课学期个性拓展GT第4或6学期网络工程专业、计算机科学与技术专业36学时/2学分（理论课：28学时/1.5学分；实验课：8学时/0.5学分）离散数学、数据结构、程序设计推理、研究、思考、规划等人类智能活动，来解决需要用人类智能才能解决的问题，以延伸人们智能的科学。

该课程主要讲述人工智能的基本概念及原理、知识与知识表示、机器推理、搜索策略、神经网络、机器研究、遗传算法等方面内容。

二、课程教学目标《人工智能》是计算机科学与技术专业的一门专业拓展课，通过本课程的研究使本科生对人工智能的基本内容、基本原理和基本方法有一个比较初步的认识，掌握人工智能的基本概念、基本原理、知识的表示、推理机制和智能问题求解技术。

启发学生开发软件的思路，培养学生对相关的智能问题的分析能力，提高学生开发应用软件的能力和水平。

三、教学学时分配《人工智能》课程理论教学学时分派表章次第一章第二章第三章第四章第五章第六章首要内容人工智能概述智能程序设计言语图搜索技术基于谓词逻辑的机器推理呆板进修与专家系统智能计算与问题求解合计学时分配35464628教学方法或手段讲授法、多媒体讲授法、多媒体探究式、多媒体讲授法、多媒体概述法、多媒体开导式、多媒体《人工智能》课程实验内容设置与教学要求一览表实学尝试序项目号名称配1)了解PROLOG语言中常1) Prolog运转环境；量、变量的表示方法；实分支2)使用PROLOG举行事实验与循实库、规则库的编写；库、规则库的编写方法；环程3)分支程序设计；一序设4)循环程序设计；一计5)输入出程序设计。

5)掌握PROLOG输入输出程序设计；1）了解PROLOG中的谓词1)谓词asserta和递归实与表实处理验程序二设计4）掌握PROLOG表处理程4)综合应用程序设计。

1．什么是搜索？有哪两大类不同地搜索方法？两者地区别是什么？解：像这种根据问题地实际情况,不断寻找可利用知识,从而构造一条最小地推理路线,使问题得以解决地过程称为搜索可根据搜索过程是否使用启发式信息分为盲目搜索与启发式搜索,也可根据问题地表示方式分为状态空间搜索与与/或搜索盲目搜索是按预定地控制策略进行搜索,在搜索过程中获得地中间信息并不改变控制策略启发式搜索是在搜索中加入了与问题有关地启发性信息,用于指导搜索朝着最有希望地方向前进,加速问题地求解过程,并找到最优解。

状态空间搜索是指用状态空间法来表示问题所进行地搜索。

与/或搜索是指用问题归约法来表示问题时所进行地搜索。

2．深度优先搜索与广度优先搜索地区别是什么？解：深度优先搜索与广度优先搜索地区别在于：在对节点n进行扩展时,其后继节点在OPEN表中地存放位置不同。

广度优先搜索是将后继节点放入OPEN表地末端,而深度优先搜索则是将后继节点放入OPEN表地前端。

广度优先搜索是一种完备搜索,即只要问题有解就一定可以求出,而深度优先搜索是不完备搜索。

在不要求求解速度且目标节点地层次较深地情况下,广度优先搜索优于深度优先搜索;在要求求解速度且目标节点地层次较浅地情况下,深度优先搜索优于广度优先搜索。

3．为什么说深度优先搜索与代价树地深度优先搜索可以看成局部择优搜索地两个特例？解：深度优先搜索,代价树地深度优先搜索以与局部优先搜索都是以子节点作为考察范围,但节点选择地标准不同。

如果取估价函数f(n)=g(n),则它将退化为代价树地深度优先搜索。

如果取估价函数f(n)=d(n),则它将退化为深度优先搜索。

因此,深度优先搜索与代价树地深度优先搜索是局部择优搜索地两个特例。

4.局部择优搜索与全局择优搜索地相同之处与区别是什么？解：根据搜索过程中选择扩展节点地范围,启发式搜索算法可分为全局择优搜索算法与局部择优搜索算法。

其中,全局择优搜索算法每当需求扩展节点时,总是从Open表地所有节点中选择一个估价函数值最小地节点进行扩展,局部择优搜索算法每当需求扩展节点时,总是从刚生成地子节点中选择一个估价函数值最小地节点进行扩展。

湖北省高等教育自学考试课程考试大纲课程名称：人工智能导论课程代码：07844第一部分课程性质与目标一、课程性质与特点人工智能导论是电子信息工程专业的必修核心课程。

本课程系统阐述了人工智能的基本理论、基本方法和基本技术。

本课程是人工智能方向的引导性课程，对后续在人工智能领域的进一步研究工作和软件实践奠定良好的基础。

二、课程目标与基本要求人工智能导论是理论性较强，涉及知识面较广，方法和技术较复杂的一门学科。

通过对本课程的学习，学生应掌握人工智能的一个问题和三大技术，即通用问题求解和知识表示技术、搜索技术、推理技术。

学生在较坚实打好的人工智能数学基础上，能够利用这些数学手段对确定性和不确定性的知识完成推理；理解问题求解的状态空间法，能应用几种主要的盲目搜索和启发式搜索算法完成问题求解；熟悉几种重要的不确定推理方法，利用数值分析中常用方法进行正确计算。

认识机器学习对于智能软件研制的重要性，掌握机器学习的相关概念，机器学习的方法及其相应的学习机制，几个典型的机器学习系统的学习方法、功能和领域应用。

三、与本专业其他课程的关系与本课程相关的课程有：数字图像处理、计算机信息处理等专业课程。

第二部分考核内容与考核目标第1章概述一、学习目的与要求本章包括人工智能研究目标、研究内容、研究的途径（方法）、研究的领域等内容。

通过对本章的学习，学生应理解什么是智能、理解什么是人工智能、人工智能研究的目标、人工智能研究的内容、人工智能研究的途径，了解人工智能研究的历史和研究领域。

二、考核知识点与考核目标（一）人工智能定义；人工智能的技术特征；（重点）识记：（1）人工智能的定义；理解：（1）人工智能的技术特征；（二）专家系统和知识工程（次重点）识记：（1）专家系统的定义；理解：（1）知识工程的主要研究内容；（三）人工智能应用系统（一般）理解：（1）人工智能的研究领域和应用领域；第2章用搜索求解问题的基本原理一、学习目的与要求通过对本章的学习，了解搜索求解问题的基本思路，掌握实现搜索过程的三大要素，理解通过搜索求解问题的方法，理解问题特征分析方法。

习题一、选择题1 .关于“与/或”图表示法的叙述中，正确的是（）A用“AND”和“OR”连续各部分的图形，用来描述各部分的因果关系B用“AND”和“OR”连续各部分的图形，用来描述各部分之间的不确定关系C是用“与”节点和“或”节点组合起来的树形图，用来描述某类问题的求解过程D是用“与”节点和“或”节点组合起来的树形图，用来描述某类问题的层次关系2 .在与或树和与或图中，把没有任何父辈节点的节点叫做：A叶节点B端节点C根节点D起始节点3 .启发式搜索中，通常OPEN表上的节点按照它们的估价函数f值的（）顺序排列：A递增B平均值C递减D最小4 .启广度优先搜索方法能够保证在搜索树种找到一条通向目标节点的（）路径（如果有路径存在时）。

A可行B最短C最长D解答5 .下列属于遗传算法的基本内容的是（）A图像识别B遗传算子C语音识别D神经调节6 .A*算法是一种（）。

A图搜索策略B有序搜索算法C盲目搜索D启发式搜索二、简答题1 .什么是搜索？有哪两大类不同的搜索方法？两者的区别是什么？2 .什么是与树？什么是或树？什么是与/或树？什么是可解节点？什么是解树？3 .何为股价函数？估价函数中，g（n）和h（n）各起什么作用？4 .什么是遗传算法？简述其基本思想和基本结构。

5 .常用的适应度函数有哪几种？参考答案一、选择题1. D2.C3.D4.A5.B6.D二、简答题1 .向这种根据世界情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。

简单地说，搜索就是利用已知条件在(知识)寻求解决问题办法的过程。

根据是否采用智能方法，搜索算法分为盲目搜索算法和智能搜索算法。

3 .用于估价结点重要性的函数称为估价函数，其一般形式为：/(n)=gQ)+h(n)其中，g(〃)是代价函数，表示从初始结点S。

到结点〃已经实际付出的代价；力(〃)是启发式函数，表示从结点〃到目标结点Sg的最优路径的估计代价。