Metoda backtracking

Metoda backtracking construiește soluția pas cu pas și verifică după fiecare alegere dacă soluția parțială mai poate fi continuată. Când o alegere nu mai poate duce la o soluție, metoda renunță la ea și revine pe nivelul anterior, unde încearcă valoarea următoare.

Lecția urmează planul de idei cerut la Titularizare 2019: principiul metodei, oportunitatea utilizării ei și exemplificarea prin probleme rezolvate, cu implementare iterativă și recursivă. Cele trei aplicații clasice din programă — reginele, comis-voiajorul și labirintul — au fiecare enunț, descriere în limbaj natural, cod și o parcurgere cu valori, iar problema reginelor este scrisă în ambele variante. Din ele se aleg cele două probleme cerute la examen.

Principiul metodei

Metoda se aplică problemelor a căror soluție se scrie sub forma unui vector

x = (x[1], x[2], ..., x[n]),    x[k] ∈ S[k]

unde S[1], S[2], ..., S[n] sunt mulțimi finite, iar componentele trebuie să respecte niște condiții interne, adică restricțiile problemei. Vectorul x se numește stivă și se notează de obicei st, fiindcă valorile se adaugă și se scot de la un singur capăt.

Generarea tuturor combinațiilor posibile și verificarea lor la sfârșit ar însemna |S[1]| × |S[2]| × ... × |S[n]| încercări, dintre care cele mai multe se resping abia după ce au fost construite complet. Backtracking-ul schimbă ordinea celor două operații: verifică imediat ce a construit, la fiecare nivel, și abandonează drumul din momentul în care condițiile interne nu mai sunt respectate.

Principiul, în patru puncte:

1. Se lucrează pe niveluri. Nivelul k înseamnă alegerea componentei st[k] din mulțimea S[k].
2. Pe nivelul k valorile se încearcă una câte una, în ordinea în care apar în S[k].
3. O valoare aleasă se testează pe loc. Dacă soluția parțială st[1..k] respectă condițiile interne, se coboară pe nivelul k + 1; dacă nu, se trece direct la valoarea următoare, fără să se mai construiască nimic dincolo de ea.
4. Când valorile nivelului k s-au epuizat, se revine pe nivelul k − 1 și se continuă acolo cu valoarea următoare. Această întoarcere dă numele metodei.

Când soluția parțială este completă — de obicei la k = n — ea se prelucrează sau se afișează, iar căutarea continuă, fiindcă în general se cer toate soluțiile.

Arborele căutării

Căutarea se poate reprezenta printr-un arbore: rădăcina este soluția vidă, un nod de pe nivelul k este o soluție parțială st[1..k], iar fiii lui sunt soluțiile parțiale obținute prin adăugarea unei valori din S[k+1].

Backtracking-ul parcurge acest arbore în adâncime și taie subarborii ai căror rădăcini nu respectă condițiile interne. Ce se câștigă este tocmai ceea ce nu se mai construiește: dacă o soluție parțială este respinsă la nivelul 3, niciunul dintre descendenții ei nu mai este generat.

Oportunitatea utilizării

Metoda se potrivește unei probleme în care:

• soluția se poate scrie ca un vector construit pe niveluri;
• pe fiecare nivel există un număr finit de alegeri;
• o soluție parțială poate fi verificată înainte de a fi completată;
• se cer toate soluțiile, o soluție oarecare sau soluția optimă dintre toate.

Prin backtracking se generează elementele combinatoriale — permutări, aranjamente, combinări, submulțimi, partiții — și se rezolvă probleme precum așezarea reginelor, găsirea unui drum într-un labirint, circuitul comis-voiajorului sau obținerea unei sume date.

Costul metodei

Dacă pe fiecare nivel se încearcă cel mult m valori și soluția are n componente, numărul nodurilor arborelui de căutare este de ordinul m^n. Adăugând costul verificării unei soluții parțiale, complexitatea este

O(p × m^n),    p = costul unei verificări

adică exponențială. Tăierile micșorează constanta și, în practică, un număr mare de ramuri, dar nu schimbă ordinul de creștere.

