我有两个数组，一个是节点节点成本数组 [a_node,b_node,cost]，它有 8000 个条目，另一个是节点与坐标 [node,x,y] 的关联，它也有大约 8000 个条目. 拥有这两个的静态数组更好还是将它们存储在数据库中并从中创建一个数组作为性能问题更好？
这两个数组将用于运行最短路径算法。
问问题
445 次
2 回答
0
听起来您可能希望使用动态编程解决方案，在每次迭代中计算问题的一小部分并存储中间结果，这将允许您在完成所有中间计算后计算最短路径.
我建议将您的所有信息存储在数据库中并选择记录的子集（一次可能 100 条？）。计算每个节点的中间信息并将其存储回数据库。如果您要重复使用此路径信息数千或数百万次，您不希望不断地重新计算它。您只想在图表更改时重新计算。
我首选的最短路径算法是http://en.wikipedia.org/wiki/Dijkstra 's_algorithm，它适用于高效的动态编程解决方案。
于 2011-03-04T03:00:19.240 回答
0
如果您已经对其进行了测试，您会为自己找到答案——很大程度上取决于您如何填充数组以及您从现有数组中取消引用元素的频率。当使用数据库存储/操作数据时，前者的速度要快得多。后者更像是一个灰色地带——但在大多数情况下，数据库仍然可以证明更快。
（除非这是你的作业，并且考虑到节点的数量，我建议考虑使用非确定性方法 - 遗传算法是一个明显的候选者）
于 2011-03-04T09:08:56.200 回答