Aplicații ale backtracking-ului

Aranjamente, combinări, submulțimi, produs cartezian și problema damelor, toate cu aceeași schemă și alt valid.

Un tabel de comparație

Toate problemele de mai jos folosesc schema din lecția anterioară. Diferă doar două lucruri: câte poziții are soluția și ce verifică valid.

Uită-te în tabel înainte de fiecare problemă nouă. Aproape sigur cerința se încadrează undeva în el.

Produsul cartezian

Toate șirurile de lungime n cu valori de la 1 la m. Nicio restricție.

void back(int k) {
    for (int i = 1; i <= m; i++) {
        st[k] = i;
        if (k == n) afisare();
        else back(k + 1);
    }
}

Nu există deloc valid. Pentru n = 2, m = 3: 1 1, 1 2, 1 3, 2 1, … , 3 3.

Este cazul de bază al schemei. Cu m = 2 îl poți folosi și ca generator de configurații binare.

Aranjamente

Alegi p elemente distincte din n, iar ordinea contează. Este permutarea oprită mai devreme:

void back(int k) {
    for (int i = 1; i <= n; i++)
        if (!folosit[i]) {
            st[k] = i;
            folosit[i] = true;
            if (k == p) afisare();
            else back(k + 1);
            folosit[i] = false;
        }
}

Singura schimbare față de permutări: k == p în loc de k == n.

Combinări

Alegi p elemente din n, iar ordinea nu contează. Ca să nu generezi de mai multe ori aceeași mulțime în ordini diferite, impui o ordine unică: strict crescătoare.

void back(int k) {
    for (int i = st[k-1] + 1; i <= n; i++) {
        st[k] = i;
        if (k == p) afisare();
        else back(k + 1);
    }
}

cu st[0] = 0 înainte de primul apel.

Bucla pornește acum de la valoarea precedentă plus unu, nu de la 1. Condiția a intrat în antetul buclei. Așa e mai eficient decât s-o verifici după, pentru că valorile invalide nici nu se mai încearcă.

O îmbunătățire utilă: dacă mai ai de completat p - k + 1 poziții, nu are rost să pornești de la o valoare prea mare. Bucla poate merge doar până la n - p + k. Așa tai ramuri care oricum nu duc nicăieri.

Submulțimi

Toate submulțimile unei mulțimi cu n elemente. Față de combinări, lungimea nu mai este fixată, deci fiecare stare parțială este ea însăși o soluție.

void back(int k) {
    for (int i = st[k-1] + 1; i <= n; i++) {
        st[k] = i;
        afisare(k);         // afișez la fiecare pas, nu doar la capăt
        back(k + 1);
    }
}

Sunt 2ⁿ submulțimi, inclusiv cea vidă. Pe aceasta o afișezi separat, înainte de apel, dacă enunțul o cere.

Toată diferența este că apelul afisare a trecut din interiorul unui if în corpul buclei. Observă cât de puțin se schimbă.

Problema damelor

Se așază n dame pe o tablă n × n astfel încât să nu se atace: nu pe aceeași linie, coloană sau diagonală.

Trucul principal este reprezentarea: st[k] este coloana damei de pe linia k. Astfel condiția „nu pe aceeași linie" este satisfăcută automat, prin construcție.

Rămân două condiții:

bool valid(int k) {
    for (int i = 1; i < k; i++)
        if (st[i] == st[k] ||                       // aceeași coloană
            k - i == abs(st[k] - st[i]))            // aceeași diagonală
            return false;
    return true;
}

Două dame sunt pe aceeași diagonală când diferența liniilor este egală cu diferența coloanelor, în valoare absolută. Verific-o pe o tablă desenată. E genul de condiție pe care o uiți ușor, dar o redescoperi la fel de ușor.

Restul programului este schema nemodificată.

Cum abordezi o problemă nouă

Pune-ți trei întrebări, în ordine:

1. Ce este o soluție? Un șir de câte elemente, cu ce semnificație are fiecare poziție?
2. Ce valori poate lua o poziție? Asta îți dă bucla for.
3. Când este o alegere compatibilă cu cele dinainte? Asta îți dă valid.

Dacă răspunzi la ele, programul se scrie aproape singur. Cel mai mult exercițiu cere alegerea reprezentării, ca la dame, unde indicele este linia și valoarea este coloana.

De reținut

• Produs cartezian: fără condiție. Permutări: valori distincte. Combinări: strict crescătoare.
• Aranjamentele sunt permutări oprite la p.
• La combinări, pune condiția în antetul buclei, nu în valid.
• La submulțimi, fiecare stare parțială este o soluție.
• La dame, indicele este linia și valoarea este coloana. Așa o condiție dispare prin construcție.
• Începe mereu de la „ce este o soluție și ce înseamnă st[k]".