Non so se il problema di cui sto parlando abbia un nome, se questo è il caso, mi piacerebbe conoscerlo per fare ulteriori ricerche.Quale algoritmo può ridurre razionalmente più elenchi? ("chi ha ucciso chi" pro blem)
Per spiegare il mio problema, è più semplice visualizzarlo.
Darò una rappresentazione ma molti altri sono stati possibili.
- In una piccola città, la polizia ha trovato un gran numero di cadaveri.
- Per ogni cadavere trovato, c'è un numero di sospetti tra gli abitanti di della città.
- Un assassino non può uccidere più di una persona.
- C'è una soluzione.
Scopri chi ha ucciso chi!
Mentre scrivo questo, mi rendo conto che ci possono avere molte varianti di questo problema, quindi sarebbe molto utile per sapere che tipo di problema si tratta.
Userò un gioco di prova.
Quindi, per ogni cadavere, abbiamo una serie di sospetti tra gli abitanti.
C1 -> [S1, S3]
C2 -> [S1, S3, S4]
C3 -> [S2]
C4 -> [S2, S3]
Con deduzione logica, è quindi facile determinare chi ha ucciso chi.
- C'è un solo sospetto per C3, quindi S2 è l'assassino.
- S2 è l'assassino di C3, quindi non può essere l'assassino di C4. Ciò significa che S2 ha ucciso C4.
- S1 è l'ultimo potenziale sospettato per C1, quindi è l'assassino.
- Infine, S4 è l'assassino di C2.
Il che ci dà la soluzione:
C1 -> S1
C2 -> S4
C3 -> S2
C4 -> S3
Un'implementazione ingenuo dell'algoritmo per risolvere questo sarebbe:
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
Il problema è che diventa molto costoso, con un gran numero di di corpi e sospetti, il ciclo richiede molto tempo. Certamente, piccoli miglioramenti sono possibili (rimuovere il corpo dalla lista una volta trovato il sospetto, per esempio) ma l'algoritmo non mi sembra ancora ottimale.
Esiste un algoritmo migliore per questo problema? E ripeto ancora, è un nome specifico per questo tipo di problema? Potrebbe sicuramente aiutarmi molto.
Ci devono essere tanti cadaveri quanti sono i sospetti? Oppure i casi possono essere irrisolti? – flakes
@Calpratt Nel caso specifico ho affermato, poiché ogni assassino ha ucciso solo una persona, e poiché esiste una soluzione, tutti gli omicidi saranno risolti in casi. Ma questa affermazione può facilmente cambiare modificando un singolo parametro dell'istruzione. – Delgan
Scusa, mi sbagliavo –