Algoritmo ungherese: ho problemi ad assegnare il maggior numero possibile di posti di lavoro ai lavoratori

Question

Ho creato un'implementazione dell'algoritmo ungherese in C++. Questa implementazione funziona molto bene per in molti casi. Tuttavia ci sono alcuni casi in cui il mio algoritmo non funziona affatto perché credo (ed è vero) che la mia implementazione di un passo dell'algoritmo sia errata.

La mia implementazione prende come input l'array X, esegue i passaggi dell'algoritmo e produce l'assegnazione finale.

I passi dell'algoritmo possono essere trovati sul wiki: Hungarian Algorithm

Nel passaggio 3 ha la seguente matrice di spedizione (lavoratori sono rappresentati da righe e lavori per colonne)

e poi si dice

Initially assign as many tasks as possible then do the following 

Tuttavia non capisco quello che una corretta l'implementazione di questo sarebbe. Come puoi assegnare il maggior numero di compiti possibile? La scelta sarebbe casuale? Quindi, se la scelta fosse casuale, potrei scegliere il primo lavoratore a svolgere il primo lavoro, il secondo lavoratore a svolgere il quarto lavoro e il quarto lavoratore a svolgere il secondo lavoro. Quindi il secondo lavoratore è escluso. Tuttavia in wikipedia gli autori hanno adottato un approccio diverso. Il terzo lavoratore deve svolgere il primo lavoro, il secondo lavoratore deve svolgere il secondo lavoro e il quarto lavoratore deve svolgere il secondo lavoro. Quindi il primo lavoratore è escluso.

Il problema di fare queste azioni casuali è il seguente caso:

Supponiamo mentre corriamo l'algoritmo e fare le nostre operazioni aritmetiche sull'ingresso, prima di assegnare il maggior numero di compiti ai lavoratori possibile, abbiamo la seguente matrice costo :

2 2 0 3 
6 1 6 0 
0 0 6 1 
0 3 5 3 

Se scelgo a caso per assegnare il terzo lavoro per il primo operaio, il quarto lavoro per il secondo operaio e poi il primo lavoro al terzo lavoratore, avrò il quarto operaio lasciato fuori. Ma perché l'algoritmo funzioni correttamente dobbiamo assegnare as many jobs to workers as possible. È questo il caso qui? No, perché se invece di assegnare il primo lavoro al terzo lavoratore assegnassi il primo lavoro al quarto lavoratore, potrei quindi assegnare il secondo lavoro al terzo lavoratore e quindi l'algoritmo non solo assegnerebbe il maggior numero possibile di lavori ai lavoratori ma troverà il risultato ottimale.

Conclusione: eseguire assegnazioni casuali non è un buon approccio.

Ho cercato su questo un po 'e ho trovato la seguente lezione:

http://www.youtube.com/watch?v=BUGIhEecipE

In questa conferenza il professore suggerisce un approccio diverso per il problema di assegnare più compiti possibili. Secondo lui se qualsiasi riga o colonna ha esattamente uno zero, faremo un incarico. Quindi, partendo dalla prima riga, controlla se la prima riga ha solo uno zero, se è il caso, effettua un incarico. Altrimenti ignora quella riga e vai alla seconda riga, fai ripetutamente la stessa cosa riscansionando la tabella finché tutti gli zeri non sono coperti a causa di assegnazioni.

Seguendo questo approccio, si può vedere che il caso precedente è risolto. Quello che facciamo è assegnare il terzo lavoro al primo lavoratore, il quarto al secondo lavoratore, poi vediamo che il terzo lavoratore può prendere 2 lavori, quindi lo ignoriamo per un po ', assegniamo il primo lavoro al quarto lavoratore e quindi tornare al fine di assegnare il secondo lavoro al terzo lavoratore.

La mia implementazione segue questa logica, tuttavia, di nuovo, non risolve tutti i casi.

Prendiamo ad esempio il caso seguente:

0 0 0 0 
0 0 0 0 
0 0 4 9 
0 0 2 3 

Il primo lavoratore può prendere 4 posti di lavoro, il secondo 4, il terzo 2 e la quarta 2. Così la mia applicazione non fa le assegnazioni, perché avrei bisogno almeno un lavoratore che può svolgere solo un lavoro per svolgere un incarico e quindi continuare la scansione della tabella. Quindi cosa faccio in questo caso? Assegnazioni arbitrarie sarebbe una brutta cosa da fare, purtroppo in questa lezione non viene suggerito nulla. Posso solo pensare a quanto segue:

Per ogni lavoratore ha un contatore il cui valore indica la quantità di attività che possono essere assegnate a lui, quindi quanti zeri abbiamo in quella riga? questo è il valore del contatore. Quindi inizia ad assegnare compiti arbitrari al lavoratore con il contatore più piccolo. Quindi, in questo caso, la matrice di contatori per ogni lavoratori includerebbe i seguenti valori:

4 
4 
2 
2 

vorrei scegliere ad esempio il terzo dei lavoratori e assegnare arbitrario a lui il primo lavoro. I nuovi contatori sarebbero:

3 
3 
0 
1 

Vorrei quindi scegliere il quarto dei lavoratori e fare l'unica assegnazione disponibile per lui (che è il secondo lavoro). I nuovi contatori sarebbero:

2 
2 
0 
0 

Quindi potrei scegliere il primo operatore o il secondo. Farei un incarico arbitrario per il primo lavoratore e dargli il terzo lavoro. I contatori sarebbero

1 
0 
0 
0 

Infine darei il quarto compito al primo lavoro.

assegnazioni Così il finale:

0 0 0 * 
0 0 * 0 
* 0 4 9 
0 * 2 3 

sembra un buon approccio, ma ho paura che ci potrebbe essere un caso particolare che questo metodo non avrebbe funzionato. Come posso verificare se questo approccio funzionerebbe per tutti i casi e, in caso contrario, quale approccio risolverebbe completamente il mio problema?

Grazie in anticipo

Answer 1

Il tuo approccio attuale non non lavoro.

0 2 0 
3 0 0 
4 0 0 

Il tuo metodo: "Allora iniziare ad assegnare compiti arbitrari al lavoratore con il più piccolo contatore" Tutti i lavoratori hanno lo stesso contatore, così dicono si sceglie lavoratore 1 e lo assegna al compito 3, è possibile abbinare un solo dei rimanenti lavoratori, mentre con questa matrice si potrebbe ovviamente eguagliare tutti e tre.

Quello che ti serve è un massimo di corrispondenza bipartito tra quei lavoratori e le attività, dove una coppia è abbinabile se c'è uno 0 nella posizione pertinente. È possibile trovare tale corrispondenza passando manualmente attraverso percorsi di conversione o più rapidamente utilizzando l'algoritmo di Hopcroft-Karp.