python - 哪种算法可以合理地减少多个列表？ ("who killed who"问题)

Question

我不知道我所说的问题是否有名字，如果是这样，我想知道它以便做更多的研究。

为了解释我的问题，更容易形象化。

我会给出一个表示，但还有很多其他的可能。

• In a small town, the police found a large number of corpses.
• For each corpse found, there is a number of suspects among the inhabitants of the city.
• A murderer can not kill more than one person.
• There is a solution.
  
  Find out who killed who!

在写这篇文章时，我意识到这个问题可能有很多变体，所以了解它是什么类型的问题真的很有用。

---

我会用一个测试游戏。
因此，对于每具尸体，我们在居民中都有一组嫌疑人。

C1 -> [S1, S3]
C2 -> [S1, S3, S4]
C3 -> [S2]
C4 -> [S2, S3]

通过逻辑推理，很容易判断谁杀了谁。

1. C3只有一个嫌疑人，所以，S2就是凶手。
2. S2是C3的凶手，所以他不可能是C4的凶手。这意味着 S2 杀死了 C4。
3. S1 是 C1 的最新潜在嫌疑人，因此他就是凶手。
4. 最后，S4是C2的凶手。

这给了我们解决方案:

C1 -> S1
C2 -> S4
C3 -> S2
C4 -> S3

解决这个问题的算法的简单实现是:

found = []

for corpse in corpses:
    corpse.suspects = [s for s in corpse.suspsects if s not in found]
    if len(corpse.suspects) == 1:
        found.append(suspects[0])
        continue # Restart the loop to remove the new killer found 
                 # from previous corpses suspects

问题是如果有大量的尸体和嫌疑人，它会变得非常昂贵，循环需要很长时间。当然，小的改进是可能的(例如，一旦发现嫌疑人就将尸体从列表中删除)但在我看来算法仍然不是最优的。

这个问题有更好的算法吗？我再重复一遍，它是这种问题的特定名称吗？它绝对可以帮到我很多。

Answer 1

这是一个 maximum bipartite matching 的例子.所讨论的二分图由两组人(尸体和嫌疑人)以及将每具尸体连接到可能杀死他的嫌疑人的边定义。最大匹配将为每个尸体选择一条边(在可能的情况下)，而不会为每个嫌疑人选择多条边。