资源描述：
《人工智能一般搜索算法原理.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、第三章一般搜索原理盲目搜索启发式搜索归结原理8/9/20211人工智能讲义盲目搜索图搜索策略深度优先搜索宽度优先搜索等代价搜索8/9/20212人工智能讲义一些基本概念节点深度：根节点深度=0其它节点深度=父节点深度+101238/9/20213人工智能讲义一些基本概念（续1）路径设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。8/9/2
2、0214人工智能讲义一些基本概念（续1）扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。8/9/20215人工智能讲义一般的图搜索算法（GRAPHSEARCH）1,G=G0(G0=s),OPEN=(s);2,CLOSED=();3,LOOP:IFOPEN=()EXIT(FAIL);4,n=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IFGOAL(n)EXIT(SUCCESS);6,EXPAND(n)→{mi},G=ADD(mi,G);8/9/202
3、16人工智能讲义一般的图搜索算法（续）7,标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；8/9/20217人工智能讲义深度优先搜索在深度优先搜索中，首先扩展最新产生的(最深的)节点，深度相等的节点可以任意排列。“最晚产生的节点最先扩展”8/9/20218人工智能讲义深度优先搜索算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPEN=()EXIT(
4、FAIL);3,n=FIRST(OPEN);4,IFGOAL(n)EXIT(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的指针;10,GOLOOP;8/9/20219人工智能讲义231847652318476528314765231847652831476528316475283147652831
5、647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标8/9/202110人工智能讲义深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法8/9/202111人工智能讲义宽度优先搜索如果搜索是以接近起始节
6、点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索使逐层进行的，在对下一层的任意节点进行搜索之前，必须搜索完本层的所有节点。“先产生的节点先扩展”8/9/202112人工智能讲义宽度优先搜索算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(OPEN);4,IFGOAL(n)EXIT(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;8/9/202113人工智能讲义23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标82341876548/9/202114人工智能讲义宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且
8、问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法8/9/202115人工智能讲义等代价搜索宽度优先搜索可被推广用来解决寻找从起始节点到目标节点具有最小代价路径问题，这种推广了的宽度优先搜索算法
