Revizia anterioară Revizia următoare
Algoritmul lui Kuhn(Ungar)
Introducere
Voi prezenta in continuare problema afectarii impreuna cu una din cele mai eficiente solutii pentru rezolvarea ei: Algoritmul lui Kuhn. In ultima parte a articolului, voi oferi un exemplu de implementare usor de folosit in concursurile de informatica. Se presupun cunoscute notiunile de cuplaj maxim si suport minim intr-un graf bipartit, precum si modul de obtinere a unui cuplaj maxim intr-un graf bipartit cu ajutorul drumurilor de crestere. Sa incepem cu definitia problemei discutate.
Problema de afectare: Exista m muncitori si n lucrari, fiecare muncitor putand efectua una sau mai multe lucrari. Notam muncitorii cu x 1 , x 2 , ..., x m , lucrarile cu y 1 , y 2 , ..., y n , si asociem costul v ij ≤ 0 efectuarii de catre muncitorul x i a lucrarii y j , faptul ca v ij = ∞ avand semnificatia ca muncitorul x i nu poate efectua lucrarea y j . Sa se gaseasca o repartizare a celor m muncitori la cele n lucrari astfel incat un muncitor sa efectueze cel mult o lucrare, iar o lucrare sa fie efectuata de cel mult un muncitor, cu conditia ca costul total de executie sa fie minim.
