热门标签 | HotTags
当前位置:  开发笔记 > 后端 > 正文

双向BFS和sixdegree

http:isites.harvard.edufsdocsicb.topic707165.filespdfsJirapinyo_Yang.pdf今天liveramp面试考到了

http://isites.harvard.edu/fs/docs/icb.topic707165.files/pdfs/Jirapinyo_Yang.pdf

今天liveramp面试考到了six degree的题,上面这篇论文阐述的相当好,值得参考。同时也转载了一些,供自己复习。

如果已经知道搜索的开始状态和结束状态,要找一个满足某种条件的一条路径(一般是最短路径),为了避免无谓的“组合爆炸”产生,就可以采取双向广度搜索算法,也就是从开始状态和结束状态同时开始搜索,一个向前搜,一个向后找。 

这样做的好处是什么?
    我们不妨假设每次搜索的分支因子是r,如果最短的路径长为L的话(也就是搜了L层),那么,用一般的BFS算法(不考虑去掉重复状态),总的搜索状态数是r^L(^表示乘方运算);而如果采取双向BFS算法,那么,从前往后搜,我们只需要搜索L/2层,从后往前搜,我们也只要搜L/2层,因此,搜索状态数是2*(r^(L/2)),比普通BFS就快了很多了。 

    双向BFS算法的实质还是BFS,只不过两边同时开始BFS而已。还是可以利用队列来实现:可以设置两个队列,一个用于向前的BFS,另一个用于向后的BFS,利用这两个队列,同时从前、后开始层次遍历搜索树。

双向bfs(转载)

双向bfs(转载)

推荐阅读
author-avatar
kingseao
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有