python – 在给定的点集中选择最远点的子集
想象一下,你给出了3个维度中n个点的集合S.任意2点之间的距离是简单的欧几里德距离.您希望从该集合中选择k个点的子集Q,使得它们彼此相距最远.换句话说,不存在k个点的其他子集Q’,使得Q中的所有成对距离的min小于Q’中的min. 如果n约为1600万,k约为300,我们如何有效地做到这一点? 我猜这个NP难,所以我们可能只想关注近似.我能想到的一个想法是使用多维缩放对一行中的这些点进行排序,然后使用二进制搜索的版本来获得该行上最远的点. 最佳答案
我也很确定问题是NP-Hard,我发现最类似的问题是k-Center Problem.如果运行时比正确性更重要,贪心算法可能是你的最佳选择:
附注:在类似的问题中,例如,set-cover problem可以证明来自贪婪算法的解决方案至少是最佳解决方案的63%. 为了加快速度,我看到了3种可能性: >首先在R-Tree中索引数据集,然后执行贪婪搜索. R-Tree的构造是O(n log n),但是虽然是为最近邻搜索而开发的,但它也可以帮助您找到O(log n)中一组点的最远点.这可能比天真的O(k * n)算法更快. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |