从平面分布的点中选择分散的散点。

Question

从平面分布的点中选择分散的散点。

algorithmoptimization

4

我有一个平面上分布着 N=200个点 （已知其x和y坐标）。

我想选择其中的M=10个点，然后它们之间会有M*(M-1)/2 = 10 * 9 / 2 = 45条边。

我需要保持这些10个点足够分散，也就是说我希望以最大化最小边长的方式来选择这10个点。

换句话说，我想通过调整所选的10个点来解决一个优化问题（寻找最大值），该问题的函数为：

F = min (lengths_of_all_45_edges)

您有快速实现此算法的方法吗？

- ThunderEX

1

你的意思不是很清楚：“足够大”的距离是指高于某个阈值，还是应该最大化？如果是后者，是所有选定点之间的距离要最大化，还是其他什么？请给我们更多细节。 - Pavel K

1

此外，“some”是一个固定的点数吗？如果不是，您设想了什么标准？ - microtherion

这个方案已经比之前好了，但还不够清晰。你是不是想说 min ( sum_for_each_selected_point( sum_of_distances_to_other_selected_points ) )？结果仍然极大程度上取决于所选择的点数。我在谈论这个数字的边界条件。如果数字可以是任意的，那么显而易见的解决方案就是只选择2个点，并且选择那些距离最远的点。 - Pavel K

@PavelK 我的意思是选择点对之间的最小距离，如果只选择固定的10个点呢？ - ThunderEX

我已经添加了一个正式的优化问题定义，因此这个问题不再含糊不清（因为它有明确的要找到什么）。请重新打开它。 - Pavel K

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Micromega · Answer 1

你可以获取最小生成树，然后寻找任何10条边，使其成为最短路径。