资源描述:
《华工人工智能复习重点PPT总结课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、人工智能复习PPT总结水青木白AI的本质问题研究如何制造出人造的智能机器或系统,来模拟人类智能活动的能力,以延伸人们智能的科学。AI的研究内容搜索技术知识表示规划方法机器学习认知科学4第一章搜索问题内容:状态空间的搜索问题。搜索方式:盲目搜索启发式搜索关键问题:如何利用知识,尽可能有效地找到问题的解(最佳解)。5回溯搜索算法递归过程BACKTRACK(DATA)1,IFTERM(DATA)RETURNNIL;2,IFDEADEND(DATA)RETURNFAIL;3,RULES:=APPRULES(DATA);4,LOOP:IFNULL(RULES)RETURNFAIL;5,
2、R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IFPATH=FAILGOLOOP;10,RETURNCONS(R,PATH);6回溯搜索算法11,DATA:=FIRST(DATALIST)2,IFMENBER(DATA,TAIL(DATALIST))RETURNFAIL;3,IFTERM(DATA)RETURNNIL;4,IFDEADEND(DATA)RETURNFAIL;5,IFLENGTH(DATALIST)>BOUNDRETURNFAIL;6,RU
3、LES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8,R:=FIRST(RULES);7回溯搜索算法1(续)9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IFPATH=FAILGOLOOP;14,RETURNCONS(R,PATH);81.2图搜索策略问题的引出回溯搜索:只保留从初始状态到当前状态的一条路径。图搜索:保留所有已经搜索过的路径。9一些基本概
4、念节点深度:根节点深度=0其它节点深度=父节点深度+1012310一般的图搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);11一般的图搜索算法(续)7,标记和修改指针:ADD(mj,OPEN),并标记mj到n的指针;计算是否要修改mk、ml到n的指针;计算是否要修改ml到其后继
5、节点的指针;8,对OPEN中的节点按某种原则重新排序;9,GOLOOP;12深度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目标在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n
6、的指针;10,GOLOOP;13深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制最坏情况时,搜索空间等同于穷举与回溯法的差别:图搜索是一个通用的与问题无关的方法14宽度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G:=ADD(mi,G);7,IF
7、目标在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GOLOOP;15宽度优先搜索的性质当问题有解时,一定能找到解当问题为单位耗散值,且问题有解时,一定能找到最优解方法与问题无关,具有通用性效率较低属于图搜索方法161.4启发式图搜索利用知识来引导搜索,达到减少搜索范围,降低问题复杂度的目的。启发信息的强度强:降低搜索工作量,但可能导致找不到最优解弱:一般导致工作量加大,极限情况下变为盲目搜索,但可能可以找到最优解17符号的意义g*(n):从s到n