Algoritmo di ordinamento di elenchi per confronti effettuati dall'uomo

Question

Questa domanda è stata posta una volta prima ma non è stata data risposta, quindi ho pensato di chiedere di nuovo con alcune specifiche della mia situazione.

Sto provando a sviluppare un'applicazione che consente di inserire un elenco di elementi discreti (per questo esempio, frutta) e offre confronti tra due. Scegli il tuo preferito tra i due e poi questo processo si ripete finché alla fine hai una lista ordinata per preferenza di questi oggetti (in questo esempio, un elenco dei tuoi frutti preferiti, in ordine).

Il problema è che le tradizionali strategie di smistamento, non importa quanto velocemente, coinvolgeranno necessariamente più operazioni di quanto sia fattibile per un umano in qualsiasi ragionevole lasso di tempo (anche con una lista di soli 50, come il mio la lista di test corrente è).

Poiché ovviamente non esiste un algoritmo di ordinamento garantito con una complessità sufficientemente bassa, credo che alcune indennità debbano essere fatte. C'è un modo per saltare grandi blocchi di smistamento? Ho considerato un modo per assegnare valori alle voci in base al numero di confronti che hanno "vinto" e quindi arrestare l'ordinamento dopo un po 'e assumendo che quei valori danno l'ordine corretto, simile allo stile che si potrebbe risolvere con un scacchi svizzero torneo se non riesci a completare abbastanza round per determinare un vincitore normalmente. Non so se sia plausibile.

Un esempio per chiarire cosa intendo: dire che aveva una lista di

Apple 
Orange 
Kiwi 
Banana 
Melon 

Sarebbe di offrire i confronti come

Do you prefer: 
A Apple 
B Kiwi 

e così via fino a quando si dispone di un elenco che sembra

Kiwi 
Apple 
Orange 
Melon 
Banana 

che è il vostro ordine di preferenza di quei frutti.

Answer 1

Quali sono le tue preferenze di frutta? Hai una lista completa di preferenze nella tua mente, o hai dei frutti che "ti piacciono più dei più", frutti che "ti piacciono meno della maggior parte", e il resto di cui non hai sentimenti forti - o non hai nemmeno provato.

Il problema con il modo in cui si è formulato il problema è che si è assunto che le preferenze di una persona siano total order, che è naturalmente codificata come elenco. In realtà, le preferenze di una persona sono spesso pari a partial order, che è naturalmente codificata come directed acyclic graph.

Ad esempio, per l'insieme dei frutti {Apple, Orange, Kiwi, Banana, Melon, Starfruit}, potrei avere preferenze frutta come segue:

Melon < Apple 
Apple < Banana 
Banana < Kiwi 
Banana < Orange 

Un buon modo per arrivare ad un ordine parziale in base all'input dell'utente è di riprodurre radix sort. Per iniziare, chiedi all'utente di selezionare, per ogni frutto, se gli piace, se non lo gradisce, se si sente neutrale o non lo sa. Vorrei rispondere a questa come segue:

  Like Dislike Neutral Unknown 
Apple     x 
Orange  x 
Kiwi  x 
Banana  x 
Melon   x 
Starfruit      x 

Supponendo Dislike < Neutral < Like, queste risposte codificare le seguenti informazioni, anche se ho risposto solo le domande che ci sono frutti:

Melon < Apple 
Apple < Orange 
Apple < Kiwi 
Apple < Banana 

Avanti, identificare quali risposta (s) ha ricevuto il maggior numero di segni di spunta. In questo caso, mi sembra di avere 3 frutti che mi piacciono, 1 non mi piacciono, e 1 mi sento neutrale (a meno che non sia coinvolto il burro di arachidi), e 1 non ho mai provato (quindi non ho alcuna preferenza rispetto a gli altri frutti).

Quindi il luogo naturale per approfondire le mie preferenze sarebbe nei frutti che mi piacciono. Il problema è ricorsivo: ora vuoi determinare le mie preferenze nel set di frutti {Orange, Kiwi, Banana}. Potresti chiedermi quali di quei frutti sono i miei preferiti e fare clic su Orange e Kiwi. Che ti dice quanto segue:

Banana < Orange 
Banana < Kiwi 

In combinazione con il primo turno di informazioni, ora avete:

Melon < Apple 
Apple < Orange 
Apple < Kiwi 
Apple < Banana 
Banana < Kiwi 
Banana < Orange 

Apple < Banana e Banana < Kiwi implica Apple < Kiwi; Apple < Banana e Banana < Orange implicano Apple < Orange. Quindi possiamo eliminare le informazioni ridondanti per arrivare al seguente:

Melon < Apple 
Apple < Banana 
Banana < Kiwi 
Banana < Orange 

Answer 2

Si può consentire all'utente non solo di determinare se un articolo è più preferibile rispetto a un altro, ma anche un voto da 1 a 10 per esempio quanto più preferisce l'uno dall'altro. In questo modo hai più informazioni e puoi facilmente creare una classifica.

Nell'approccio ottimale in cui un utente può solo dire più piccolo o più grande è necessario eseguire la ricerca binaria per ogni elemento nell'elenco. La ricerca binaria ha complessità O(log n). In questo modo n con n passando da 1 a n fa un totale di O(n * log (n/2)). In caso di 50 articoli che richiederebbero un po 'più di 200 passaggi.

Answer 3

Utilizzare un insertion sort. Invece di chiedere all'utente di confrontare due elementi alla volta, chiedigli di selezionare il loro preferito dall'intero elenco rimanente. Metti quell'elemento alla fine dell'elenco ordinato, rimuovilo dagli altri elementi e ripeti fino a quando gli oggetti rimanenti sono esauriti.