algorithm - 使用图解决以下 whodunnit 问题

Question

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

答：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 ，这会改变结果。

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

标签： algorithmgraphgraph-algorithm

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

你可以在这里玩代码。例如，您的访问计划会产生以下嫌疑人的答案：

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