人工智能第一章课件讲义.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《人工智能第一章课件讲义.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 第一章 课件 讲义
- 资源描述:
-
1、 有许多智力问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)许多实际问题(如最优路径规划、人力排班、装箱问题、机器人行动规划等)都可以归结为在某一状态空间中搜索目标都可以归结为在某一状态空间中搜索目标或路径的问题。或路径的问题。问题:如何解决这类问题?这类问题不能用简单的数学公式/数学方程来描述,属于非结构化问题。难以获得求解所需的全部信息;更没有现成的算法可供求解使用 属于组合爆炸问题,稍大规模的问题就超出了人类的认知负荷解决方法:利用计算机的超人计算能力,通过不断试探搜索找到问题的(最优)解。优点建模简单具体方法:状态空间法 状态:是指问题状态的的向量表示(x,y,z,.)。问题
2、有初始状态,有目标状态 有些状态可能是非法的,问题不可能发展到那种状态 问题表示为向量,向量就是在Euclidean空间,因此问题的初始状态和目标状态都是此空间中的点。此类问题的特征是找出从初始状态到目标状态的路径,方法是通过一个状态向另一个状态的转换实现的。内容:状态空间的搜索问题。搜索方式:盲目搜索 启发式搜索 关键问题:如何利用知识,尽可能有效地找到问题的解(最佳解),寻找过程就是搜索。状态空间法状态空间法1.状态空间表示方法状态空间表示方法状态状态(State):求解过程中每一步问题状况的表示:求解过程中每一步问题状况的表示Sk=Sk0,Sk1)当对每一个分量都给以确定的值时,就得到了
3、一个具体的当对每一个分量都给以确定的值时,就得到了一个具体的状态。状态。操作操作(Operator):也称为算符,它是把问题从一种状态变也称为算符,它是把问题从一种状态变换为另一种状态的手段。操作可以是一个机械步骤,一换为另一种状态的手段。操作可以是一个机械步骤,一个运算,一条规则或一个过程。个运算,一条规则或一个过程。状态空间状态空间(State space):用来描述一个问题的全部状态用来描述一个问题的全部状态以及这些状态之间的相互关系。常用表示为以及这些状态之间的相互关系。常用表示为(S,F,G)其中,其中,S为问题的所有初始状态的集合;为问题的所有初始状态的集合;F为操作的集合;为操作
4、的集合;G为目标状态的集合。为目标状态的集合。状态空间也可用一个赋值的有向图来表示,称为状态状态空间也可用一个赋值的有向图来表示,称为状态空间图空间图,其中节点表示问题的状态,有向边表示操作。其中节点表示问题的状态,有向边表示操作。状态空间法求解问题的基本过程:状态空间法求解问题的基本过程:1.1.首先为问题选择适当的首先为问题选择适当的“状态状态”及及“操作操作”的的形式化描述方法;形式化描述方法;2.2.然后从某个初始状态出发,每次使用一个然后从某个初始状态出发,每次使用一个“操操作作”,递增地建立起操作序列,直到达到目标,递增地建立起操作序列,直到达到目标状态为止;状态为止;此时,由初始
5、状态到目标状态所使用的算符序此时,由初始状态到目标状态所使用的算符序列就是该问题的一个解。列就是该问题的一个解。状态空间法状态空间法2.状态空间问题求解状态空间问题求解 修道士修道士(Missionaries)和野人和野人(Cannibals)问题问题(简称简称M-C问问题题)。设在河的一岸有三个野人、三个修道士和一条船,修道士想设在河的一岸有三个野人、三个修道士和一条船,修道士想用这条船把所有的人运到河对岸,但受以下条件的约束:用这条船把所有的人运到河对岸,但受以下条件的约束:1.修道士和野人都会划船,但每次船上至多可载两个人;修道士和野人都会划船,但每次船上至多可载两个人;2.在河的任一岸
6、,如果野人数目超过修道士数,修道士会被在河的任一岸,如果野人数目超过修道士数,修道士会被野人吃掉。野人吃掉。如果野人会服从任何一次过河安排,请规划一个确保修道如果野人会服从任何一次过河安排,请规划一个确保修道士和野人都能过河,且没有修道士被野人吃掉的安全过河士和野人都能过河,且没有修道士被野人吃掉的安全过河计划。计划。状态空间法状态空间法3.状态空间的例子状态空间的例子 解:首先选取描述问题状态的方法。在这个问题中,需要解:首先选取描述问题状态的方法。在这个问题中,需要考虑两岸的修道士人数和野人数,还需要考虑船在左岸还是在考虑两岸的修道士人数和野人数,还需要考虑船在左岸还是在右岸。从而可用一个
7、三元组来表示状态右岸。从而可用一个三元组来表示状态 S=(m,c,b)其中,其中,m表示左岸的修道士人数,表示左岸的修道士人数,c表示左岸的野人数,表示左岸的野人数,b表示表示左岸的船数。左岸的船数。右岸的状态可由下式确定:右岸的状态可由下式确定:右岸修道士数右岸修道士数 m=3-m 右岸野人数右岸野人数 c=3-c 右岸船数右岸船数 b=1-b 在这种表示方式下,在这种表示方式下,m和和c都可取都可取0、1、2、3中之一,中之一,b可取可取0和和1中之一。因此,共有中之一。因此,共有442=32种状态。种状态。状态空间法状态空间法3.状态空间的例子状态空间的例子 这这32种状态并非全有意义,
8、除去不合法状态和修道士被野人吃种状态并非全有意义,除去不合法状态和修道士被野人吃掉的状态,有意义的状态只有掉的状态,有意义的状态只有16种:种:S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S11=(2,2,0)S12=(1,1,0)S13=(0,2,0)S14=(0,1,0)S15=(0,0,0)有了这些状态,还需要考虑可进行的操作。有了这些状态,还需要考虑可进行的操作。操作是指用船把修道士或野人从河的左岸运到右岸,或
9、从河的操作是指用船把修道士或野人从河的左岸运到右岸,或从河的右岸运到左岸。右岸运到左岸。每个操作都应当满足如下条件:每个操作都应当满足如下条件:一是船至少有一个人(一是船至少有一个人(m或或c)操作,离开岸边的)操作,离开岸边的m和和c的减少数的减少数目应该等于到达岸边的目应该等于到达岸边的m和和c的增加数目;的增加数目;二是每次操作船上人数不得超过二是每次操作船上人数不得超过2个;个;三是操作应保证不产生非法状态。三是操作应保证不产生非法状态。因此,操作应由条件部分和动作部分:因此,操作应由条件部分和动作部分:条件:只有当其条件具备时才能使用条件:只有当其条件具备时才能使用 动作:刻划了应用
10、此操作所产生的结果。动作:刻划了应用此操作所产生的结果。操作的表示:操作的表示:用符号用符号Pij表示从左岸到右岸的运人操作表示从左岸到右岸的运人操作 用符号用符号Qij表示从右岸到左岸的操作表示从右岸到左岸的操作其中:其中:i表示船上的修道士人数表示船上的修道士人数 j表示船上的野人数表示船上的野人数操作集操作集 本问题有本问题有10种操作可供选择:种操作可供选择:F=P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20 下面以下面以P01和和Q01为例来说明这些操作的条件和动作。为例来说明这些操作的条件和动作。操作符号操作符号 条件条件 动作动作 P01 b=1,
11、m=0或或m=3,c1 b=0,c=c-1 Q01 b=0,m=0或或m=3,c2 b=1,c=c+1 S0Sg 讨论的问题:有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗?什么情况下可以找到最佳解?求解的效率如何。例:皇后问题QQQQ()()Q(1,1)()QQ(1,1)(1,1)(2,3)()Q(1,1)(1,1)(2,3)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4)(3.2)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()Q(1,1)(
12、1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)
13、Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)Q(1,2)(2,4)(3,1)(4,3)当前状态目标状态gint ListLenght(LIST*pList)if(pList=NULL)return 0;else return ListLength(pList-next)+1;NULLpLIST123BACKTRACK(DATA)DATA:当前状态。返回值:从当前状态到目标状态的路径(以规则表的形式表示)或FAIL。递归过程BACKTRACK(DATA)1,IF TERM(DATA)RETURN NIL;2,IF DEADEND(DATA)RETURN FAIL;3,RUL
14、ES:=APPRULES(DATA);4,LOOP:IF NULL(RULES)RETURN FAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IF PATH=FAIL GO LOOP;10,RETURN CONS(R,PATH);解决办法:对搜索深度加以限制 记录从初始状态到当前状态的路径当前状态l问题:深度问题死循环问题BACKTRACK1(DATALIST)DATALIST:从初始到当前的状态表(逆向)返回值:从当前状态到目标状态的路径(以规则表的形式表示
15、)或FAIL。1,DATA:=FIRST(DATALIST)2,IF MENBER(DATA,TAIL(DATALIST)RETURN FAIL;3,IF TERM(DATA)RETURN NIL;4,IF DEADEND(DATA)RETURN FAIL;5,IF LENGTH(DATALIST)BOUND RETURN FAIL;6,RULES:=APPRULES(DATA);7,LOOP:IF NULL(RULES)RETURN FAIL;8,R:=FIRST(RULES);9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=
16、CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R,PATH);失败原因分析、多步回溯QQ 回溯搜索中知识的利用基本思想(以皇后问题为例):尽可能选取划去对角线上位置数最少的。QQQQ3 2 2 3 问题的引出 回溯搜索:只保留从初始状态到当前状态的一条路径。图搜索:保留所有已经搜索过的路径。节点深度:根节点深度=0其它节点深度=父节点深度+10123 路径设一节点序列为(n0,n1,nk),对于i=1,k,若节点ni-1具有一个后继节点ni,则该序列称为从n0到n
17、k的路径。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。扩展一个节点生成出该节点的所有后继节点,并给出它们之间的耗散值。这一过程称为“扩展一个节点”。1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IF OPEN=()THEN EXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IF GOAL(n)THEN EXIT(SUCCESS);6,EXPAND(n)mi,G:=ADD(mi,G);7,标记和修改指针:ADD(m
展开阅读全文