1

我正在做一个学术项目：编写一个库，用于在大型加权有向图上找到最短路径。

规格为：

  • 示例数据集是一个包含 1500 个顶点的图，每个节点平均有 5.68 条边。规格可能会有所不同，最多 20.000 个节点。

  • 此外，我正在一个 cpu / memory bound 环境中工作：Android。

  • 边缘权重不是微不足道的，也不是恒定的。它取决于图形的可变状态。

  • 我们必须离线工作。

我面临几个困难：

  • 我需要一种有效的方法来存储、检索和更新图形数据。我应该使用带有来自 Java 类的查询的 SQLite 对象、堆上的大型自定义 java 对象，还是什么？我认为这是对性能最关键的方面。

  • 我需要一种有效的方法来实现某种短路径算法。由于所有权重都是正数，我是否应该应用 Dijikstra 算法和 ArrayList 作为访问节点的容器？

  • 这是使用 NDK 的好案例吗？该任务是 CPU 密集型的，但它也会频繁访问内存，所以我不这么认为，但我愿意做出贡献。

  • 永远记住资源稀缺，内存不足，磁盘慢，cpu 是宝贵的（电池）。

欢迎任何建议，干杯:)

4

2 回答 2

3

对于这么多节点，我建议购买一些云计算服务，让安卓应用程序与之通信。
Hadoop 的 MapReduce on Amazon's Cloud 怎么样，有很多图框架，例如 Mahout，它真的很快。
如果有更多的节点和边，至少是非常可扩展的。

于 2011-01-16T11:36:41.980 回答
0

链表是存储大稀疏图的最佳数据结构。

于 2020-11-13T15:58:46.137 回答