A*（AStar）算法的良好基准是什么？

Question

我写了一个A*算法，它运行得很好，现在是时候评估它的性能了（可能与其他解决方案进行比较以查看其表现）。

为了获得视觉反馈和乐趣，我将其用作图像迷宫求解器。首先 - 我知道这不是A*算法的主要设计目的，但我认为这是一个相当不错的测试方法（虽然不是唯一的方法）。同意吗？我将其保持非常简单：白色像素是节点，其他颜色是墙壁。

我考虑过向它投掷this maze（大图片），但我知道这会：

• 显然需要一些时间，因为它有超过3,000,000个边缘（还有一半不到的墙壁，但仍然很多）
• 不一定是一个好的指标，因为环境过大

总之：什么样的环境是对A*算法的良好压力测试？应用A*算法中图形的数量级是多少（例如在游戏中）？

- teh internets is made of catz

---

我不确定这个问题是否有意义 - 我认为根本不存在“普遍有效的指标”。不同的优化方法在问题上的表现好坏也不同; 一些方法，如使用布尔网格来存储关闭列表，在许多情况下甚至根本不适用，但是当它们适用时可能（但并不一定）非常棒。 - harold

@harold 可能没有“一张桌子统治它们所有”，那是肯定的，但我认为有一些有趣的尝试。我不是在谈优化，我想知道像我链接的迷宫那样的迷宫是否是一个非常特殊的情况，不能代表算法的全局用途。 - teh internets is made of catz

好吧，至少这是一个有趣的测试，如果这就是你的意思。 - harold

Answer 1

一个好的压力测试需要一个数字化的道路网络：
1）涵盖一个大国家的一部分（如西班牙，法国，德国），然后
2）整个国家。（数百万节点）
OpenStreetMap提供了这样的数据，但导入到图形中需要很多工作。

- AlexWien

---

这是一个非常好的想法，但恐怕它超出了我的专业知识范围（我认为这是非常复杂的数据）。不过我还是会去看一下的！ - teh internets is made of catz

@tehinternetsismadeofcatz GraphHopper 已经可以轻松地导入大量来自OpenStreetMap的数据（例如全球），因此这不再需要太多工作。它实现了A *算法，但您可以轻松地使用Java实现自己的算法，并且更重要的是：您可以比较和改进性能 :) - Karussell

@AlexWien 对于我/GraphHopper来说，全球范围内的场景大约有8千万个节点和近1.1亿条汽车边缘。德国有900万条边缘和700万个节点。 - Karussell

谢谢提供的信息。Navis通常使用分层网络计算最短路径：但在服务器端，您有8000万个节点的内存。 - AlexWien

@AlexWien 在 Android 上，我可以使用内存映射方法，其中几百万个节点也可以正常工作（仅适用于分层网络），或者通过启发式方法。 - Karussell

Answer 2

我已经在大约420 x 760个六边形的地形图上（总计超过325,000个六边形）实现了Parallel New Bidirectional A*的串行版本。在单个i7核心上，这张地图上最困难的长对角线路径大约需要1080步，完成时间约为0.45秒，完成后关闭集合元素略少于90,000个。

请注意，地形图在Dijkstra和A*方面具有“迷宫般”的特性，因为步骤成本的范围很广（对于此地图从2到10+），确保所有可接受的启发式算法都是低效的。

- Pieter Geerkens