人工智能_一般搜索算法原理153

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

2019/8/1人工智能讲义1第三章一般搜索原理•盲目搜索•启发式搜索•归结原理2019/8/1人工智能讲义2盲目搜索•图搜索策略•深度优先搜索•宽度优先搜索•等代价搜索2019/8/1人工智能讲义3一些基本概念•节点深度:根节点深度=0其它节点深度=父节点深度+101232019/8/1人工智能讲义4一些基本概念(续1)•路径设一节点序列为(n0,n1,…,nk),对于i=1,…,k,若节点ni-1具有一个后继节点ni,则该序列称为从n0到nk的路径。•路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。2019/8/1人工智能讲义5一些基本概念(续1)•扩展一个节点生成出该节点的所有后继节点,并给出它们之间的耗散值。这一过程称为“扩展一个节点”。2019/8/1人工智能讲义6一般的图搜索算法(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);2019/8/1人工智能讲义7一般的图搜索算法(续)7,标记和修改指针:ADD(mj,OPEN),并标记mj到n的指针;计算是否要修改mk、ml到n的指针;计算是否要修改ml到其后继节点的指针;8,对OPEN中的节点按某种原则重新排序;9,GOLOOP;2019/8/1人工智能讲义8深度优先搜索•在深度优先搜索中,首先扩展最新产生的(最深的)节点,深度相等的节点可以任意排列。“最晚产生的节点最先扩展”2019/8/1人工智能讲义9深度优先搜索算法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,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G=ADD(mi,G);8,IF目标在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GOLOOP;2019/8/1人工智能讲义10231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标2019/8/1人工智能讲义11深度优先搜索的性质•一般不能保证找到最优解•当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制•最坏情况时,搜索空间等同于穷举•与回溯法的差别:图搜索•是一个通用的与问题无关的方法2019/8/1人工智能讲义12宽度优先搜索•如果搜索是以接近起始节点的程度依次扩展节点的,那么这种搜索就叫做宽度优先搜索。这种搜索使逐层进行的,在对下一层的任意节点进行搜索之前,必须搜索完本层的所有节点。“先产生的节点先扩展”2019/8/1人工智能讲义13宽度优先搜索算法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目标在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GOLOOP;2019/8/1人工智能讲义1423184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标82341876542019/8/1人工智能讲义15宽度优先搜索的性质•当问题有解时,一定能找到解•当问题为单位耗散值,且问题有解时,一定能找到最优解•方法与问题无关,具有通用性•效率较低•属于图搜索方法2019/8/1人工智能讲义16等代价搜索•宽度优先搜索可被推广用来解决寻找从起始节点到目标节点具有最小代价路径问题,这种推广了的宽度优先搜索算法叫做等代价搜索算法。2019/8/1人工智能讲义17等代价搜索算法•算法1,G=G0(G0=s),OPEN=(s),CLOSED=(),g(s)=0;2,LOOP:IFOPEN=()EXIT(FAIL);3,从OPEN表中选择一个节点i,使其g(i)为最小。如果有几个节点都合格,那么就要选择一个目标节点作为i(要是有目标节点的话);否则,就从中选一个作为节点I;REMOVE(i,OPEN),ADD(i,CLOSED);4,IFGOAL(i)EXIT(SUCCESS);5,EXPAND(i)→{j},G=ADD(j,G);6,对每个后继节点j,计算g(j)=g(i)+c(i,j)且ADD(OPEN,j),并标记j到i的指针;7,GOLOOP;2019/8/1人工智能讲义18启发式图搜索•利用知识来引导搜索,达到减少搜索范围,降低问题复杂度的目的。•启发信息的强度–强:降低搜索工作量,但可能导致找不到最优解–弱:一般导致工作量加大,极限情况下变为盲目搜索,但可能可以找到最优解2019/8/1人工智能讲义19希望:•引入启发知识,在保证找到最佳解的情况下,尽可能减少搜索范围,提高搜索效率。2019/8/1人工智能讲义20基本思想•定义一个评价函数f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展。2019/8/1人工智能讲义211,启发式搜索算法A(A算法)•评价函数的格式:f(n)=g(n)+h(n)f(n):评价函数h(n):启发函数2019/8/1人工智能讲义22符号的意义•g*(n):从s到n的最短路径的耗散值•h*(n):从n到g的最短路径的耗散值•f*(n)=g*(n)+h*(n):从s经过n到g的最短路径的耗散值•g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值2019/8/1人工智能讲义23A算法1,OPEN=(s),f(s)=g(s)+h(s);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},计算f(n,mi)=g(n,mi)+h(mi);2019/8/1人工智能讲义24A算法(续)ADD(mj,OPEN),标记mj到n的指针;IFf(n,mk)f(mk)f(mk)=f(n,mk),标记mk到n的指针;IFf(n,ml)f(ml,)f(ml)=f(n,ml),标记ml到n的指针,ADD(ml,OPEN);7,OPEN中的节点按f值从小到大排序;8,GOLOOP;2019/8/1人工智能讲义25一个A算法的例子定义评价函数:f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的耗散值h(n)为当前节点“不在位”的将牌数28316475123847652019/8/1人工智能讲义26h计算举例h(n)=428316475123457682019/8/1人工智能讲义272831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标123456定义评价函数:f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的耗散值h(n)为当前节点“不在位”的将牌数2019/8/1人工智能讲义28最佳图搜索算法A*(A*算法)•在A算法中,如果满足条件:h(n)≤h*(n)则A算法称为A*算法。2019/8/1人工智能讲义29A*条件举例•8数码问题–h(n)=“不在位”的将牌数–h(n)=将牌“不在位”的距离和2831647512345768将牌1:1将牌2:1将牌6:1将牌8:22019/8/1人工智能讲义30A*算法的性质定理1:对有限图,如果从初始节点s到目标节点t有路径存在,则算法A一定成功结束。2019/8/1人工智能讲义31A*算法的性质(续1)引理2.1:对无限图,若有从初始节点s到目标节点t的路径,则A*不结束时,在OPEN表中即使最小的一个f值也将增到任意大,或有f(n)f*(s)。2019/8/1人工智能讲义32A*算法的性质(续2)引理2.2:A*结束前,OPEN表中必存在f(n)≤f*(s)。2019/8/1人工智能讲义33A*算法的性质(续3)定理2:对无限图,若从初始节点s到目标节点t有路径存在,则A*一定成功结束。2019/8/1人工智能讲义34A*算法的性质(续4)推论2.1:OPEN表上任一具有f(n)f*(s)的节点n,最终都将被A*选作扩展的节点。2019/8/1人工智能讲义35A*算法的性质(续5)定理3(可采纳性定理):若存在从初始节点s到目标节点t有路径,则A*必能找到最佳解结束。2019/8/1人工智能讲义36A*算法的性质(续6)推论3.1:A*选作扩展的任一节点n,有f(n)≤f*(s)。2019/8/1人工智能讲义37A*算法的性质(续7)定理4:设对同一个问题定义了两个A*算法A1和A2,若A2比A1有较多的启发信息,即对所有非目标节点有h2(n)h1(n),则在具有一条从s到t的路径的隐含图上,搜索结束时,由A2所扩展的每一个节点,也必定由A1所扩展,即A1扩展的节点数至少和A2一样多。简写:如果h2(n)h1(n),则A1扩展的节点数≥A2扩展的节点数2019/8/1人工智能讲义38A*算法的改进•问题的提出:因A算法第6步对ml类节点可能要重新放回到OPEN表中,因此可能会导致多次重复扩展同一个节点,导致搜索效率下降。2019/8/1人工智能讲义39s(10)A(1)B(5)C(8)G目标631118一个例子:OPEN表CLOSED表s(10)s(10)A(7)B(8)C(9)A(7)s(10)B(8)C(9)G(14)A(5)C(9)G(14)C(9)G(12)B(7)G(12)A(4)G(12)G(11)A(7)B(8)s(10)A(5)B(8)s(10)C(9)A(5)B(8)s(10)A(5)B(7)C(9)s(10)A(4)B(7)C(9)s(10)2019/8/1人工智能讲义40出现多次扩展节点的原因•在前面的扩展中,并没有找到从初始节点到当前节点的最短路径,如节点A。2019/8/1人工智能讲义41解决的途径•对h加以限制–能否对h增加适当的限制,使得第一次扩展一个节点时,就找到了从s到该节点的最短路径。•对算法加以改进–能否对算法加以改进,避免或减少节点的多次扩展。2019/8/1人工智能讲义42改进的条件•可采纳性不变•不多扩展节点•不增加算法的复杂性2019/8/1人工智能讲义43对h加以限制•定义:一个启发函数h,如果对所有节点ni和nj,其中nj是ni的子节点,满足h(ni)-h(nj)≤c(ni,nj)h(t)=0则称h

1 / 153
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功