Ho una serie di canzoni in cui voglio ordinarle per una particolare qualità. Per fare questo (tramite crowdsourcing) presenterò agli utenti un confronto tra due canzoni. L'utente sceglierà quale classifica sarà più in alto.
Quale algoritmo posso utilizzare per ponderare i diversi confronti? Dato che avrò un set di dati di confronti tra due punti come ...
[ A >= B : 2
A <= B : 0
A >= C : 1
A <= C : 4
...
( two dimensional array of size 2 * |songs - 1|^2 )
...
]
Una possibile formalizzazione è come un problema con il percorso più lungo . Costruisci un grafo diretto in cui i nodi sono etichettati con canzoni, e per ogni coppia ordinata di canzoni (A, B) c'è un bordo ponderato A - > B con peso uguale al numero di voti per A < B. Quindi il percorso semplice più lungo è un ordine totale che concorda con il numero massimo di voti. Se il percorso più lungo contiene il bordo A - > B, quindi il consenso è che A < B.
Sfortunatamente, questo problema è NP-hard a meno che il grafico non sia aciclico (cioè non vi siano classificazioni incoerenti nel database). Potresti essere ancora in grado di risolverlo in un ragionevole lasso di tempo a seconda di quante canzoni ci sono.
Il problema non richiede una soluzione esatta. E le opinioni non sono comunque una misura esatta. Puoi semplicemente contare +1 ogni volta che una canzone è preferita e -1 ogni volta che non è preferita.
A B C
A >= B : 2 +2 -2
A <= B : 0 0 0
A >= C : 1 +1 -1
A <= C : 4 -4 +4
----------
-1 -2 +3
Questo darebbe l'ordine C > A > B.
Leggi altre domande sui tag algorithms sorting