De aici regula de folosire:

• backtracking-ul se aplică numai când nu se cunoaște un algoritm mai eficient pentru problema dată;
• se aplică pentru valori mici ale datelor de intrare, fiindcă timpul crește exponențial;
• dacă problema cere doar existența unei soluții, căutarea se oprește la prima găsită;
• dacă problema are o soluție greedy, o rezolvare prin programare dinamică sau o formulă directă, acelea se folosesc, nu backtracking-ul.

Modelul general

Soluția se construiește în vectorul st. Pozițiile lui sunt nivelurile: st[k] este valoarea aleasă pe nivelul k, iar variabila k arată nivelul curent.

Algoritmul se scrie cu cinci subprograme, care sunt singurele ce se schimbă de la o problemă la alta:

• init() pregătește nivelul k, punând în st[k] o valoare aflată chiar înaintea primei valori posibile;
• succesor() trece la valoarea următoare de pe nivelul k și întoarce 0 când valorile s-au epuizat;
• valid() spune dacă valoarea așezată pe nivelul k respectă condițiile interne;
• solutie() spune dacă soluția parțială este completă;
• tipar() prelucrează sau afișează soluția completă.

Varianta iterativă

/* as - exista succesor pe nivelul curent
   ev - valoarea asezata pe nivelul curent este valida */
void bt_iterativ() {
    k = 1;
    init();

    while (k > 0) {
        as = 1;
        ev = 0;

        // cat timp exista un succesor si acesta nu este valid
        while (as && !ev) {
            as = succesor();
            if (as)
                ev = valid();
        }

        if (as)
            if (solutie())
                tipar();
            else {
                k++;
                init();
            }
        else
            k--;
    }
}

# exista      - exista succesor pe nivelul curent
# este_valid  - valoarea asezata pe nivelul curent este valida
k = 1
init(k)

while k > 0:
    exista = True
    este_valid = False

    # cat timp exista un succesor si acesta nu este valid
    while exista and not este_valid:
        exista = succesor(k)
        if exista:
            este_valid = valid(k)

    if exista:
        if solutie(k):
            tipar()
        else:
            k += 1
            init(k)
    else:
        k -= 1

Bucla interioară caută pe nivelul curent prima valoare validă. Bucla exterioară hotărăște ce urmează: dacă valoarea s-a găsit și soluția este completă, soluția se afișează și căutarea continuă de pe același nivel; dacă soluția nu este completă, se coboară pe nivelul următor; dacă valoarea nu s-a găsit, se revine pe nivelul anterior. Algoritmul se oprește când revenirea de pe nivelul 1 duce la nivelul 0.

Două amănunte țin de corectitudine:

• init() se apelează la fiecare coborâre, nu o singură dată la începutul programului: un nivel la care se ajunge a doua oară trebuie să-și reia valorile de la capăt;
• la revenire nu se apelează init(): nivelul pe care se revine trebuie să continue de la valoarea la care rămăsese, altfel aceleași soluții s-ar genera la nesfârșit.

Varianta recursivă

În varianta recursivă, nivelul curent este parametrul subprogramului. Coborârea pe nivelul următor se scrie ca apelul bt_recursiv(k + 1), iar pentru revenire nu se scrie nicio instrucțiune: ea se produce la încheierea apelului, când execuția se întoarce în bucla nivelului anterior și continuă cu valoarea următoare.

void bt_recursiv(int k) {
    init(k);
    while (succesor(k))
        if (valid(k)) {
            if (solutie(k))
                tipar();
            else
                bt_recursiv(k + 1);
        }
}

def bt_recursiv(k):
    init(k)
    while succesor(k):
        if valid(k):
            if solutie(k):
                tipar()
            else:
                bt_recursiv(k + 1)

Cele două variante fac aceeași căutare și dau aceleași soluții, în aceeași ordine. Deosebirea este unde se păstrează nivelurile în lucru: varianta iterativă le ține în vectorul st și în variabila k, varianta recursivă le ține în stiva sistemului, prin apelurile neîncheiate.

