我有一个GPS点列表...但是我要问的内容也可以用于任何X，Y坐标。
在我的用例中，我想在集合中分配点。每个点只能属于一个集合，并且每个集合都有一个条件，即集合中两个点之间的距离不大于某个常数...这意味着集合中的所有点都适合特定直径的圆。
对于点列表，我想找到套数最少的最佳（或至少某些）安排。
会有一个只有一个点的集合，因为周围的其他点已经在不同的集合中，或者仅仅是因为周围没有点（它们之间的距离大于集合的条件）...我想避免的是效率低下的集合分配，例如，而不是找到理想的2套，每套30分，我发现5套，一套1分，第二套40分，依此类推...
我所能做的就是蛮力解决方案，计算所有距离，建立所有可能的集合安排，按集合数对它们进行排序，然后选择集合数最少的一个。
有没有更好的方法？
这里的问题是NP完全的。您尝试解决的问题是最大爬坡问题和集合覆盖问题。
您的问题可以表示为图形G =（V，E），其中顶点是您的坐标，而边缘是距离的连接。该图可以在O（n ^ 2）时间内绘制。然后，您滤除所有边的距离大于给定图形G'的常数。
对于其余的图G'，您想查找所有集团（有效求解最大倾斜度）。一个集团是一组完全相连的顶点。将此清单命名为S。
现在找到覆盖所有顶点V的S的最小元素集是集合覆盖问题。
布景问题和最大派系都是NP完整的。因此，找到最佳解决方案将花费指数时间。您可以查看这两个问题的近似算法。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句