资源描述：
《华工人工智能复习重点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
