-1

我现在这是一个被问过很多次的问题。但是，我找不到针对我的具体问题的解决方案。

我已经在 C++11 和两个不同的变体中实现了快速行进方法（非常类似于 Dijkstra）：斐波那契堆和二进制堆。为此，我使用了 Boost 1.55 堆实现（Fibonacci 和 D_ary，D=2）。

预计二进制堆在小型网格中更快，而斐波那契在大型网格中更快。但是，二叉堆总是更快（并且存在“巨大”差异）。例如：

200x200 grid: 
 Binary: 16 ms
 Fibonacci: 24 ms

300x300 grid: 
 Binary: 38 ms
 Fibonacci: 50 ms

500x500 grid: 
 Binary: 113 ms
 Fibonacci: 148 ms

1000x1000 grid: 
 Binary: 504 ms
 Fibonacci: 642 ms

我-Ofast -fno-finite-math-only在 G++ 4.8 中使用标志。

要点是我可以保证几周前完全相同的实现返回了预期的结果。

有人可以给我一些启示吗？

谢谢！

4

1 回答 1

1

其实我找到了答案，不需要代码：

有两个不同的问题： - 1：这取决于 CPU。相同的 Ubuntu 发行版、相同的编译器、相同的代码在同一台计算机上提供不同的结果。- 2：网格尺寸不够大。我不得不提高到 4000x4000 以便 Dary 版本比 Fibonacci 版本获得更长的时间。在我测试的其他计算中（均为 64 位），使用 2000x2000 网格就足够了，以获得预期的结果。

此外，它取决于计算距离图的原点，以及其他取决于堆理论和快速行进方法的小点。

于 2014-04-09T09:51:00.250 回答