I do not know if the problem I am talking about has a name, if so, I would like to know this in order to do more research.
To explain my problem, it’s easier to visualize.
I will give an idea, but many others were possible.
- In a small town, police found a large number of corpses.
- For each corpse found among the inhabitants of the city.
- A killer cannot kill more than one person.
- There is a solution.
Find out who killed whom !
As I write this, I understand that there can be many options for this problem, so it would be very helpful to know what the problem is.
I will use a test game.
Therefore, for each corpse, we have many suspects among residents.
C1 -> [S1, S3] C2 -> [S1, S3, S4] C3 -> [S2] C4 -> [S2, S3]
According to the logical conclusion, then it is easy to determine who killed whom.
- There is only one suspect in C3, so S2 is a killer.
- S2 is the killer of C3, so he cannot be the killer of C4. This means that S2 killed C4.
- S1 is the last potential suspect for C1, so he is a killer.
- Finally, S4 is the killer of C2.
What gives us the solution:
C1 -> S1 C2 -> S4 C3 -> S2 C4 -> S3
A naive implementation of the algorithm to solve this problem:
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
The problem is that it becomes very expensive with a lot of bodies and suspects, the cycle takes a lot of time. Of course, slight improvements are possible (remove the body from the list as soon as the suspect is found, for example), but the algorithm seems to me not yet optimal.
Is there a better algorithm for this problem? And I repeat, is this a specific name for this kind of problem? It can definitely help me.