algorithm - "Assignment Problem"解决问题

Question

我在这里阅读了分配问题的解决方案:http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm

我了解 O(n3) 解决方案)，但对更简单的 O(n4) 解决方案有疑问。

也许我误解了这个符号，但是当他在第 2 步中修改权重时——为什么 w1->j2 的权重增加的方式与 w2->j1 增加的方式不同。

谁能更好地解释
中定义的规则中的符号

Answer 1

看起来这两个逻辑符号应该分别是“and”和“xor”。选择的异或符号看起来更像是一个包容性的或，这可能是一个拼写错误。参见 http://en.wikipedia.org/wiki/Exclusive_or对于一些不那么令人困惑的替代方案。

通过这种解释，您有以下可能性:

1. i 和j 都不在V 中。然后你得到第一个案例。
2. i 在 V 中，但 j 不在。然后你得到第二种情况。
3. i 不在 V 中，但 j 是。然后你得到第二种情况。
4. i 和j 都在V 中。然后你得到第三种情况。

如您所见，所有情况都已涵盖，并且没有歧义。