algoritm-kuhn

 Algoritmul lui Kuhn (Ungar)

h1. Algoritmul lui Kuhn(Ungar)

h1. Algoritmul lui Kuhn (Ungar)
 
== include(page="template/implica-te/scrie-articole" user_id="sims_gl") ==
 
(Categoria _Algoritmi_, Autor _Tiberiu Florea_)

h2. Introducere

Vom adopta urmatoarele conventii de transpunere a limbajului de teoria grafurilor in termeni de matrice:

* Spunem despre o linie sau despre o coloana ca este _acoperita_ daca la un anumit pas face parte din multimea nodurilor marcate in cadrul procesului de determinare a unui suport minim.

* Spunem despre o linie sau despre o coloana ca este *acoperita* daca la un anumit pas face parte din multimea nodurilor marcate in cadrul procesului de determinare a unui suport minim.

* Spunem despre un element al matricei ca este _incercuit_ daca face parte din cuplajul gasit pana in momentul respectiv.

* Spunem despre un element al matricei ca este *incercuit* daca face parte din cuplajul gasit pana in momentul respectiv.

* Spunem despre un element al matricei ca este _taiat_ daca corespunde unei muchii care va putea fi folosita pentru obtinerea unui drum de crestere, intr-un sens ce va fi clarificat ulterior.

* Spunem despre un element al matricei ca este *taiat* daca corespunde unei muchii care va putea fi folosita pentru obtinerea unui drum de crestere, intr-un sens ce va fi clarificat ulterior.

h2. Algoritmul propriu-zis
Initial, toate liniile si coloanele sunt decuplate. Algoritmul se va desfasura in $n$ pasi, fiecare pas decurgand dupa cum urmeaza:

Se descopera toate liniile si coloanele matricei si se acopera toate coloanele cuplate. Se pastreaza elementele incercuite, dar se considera ca nici un element nu este taiat. Pornind de la cuplajul obtinut la pasul anterior, se determina un suport minim de acelasi cardinal, adica o multime de linii si coloane care _acopera_ toate zerourile. Modul de obtinere a suportului minim a fost dezvoltat de Egerváry, iar demonstratia corectitudinii sale depaseste scopul acestui articol. Cititorii interesati pot consulta Caius Iacob, _Matematici clasice si moderne_, vol. I, Bucuresti: Editura Tehnica, 1978 pentru o demonstratie completa. Atata timp cat putem gasi un zero descoperit pe o linie $i$ si o coloana $j$, il taiem si consideram urmatoarele doua cazuri:

Se descopera toate liniile si coloanele matricei si se acopera toate coloanele cuplate. Se pastreaza elementele incercuite, dar se considera ca nici un element nu este taiat. Pornind de la cuplajul obtinut la pasul anterior, se determina un suport minim de acelasi cardinal, adica o multime de linii si coloane care acopera toate zerourile. Modul de obtinere a suportului minim a fost dezvoltat de Egerváry, iar demonstratia corectitudinii sale depaseste scopul acestui articol. Cititorii interesati pot consulta Caius Iacob, _Matematici clasice si moderne_, vol. I, Bucuresti: Editura Tehnica, 1978 pentru o demonstratie completa. Atata timp cat putem gasi un zero descoperit pe o linie $i$ si o coloana $j$, il taiem si consideram urmatoarele doua cazuri:

# *Linia $i$ este cuplata*: Acoperim linia $i$ si descoperim coloana cu care este cuplata. Coloana cu care este cuplata linia $i$ va fi mereu acoperita din cauza modului in care lucreaza algoritmul: in orice moment ori linia ori coloana pe care se afla un zero incercuit vor fi acoperite, deoarece initial toate coloanele cuplate sunt acoperite, si singura operatie pe care o efectuam este descoperirea unei coloane si acoperirea liniei cu care aceasta este cuplata.
# *Linia $i$ nu este cuplata*: Incercam sa construim un drum de crestere, dupa cum urmeaza:

    for (min = 1 << 30, i = 1; i <= N; ++ i) if (!cr[i])
        for (j = 1; j <= N; ++ j) if (!cc[j])

            min = G[i][j] + vr[i] - vc[j];

            min <?= G[i][j] + vr[i] - vc[j];

    for (i = 1; i <= N; ++ i) if (cr[i]) vr[i] += min;
    for (j = 1; j <= N; ++ j) if (!cc[j]) vc[j] += min;

    for (j = 1; j <= N; ++ j) if (!cc[j] && G[i][j] + vr[i] == vc[j])
        if (r[i]) {
            p[i] = j, cr[i] = 1, cc[r[i]] = 0;
            break;
        } else {
            do t = l[j], r[i] = j, l[j] = i, i = t, j = p[i]; while (t);
            return;
        }

    for (i = 1; i <= N; ++ i) if (!cr[i])
        for (j = 1; j <= N; ++ j) if (!cc[j] && G[i][j] + vr[i] == vc[j])
            if (r[i]) {
                p[i] = j, cr[i] = 1, cc[r[i]] = 0;
                break;
            } else {
                do t = l[j], r[i] = j, l[j] = i, i = t, j = p[i]; while (t);
                return;
            }

    find_zero ();
}

        for (j = 1; j <= N; ++ j) scanf("%d", &G[i][j]);
    memset (vr, 0, sizeof (vr)), memset (vc, 0, sizeof (vc));

    memset (1, 0, sizeof (1)), memset (r, 0, sizeof (r));

    memset (l, 0, sizeof (l)), memset (r, 0, sizeof (r));

    for (cnt = 0; cnt < N; ++ cnt) {
        memset (cr, 0, sizeof (cr)), memset (p, 0, sizeof (p));

        memcpy (cc, 1, sizeof (cc));

        memcpy (cc, l, sizeof (cc));

        find_zero ();
    }

3701