聚类不同角度的圆形区域

Question

假设我有一个圆形区域和n个在这个区域随机部署的对象。我想从中心位置将圆圈分成K组，使同一区域中的物体被视为同一组的成员。此外，K人被分配从圆圈中心的位置访问K组（具体来说，一人一组）。现在，我想以这样的方式分组，每个组的人的行进距离彼此接近。

如果对象统一部署，则非常简单。只有将区域分成相等的角度才能获得理想的结果。但是，对于随机部署物体，我不能划分圆形区域（具体地说，不能固定角度），这给出了每个组中彼此接近的每个人的行进距离。

Answer 1

正如在评论中提到的，在一个小组内找到最短路径的子问题是NP难的。因此，总体问题是NP难。我将介绍一种动态规划算法，它可以精确地解决问题（以指数时间）或用启发式（在多项式时间内）逼近它。

这两个变体都需要一个函数f(g)来评估组的行程距离。在确切的变体中，您需要解决TSP。在大致的变体中，您使用启发式。你应该尝试几种启发式方法，看看哪一种最适合。例如，对象的边界环的面积可能是一个好的开始（加上最近的对象到中心的距离）。

实际算法如下所示：计算每个对象的角度位置并将它们相对于此位置进行排序。另外，计算到中心的距离。

现在，我们假设第一组从第一个对象开始。然后，我们希望找到最小化所有组的总和f(g)的分组。动态程序的状态通过到目前为止指定的组的数量和属于第一个下一组的对象来参数化。这使得2D表。您可以轻松地对结果组计算f()初始化第一列：

 groups | 1   2 3 4 5 6 ... K 
next object | 
--------------+------------------------ 
    o2   | f(o1->o1) 
    o3   | f(o1->o2) 
    ...  | ... 
    on   | f(o1->on-1) 
    o1   | f(o1->on) 

然后，您填写的后续列。对于每个条目，您必须将组比较各组上一列中，找到具有最小总和：

entry(column i, object j) = min_k (entry(i - 1, k) + f(ok->j-1)) 

其实，你不必计算整列。如果他们不允许适合K组，则可以在开始处将条目留空。例如。在第一列中，您只需要计算最多on-(K-1)，因为您必须将K-1对象保留为未分配状态才能获得有效的分组。您可以缓存f的结果以避免重复计算。

填表后，您有兴趣entry(K, o1)。按照从这个条目返回到开始的路径，您将获得最佳分组，其中第一个分组的起始位置为o1。在组合开始时为第一个n-K对象执行此操作，并获得总体最佳效果。

该算法的时间复杂度为O(n^3 * K * T(f))其中T(f)是计算f(g)的复杂度。