热门标签 | 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(转载)

推荐阅读
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • Coursera ML 机器学习
    2019独角兽企业重金招聘Python工程师标准线性回归算法计算过程CostFunction梯度下降算法多变量回归![选择特征](https:static.oschina.n ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 利用决策树预测NBA比赛胜负的Python数据挖掘实践
    本文通过使用2013-14赛季NBA赛程与结果数据集以及2013年NBA排名数据,结合《Python数据挖掘入门与实践》一书中的方法,展示如何应用决策树算法进行比赛胜负预测。我们将详细讲解数据预处理、特征工程及模型评估等关键步骤。 ... [详细]
  • 本文深入探讨了MySQL中常见的面试问题,包括事务隔离级别、存储引擎选择、索引结构及优化等关键知识点。通过详细解析,帮助读者在面对BAT等大厂面试时更加从容。 ... [详细]
  • ML学习笔记20210824分类算法模型选择与调优
    3.模型选择和调优3.1交叉验证定义目的为了让模型得精度更加可信3.2超参数搜索GridSearch对K值进行选择。k[1,2,3,4,5,6]循环遍历搜索。API参数1& ... [详细]
  • PHP 编程疑难解析与知识点汇总
    本文详细解答了 PHP 编程中的常见问题,并提供了丰富的代码示例和解决方案,帮助开发者更好地理解和应用 PHP 知识。 ... [详细]
  • 本文详细介绍了福昕软件公司开发的Foxit PDF SDK ActiveX控件(版本5.20),并提供了关于其在64位Windows 7系统和Visual Studio 2013环境下的使用方法。该控件文件名为FoxitPDFSDKActiveX520_Std_x64.ocx,适用于集成PDF功能到应用程序中。 ... [详细]
  • 本文介绍了在Java环境中使用PDFBox和XPDF工具从PDF文件中提取文本内容的方法。重点讨论了处理中文字符集及解决相关错误的技术细节,特别是针对某些特定格式的PDF文件(如网上填写的报名表和下载的论文)遇到的问题及解决方案。 ... [详细]
  • Ulysses Mac v29:革新文本编辑与写作体验
    探索Ulysses Mac v29,这款先进的纯文本编辑器为Mac用户带来了全新的写作和编辑环境。它不仅具备简洁直观的界面,还融合了Markdown等标记语言的最佳特性,支持多种格式导出,并提供强大的组织和同步功能。 ... [详细]
  • ABBYY FineReader:高效PDF转换、精准OCR识别与文档对比工具
    在处理PDF转换和OCR识别时,您是否遇到过格式混乱、识别率低或图表无法正常识别的问题?ABBYY FineReader以其强大的功能和高精度的识别技术,完美解决这些问题,帮助您轻松找到最终版文档。 ... [详细]
  • 设计模式在软件开发中被广泛应用,但如果不当使用,可能会导致系统复杂性增加。例如,过度添加类可能导致类图难以理解,代码跟踪变得复杂。本文探讨如何在使用设计模式时保持系统的简洁和高效。 ... [详细]
  • 程序员如何优雅应对35岁职业转型?这里有深度解析
    本文探讨了程序员在职业生涯中如何通过不断学习和技能提升,优雅地应对35岁左右的职业转型挑战。我们将深入分析当前热门技术趋势,并提供实用的学习路径。 ... [详细]
  • 优化后的摘要:本文详细分析了当前面临的挑战和机遇,结合具体实例探讨了如何通过创新和改革来推动长期可持续发展。文中还介绍了多种可行的解决方案,并强调了在不同阶段实施这些方案的重要性。 ... [详细]
  • 本文介绍如何在 Visual Studio Code 中使用 Jupyter Notebook 插件,包括创建、编辑和运行笔记本的基本操作。 ... [详细]
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社区 版权所有