algorithm - 如何找到一个组内最多的变化/排列(也许是一个图表)

Question

假设我的公司有 N 个 worker 和 M 个部门。每个 worker 目前分配到一个部门，也每个 worker 都愿意换到另一个部门。

例如:

Worker A is in sector 1 but want to go to sector 2
B is in 2 but want 3
C is in 3 but want 2
D is in 1 but want 3
and so on...

但他们都必须彼此改变。

A到B位置，B到A位置

或

A到B位/B到C位/C到A位

我知道不是每个人都会改变扇区，但我想知道是否有任何特定的算法可以找到哪些运动会产生最大的变化量。

我想天真地交换两个 worker ，但他们中的一些人可能会失踪，他们都可以形成一个“循环”并且没有人会被排除在外(如果可能的话)

我可以使用 Monte Carlo 来链接 worker 并找到最长的链/环，但是随着 N 和 M 的增长，这会太昂贵

也很难使用 djikstra 在图中找到最长的路径，但它看起来像 NP-hard problem

有谁知道算法或者我怎样才能有效地解决这个问题？或者我想飞得离太阳太近了？

Answer 1

这可以作为最小成本循环问题来解决。构建一个流网络，每个扇区对应一个节点，每个 worker 对应一个弧。每个弧的容量为 1，成本为 −1(即，如果可以的话，我们应该移动 worker )。流动约束守恒确保我们可以将 worker 运动分解为简单循环的总和。

Klein 的循环取消算法不是最有效的，但它非常简单。使用(例如)Bellman-Ford 在网络中找到负成本循环(如果存在)。如果是，则反转循环中每条弧的方向，将循环中每条弧的成本乘以-1，然后循环回到起点。