在加权有向图中删除循环

Question

3

这是我其他帖子的跟进问题。带大小约束的聚类算法我正在研究一种聚类算法，经过一些重新聚类后，现在我有一组点，它们都不在其最佳聚类中，但不能单独重新分配，因为这会违反约束条件。

我试图使用图形结构来解决这个问题，但在实现过程中遇到了一些问题。

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

根据@Kittsil的答案

建立一个以聚类为节点的有向图，使得如果A中的某个点移动到B可以最小化全局解，则存在边（A，B）。在此图中查找循环将允许您找到潜在的移动（其中每个顶点的移动均由移动该循环中的每个顶点组成）。

我修改了图表，将权重添加为从A移动到B的点数之和。

以下是一些情况，我不确定如何决定重新分配哪个点。

场景1。对于以下循环。有两个点可以从A移动到B，三个点可以从B移动到C。在这种情况下，我应该选择哪个点进行重新分配？

enter image description here

情景2。对于下面的一个循环。让所有边缘权重都为1。对于集群A中的点，可以重新分配到集群B或D。在这种情况下，我应该如何重新分配？

enter image description here

方案3 与方案2类似。让所有边的权重都为1。在更大的循环中有两个小循环。簇A中的点可以重新分配到B和E，那么在这种情况下如何决定重新分配？

enter image description here

欢迎提出有关这两种情况的想法！另外，针对上述情况实施算法的任何建议都可以。最好附带伪代码。谢谢！

- qshng

1个回答

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

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

- Kittsil · Accepted Answer

如果边权与重新聚类点所获得的利益成比例，那么一个不错的启发式算法是选择总权重最高的循环。我认为这解决了你提到的三种情况：每当有选择时，都选择能够做出最大贡献的那个选项。

讨论：

带大小限制的聚类算法中描述的算法是一种贪心算法，用于寻找局部最小值。因此，无论您在这些情况下如何选择，都不能保证找到最佳解决方案，任何选择都会使您更接近局部最小值。

由于与具有约束条件的排序类似问题的关系，我认为最小问题将成为NP难问题。如果不是这种情况，则存在比我之前描述的算法更好的算法。然而，这个贪心算法似乎是最小问题的快速解决方案。