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₁ , x₂, ..., x_m, lucrarile cu y₁, y₂ , ..., 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.

Definim matricea de afectare astfel: X = (x_ij), 1 ≤ i ≤ m, 1 ≤ j ≤ n, x_ij = 1 daca muncitorul x_i efectueaza lucrarea y_j, si x_ij = 0 in caz contrar. Cand ∑_ij = min(m, n), matricea de afectare se numeste saturanta. Voi prezenta algoritmul elaborat in 1955 de Kuhn, numit de acesta algoritmul ungar pentru rezolvarea problemelor de afectare definite de matrice saturante, cunoscut si sub numele de metoda ungara, deoarece se bazeaza pe rezultatele a doi matematicieni maghiari: D. König si E. Egerváry. Demonstratia va presupune ca m = n; se va vedea apoi ca algoritmul se poate extinde foarte usor la matrice care nu sunt patrate.

Descrierea algoritmului

Algoritmul utilizeaza urmatoarea proprietate:

Propozitia 1: Multimea solutiilor minime ale unei probleme de afectare nu se modifica daca la toate elementele unei linii sau coloane a matricei costurilor se aduna acelasi numar real λ.

De asemenea, este necesara cunoasterea urmatoarei teoreme:

Teorema 1 (Teorema lui König): Fie G un graf bipartit, ν(G) cardinalul unui cuplaj maxim in acest graf, si τ(G) cardinalul unui suport minim. Atunci exista egalitatea: ν(G) = τ(G), adica numarul maxim de muchii ale unui cuplaj este egal cu numarul minim de varfuri ale unui suport.

Deoarece m = n si matricea de afectare este saturanta, orice solutie a problemei de afectare contine un singur 1 in fiecare linie si in fiecare coloana, deci, prin transformarea matricei costurilor, costul asociat oricarei solutii creste cu λ. Din acest motiv, multimea solutiilor minime ale problemei de afectare nu se modifica prin transformari de acest tip ale matricei costurilor.

Algoritmul lui Kuhn se bazeaza si pe faptul ca o solutie a problemei de afectare corespunde unui cuplaj al grafului bipartit cu partile X = {x₁, x₂, ..., x_n} si Y = {y₁, y₂, ..., y_n}, si se desfasoara in mai multi pasi, fiind prezentat aici intr-o varianta modificata si simplificata fata de cea originala.