Când problema se scrie mai firesc cu alte date pe un nivel — o poziție într-o matrice, un cost acumulat — varianta recursivă se scrie mai scurt, cu acele date ca parametri. Acesta este cazul labirintului și al comis-voiajorului, de mai jos.

Problema reginelor

Descrierea soluției în limbaj natural

Cele n regine trebuie așezate pe n linii, iar două regine de pe aceeași linie s-ar ataca. Rezultă că pe fiecare linie se află exact o regină, iar soluția se poate reprezenta prin vectorul st:

st[k] = coloana reginei de pe linia k

• nivelul k este linia k a tablei;
• valorile încercate pe nivelul k sunt coloanele 1, 2, ..., n;
• condiția internă: regina de pe linia k nu trebuie să se atace cu niciuna dintre cele așezate pe liniile 1, 2, ..., k−1. Atacul pe linie nu mai trebuie verificat, prin felul în care a fost aleasă reprezentarea. Rămân două verificări, pentru fiecare i < k:

st[i] = st[k]                          — aceeași coloană
|st[i] − st[k]| = |i − k|              — aceeași diagonală

• soluție completă: k = n, adică toate liniile au primit o regină;
• revenirea: când pe linia k s-au încercat toate cele n coloane, se revine pe linia k − 1 și se mută regina de acolo pe coloana următoare.

Cea de-a doua condiție spune că două regine se află pe aceeași diagonală atunci când diferența liniilor este egală, în valoare absolută, cu diferența coloanelor. Verificarea se face imediat ce regina a fost așezată, nu după completarea tablei: o așezare greșită pe linia 2 oprește construirea tuturor așezărilor care ar fi continuat-o.

Implementare recursivă

#include <iostream>
#include <cstdlib>                      // pentru abs, valoarea absoluta
using namespace std;

int st[20], n;                          // st[k] = coloana reginei de pe linia k

/* Spune daca regina abia asezata pe linia k se impaca cu reginele
   asezate pe liniile 1, 2, ..., k-1. */
int valid(int k) {
    for (int i = 1; i <= k - 1; i++)
        if (st[i] == st[k]                          // aceeasi coloana
            || abs(st[i] - st[k]) == abs(i - k))    // aceeasi diagonala
            return 0;
    return 1;
}

/* Solutia este completa cand fiecare dintre cele n linii are o regina. */
int solutie(int k) {
    return k == n;
}

void tiparire() {
    cout << "Solutie: ";
    for (int i = 1; i <= n; i++)
        cout << st[i] << " ";
    cout << endl;
}

void bt(int k) {
    for (int i = 1; i <= n; i++) {      // coloanele care se incearca pe linia k
        st[k] = i;                      // asezam regina pe linia k, coloana i
        if (valid(k))                   // daca niciuna dintre cele dinainte nu o ataca
            if (solutie(k))             // si daca toate liniile au primit regina
                tiparire();
            else
                bt(k + 1);              // altfel coboram pe linia urmatoare
    }
    /* Cand bucla s-a incheiat, pe linia k nu mai sunt coloane de incercat.
       Apelul se termina si controlul revine pe linia k-1, care continua
       cu coloana urmatoare. Aceasta este revenirea. */
}

int main() {
    cin >> n;
    bt(1);                              // prima regina se aseaza pe linia 1
    return 0;
}

# st[k] = coloana reginei de pe linia k


def valid(k):
    """Regina abia asezata pe linia k se impaca cu cele dinainte?"""
    for i in range(1, k):
        if (st[i] == st[k]                              # aceeasi coloana
                or abs(st[i] - st[k]) == abs(i - k)):   # aceeasi diagonala
            return False
    return True


def solutie(k):
    """Solutia e completa cand fiecare dintre cele n linii are o regina."""
    return k == n


def tiparire():
    print("Solutie:", *st[1:n + 1])


