Nie wiem, czy problem, o którym mówię, ma nazwę, jeśli tak jest, chciałbym to wiedzieć, aby przeprowadzić więcej badań.Który algorytm może racjonalnie redukować wiele list? ("kto zabił, kto" pro blem)
Aby wyjaśnić mój problem, łatwiej jest go zwizualizować.
Dam reprezentację, ale wiele innych było możliwe.
- W małym mieście, policja znalazła dużą liczbę zwłok.
- Dla każdego odnalezionego zwłok istnieje liczba podejrzanych wśród mieszkańców miasta .
- Morderca nie może zabić więcej niż jednej osoby.
- Istnieje rozwiązanie.
Dowiedz się, kto zabił, kto!
Kiedy piszę te słowa, zdaję sobie sprawę, że nie może mieć wiele wariantów tego problemu, więc byłoby bardzo przydatne wiedzieć, jaki rodzaj problemu jest.
Będę używać gry testowej.
Tak więc dla każdego zwłok mamy grupę podejrzanych wśród mieszkańców.
C1 -> [S1, S3]
C2 -> [S1, S3, S4]
C3 -> [S2]
C4 -> [S2, S3]
Dzięki logicznej dedukcji łatwo jest ustalić, kto zabił.
- Jest tylko jeden podejrzany o C3, więc S2 jest mordercą.
- S2 jest mordercą C3, więc nie może być mordercą C4. Oznacza to, że S2 zabiło C4.
- S1 jest najnowszym potencjalnym podejrzanym dla C1, więc jest mordercą.
- Wreszcie S4 jest mordercą C2.
co daje nam rozwiązanie:
C1 -> S1
C2 -> S4
C3 -> S2
C4 -> S3
Naiwny implementacja algorytmu do rozwiązania tego byłoby:
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
Problemem jest to, że staje się bardzo kosztowne z dużą liczbą ciał i podejrzanych, pętla zajmuje dużo czasu. Oczywiście możliwe są drobne poprawki (usuń ciało z listy, gdy na przykład podejrzewał), ale algorytm wydaje mi się nadal nieoptymalny.
Czy istnieje lepszy algorytm dla tego problemu? I powtarzam jeszcze raz, czy jest to nazwa specyficzna dla tego rodzaju problemu? To na pewno może mi bardzo pomóc.
Musi być tylu ciał, ilu jest podejrzanych? A może sprawy nie zostaną rozwiązane? – flakes
@Calpratt W konkretnym przypadku, o którym mówiłem, ponieważ każdy morderca zabił tylko jedną osobę, a ponieważ istnieje rozwiązanie, wszystkie morderstwa zostaną rozwiązane. Ale to stwierdzenie można łatwo zmienić, modyfikując pojedynczy parametr instrukcji. – Delgan
Przepraszam, myliłem się. –