人工智能全套课件.pptx

单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,2022/1/4,#,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,2022/1/4,#,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,2022/1/4,#,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,2022/1/4,#,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,2022/1/4,#,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,2022/1/4,#,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,2022/1/4,#,人工智能,第,1,章 绪论,主要内容,人工智能的历史及概念,人工智能关键技术,人工智能产业现状及趋势,安全、伦理、隐私问题,人工智能专业课程体系,人工智能的历史,人工智能,60,余年的发展历程还是颇具周折的，大致可以划分为以下,6,个阶段：,人工智能的概念,人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能，但能像人那样思考，甚至也可能超过人的智能。人工智能企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器。自从诞生以来，人工智能的理论和技术日益成熟，应用领域也不断扩大，可以预期，人工智能所带来的科技产品将会是人类智慧的“容器”，因此，人工智能是一门极富挑战性的学科。,人工智能关键技术,机器学习,知识图谱,自然语言处理,人机交互,计算机视觉,生物特征识别,虚拟现实,/,增强现实,人工智能产业现状及趋势,智能基础设施,智能信息及数据,智能技术服务,人工智能行业应用,人工智能产业现状及趋势,人工智能产业发展趋势,（,1,）智能服务呈现线下和线上的无缝结合,（,2,）智能化应用场景从单一向多元发展,（,3,）人工智能和实体经济深度融合进程将进一步加快,安全、伦理、隐私问题,人工智能的安全问题,人工智能的伦理问题,人工智能的隐私问题,人工智能专业课程体系,第,2,章 知识表示方法,及搜索方法,主要内容,知识表示,搜索方法,知识表示,状态空间法,1,、状态（,State,）的基本概念,状态,(state),是为描述某类不同事物间的差别而引入的一组最少变量,q,0,，,q,1,，,，,q,n,的有序集合，其矢量形式如下：,Q=,q,0,q,1,q,n,T,(2.1),式中每个元素,q,i,(i=0,1,，,，,n),为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如,Q,k,=,q,k,q,1k,，,q,nk,T,(2.2),算符,：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。,问题的状态空间,(state space),是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合,S,、操作符集合,F,以及目标状态集合,G,。因此，可把状态空间记为三元状态,(S,，,F,，,G),。,知识表示,状态空间的表示法举例,问题：,猴子与香蕉的问题：在一个房间内有一只猴子、一个箱子和一束香蕉，初始的方位示意如图,2-1,所示。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能如图,2-2,所示摘到香蕉呢,?,状态空间法,知识表示,状态空间表示,用四元组（,W,，,x,，,y,，,z,）其中：,W,猴子的水平位置；,x,当猴子在箱子顶上时取,x=1,；否则取,x=0,；,Y,箱子的水平位置；,z,当猴子摘到香蕉时取,z=1,；否则取,z=0,。,算符：,（,1,）,goto(U),猴子走到水平位置,U,；,（,2,）,pushbox(V),猴子把箱子推到水平位置,V,；,（,3,）,climbbox,猴子爬上箱顶；,（,4,）,grasp,猴子摘到香蕉。,状态空间法,知识表示,求解过程,令初始状态为,(a,0,b,0),。这时，,goto(U),是唯一适用的操作，并导致下一状态,(U,，,0,，,b,0),。现在有,3,个适用的操作，即,goto(U),，,pushbox(V),和,climbbox(,若,U=b),。把所有适用的操作 继续应用于每个状态，我们就能够得到状态空间图，如图,2-3,所示。从图中不难看出，把该初始状态变换为目标状态的操作序列为：,goto(b),pushbox(c),climbbox,grasp,状态空间法,知识表示,状态空间图,状态空间法,知识表示,问题归约法,1,、问题归约法的概念,已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。,该方法也就是从目标,(,要解决的问题,),出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。,2,、问题归约法的组成部分,（,1,）一个初始问题描述；,（,2,）一套把问题变换为子问题的操作符；,（,3,）一套本原问题描述。,知识表示,示例：梵塔难题,问题,有,3,个柱子,(1,，,2,，,3),和,3,个不同尺寸的圆盘,(A,，,B,，,C),。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部,3,个圆盘都堆在柱子,1,上：最大的圆盘,C,在底部，最小的圆盘,A,在顶部，如图,2-4,所示。要求：把所有圆盘都移到柱子,3,上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上，具体的移动过程如图,2-5,所示。,问题归约法,知识表示,归约描述,问题归约方法是应用算符来把问题描述变换为子问题描述。,归约过程如下：,（,1,）移动圆盘,A,和,B,至柱子,2,的双圆盘难题；,（,2,）移动圆盘,C,至柱子,3,的单圆盘难题；,（,3,）移动圆盘,A,和,B,至柱子,3,的双圆盘难题。,问题归约法,三阶梵塔问题的归约图,知识表示,问题归约法,知识表示,与或图表示法,与或图的概念,用一个类似图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图。,例如，设想问题,A,需要由求解问题,B,、,C,和,D,来决定，那么可以用一个与图来表示；同样，一个问题,A,或者由求解问题,B,、或者由求解问题,C,来决定，则可以用一个或图来表示。,2,、与或图的有关术语,父节点,是一个初始问题或是可分解为子问题的问题节点；,子节点,是一个初始问题或是子问题分解的子问题节点；,或节点,只要解决某个问题就可解决其父辈问题的节点集合；,与节点,只有解决所有子问题，才能解决其父辈问题的节点集合；,弧线,是父辈节点指向子节点的圆弧连线；,终叶节点,是对应于原问题的本原节点。,知识表示,与或树示意图,与或图表示法,知识表示,可解节点,与或图中一个可解节点的一般定义可以归纳如下：,(1),终叶节点是可解节点,(,因为它们与本原问题相关连,),。,(2),如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。,(3),如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。,不可解节点,不可解节点的一般定义归纳于下：,(1),没有后裔的非终叶节点为不可解节点。,(2),如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。,(3),如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。,与或图表示法,知识表示,谓词逻辑法,1,、语法和语义,谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。,原子公式是由若干谓词符号和项组成，只有当其对应的语句在定义域内为真时，才具有值,T(,真,),；而当其对应的语句在定义域内为假时，该原子公式才具有值,F(,假,),。,2,、连词和量词,连词有,(,与,),、,(,或,),，全称量词,(x),，存在量词,(x),。,原子公式是谓词演算的基本积木块，运用连词能够组合多个原子公式以构成比较复杂的合适公式。,谓词逻辑法,知识表示,谓词逻辑法举例,-,以猴子和香蕉问题为例,描述状态的谓词：,AT(x,y),：,x,在,y,处,ONBOX,：猴子在箱子上,HB,：猴子得到香蕉,个体域：,x,：,monkey,box,banana,y,：,a,b,c,问题的初始状态,AT(monkey,a),AT(box,b),ONBOX,HB,问题的目标状态,AT(monkey,c),AT(box,c),ONBOX,HB,谓词逻辑法,知识表示,描述操作的谓词,Goto(u,v),：猴子从,u,处走到,v,处,条件：,ONBOX,，,AT(monkey,u),动作：删除表：,AT(monkey,u),；添加表：,AT(monkey,v),Pushbox(v,w),：猴子推着箱子从,v,处移到,w,处,条件：,ONBOX,，,AT(monkey,v),，,AT(box,v),动作：删除表：,AT(monkey,v),，,AT(box,v),添加表：,AT(monkey,w),，,AT(box,w),谓词逻辑法,知识表示,Climbbox,：猴子爬上箱子,条件：,ONBOX,，,AT(monkey,w),，,AT(box,w),动作：删除表：,ONBOX,；添加表：,ONBOX,Grasp,：猴子摘取香蕉,条件：,ONBOX,，,AT(box,c),动作：删除表：,HB,；添加表：,HB,谓词逻辑法,知识表示,猴子摘香蕉的谓词逻辑法,谓词逻辑法,知识表示,语义网络法,语义网络是奎廉,(J.R.Quillian)1968,年在研究人类联想记忆时提出的一种心理学模型，认为记忆是由概念间的联系实现的。随后，奎廉又把它用作知识表示。,1972,年，西蒙在他的自然语言理解系统中也采用了语义网络表示法。语义网络是一种表达能力强而且灵活的知识表示方法，目前已经广泛应用于人工智能领域，尤其是在自然语言处理方面。,知识的语义网络表示法是通过节点和弧线来构成语义网络。,语义网络法,知识表示,语义网络的基本概念,语义网络是知识的一种结构化图解表示，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。,语义网络表示由下列,4,个相关部分组成：,(1),词法部分 决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线。,(2),结构部分 叙述符号排列的约束条件，指定各弧线连接的节点对。,(3),过程部分 说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。,(4),语义部分 确定与描述相关的,(,联想,),意义的方法即确定有关节点的排列及其占有物和对应弧线。,语义网络法,知识表示,语义网络具有下列特点：,(1),能把实体的结构、属性与实体间的因果关系显式地和简明地表达出来，与实体相关的事实、特征和关系可以通过相应的节点弧线推导出来。,(2),由于与概念相关的属性和联系被组织在一个相应的节点中，因而使概念易于受访和学习。,(3),表现问题更加直观，更易于理解，适于知识工程师与领域专家沟通。,(4),语义网络结构的语义解释依赖于该结构的推理过程而没有结构的约定，因而得到的推理不能保证像谓词逻辑法那样有效。,(5),节点间的联系可能是线状、树状或网状的，甚至是递归状的结构，使相应的知识存储和检索可能需要比较复杂的过程。,语义网络法,知识表示,二元语义网络的表示,用两个节点和一条弧线可以表示一个简单的事实，对于表示占有关系的语义网络，是通过允许节点既可以表示一个物体或一组物体，也可以表示情况和动作。每一情况节点可以有一组向外的弧,(,事例弧,),，称为事例框，用以说明与该事例有关的各种变量。,例如：若有语义基元（,A,R,B,），其中，,A,、,B,分别表示两个结点，,R,表示,A,与,B,之间的某种语义联系，则它所对应的基本语义如图,2-9,所示：,语义网络法,知识表示,语义网络法举例,例如：用语义网络表示：,1,）动物能运动、会吃；,2,）鸟是一种动物，鸟有翅膀、会飞；,3,）鱼是一种动物，生活在水中、会游泳。这个问题的语义网络图如图所示。,语义网络法,知识表示,框架表示法,框架表示法是在框架理论的基础上发展起来的一种结构化知识表示方法。框架理论是明斯基于,1975,年作为理解视觉、自然语言对话及其它复杂行为的一种基础提出来的。,框架理论认为，人们对现实世界中各种事物的认识都是以一种类似于框架的结构存储在记忆中的。当遇到一个新事物时，就从记忆中找出一个合适的框架，并根据新的情况对其细节加以修改、补充，从而形成对这个新事物的认识。,知识表示,框架的构成,框架通常由描述事物的各个方面的槽组成，每个槽可以拥有若干个侧面，而每个侧面又可以拥,有若干个值。一个框架的一般结构如下：,框架名,槽,1,侧面,11,值,111,侧面,12,值,121,槽,2,侧面,21,值,211,槽,n,侧面,n1,值,n11,侧面,nm,值,nm1,框架表示法,知识表示,较简单的情景是用框架来表示诸如人和房子等事物。,例如,，一个人可以用其职业、身高和体重等项描述，因而可以用这些项目组成框架的槽。当描述一个具体的人时，再用这些项目的具体值填入到相应的槽中。表,2-1,给出的是描述,John,的框架。,JOHN,Isa,:,PERSON,Profession,:,PROGRAMMER,Height,:,1,.,8m,Weight,:,79kg,框架表示法,知识表示,剧本表示法,剧本是框架的一种特殊形式，它用一组槽来描述某些事件的发生序列，就像,剧本中的事件序列一样，故称为“剧本”或脚本。,剧本的构成,一个剧本一般由以下各部分组成：,(1),开场条件 给出在剧本中描述的事件发生的前提条件。,(2),角色 用来表示在剧本所描述的事件中可能出现的有关人物的一些槽。,(3),道具 这是用来表示在剧本所描述的事件中可能出现的有关物体的一些槽。,(4),场景 描述事件发生的真实顺序，可以由多个场景组成，每个场景又可以是其它的剧本。,(5),结果 给出在剧本所描述的事件发生以后通常所产生的结果。,知识表示,例子：,以餐厅剧本为例说明剧本各个部分的组成。,开场条件,(a),顾客饿了，需要进餐。,(b),顾客有足够的钱。,角色,顾客，服务员，厨师，老板。,道具,食品，桌子，菜单，钱。,剧本表示法,知识表示,场景：,5,个场景,场景,1,：进入餐厅,(a),顾客走入餐厅。,(b),寻找桌子。,(c),在桌子旁坐下,场景,2,：点菜,(a),服务员给顾客菜单。,(b),顾客点菜。,(c),顾客把菜单还给服务员。,(d),顾客等待服务员送菜。,场景,3,：等待,(a),服务员把顾客所点的菜告诉厨师。,(b),厨师做菜。,场景,4,：吃菜,(a),厨师把做好的菜给服务员。,(b),服务员给顾客送菜。,(c),顾客吃菜。,场景：,5,个场景,场景,5,：离开,(a),服务员拿来帐单。,(b),顾客付钱给服务员。,(c),顾客离开餐厅。,剧本表示法,知识表示,结果,(a),顾客吃了饭，不饿了。,(b),顾客花了钱。,(c),老板挣了钱。,(d),餐厅食品少了。,剧本表示法,知识表示,剧本的推理,一旦剧本被启用，则可以应用它来进行推理。其中最重要的是运用剧本可以预测没有明显提及的事件的发生。,例如：对于以下情节：“昨晚，约翰到了餐厅。他点了牛排。当他要付款时发现钱已用光。因为开始下雨了，所以他赶紧回家了“。,推理：“昨晚，约翰吃饭了吗？”,虽然上面的情节中没有提到约翰吃没吃饭的问题，但借助于餐厅剧本，可以回答：他吃了。因为启用了餐厅剧本，情节中的所有事件与剧本中所预测的事件序列相对应，可以推断出整个事件正常进行时所得出的结果。,剧本表示法,搜索技术,图搜索策略的定义,图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。,搜索技术,图搜索算法中的几个重要名词术语,OPEN,表与,CLOSE,表,节点深度：根节点深度,=0,；,其它节点深度,=,父节点深度,+1,路径：设一节点序列为,(n0,n1,nk),，对于,i=1,k,，若节点,ni-1,具有一个后继节点,ni,，则该序列称为从,n0,到,nk,的路径。,路径的耗散值：一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用,C(ni,nj),表示从,ni,到,nj,的路径的耗散值。,扩展一个节点：生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。,搜索技术,图搜索的一般过程,(1),建立一个只含有起始节点,S,的搜索图,G,，把,S,放到一个叫做,OPEN,的未扩展节点 表中。,(2),建立一个叫做,CLOSED,的已扩展节点表，其初始为空表。,(3)LOOP,：若,OPEN,表是空表，则失败退出。,(4),选择,OPEN,表上的第一个节点，把它从,OPEN,表移出并放进,CLOSED,表中。称此节点为节点,n,。,(5),若,n,为一目标节点，则有解并成功退出，此解是追踪图,G,中沿着指针从,n,到,S,这条路径而得到的,(,指针,将在第,7,步中设置,),。,(6),扩展节点,n,，同时生成不是,n,的祖先的那些后继节点的集合,M,。把,M,的这些成员作为,n,的后继节点添入图,G,中。,(7),对那些未曾在,G,中出现过的,(,既未曾在,OPEN,表上或,CLOSED,表上出现过的,)M,成员设置一个通向,n,的指针。把,M,的这些成员加进,OPEN,表。对已经在,OPEN,或,CLOSED,表上的每一个,M,成员，确定是否需要更改通到,n,的指针方向。对已在,CLOSED,表上的每个,M,成员，确定是否需要更改图,G,中通向它的每个后裔节点的指针方向。,(8),按某一任意方式或按某个探试值，重排,OPEN,表。,(9),GO LOOP,。,搜索技术,图搜索方法分析：,图搜索过程的第,8,步对,OPEN,表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第,4,步扩展用。这种排序可以是任意的即盲目的,(,属于盲目搜索,),，也可以用以后要讨论的各种启发思想或其它准则为依据,(,属于启发式搜索,),。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向,S,返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终,(,某些节点最终可能没有后继节点，所以,OPEN,表可能最后变成空表,),。在失败终止的情况下，从起始节点出发，一定达不到目标节点。,搜索技术,盲目搜索,盲目搜索是按预定的控制策略进行搜索，在搜索过程中获得的中间信,息不用来改进控制策略。本节主要介绍两种盲目搜索方法：宽度优先搜索和,深度优先搜索。,宽度优先搜索,1,、定义,如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽,度优先搜索,(breadth-first search),。,2,、特点,这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完,本层的所有节点。,搜索技术,宽度优先搜索算法,(1),把初始节点,s,放入,OPEN,表；,(2),若,OPEN,表为空，则问题无解，退出；,(3),把,OPEN,表的第一个节点,(,记为节点,n),取出放入,CLOSE,表；,(4),考察节点,n,是否为目标节点。若是，则求得了问题的解，退出；,(5),若节点,n,不可扩展，则转第,2,步；,(6),扩展节点,n,，将其子节点放入,OPEN,表的尾部，并为每一个子节点配置指向父节点的指针，然后转第,2,步。,搜索技术,例子：,把宽度优先搜索应用于八数码难题时所生成的搜索树，这,个问题就是要把初始棋局变为如下目标棋局的问题：,初始状态：目标状态：,2 3,1,2,3,1 8 4,8,4,7 6 5,7,6,5,使用的操作有：,空格上移，空格下移，空格左移，空格右移,宽度优先搜索法,搜索技术,宽度优先搜索法,搜索技术,深度优先搜索,1,、定义,在此搜索中，首先扩展最新产生的,(,即最深的,),节点。深度相等的节点可以任意排列。,这种盲目,(,无信息,),搜索叫做深度优先搜索,(depth-first search),。,2,、特点,首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。,搜索技术,深度优先搜索算法,(1),把初始节点,s,放入,OPEN,表；,(2),若,OPEN,表为空，则问题无解，退出；,(3),把,OPEN,表的第一个节点,(,记为节点,n),取出放入,CLOSE,表；,(4),考察节点,n,是否为目标节点。若是，则求得了问题的解，退出；,(5),若节点,n,不可扩展，则转第,2,步；,(6),扩展节点,n,，将其子节点放入到,OPEN,表的首部，并为每个子节点配置指向父节,点的指针，然后转第,2,步。,深度界限,为了避免考虑太长的路径,(,防止搜索过程沿着无益的路径扩展下去,),，往往,给出一个节点扩展的最大深度,深度界限。任何节点如果达到了深度界,限，那么都将把它们作为没有后继节点处理。,深度优先搜索法,搜索技术,例子：,把有界深度优先搜索（深度为,4,）应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：,初始状态：目标状态：,2 3,1,2,3,1 8 4,8,4,7 6 5,7,6,5,使用的操作有：,空格上移，空格下移，空格左移，空格右移,深度优先搜索法,搜索技术,深度优先搜索法,搜索技术,启发式搜索,进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种,信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。,一个比较灵活,(,但代价也较大,),的利用启发信息的方法是应用某些准则,来重新排列每一步,OPEN,表中所有节点的顺序。然后，搜索就可能沿,着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某,些估算节点“希望”的量度，这种量度叫做估价函数,(evalution function),。,为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，,以便确定哪个节点最有可能在通向目标的最佳路径上。,f(n),表示节点,n,的估价函数值,搜索技术,定义,用估价函数,f,来排列,GRAPHSEARCH,第,8,步中,OPEN,表上的节点。应用某个算法,(,例如等代价算法,),选择,OPEN,表上具有最小,f,值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索,(ordered search),或最佳优先搜索,(best-first search),，而其算法就叫做有序搜索算法或最佳优先算法。,尼尔逊,(Nilsson),曾提出一个有序搜索的基本算法。估价函数,f,是这样确定的：一个节点的希望程度越大，其,f,值就越小。被选为扩展的节点，是估价函数最小的节点。,启发式搜索,搜索技术,算法流程,(1),把起始节点,S,放到,OPEN,表中，计算,f(S),并把其值与节点,S,联系起来。,(2),如果,OPEN,是个空表，则失败退出，无解。,(3),从,OPEN,表中选择一个,f,值最小的节点,i,。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中,任一个节点作为节点,i,。,(4),把节点,i,从,OPEN,表中移出，并把它放入,CLOSED,的扩展节点表中。,(5),如果,i,是个目标节点，则成功退出，求得一个解。,(6),扩展节点,i,，生成其全部后继节点。对于,i,的每一个后继节点,j,：,(a),计算,f(j),。,(b),如果,j,既不在,OPEN,表中，又不在,CLOSED,表中，则用估价函数,f,把它添入,OPEN,表。从,j,加一指向其父辈节点,i,的指针，以便一旦找,到目标节点时记住一个解答路径。,(c),如果,j,已在,OPEN,表上或,CLOSED,表上，则比较刚刚对,j,计算过的,f,值和前面计算过的该节点在表中的,f,值。如果新的,f,值较小，则,(i),以此新值取代旧值。,(ii),从,j,指向,i,，而不是指向它的父辈节点。,(iii),如果节点,j,在,CLOSED,表中，则把它移回,OPEN,表。,(7),转向,(2),，即,GO TO(2),。,启发式搜索,搜索技术,例子：八数码难题,采用了简单的估价函数,f(n)=d(n)+W(n),其中：,d(n),是搜索树中节点,n,的深度；,W(n),用来计算对应于节点,n,的数据库中错放的棋子个数。,比如，起始节点棋局,2,8,3,1,6,4,7,5,的,f,值等于,0+4=4,。,启发式搜索,搜索技术,启发式搜索,搜索技术,A*,算法,A*,算法是一种有序搜索算法，其特点在于对估价函数的定义上。在,A,算法中，如果满足条件：,h(n)h*(n),则,A,算法称为,A*,算法。,几个记号,令,k(n,i,，,n,j,),表示任意两个节点,n,i,和,n,j,之间最小代价路径的实际代价,(,对于两节点间没有通路的节点，函数,k,没有定义,),。于是，从节点,n,到某个具体的目标节点,t,i,，某一条最小代价路径的代价可由,k(n,t,i,),给出。令,h*(n),表示整个目标节点集合,t,i,上所有,k(n,t,i,),中最小的一个，因此，,h*(n),就是从,n,到目标节点最小代价路径的代价，而且从,n,到目标节点能够获得,h*(n),的任一路径就是一条从,n,到某个目标节点的最佳路径,(,对于任何不能到达目标节点的节点,n,，函数,h*,没有定义,),。,搜索技术,估价函数的定义,定义,g*,为,g*(n)=k(S,n),定义函数,f*,，使得在任一节点,n,上其函数值,f*(n),就是从节点,S,到节点,n,的一条最佳路径的实际,代价加上从节点,n,到某目标节点的一条最佳路径的代价之和，即,f*(n)=g*(n)+h*(n),希望估价函数,f,是,f*,的一个估计，此估计可由下式给出：,f(n)=g(n)+h(n),其中：,g,是,g*,的估计；,h,是,h*,的估计。对于,g(n),来说，一个明显的选择就是搜索树,中从,S,到,n,这段路径的代价，这一代价可以由从,n,到,S,寻找指针时，把所遇到的各段,弧线的代价加起来给出,(,这条路径就是到目前为止用搜索算法找到的从,S,到,n,的最小,代价路径,),。这个定义包含了,g(n)g*(n),。,h*(n),的估计,h(n),依赖于有关问题的领域,的启发信息。这种信息可能与八数码难题中的函数,W(n),所用的那种信息相似。把,h,叫做启,发函数。,A*,算法,搜索技术,A*,算法举例,估价函数,f(n)=d(n)+p(n),其中：,d(n),是搜索树中节点,n,的深度；,p(n),用来计算对应于节点,n,的数据库中错放的棋子的距离和。,比如，起始节点棋局,2,8,3,1,6,4,7,5,的,f,值等于,0+5=5,。,A*,算法,搜索技术,A*,算法,第,3,章,Python,编程简介,主要内容,Python,简介,IPython,及其使用,数据结构,程序控制,脚本,输入、输出与可视化,Python,简介,Why Python,Python is powerful.and fast;plays well with others;runs everywhere;is friendly is Open.,These are some of the reasons people who use Python would rather not use anything else.,-https:/www.python.org/about/,下载,https:/www.python.org/downloads/,Looking for Python with a different OS?Python for,Windows,Linux/UNIX,Mac OS X,Other,.,Python,简介,包管理,PyPI,查看,pip,版本（一般自带）,pip version,安装,pip,python -m ensurepip -default-pip,或者下载,get-pip.py,，并执行,python get-pip.py,确保安装工具版本最新,python-m pip install-upgrade pip setuptools wheel,Python,简介,包管理,PyPI,安装,To install the latest version of“SomeProject”:,pip install SomeProject,To install a specific version:,pip install SomeProject=1.4,To install greater than or equal to one version and less than another:,pip install SomeProject=1,=1.4.2”.,Python,简介,包管理,PyPI,安装,Install from an alternate index,pip install-index-url my.package.repo/simple/SomeProject,更新,pip install-upgrade SomeProject,Python,简介,Anaconda,一个开源的,Python,发行版,Development Environment,）,PyCharm,Notebook,Anaconda,自带,Spyder,Winpython,、,Anaconda,自带,IDLE,Winpython,、,anaconda,自带,IPython,及其使用,IPython,控制台,IPython,是一个交互式,Python,开发环境。,主要的,Python,开发环境，例如,Anaconda,等，都包含了,IPython,。,用户可以利用其方便地进行开发。,Python 3.4.4(v3.4.4:737efcadf5a6,Dec 20 2015,20:20:57)MSC v.1600 64 bit(AMD64),Type copyright,credits or license for more information.,IPython 5.8.0-An enhanced Interactive Python.,?-Introduction and overview of IPythons features.,%quickref-Quick reference.,help -Pythons own help system.,object?-Details about object,use object?for extra details.,In 1:,IPython,及其使用,语句与表达式,a=5,程序由一系列这样的拥有不同功能的语句构成，从而可以执行各种复杂的操作。,表达式由常量（如,5,）、变量名（如,a,，每个变量都有自己的变量名）和操作符（如,=,，代表赋值）和函数（实现定义好的可以完成一系列操作的功能模块，有名字，即函数名，可以通过函数名调用）。,IPython,及其使用,语句与表达式,（,1,）常量,Python,支持整型、浮点型、复数、布尔型、字符串、列表等不同数据类型。,某个数据的值如果是显式给出的，就是常量，如,23,，,12.12,，,2+3j,，,True,或,False,，,Python for AI,等等。常量可被用于赋值、计算、比较等不同操作，但常量本身的值不能被改变。,（,2,）变量,在程序执行过程中其值可以变化的量是变量。每个变量都有变量名，用来在程序中引用变量。,变量命名必须遵循一定的规则，例如不能以数字开头，不能有空格和句点，不能使用,Python,中的保留字，例如,from,、,import,、,if,、,for,、,print,等，而且,Python,中变量名是大小写敏感的。,变量可以被赋值，但是常量不能被赋值。,IPython,及其使用,语句与表达式,（,3,）算术操作,Python,支持加减乘除和幂运算等算术运算，分别使用,+,-,*,/,和*等运算符。,IPython,及其使用,语句与表达式,（,4,）注释,Python,支持两类注释，分别面向行的和面向程序块。,#,用于行注释，若代码中出现,#,，其后的内容即为注释内容，不被解释器解释执行。,一对三个单引号组（,）或者双引号组（,”,）把括在其中的行进行注释,。,IPython,及其使用,语句与表达式,（,5,）函数,当实现某一特定功能的代码在程序中要多次使用时，可以定义函数。,当程序中需要实现该功能时调用这个函数就可以了。,一个函数的结构,函数的定义主要包括三部分，函数名、函数体和返回值。,IPython,及其使用,语句与表达式,（,5,）函数,IPython,及其使用,语句与表达式,（,5,）错误信息,程序会有语法或者逻辑上的错误，因此错误信息提示对程序员很重要。,Python,有警告（,Warning,）和错误（,Error,）两类错误信息。,警告一般不影响程序运行，但错误会导致程序无法继续运行。,IPython,及其使用,模块,Python,有健全的开原生态系统支撑。,有大量功能丰富、强大的软件库（例如数值计算库,NumPy,、科学计算库,SciPy,，绘图库,Matplotlib,等）。,这些程序以模块的形式提供并被使用,使用时，需要使用,import,等关键字导入。,IPython,及其使用,模块,Import numpy,只是导入,numpy,包，要调用其中的开方函数需要使用,numpy.sqrt(),。,可以利用关键字,as,给包起一个别名，例如其中的,np,。,也可以指定要导入的函数，例如,from numpy import sqrt,exp,，即导入其中的开放函数,sqrt(),和底为自然对数的幂函数,exp(),，这时就不需要指出包名或者其别名，而直接调用即可。,In 16:import numpy,In 17:numpy.sqrt(4),Out17:2.0,In 18:import numpy as np,In 19:np.sqrt(4),Out19:2.0,In 20:from numpy import sqrt,exp,In 21:sqrt(4),Out21:2.0,In 22:exp(3),Out22:20.085536923187668,数据结构,程序中的数据以一定的方式被组织在一起。,常见的数据结构包括对象，列表和数组。,对象,对象是数据和函数的组合体，数据用来表征对象的静态属性，简称属性；函数用来表征对象的动态属性，例如属于对象的各类操作，一般称为方法。,In 33:f=3.14,In 34:f.is_integer(),Out34:False,In 35:s=This is a string.,In 36:s.upper(),Out36:THIS IS A STRING.,数据结构,列表,列表（,List,）是一系列对象的有序集合。,可以将任意一个对象集合使用方括号括起来，创建一个列表对象。,In 3:l=3.14,4,2+1j,c,string,1,2,3,In 4:l0,Out4:3.14,In 5:l1,Out5:4,In 6:l2,Out6:(2+1j),In 7:l3,Out7:c,In 8:l4,Out8:strin