删除加权有向图中的循环
Removing cycles in weighted directed graph
这是我其他帖子的后续问题。
我正在研究聚类算法，
经过一些重新聚类后，现在我有了这组点，其中 none 个点在它们的最佳聚类中，但不能单独重新分配，因为它会违反约束。
我正在尝试使用图形结构来解决问题，但在实施过程中遇到了一些问题。
我是初学者，如有错误请指出。
根据@Kittsil 的回答
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 的点数的总和。
在某些情况下，我不确定如何决定重新分配哪个点。
场景 1。对于一个循环如下。有两个点可以从A移到B，三个点从B移到C，在这种情况下，我应该select重新分配哪个点？
场景 2。对于一个循环如下。令所有边权重为 1。对于群集 A 中的点，可以将其重新分配给群集 B 或 D。在这种情况下。我该如何重新分配？
场景三 和场景二类似，设所有边的权值都为1，大圈内有两个小圈。聚类A中的点可以重新分配给B和E，在这种情况下如何决定重新分配？
欢迎提出关于这两种情况的想法！
考虑到上述情况，还有关于实施算法的任何建议吗？用伪代码更好。谢谢！
如果边权重与重新聚类点所获得的收益成正比，那么一个合适的启发式方法是选择总权重最高的循环。我认为这解决了您的所有三种情况：只要您有选择，请选择最有益的一种。
讨论：
中描述的算法是一种寻找局部最小值的贪心算法。因此，无论您在这些场景中如何选择，都不能保证您会找到最佳解决方案，任何选择都会使您更接近局部最小值。
由于与带约束排序的类似问题的关系，我的直觉是最小问题将是 NP 难问题。如果不是这种情况，那么存在一种比我之前描述的算法更好的算法。然而，这种贪心算法似乎是解决最小问题的快速方法。
这是我其他帖子的后续问题。
我正在研究聚类算法， 经过一些重新聚类后，现在我有了这组点，其中 none 个点在它们的最佳聚类中，但不能单独重新分配，因为它会违反约束。
我正在尝试使用图形结构来解决问题，但在实施过程中遇到了一些问题。
我是初学者，如有错误请指出。
根据@Kittsil 的回答
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 的点数的总和。
在某些情况下，我不确定如何决定重新分配哪个点。
场景 1。对于一个循环如下。有两个点可以从A移到B，三个点从B移到C，在这种情况下，我应该select重新分配哪个点？
场景 2。对于一个循环如下。令所有边权重为 1。对于群集 A 中的点，可以将其重新分配给群集 B 或 D。在这种情况下。我该如何重新分配？
场景三 和场景二类似，设所有边的权值都为1，大圈内有两个小圈。聚类A中的点可以重新分配给B和E，在这种情况下如何决定重新分配？
欢迎提出关于这两种情况的想法！
考虑到上述情况，还有关于实施算法的任何建议吗？用伪代码更好。谢谢！
如果边权重与重新聚类点所获得的收益成正比，那么一个合适的启发式方法是选择总权重最高的循环。我认为这解决了您的所有三种情况：只要您有选择，请选择最有益的一种。
讨论：
由于与带约束排序的类似问题的关系，我的直觉是最小问题将是 NP 难问题。如果不是这种情况，那么存在一种比我之前描述的算法更好的算法。然而，这种贪心算法似乎是解决最小问题的快速方法。