Algoritmo per abbinare i partner preferiti in gruppi di tre
https://stackoverflow.com/questions/294660
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Qual è un buon algoritmo per risolvere questo problema?
Ho tre gruppi di persone: gruppo A, gruppo B e gruppo C. Vi è lo stesso numero di persone in ciascun gruppo. Ognuno di essi ha un elenco di persone negli altri gruppi con cui sono disposti a lavorare. Voglio raggruppare tutte queste persone in gruppi di 3 (uno da A, uno da B e uno da C) in modo che tutti in un gruppo vogliano lavorare con le altre persone nel loro gruppo.
Come posso trovare questi gruppi in modo rapido? Se non c'è modo di rendere felici tutti, l'algoritmo dovrebbe prima rendere molti gruppi con tre persone che vogliono lavorare l'uno con l'altro, quindi rendere felici quante più persone negli altri gruppi.
Un ultimo punto: le persone concordano con chi vogliono lavorare (se la persona x vuole lavorare con la persona y, allora anche y vuole lavorare con x). Se anche tu potessi dare una grande O del tempo di esecuzione del tuo algoritmo, sarebbe fantastico!
Soluzione
Questo è come il problema del matrimonio stabile, ma con 3 parti anziché due.
Dai un'occhiata a soluzioni efficienti per il problema precedente (corrispondenza del grafico bipartito) e adattale alle tue esigenze.
http://en.wikipedia.org/wiki/Stable_marriage_problem
Un adattamento potrebbe essere innanzitutto quello di costruire coppie di lavoro solo dai gruppi A e B. Quindi queste coppie devono essere accoppiate con un lavoratore del gruppo C ciascuno. Lascia che le coppie preferiscano solo i lavoratori su cui entrambi i membri della coppia concordano (date le loro liste). Nota che questo darà solo un ottimo locale.
Una soluzione ottimale per la corrispondenza k-partite è NP-difficile da trovare:
http://www.math.tau.ac .il / ~ safra / PapersAndTalks / k-DM.ps
Vedi questo documento per una soluzione non ottimale al problema della corrispondenza k-part:
Sono sicuro che puoi trovarne altri su Google tu stesso ora che conosci i termini da cercare. Non so se esiste un algoritmo efficiente che fornisce la soluzione ottimale per k = 3.
Altri suggerimenti
Questo è diverso da un'estensione del problema del matrimonio stabile, dal momento che, come ho capito la domanda del PO, le persone in ciascun gruppo non hanno un elenco ordinato di chi vogliono lavorare dalla maggior parte alla meno; è una relazione binaria (disponibile / non disponibile).
Questo può essere formulato come un problema di programmazione di numeri interi che può essere risolto abbastanza rapidamente. Fornisco la formulazione matematica del problema di seguito; puoi usare un pacchetto come glpk o AMPL / CPLEX per elaborare i dati.
Definisce le seguenti matrici:
M1 = |A| x |B| matrice, dove
M1(a,b) = 1 se un (dato membro di A) è disposto a lavorare con b (dato membro di B) e 0 altrimenti
M2 = |A| x |C| matrice, dove M2(a,c) = 1 se un (dato membro di A) è disposto a lavorare con c (dato membro di C) e 0 altrimenti
M2 = |B| x |C| matrice, dove
M3(b,c) = 1 se b (dato membro di B) è disposto a lavorare con c (dato membro di C) e 0 altrimenti
Adesso definisci una nuova matrice che useremo per la nostra massimizzazione:
X = |A| x |B| x |C| matrice, dove
X(a,b,c) = 1 se facciamo in modo che a, b e c lavorino insieme.
Ora, definisci la nostra funzione oggettiva:
// Massimizza il numero di gruppi
massimizza Sum[(all a, all b, all c) X(a,b,c)]
soggetto ai seguenti vincoli:
// Per garantire che nessuno venga inserito in due gruppi
Per tutti i valori di a: Sum[(all j, k) X(a, j, k)] <= 1
Per tutti i valori di b: Sum[(all i, k) X(i, b, k)] <= 1
Per tutti i valori di c: Sum[(all i, j) X(i, j, c)] <= 1
// Per garantire che tutti i gruppi siano composti da individui compatibili
Per tutti a, b, c: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3
Solo una breve nota a questo problema. In primo luogo, non è un esempio del problema del matrimonio stabile, né in realtà una sua estensione (cioè il problema del 3D matching stabile). Indipendentemente da ciò, si tratta di un problema di abbinamento 3D noto per essere NP-difficile (vedi Garey e Johnson). Per risolvere un problema del genere in modo ragionevole, è probabile che sia necessario utilizzare una qualche forma di vincolo, numero intero o programmazione lineare (esistono altri metodi). Qualcosa che potrebbe essere utile è la nuova Microsoft Solver Foundation, quindi dai un'occhiata.
Per cominciare, puoi eliminare tutti i fatti in cui le due parti hanno elenchi disgiunti di chi lavoreranno nel terzo gruppo. Quindi avvia una forza bruta, approfondisci la prima ricerca, scegliendo sempre dal meno popolare al più popolare.
In alternativa, equivalente alla precedente eliminazione, forma un elenco di tutti i trio possibili e lavora invece da quello.
Ho riscontrato un problema simile e ho appena scritto uno script che lo costringe brutalmente ... http: // grouper. owoga.com/
I miei pensieri iniziali erano: per un gruppo più numeroso che era troppo grande per forza bruta, un qualche tipo di algoritmo genetico? Effettua N scambi casuali M volte. Segna ogni nuovo accordo con una funzione di "felicità". Prendi i migliori, alleva, ripeti.
Per i piccoli gruppi ho finito per ottenere risultati migliori ripetendo alcuni gruppi, trovando lo scambio "migliore" (quello che ha prodotto il più alto guadagno di "felicità"), facendolo, quindi ripetendo.
