Algoritmo ungherese e molteplici fattori

Question

Ho una situazione in cui devo assegnare le persone a diversi eventi. Se avessimo solo un prezzo come fattore, andrebbe bene, ma ci sono un certo numero di fattori che arrivano.

Innanzitutto, alcuni retroscena. Questo è per un'organizzazione senza scopo di lucro che promuove ore di storia per i bambini ricoverati in ospedale per qualsiasi motivo, quindi dipendono dal lavoro volontario per farlo. Quindi, poiché fanno affidamento sulla buona volontà delle persone, offrono alle persone tutto il lavoro che le persone possono / vogliono fare, che varia come:

• Alcune persone possono fare solo le mattine e altre persone possono fare solo i pomeriggi;
• Alcune persone possono fare solo il lunedì e il giovedì, altre persone non possono andare ad agosto o dicembre;
• Alcune persone possono andare solo una volta al mese, altre possono andare 4 volte (e anche ad altre persone viene data la "priorità" in queste azioni perché hanno più esperienza e sono disponibili a farlo 10 volte al mese)

Quindi, ho capito un po 'i primi due. Dato che l'algoritmo ungherese riguarda il prezzo, darei loro un prezzo stupidamente alto per le volte che non possono andare. Tuttavia, come faresti con gli altri?

Ho pensato di dare loro una sorta di punteggio. Qualcosa del genere: una persona che può farlo una volta al mese costa qualcosa come 1000 punti. Se qualcuno può andare 10 volte al mese, quella persona costa 100 punti (1000 base divisa per 10). Inoltre, il modo di distribuirlo sarebbe aumentare il prezzo ogni volta che si farebbe un'azione separata, in questo modo (le persone selezionate hanno un * sul loro costo associato):

Prima iterazione

         | August 1st 2009
Person A | 1000
Person B | 500 *

Seconda iterazione

         | August 8th 2009
Person A | 1000 *
Person B | 1000 

Questo sarebbe il modo di distribuire di conseguenza tra tutte le persone, dando più priorità a quelli che possono farlo più volte.

Cosa ne pensi e come lo faresti?

Answer 1

Questo è un problema di pianificazione / ottimizzazione, quindi la domanda chiave è "quale quantità stai cercando di massimizzare"? Immagino che tu stia cercando di massimizzare il numero totale di ore lavorate tra tutti i tuoi volontari senza scontri, fatti salvi i vincoli di orario di ciascun volontario. Parli anche di dare la priorità ai volontari con più esperienza, quindi sembra che tu stia dicendo " alcuni volontari sono preferiti rispetto ad altri " ;.

Questo è quindi un classico problema di corrispondenza bipartita . Vedi ad es. p.498 di The Algorithm Design Manual (2a edizione), di Steven Skiena. L'approccio di base è quello di costruire un grafico con vertici che rappresentano sia l'insieme dei volontari, sia l'insieme delle fasce orarie che si sta tentando di riempire. I bordi collegano i volontari a intervalli di tempo validi. La soluzione ottimale è quindi la più grande serie possibile di spigoli in cui non viene ripetuto volontario o intervallo di tempo. Questa è una corrispondenza.

Alcuni dei tuoi volontari potrebbero essere in grado di fare più di uno slot; questo può essere modellato replicando quel vertice volontario più volte.

Se si desidera implementare la definizione delle priorità dei volontari, ciò aggiunge effettivamente una ponderazione a ciascun margine, modellando l'esperienza di quel volontario per quel compito. In questo caso, come pensavi, avrai bisogno di qualcosa di simile all'algoritmo ungherese. Se riesci a cavartela senza questo, puoi trasformare il problema in un grafico di flusso e applicare un algoritmo di flusso di rete. Ecco un esempio di che implementa la corrispondenza ponderata e non ponderata .

Se vuoi maggiori dettagli, comprese altre alternative e più collegamenti alle implementazioni, ti consiglio vivamente di procurarti una copia del Manuale di progettazione algoritmo: è un riferimento straordinariamente chiaro e pratico.