文档介绍：盲目搜索图搜索策略深度优先搜索宽度优先搜索等代价搜索2020/3/271人工智能讲义一些基本概念节点深度: 根节点深度=0 其它节点深度=父节点深度+101232020/3/272人工智能讲义一些基本概念(续1)路径设一节点序列为(n0,n1,…,nk),对于i=1,…,k,若节点ni-1具有一个后继节点ni,则该序列称为从n0到nk的路径。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。2020/3/273人工智能讲义一些基本概念(续1)扩展一个节点生成出该节点的所有后继节点,并给出它们之间的耗散值。这一过程称为“扩展一个节点”。2020/3/274人工智能讲义一般的图搜索算法(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(ESS);6,EXPAND(n)→{mi},G=ADD(mi,G);2020/3/275人工智能讲义一般的图搜索算法(续)7,标记和修改指针: ADD(mj,OPEN),并标记mj到n的指针; 计算是否要修改mk、ml到n的指针; 计算是否要修改ml到其后继节点的指针;8,对OPEN中的节点按某种原则重新排序;9,GOLOOP;2020/3/276人工智能讲义深度优先搜索在深度优先搜索中,首先扩展最新产生的(最深的)节点,深度相等的节点可以任意排列。“最晚产生的节点最先扩展”2020/3/277人工智能讲义深度优先搜索算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(OPEN);4,IFGOAL(n)EXIT(ESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G=ADD(mi,G);8,IF目标在{mi}中THENEXIT(ESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GOLOOP;2020/3/278人工智能讲义231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标2020/3/279人工智能讲义深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制最坏情况时,搜索空间等同于穷举与回溯法的差别:图搜索是一个通用的与问题无关的方法2020/3/2710人工智能讲义