Algoritmo per massimizzare i confronti a coppie usando la proprietà transitiva

0

Sto cercando un modo per costruire un algoritmo che massimizzi il numero di confronti a coppie degli oggetti in un set usando la transitività.

Per spiegarti in dettaglio:

Suppose there are x number of objects to be compared. Then there are x[(x-1)/2] possible comparisons of these objects. A constraint is that only subsets of x can be evaluated for comparisons and there is always one most and one least preferred object as defined by a user. These subsets have a constant number of y objects in them.

Ad esempio, supponiamo che ci siano 7 oggetti numerati (1, 2, 3, 4, 5, 6, 7), 4 oggetti per sottoinsieme, che formano la matrice sottostante:

1   4   6   7
2   3   4   6
2   4   5   7
1   2   5   6
1   3   4   5
3   5   6   7
1   2   3   7

Supponiamo anche che a un utente venga assegnata in modo casuale la prima riga da valutare scegliendo un oggetto più desiderato e meno desiderato e che non conosca il layout della matrice precedente. La prima riga 1 contiene 1, 4, 6, 7 (si noti che ci sono 21 possibili confronti a coppie) e l'utente sceglie 1 come preferito e 7 come preferito. Vengono generati 5 confronti a coppie (1 > 4, 1 > 6, 1 > 7, 4 > 7 e 6 > 7). Quale sarebbe la riga successiva migliore per mostrare all'utente di massimizzare il numero di confronti sfruttando la transitività. Quindi la riga successiva da mostrare in base alle scelte più e meno preferite degli utenti nella seconda iterazione e così via. Lo scopo è di minimizzare il numero di sottoinsiemi / righe della matrice da mostrare che rivelerà il massimo x [(x-1) / 2] possibili confronti.

Immagino una seconda matrice che tenga traccia dei confronti posizionando un 1 nelle diagonali off della matrice se un oggetto era più desiderato. Ad esempio, se vengono utilizzati i confronti oggetto ipotetici per il primo sottoinsieme / riga (ad esempio 1 > 4, 1 > 6, 1 > 7, 4 > 7 e 6 > 7):

    1   2   3   4   5   6   7
1   0   0   0   0   0   0   0
2   0   0   0   0   0   0   0
3   0   0   0   0   0   0   0
4   1   0   0   0   0   0   0
5   0   0   0   0   0   0   0
6   1   0   0   0   0   0   0
7   1   0   0   1   0   1   0

L'algoritmo potrebbe utilizzare le informazioni in questa matrice per scegliere la riga / sottogruppo successiva migliore da mostrare tenendo conto della possibile riga / sottoinsiemi nella prima matrice.

Aggiornamento: Dopo un'ulteriore indagine, ho capito che risolvere gli elementi per gli elementi (cioè i confronti a coppie) nelle diagonali appena al di fuori della diagonale principale nella seconda matrice massimizzerebbe il numero di confronti accoppiati prodotti dalla transitività. Questo può essere fatto mostrando serie di x che contengono numeri consecutivi.

    
posta user3290799 16.09.2015 - 03:45
fonte

0 risposte

Leggi altre domande sui tag