Un team di selezione automatica

Question

Una squadra composta da 100 membri deve essere assemblata da un pool di 1000 candidati. Ogni candidato riceve i 99 altri candidati che vorrebbe avere come compagni di squadra.

Ogni squadra possibile ottiene un punteggio che misura quanto soddisfi le preferenze del compagno di squadra dei suoi membri. Se Lisa è in una squadra e 11 della gente nella lista dei desideri di Lisas sono anche nella squadra, quella squadra ottiene 11 punti per Lisa. I punti per tutti i membri sono sommati. Il massimo teorico che qualsiasi squadra possibile può ottenere è 99 * 100. Il minimo è 0.

Ora vogliamo trovare la squadra con il punteggio più alto. Cercare di forzare questo problema calcolando il punteggio per ciascuna combinazione possibile (≈ 10^140) non è un'opzione.

Esiste un algoritmo intelligente che prenderà una scorciatoia per la risposta migliore o si dovrà accontentarsi di un algoritmo che trova una buona risposta?

Answer 1

Si potrebbe provare un algoritmo hill climbing. Inizia con un membro che è "popolare" (scelto più spesso dagli altri membri) e aggiunge in modo incrementale nuovi membri che aumentano di più il punteggio della squadra. Questo purtroppo non è garantito per trovare la soluzione migliore, ma probabilmente ne troverà di buone. Per migliorare la tua soluzione potresti provare simulated annealing.

Answer 2

Penso che se fosse possibile risolvere questo problema in modo efficiente, è possibile risolvere in modo efficiente lo http://en.wikipedia.org/wiki/Clique_problem - laddove esiste un collegamento tra due nodi, ciascun nodo viene inserito nell'elenco dei nodi con cui l'altro desidera lavorare. Guardando l'articolo, penso che troverai difficile trovare una buona approssimazione, a meno che il tuo problema non abbia una struttura speciale.