pertinente al problema dei compagni di stanza stabili e all'algoritmo sviluppato da Robert W. Irving.
Ci sono due fasi (a volte spezzate in tre) in cui possiamo arrivare ad un abbinamento stabile di tutti in un set e alle loro preferenze dichiarate. La prima, a volte riconosciuta seconda, semplice fase di rifiuto è abbastanza auto-esplicativa su come e perché funzionano. Ma la fase finale di rotazione / ciclica è stata difficile da comprendere. L'obiettivo è trovare rotazioni ed eliminare / rifiutare le coppie trovate nelle rotazioni fino a quando non viene trovata / trovata una corrispondenza stabile. Questa fase è piuttosto difficile da spiegare a parole quindi farò del mio meglio e spero che qualcuno già conosca questo problema.
La mia formulazione:
Inizieremo con l'elenco di preferenze rimanenti di qualsiasi persona e selezioniamo la seconda preferenza rimanente person1[2] . Utilizza l'elenco di person1[2] e seleziona l'ultima preferenza rimanente person2[L] . Li usiamo come nostra coppia di partenza (person1[2],person2[L]) . Con person2[L] ripeteremo il processo di cui sopra (selezionando la seconda preferenza di person2[L] e le ultime preferenze) e continueremo fino a quando non avremo ancora una volta ruotato attorno alla nostra coppia originale di (person1[2],person2[L]) . A quel punto rifiuteremo tutte le coppie diagonali (personI[2],previous personJ[L]) . Le coppie rotazione / rifiuto-diagonale si ripetono finché tutti hanno una singola corrispondenza o finché non viene dichiarato che non tutti possono essere abbinati.
Pseudocodice dell'algoritmo:
FOR all rotations in (p1...pn) and (q1...qn)
such that qi is second preference of pi and pi+1 is last preference of qi
DO:
FOR i = 1...n -1 DO:
reject(qi,pi+1)
END
END
Il codice sembra perfetto da implementare, ma è piuttosto difficile capire perché funzioni. Devo ancora trovare un buon video o articolo che spieghi questa fase.