C++生成适合TSP的随机图

Question

我正在测试各种 TSP 模型/算法。现在我正在使用一个完整的邻接矩阵，其中填充了从 1 到 100 的随机值，它表示一个完整的有向图。

我正在寻找一种更严格的方法来尝试不同类型的随机图，例如 Erdos-Renyi、小世界网络和无标度网络。

我知道我可能必须为新图切换到邻接表。

我的方法是生成一个随机图，然后确保存在使问题成为有效 TSP 实例所必需的哈密顿路径。是否有可能，或者只是尝试解决无法解决的实例(假设所有方法都将在此类实例上终止)是否更便宜？

顺便说一句，我正在考虑使用 Boost Graph Library，但我对它不熟悉，也许有更合适的东西。欢迎提出替代建议，但不应将其视为该问题的主要范围。

我不需要 TSP 求解器，我需要一些东西来帮助生成可接受的问题。

谢谢。

Answer 1

您可以尝试单调格雷码，也就是希尔伯特曲线。它可以帮助找到哈密顿路径:http://en.m.wikipedia.org/wiki/Gray_code .