这是对我的其他职位的后续问题。

This is a follow-up question on my other posts.

Algorithm对于聚类

我工作的一个聚类算法， 一些进行重新建后，现在我有这个设定点，他们没有在他们的最佳的集群，但无法单独重新分配，因为这将违反约束。

I'm working on a clustering algorithm, After some reclustering, now I have this set of points that none of them are in their optimal cluster but could not be reassigned individually, since it'll violate the constraint.

我试图用一个图结构来解决这个问题，但对面的几个问题实施来了。

I'm trying to use a graph structure to solve the problem but came across a few issues in implementing.

我是个初学者，请让我知道如果我错了。

I'm a beginner, please let me know if I'm wrong.

每@ Kittsil的答案

Per @Kittsil's answer

与集群为节点，从而构建一个有向图的边（A，B）的存在，如果全球解决方案将通过一些点在行驶到B寻找周期在该图中可以让你找到潜在的最小化移动（其中一个举措包括移动每个顶点的周期）。

build a directed graph with clusters as nodes, such that an edge (A,B) exists if the global solution would be minimized by some point in A moving to B. Looking for cycles in this graph will allow you to find potential moves (where a move consists of moving every vertex in the cycle).

我修改了图增加重量为点动从A到B的数量的总和。

I revised the graph adding weight as the sum of number of points moving from A to B.

下面是一些场景，我不知道如何决定重新分配这一点。

Here are some scenarios where I'm not sure how to decide on which point to reassign.

案例1 。为如下一个周期。有两点可以从A移动到B，三从B到C.在这种情况下，这点我应该选择重新分配？

Scenario 1. For a cycle as below. There are two points can be moved from A to B, and three from B to C. Under this situation, which point should I select to reassign?

情景2 。为如下一个周期。让所有边缘权重为1。在集群A中的点，它可能是重新分配要么集群B或D.在这种情况下。我应该怎么办重新分配？

Scenario 2. For a cycle as below. Let all edge weights be 1. For the point in cluster A, it could be reassign to either cluster B or D. In this case. How should I do the reassignment?

方案3 类似的场景2.让所有边缘权重为1。有在大周期的两个小周期。在集群A中的点可以重新分配给B和E，我怎么决定在这种情况下，重新分配？

Scenario 3 Similar to Scenario 2. Let all edge weights be 1. There are two small cycles in the bigger cycle. The point in cluster A can be reassigned to both B and E, how do I decide on the reassignment in this case?

有关这两种情况下想法是值得欢迎的！

Ideas about either scenario is welcomed!

同样在实现该算法考虑到上述情况有什么建议？即使伪code更好。谢谢！

Also any suggestions on implementing the algorithm considering the cases above? Even better with pseudocode. Thanks!

推荐答案

如果边缘的权重比例由进行重新建点得到的利益，然后一个体面的启发是选择周期的最高总重量。我觉得这涉及所有三个的情况：只要你有一个选择，挑一个会做最擅长

If the edge weights are proportional to the benefit gained by reclustering the points, then a decent heuristic is to pick the cycle with the highest total weight. I think this addresses all three of your cases: whenever you have a choice, pick the one that will do the most good.

讨论：

在Algorithm集群与尺寸的限制是一个贪心算法来找到当地的最低水平。因此，也不能保证你会找到最好的解决方案，无论你在这些情况下如何选择，以及任何选择将接近开车送你到当地最低。

The algorithm described in Algorithm for clustering with size constraints is a greedy algorithm to find a local minimum. Therefore, there is no guarantee that you will find the best solution no matter how you choose in these scenarios, and any choice will drive you closer to the local minimum.

由于关系与约束排序类似的问题，这是我的直觉是，最小的问题将是NP难。如果这不是这种情况，则存在比pviously描述的一个I $ P $好得多算法。然而，这种贪心算法似乎是在最小的问题，一个快速的解决方案。

Due to the relation to similar problems of sorting with constraints, it is my intuition that the minimum problem is going to be NP-hard. If that is not the case, then there exists a much better algorithm than the one I previously described. However, this greedy algorithm seems like a fast solution for the minimal problem.