图搜索技术ppt课件.ppt

《图搜索技术ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3讲图搜索技术状态图搜索与或图搜索博弈树搜索1第一节状态图搜索八数码难题有3*3的方格棋盘棋盘中放置有八个小方块，分别标识有1-8八个数码，另有一空方格与棋盘中空方格相邻的小方块可以移入空方格，或从另外一个角度来说，空方格可以移动要解决的问题：从一个初始棋局（如图-1），经过若干步空方格的移动，达到指定的目标棋局（如图-2）2831647512384765图-1初始棋局图-2目标棋局228367415图-3状态空间图（部分）28316475283164752831476528316475283

2、641752831476523184765283147658326417528364175832147652837146523184765231847658326417523684175283641758321476528371465123847658326417586324175286431752836451728367415123784658321476528367415813247652837461528371465123847652368417523684175。。。。。。。。。*3状态

3、空间图针对某个具体问题节点：代表问题的一个状态（格局）边：表示节点之间的某种联系，如一步操作、一步变换、一类关系等问题确定（初始状态、操作类别、目标状态确定）以后，状态空间图确定，只是没有显式地表示出来，称为隐含图解决该问题，即要在该隐含图中寻找一条从初始节点到达目标节点的路径该问题的解即这条路径上的节点序列或边序列（如操作序列）寻找解路径的过程可以看作是在状态空间图中从初始节点出发搜索目标节点的过程不同的搜索策略形成不同的解决问题的方法4盲目搜索1、一般的图搜索算法：(1)G:=G0(G0=s

4、),OPEN:=(s);/*G表示搜索图，s为初始节点，设置OPEN表，最初只含初始节点(2)CLOSED:=();/*设置CLOSED表，起始设置为空表(3)LOOP:IFOPEN=(),THENEXIT(FAIL);(4)n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);/*称n为当前节点(5)IFGOAL(n),THENEXIT(SUCCESS);/*由n返回到s路径上的指针，可给出解路径5(6)扩展节点n,G:=ADD(mi,G);/*扩展节点n，即

5、得到与n相连的节点集合{mt}，子节点集{mi}是去掉{mt}中的n的先辈节点得到的集合/*{mi}={mj}∪{mk}∪{ml},其中{mk}为已出现在OPEN中的节点，{ml}为已出现在CLOSED中的节点(7)标记和修改指针ADD(mj,OPEN),并标记mj连接到n的指针；/*mj为OPEN和CLOSED中未出现过的子节点如果mk→n→s的路径比原mk→s的路径短，则修改mk的指针连接到n；如果ml→n→s的路径比原ml→s的路径短，则修改ml的指针连接到n，并且将ml移入OPEN表中重

6、新扩展；(8)对OPEN中的节点按某种原则重新排序；(9)GOLOOP;6S0642153S0642153扩展节点1以前扩展节点1以后7说明：这个一般的图搜索过程，通过不断循环生成一个显式表示的图G（搜索图）和一个G的子集T（搜索树）树T是由（7）中标记的指针决定的，除根节点s外，G中每个节点只有一个指针指向G中的一个父节点OPEN表中的节点（未扩展节点）是搜索树的端节点，即尚未被选作为扩展的节点；CLOSED表中的节点（已扩展节点），可以是已被扩展而不能生成后继节点的那些端节点，也可以是树中的

7、非端节点（8）中对OPEN表上的节点进行排序是为了在（4）中能选出一个“最好”的节点优先扩展，不同的排序方法可构成形式多样的专门搜索算法***上述算法的关键一步是（8），对OPEN表的排序，即决定节点的扩展顺序，典型的有两种节点扩展顺序，得到两种搜索算法（广度优先搜索、深度优先搜索）82、广度优先搜索以接近初始节点的程度依次扩展节点，即它的搜索树是自顶向下一层一层生成的这种方法能找到问题的最优解广度优先是完备的3、深度优先搜索每次扩展的都是最新产生的（即最深的）节点，它的搜索树从树根开始一枝一枝

8、形成一般的深度优先搜索都有一个深度限制，当到达一定的限度以后不再向深度扩展，而是改变方向继续搜索这种方法不一定能找到解路径（如果解路径的深度超出了限制深度），另外它得到的解也不一定是最优解迭代深入深度优先算法***以上讨论的搜索算法都试图考察状态空间图中的每一个节点(穷举法)，空间和时间效率低，称为盲目搜索9启发式搜索问题的提出利用问题的启发性信息来引导搜索减少搜索范围降低问题复杂度启发性信息用于扩展节点的选择即决定下一个扩展节点,以免象在广度优先和深度优先搜索中那样盲目地扩展用于生成节点的选择