algorithm - 使用距离度量制作完全连接的图

Question

假设我有一系列数千个节点。对于每对节点，我都有一个距离度量。该距离度量可以是物理距离(例如每个节点的 x,y 坐标)或使节点相似的其他事物。

每个节点最多可以连接到 N 个其他节点，其中 N 很小——比如 6。

如何构建一个完全连接的图(例如，我可以在图边之后的任意两个节点之间移动)，同时最小化所有图节点之间的总距离。

也就是说，我不想要一个图，其中任何遍历的总距离最小化，但对于任何节点，从该节点的所有链接的总距离最小化。

我不需要绝对最小值——因为我认为这可能是 NP 完全的——而是一种获取接近真实绝对最小值的图形的相对有效的方法。

Answer 1

我建议使用贪婪的启发式方法，您可以在其中选择边，直到所有顶点都有 6 个邻居。例如，从最小生成树开始。然后，对于一些随机的顶点对，找到它们之间的最短路径，该路径最多使用一条未选定的边(在具有选定边的图形的两个副本上使用 Dijkstra 算法，由未选定的边连接)。然后选择总距离减少最大的边。