def bt(k):
    for i in range(1, n + 1):       # coloanele care se incearca pe linia k
        st[k] = i                   # asezam regina pe linia k, coloana i
        if valid(k):                # daca niciuna dintre cele dinainte nu o ataca
            if solutie(k):          # si daca toate liniile au primit regina
                tiparire()
            else:
                bt(k + 1)           # altfel coboram pe linia urmatoare
    # Cand bucla s-a incheiat, pe linia k nu mai sunt coloane de incercat.
    # Apelul se termina si controlul revine pe linia k-1, care continua cu
    # coloana urmatoare. Aceasta este revenirea.


n = int(input())
st = [0] * (n + 2)

bt(1)                               # prima regina se aseaza pe linia 1

Implementare iterativă

Descrierea rămâne aceeași. Se schimbă numai felul în care se trece de pe un nivel pe altul: în locul apelului bt(k + 1), variabila k crește și nivelul nou se inițializează; în locul revenirii automate, k scade.

#include <iostream>
#include <cstdlib>
using namespace std;

int st[20], n, k, as, ev;

/* Pregateste linia k: coloana 0 se afla chiar inaintea primei coloane. */
void init() {
    st[k] = 0;
}

/* Trece la coloana urmatoare de pe linia k; 0 cand s-au terminat. */
int succesor() {
    if (st[k] < n) {
        st[k]++;
        return 1;
    }
    return 0;
}

int valid() {
    for (int i = 1; i <= k - 1; i++)
        if (st[i] == st[k]                          // aceeasi coloana
            || abs(st[i] - st[k]) == abs(i - k))    // aceeasi diagonala
            return 0;
    return 1;
}

int solutie() {
    return k == n;
}

void tiparire() {
    cout << "Solutie: ";
    for (int i = 1; i <= n; i++)
        cout << st[i] << " ";
    cout << endl;
}

int main() {
    cin >> n;

    k = 1;                          // incepem cu prima linie
    init();

    while (k > 0) {                 // cat timp nu am revenit sub linia 1
        as = 1;
        ev = 0;

        // caut pe linia k prima coloana neatacata
        while (as && !ev) {
            as = succesor();
            if (as)
                ev = valid();
        }

        if (as)
            if (solutie())
                tiparire();         // tabla e plina: solutie gasita
            else {
                k++;                // coboram pe linia urmatoare
                init();             // care isi ia coloanele de la capat
            }
        else
            k--;                    // coloanele s-au terminat: revenim o linie
    }

    return 0;
}

def init(k):
    """Pregateste linia k: coloana 0 e chiar inaintea primei coloane."""
    st[k] = 0


def succesor(k):
    """Trece la coloana urmatoare de pe linia k; False cand s-au terminat."""
    if st[k] < n:
        st[k] += 1
        return True
    return False


def valid(k):
    for i in range(1, k):
        if (st[i] == st[k]                              # aceeasi coloana
                or abs(st[i] - st[k]) == abs(i - k)):   # aceeasi diagonala
            return False
    return True


def solutie(k):
    return k == n


def tiparire():
    print("Solutie:", *st[1:n + 1])


n = int(input())
st = [0] * (n + 2)

k = 1                               # incepem cu prima linie
init(k)

while k > 0:                        # cat timp nu am revenit sub linia 1
    exista = True
    este_valid = False

    # caut pe linia k prima coloana neatacata
    while exista and not este_valid:
        exista = succesor(k)
        if exista:
            este_valid = valid(k)

    if exista:
        if solutie(k):
            tiparire()              # tabla e plina: solutie gasita
        else:
            k += 1                  # coboram pe linia urmatoare
            init(k)                 # care isi ia coloanele de la capat
    else:
        k -= 1                      # coloanele s-au terminat: revenim o linie

Parcurgere cu valori pentru n = 4

Ramura care începe cu st[1] = 1 nu duce la nicio soluție: oricum ar fi așezate reginele de pe primele linii, linia a patra rămâne fără coloană liberă. Căutarea continuă cu st[1] = 3, care dă a doua soluție, și cu st[1] = 4, care nu dă niciuna. Pentru n = 4 există exact două așezări:

Solutie: 2 4 1 3
Solutie: 3 1 4 2

