使用图形解决以下 whodunnit 问题

Question

有7名嫌疑人：A、OL、D、B、C、S。他们都参观了作案的城堡。访问次数最多的是罪犯。他们被问到在城堡里遇到了谁，他们的回答如下：

A: O, L, B, C.

O: A, L, D, B, S.

L: A, O, D.

D: O, L, B.

B: A, O, D, S.

C: A, S.

S: O, B, C.

我做了下图：

我试着回想他们参观城堡的可能日子。我说如果 X 和 Y 看到对方，那么他们就在同一天参观了城堡。那么，我们有：

第 1 天：{C,S}

第 2 天：{C,A}

第 3 天：{S,O,B}

第 4 天：{A,B,O}

第 5 天：{O,B,D}

第 6 天：{L,D,O}

第 7 天：{A,O,L}

据此，O访问次数最多，是罪犯。但是，从某些日子开始，我可以省略 O，这会改变结果。

我做的对还是我的推理正确？如果不是，我哪里错了？

Answer 1

对于PSO来说，这更像是一道难题，而不是算法题。

我相信，嫌疑人的回答是独一无二的：也就是说A和O正好一次见面。否则它没有意义，因为它可以是任何数字。

为了解决这个难题，我创建了一个脚本，它采用可疑访问的数组，并且对于每次访问，XYZ 创建记录，如 X: YZ、Y: XZ 和 Z: XY（顺序确实重要）。

使用我发现的脚本，你的访问方案不会导致嫌疑人的答案。然后我创建了自己的，稍微调整了一下顺序，最后我得到了几乎 100% 的结果（B 答案的顺序略有不同）：

A: O, L, B, C
O: A, L, D, B, S
L: A, O, D
D: O, L, B
B: A, D, O, S
C: A, S
S: O, B, C

看起来 A 是罪犯，有 4 次访问。脚本来源：

visits = %w[
  AO
  AL
  OLD
  BA
  CA
  BD
  OBS
  CS
]
result = {}
visits.each do |visit|
  chars = visit.chars
  chars.each do |char|
    result[char] ||= []
    result[char] += chars - [char]
  end
end
result.each do |k, v|
  puts '%s: %s' % [k, v.join(', ')]
end

您可以玩代码 here。例如，your visits scheme 产生以下嫌疑人的答案：

C: S, A
S: C, O, B
A: C, B, O, O, L
O: S, B, A, B, B, D, L, D, A, L
B: S, O, A, O, O, D
D: O, B, L, O
L: D, O, A, O

使用图形解决以下 whodunnit 问题

Solve a the following whodunnit problem using graphs

algorithm

graph

graph-algorithm