Algoritmo per classificare un elenco di elementi

Question

Algoritmo per classificare un elenco di elementi

#1 da (2 voti)
#2 da (2 voti)

1

Dato un elenco di elementi, qual è il modo più efficace per classificare quegli articoli con il minor numero di confronti? Esiste un nome per questo tipo di algoritmo (in questo modo posso focalizzare la mia ricerca)?

Inoltre, c'è un modo per farlo e ricevere una classifica parzialmente completata in ordine (1 °, 2 °, ecc.) che è ancora quasi ottimale nel numero di confronti effettuati? In questo modo, un utente può smettere di scegliere i vincitori per le coppie di articoli da qualche parte prima che l'elenco sia stato classificato in totale e conoscere i primi N elementi.

Ad esempio, supponiamo di avere 8 articoli. Mi piacerebbe conoscere la classifica di quegli articoli dando due per volta a un utente e facendoli confrontare gli articoli. Qual è il modo più efficace per farli classificare gli articoli mostrando loro il minor numero di coppie?

So che, per un elenco di 8 articoli, occorrerebbero al massimo 7 confronti per trovare il vincitore. Puoi trovarlo completando un torneo a squadre (4 coppie round 1, 2 coppie round 2, 1 paio round 3). Con altri 2 confronti, sapresti chi è il 2o (dei 3 avversari al 1 °, due round per scoprire chi sarebbe stato il 2 °). Esiste un algoritmo o una classe che risolva questi tipi di problemi?

Nota:

L'ordinamento standard non è possibile perché non conosciamo gli elementi "forza" o "classifica" in anticipo.
Gli algoritmi di classificazione come ELO non sembrano risolvere questo problema, in quanto non ti dicono quali abbinamenti sono necessari per trovare un ranking totale con un numero minimo di matchup. (Potrei sbagliarmi qui, ma questo sembra essere il caso)

algorithms ranking-systems

posta JesseBuesking 17.07.2016 - 02:45

fonte

2 risposte

Leggi altre domande sui tag algorithms ranking-systems

Emscripten: passaggio degli argomenti della riga di comando Multi threaded e event driven [chiuso]

score 2 · Answer 1

L'ordinamento standard è molto possibile ed è esattamente ciò che dovresti fare qui.

il problema è diverso dal fatto che l'ordine è sconosciuto

Non c'è differenza. Un algoritmo di ordinamento standard non conosce il "rango" o "forza" di nessuno degli elementi che sta ordinando in anticipo. Infatti, mai lo sa. Tutto ciò che sa è che esiste un modo per chiedere "l'elemento A viene prima o dopo l'elemento B?". Tipicamente questo viene fatto per mezzo di una funzione che viene chiamata più volte durante l'ordinamento.

Poiché l'obiettivo della maggior parte degli algoritmi di ordinamento è di minimizzare il numero di confronti e tu vuoi ridurre al minimo il numero di confronti, hai la tua risposta lì. Inoltre, se non vuoi ordinare tutti gli articoli ma (ad esempio) trova la top ten, ci sono algoritmi di ordinamento ben noti che faranno anche questo.

È vero che nella maggior parte dei casi discussi nei libri di testo, è possibile rispondere "fa A prima o dopo l'articolo B?" puramente algoritmicamente , utilizzando le informazioni memorizzate all'interno di A e B. Tutti gli esempi che si tende a vedere assumeranno questo. Ma questo non è essenziale. Non c'è niente di sbagliato in una funzione di confronto la cui implementazione è:

Presenta A e B all'utente.
Chiedi all'utente che deve venire prima.
Restituisce la risposta dell'utente all'algoritmo di ordinamento.

e tale funzione è esattamente ciò che useresti qui.

il problema è diverso in quanto l'ordine ... può differire tra gli utenti

Neanche qui c'è differenza. "L'ordinamento secondo l'opinione di Archibald" e "l'ordinamento secondo l'opinione di Ermintrude" sono due operazioni di ordinamento separate, condotte separatamente per conto di due utenti distinti - così come "l'ordinamento in base al peso" e "l'ordinamento in base all'altezza" sono due operazioni di ordinamento separate , condotto separatamente su due diversi criteri di classificazione.

score 2 · Answer 2

Quindi stai cercando elementi di classifica riducendo al minimo il confronto a coppie. È esattamente ciò che l'algoritmo standard di ordinamento fa in modo ottimale nel confronto con O (n * ln (n)). (La dimostrazione di ottimalità è su libri di testo come Introduzione di algoritmi)

Riguardo al problema di avere i primi k elementi ordinati, è chiamato ordinamento parziale e può essere risolto in modo ottimale in Confronto O (n * ln (k)). Si fa inserendo in un heap il primo elemento k poi per gli altri elementi nell'heap inserendo l'elemento nell'heap e rimuovendo l'elemento più piccolo dell'heap.

modifica precedente

Supponendo che non ci sia ordine totale sui tuoi articoli, non esiste un ordine di classificazione perfetto, ad esempio non esiste un grado ordinamento che risolve le dipendenze circolari come un battito B che batte C che batte A.

Se esiste un ordine totale, l'algoritmo classico funziona perfettamente perché nell'algoritmo di ordinamento classico tutto ciò che serve è poter confrontare gli elementi due a due, senza bisogno di calcolare una forza prima della mano.

Nel caso in cui non ci sia un ordine totale, sembra che tu debba guardare verso gli orari torneo , la mia migliore scommessa sarebbe essere un derivato del torneo svizzero per compromettere il numero di confronto con la precisione di un intero round-robin tournament .