Algoritmo per determinare la migliore combinazione di tenere insieme gli studenti nelle loro stanze da campo

Questa soluzione non è molto veloce e non sono sicuro che troverà sempre la migliore soluzione , ma penso che dovrebbe essere una strategia praticabile per trovare un abbastanza buono soluzione.

Per prima cosa serve una funzione per calcolare il punteggio di una stanza. Il punteggio è semplicemente la somma del numero di desideri soddisfatti di tutti i suoi abitanti attuali.

Prima distribuisci casualmente tutti gli studenti su tutti i letti del campo (i letti possono essere vuoti). Quindi cerca i letti in due stanze diverse dove scambiare gli occupanti (o spostare l'occupante quando un letto è vuoto) migliorerebbe la somma dei punteggi di entrambe le stanze:

for each bed as bed1
    for each bed as bed2 which comes after bed1
        if swapping the occupants of bed1 and bed2 improves the total score
           swap occupants of bed1 and bed2

Ripeti fino a quando non viene trovato alcuno scambio.

Possibile difetto: questo metodo non troverà un miglioramento che richiede di spostare più di due persone per raggiungere un cambiamento positivo nel punteggio. Non sono sicuro che tali situazioni siano possibili, però.

Per quanto posso dire questo problema è un caso speciale del problema di assegnazione quadratica ( QAP )

Se la dimensione del problema è ragionevole, probabilmente proverei a modellarlo come un problema intero e risolverlo con un risolutore MIP (vedi GLPK o CBC per i risolutori open source).

Il problema matematico probabilmente assomiglierebbe a qualcosa del genere (supponendo che tutte le stanze abbiano la stessa capacità, se vuoi modellare stanze eterogenee, il modello sarebbe un po 'diverso):

Supponiamo che Q sia la capacità della stanza. Sia S l'insieme di studenti. Sia $ x_ {i, j} $ una variabile binaria che dice che lo studente è nella stessa stanza dello studente j. Sia $ a_ {i, j} $ essere 1 se voglio essere con j e 0 altrimenti.

Cerchiamo di massimizzare $ \ sum_ {i \ in S, j \ in S} x_ {i, j} a_ {i, j} $

Soggetto a:

$ \ sum_ {j \ in S} x_ {i, j} = Q, \ tutto all \ in S $ $ x_ {i, j} = x_ {j, i}, \ per tutto i \ in S, j \ in S $ $ x_ {i, k} \ geq x_ {i, j} + x_ {j, k} - 1, \ per tutto i \ in S, j \ in S, k \ in S $

Wow, non è un compito facile, poiché in pratica il numero di risultati possibili cresce con la formula

Totale = M! / (n! * (M - n)!) ( Combinazione senza ripetizione )

Per 6 bambini in due stanze da tre, ci sono già 120 possibilità. Fai semplicemente i conti con i tuoi numeri e vedrai chiaramente che hai bisogno di un altro approccio.

Questo tipo di problema è ciò che è chiamato NP-Hard. Se trovi una soluzione, non sarai mai sicuro che sia il migliore finché non provi tutte le possibilità.

Puoi leggere un po 'di algoritmi genetici , che fondamentalmente ciò che fa è randomizzare la selezione usando idee simili alla genetica, sì!

Avrai anche bisogno di una funzione di bontà , per capire quando una soluzione è migliore delle altre.

Un altro approccio è quello di analizzare la popolazione e scoprire se è possibile trovare le regole per distribuirle. E.g Maschi vs femmine, con questo già dividi il problema a metà.

Diversi corsi, età, somiglianza, ecc.

Sto cercando di creare un algoritmo, se trovassi una soluzione accettabile, te lo farò sapere!