Prima înseamnă regine pe pozițiile (1,2), (2,4), (3,1) și (4,3). Cele două soluții sunt simetrice una față de cealaltă, față de axa verticală a tablei.

Urmărește căutarea pas cu pas în simulatorul problemei reginelor: tabla, vectorul st și revenirea sunt actualizate la fiecare încercare.

Problema comis-voiajorului

În limbajul teoriei grafurilor se cer ciclurile hamiltoniene ale unui graf neorientat: ciclurile care trec prin fiecare vârf exact o dată.

Descrierea soluției în limbaj natural

Legăturile se rețin în matricea de adiacență a: a[i][j] este 1 dacă între orașele i și j există autostradă și 0 dacă nu există. Traseul se reprezintă prin vectorul st:

st[k] = al k-lea oraș din traseu

• nivelul k este poziția din traseu;
• st[1] este orașul de plecare, așezat înainte de pornirea căutării, iar bt se apelează de la nivelul 2. Orice ciclu trece prin toate orașele, deci fixarea plecării nu pierde niciun traseu, dar împiedică generarea aceluiași ciclu de n ori, o dată pentru fiecare oraș de la care ar fi putut porni;
• valorile încercate pe nivelul k sunt orașele 1, 2, ..., n;
• condițiile interne, verificate de valid(k): orașul încercat nu trebuie să apară deja în traseu, iar între el și orașul de pe nivelul anterior trebuie să existe autostradă;
• soluție completă, verificată de solutie(k): traseul are toate cele n orașe și ultimul oraș se leagă de cel de plecare. A doua condiție este cea care deosebește un ciclu de un simplu drum care trece prin toate orașele;
• revenirea: când pe nivelul k s-au încercat toate orașele, apelul se încheie și controlul revine pe nivelul k − 1.

Aici orașele nu se marchează separat, într-un vector de orașe folosite: faptul că un oraș este deja în traseu se citește din chiar vectorul st, prin bucla din valid(). De aceea nici la revenire nu se demarchează nimic — valoarea rămasă în st[k] va fi oricum înlocuită de următorul oraș încercat.

Implementare

#include <iostream>
using namespace std;

int st[10], n, m, a[10][10], start, x, y;

void citire() {
    cin >> n >> m;                      // numarul de orase si de autostrazi

    for (int i = 1; i <= m; i++) {
        cin >> x >> y;                  // capetele unei autostrazi
        a[x][y] = a[y][x] = 1;          // drumul se poate parcurge in ambele sensuri
    }

    cin >> start;                       // orasul de plecare
    st[1] = start;                      // el ocupa primul nivel al traseului
}

/* Orasul asezat pe nivelul k poate ramane acolo? */
int valid(int k) {
    // fiecare oras apare o singura data in traseu
    for (int i = 1; i <= k - 1; i++)
        if (st[i] == st[k])
            return 0;

    // intre doua orase consecutive trebuie sa existe autostrada
    if (k > 1 && a[st[k]][st[k - 1]] == 0)
        return 0;

    return 1;
}

/* Traseu complet: toate cele n orase, iar ultimul se leaga de cel de plecare. */
int solutie(int k) {
    return k == n && a[st[n]][start] == 1;
}

void tiparire(int k) {
    for (int i = 1; i <= k; i++)
        cout << st[i] << " ";
    cout << start << endl;              // plecarea, scrisa din nou, ca sa se vada intoarcerea
}

void bt(int k) {
    for (int i = 1; i <= n; i++) {      // incercam pe rand orasele care ar putea urma
        st[k] = i;                      // asezam un oras pe nivelul k
        if (valid(k))                   // daca traseul de pana acum se poate parcurge
            if (solutie(k))             // si daca s-a inchis peste toate orasele
                tiparire(k);
            else
                bt(k + 1);              // altfel mai adaugam un oras
    }
    /* Bucla s-a incheiat: pe nivelul k nu mai e niciun oras de incercat,
       apelul se termina si controlul revine pe nivelul k-1. */
}

int main() {
    citire();
    bt(2);                              // nivelul 1 e ocupat de orasul de plecare
    return 0;
}