广搜(BFS)+深搜(DFS)

    xiaoxiao2023-11-07  162

    广搜(BFS)

    广搜原理

    广搜可以看作一种盲人摸象的搜索方法,大象是要求进行搜索的对象,盲人开始摸从身子开始,一个一个结点地向外扩展,当摸到大象的鼻子时找到结果,知道这是大象。 再系统地讲:

    首先访问初始点 Vi ,并将其标记为已访问过,接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2…Vit,并均标记为已访问过,然后再按照Vi1、Vi2…Vit 的次序,访问每一个顶点的所有未被访问过的邻接点,并均标记为已访问过,依此类推,直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。

    广搜优缺点

    优点 1、对于解决最短或最少问题特别有效,而且寻找深度小 2、每个结点只访问一遍,结点总是以最短路径被访问,所以第二次路径确定不会比第一次短缺点 1、内存耗费量大

    广搜模板

    void BFS() { … …//初始化起点入队 while(!q.empty()) //判断队是否为空 { … …//获取队首元素 if(...){… …}//判断是否是终点 for(int i=0;i<4;i++)//四个方向 { k.x=p.x+dir[i][0]; k.y=p.y+dir[i][1]; //向各个方向走一步 if(judge())//判断能不能走 { … …//各种处理 vis[k.x][k.y]=1; //标记 q.push(k); //入队 } } } }

    只看枯燥的文字和代码不太方便记忆,看了别人的一个比喻很好引用下: 如果广搜是一个人,那么他一定是一个花花公子,万花丛中过片叶不沾身,而且不吃回头草,与各路美女都有绯闻。一天他与一位女子一见钟情,便在内心许下了非她不娶的终身诺言,他的爱情终于有了结果。

    深搜(DFS)

    深搜原理

    大概思路

    如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到A,A也没有未访问的相邻节点,本次搜索结束).

    直接上比喻吧: 如果深搜是一个人,那么他的性格一定倔得像头牛! 他从一点出发去旅游,只朝着一个方向走,除非路断了,他绝不改变方向!除非四个方向全都不通或遇到终点,他绝不后退一步!因此,他的哥哥广搜总是嘲笑他,说他是个一根筋、不撞南墙不回头的家伙。   深搜很讨厌他哥哥的嘲笑,但又不想跟自己的哥哥闹矛盾,于是他决定给哥哥讲述自己旅途中的经历,来改善哥哥对他的看法。他成功了,而且只讲了一次。从那以后他哥哥不仅再没有嘲笑过他,而且连看他的眼神都充满了赞赏。他以为是自己路上的各种英勇征服了哥哥,但他不知道,其实另有原因……   深搜是这样跟哥哥讲的:关于旅行呢,我并不把目的地的风光放在第一位,而是更注重于沿路的风景,所以我不会去追求最短路,而是把所有能通向终点的路都走一遍。可是我并不知道往哪走能到达目的地,于是我只能每到一个地方,就向当地的人请教各个方向的道路情况。为了避免重复向别人问同一个方向,我就给自己规定:

    先往北,如果有路,那就往北走,到达下一个地方的时候就在执行此规定,如果往北不通,我就再问西,其次是南、东,要是这四个方向都不通或者抵达了终点,那我回到上一个地方,继续探索其他没去过的方向。我还要求自己要记住那些帮过他的人,但是那些给我帮倒忙的、让我白费力气的人,要忘记他们。有了这些规定之后,我就可以大胆的往前走了,既不用担心到不了不目的地,也不用担心重复走以前的路。哈哈哈……

    深搜的优缺点

    优点 1、能找出所有解决方案 2、优先搜索一棵子树,然后是另一棵,所以和广搜对比,有着内存需要相对较少的优点缺点 1、要多次遍历,搜索所有可能路径,标识做了之后还要取消。 2、在深度很大的情况下效率不高

    深搜模板

    void DFS() //N代表目前DFS的深度 { if(找到解) //进行相应的操作 {return; } for(inti=0;i<4;i++) //枚举四个方向 { DFS(N+1); //进入下层递归 } }
    最新回复(0)