哪种算法能够合理地减少多个列表？（“谁杀了谁”问题）

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的一个例子。有问题的二部图由两组人（尸体和嫌疑犯）和将每具尸体与可能杀害他的嫌疑犯联系起来的边来定义。最大匹配将为每个尸体选择一条边（如果可能），而不会为每个嫌疑人选择多条边。你知道吗