3

我给自己写了一个 A*，它工作得很好，现在是时候评估它的性能了（可能会对照其他解决方案来看看它的性能）。

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

我曾想过向它扔这个迷宫（大图），但我知道它会

  • 显然需要一些时间，因为它有超过 3 000 000 个边缘（并且比墙壁的一半还少，但仍然如此）
  • 不一定是好指标，超大环境

总结一下：什么样的环境对A*来说是一个好的压力测试？应用 A* 中图形的数量级是多少（例如在游戏中）？

4

2 回答 2

5

一个好的压力测试是一个数字道路网络，
1）一个大国（如西班牙、法国、德国）的一部分，然后
2）整个国家。（几百万个节点）

OpenStreetMap 提供了这样的数据，但是将其导入到图表中需要做很多工作。

于 2013-06-07T17:28:52.903 回答
2

我在大约 420 x 760 六边形（总共超过 325,000 个六边形）的地形图上实现了并行新双向 A*的串行版本。这张地图上最困难的长对角线路径，大约 1080 步，在单个 i7 内核上在大约 0.45 秒内完成，完成后只有不到 90,000 个封闭集元素。

请注意，就 Dijkstra 和 A* 而言，地形图具有类似迷宫的特性，因为步长成本的范围很广（此地图从 2 到 10+）确保所有可接受的启发式方法都是低效的。

于 2013-07-03T01:59:31.080 回答