假设我的公司有N个工人和M个部门。每个工人当前被分配到一个扇区，并且每个工人都愿意换到另一个扇区。
例如:
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位置
我知道不是每个人都会改变扇区，但我想知道是否有任何特定的算法可以找到哪些运动将产生最大的变化。
我想天真地交换两个工人，但其中一些可能会丢失，它们都可以形成一个"循环"。没有人会被遗漏(如果可能的话)
我可以使用蒙特卡罗将工人链起来并找到最长的链/环，但随着N和M的增长，这将过于昂贵
还考虑了使用djikstra找到图中的最长路径，但它看起来像一个NP-hard问题
有没有人知道一个算法或者我如何有效地解决这个问题?还是我想飞得离太阳太近?
这可以用最小成本循环问题来解决。构建一个流动网络，每个扇区对应一个节点，每个工人对应一个弧。每个弧的容量为1，成本为- 1(即，如果可以的话，我们应该移动工人)。流动约束的守恒保证了我们可以把工人的运动分解成简单循环的总和。
Klein的周期抵消算法不是最有效的，但它非常简单。使用(例如)Bellman - Ford在网络中找到一个负成本周期，如果存在的话。如果是，则将循环中每个弧线的方向反转，将循环中每个弧线的代价乘以−1，并返回到起点。
您可以使用以下观察结果来生成最吸引人的部门变化(以有多少工人得到他们想要的变化来衡量)。
- 识别扇区变化的所有循环链。每个人都能得到他们想要的改变。
- 非圆链识别所有行业的变化。它们可以以一个工人得不到他/她想要的东西为代价而循环。
- 重温1。以两名工人得不到他们想要的东西为代价，将任意两个循环链组合在一起。
您得到的不是一个最优解决方案，而是许多或多或少具有吸引力的选项的列表。你必须在步骤1 - 3上设置一些界限，以使选项减少到一个可处理的数字。