首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >带小ram的大型图的广度优先搜索

问带小ram的大型图的广度优先搜索
EN

Stack Overflow用户
提问于 2010-02-13 18:04:12
回答 3查看 4K关注 0票数 7

我目前有一个图,它有大约、1000万个节点、和--3500万个边缘。现在,完整的图表在程序开始时被加载到内存中。这需要几分钟(毕竟是Java ),并且需要大约半is的RAM。目前,它运行在一台带有双核处理器和4G内存的机器上。

当使用宽度优先搜索图时,内存使用量上升到1G的峰值,平均需要10秒。

我想把这个程序部署在几台电脑上。除了图搜索之外,这个功能所需的资源非常少。我的目标系统非常小,只有512兆内存。

对于如何在不消耗太多内存的情况下实现一个方法(可能使用数据库)来搜索该图,有什么建议吗?该程序大部分时间是空闲的,因为它正在访问一个硬件设备,所以路径查找可能需要大约5分钟对上述图形.

谢谢你对我提出的任何想法。

更新:

刚找到neo4j。有人知道它是否适合这种巨大的图形吗?

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2010-02-13 18:26:39

你的问题有点模糊,但总的来说,一个好的策略主要是遵循广度优先语义,同时使用与深度优先搜索相同的内存量的策略是迭代深化。这样做的想法是,首先进行深度优先搜索,限制在1层;如果没有找到解决方案,从零开始,将其限制在2层;如果失败,则尝试3层,等等。

这在一开始看起来有点多余,但是由于您正在进行深度优先搜索,所以内存中的节点要少得多,并且总是比直接的广度优先搜索少搜索一个级别。由于一个级别中节点的数量呈指数增长,在较大的图上,很可能节省最后一个额外的级别,因为冗余地尝试前面的所有层是有回报的。

票数 8
EN

Stack Overflow用户

发布于 2010-02-13 21:32:31

我想说的是,当您有这样一个像样的大小图时,Neo4j绝对是一个很好的选择。它不仅有内置的BFS算法,还可以将数据持久化到磁盘上,从而缩短启动时间。

在highscalability.com:NEO4J -一个启动臀部的图形数据库上查看这个

我使用过Neo4j,它们的文档非常好,它们提供了一些很好的入门示例,确实只需要几分钟就能完成。

看看他们的- 10分钟开始指南

票数 1
EN

Stack Overflow用户

发布于 2014-04-17 15:56:41

Neo4j将数据作为图存储在数据库中,它将成为持久化的,您可以使用图遍历Api (BFS、DBS、A* Dijkstra . )或使用Cypher查询语言进行访问。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/2258509

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档