0

只是想知道您是否有任何建议。我需要很多示例地图/图表来测试我的最短路径搜索解决方案（有人告诉我我应该拥有超过 100 个）。我的代码应该在模拟器中工作，该模拟器使用城市环境的 OpenStreetMap 地图，将路口的总数限制在几千个。问题是，模拟器只提供了两三张地图。在我看来，我在这里有几个选择：

  1. 编写我自己的随机图生成器。可能有很多工作（你觉得呢？--我以前从未做过）并重新发明轮子。
  2. 使用现成的解决方案。我不知道任何会生成类似地图的图表（好吧，至少我在 JUNG 中没有找到它:-)）
  3. 以某种自动化的方式从 OSM 中获取它们。我真的不打算自己去挑选满足 <15000 个节点要求的 100 多个城市地图。不过，我认为自动化也不容易。

我认为3将很难做到。对一些现成的解决方案有什么建议吗？或关于写我自己的评论？无论如何，我都不是经验丰富的程序员，但有几天时间。

4

1 回答 1

1

第一个想法：

您有一个已知问题，需要测试其解决方案。生成大量测试数据，使用经过验证的算法找到正确的解决方案，然后针对生成的数据集运行您的算法并比较结果。（或者只是下载经过验证的dijkstra算法实现，我相信实现这个算法是你的任务）

第二个想法：

随机生成的数据集并不是测试算法的最佳方式。您需要考虑算法可能失败的情况并创建相应的测试。例如，具有 1 个节点的图、具有循环的图、线性图即 N1---N2---N3-...-Nn、具有最大节点数的完整图。我认为，如果您创建这 4 个测试和 2-3 个小型随机测试，就足以确保您的算法得到正确实施。

于 2010-02-18T22:39:41.843 回答