...
Backtracking

Metoda backtracking, explicată pe exemple

Pe scurt

Backtracking este metoda prin care construiești o soluție pas cu pas și, de îndată ce un pas nu mai poate duce la o soluție corectă, te întorci la pasul anterior și încerci altă variantă. Așa generezi toate permutările, combinările sau submulțimile unei mulțimi și rezolvi probleme precum cele N regine sau sudoku. E mai rapidă decât încercarea tuturor variantelor, pentru că renunță devreme la drumurile greșite.

  • 3întrebări la fiecare pas: candidat, valid, soluție
  • n!permutări de n elemente
  • 2ⁿsubmulțimi de n elemente
  • 2lecții gratuite, fără card
BACKTRACKING · 4 REGINE încerci · revii N regine

Problema celor N regine, în animație

Backtracking-ul pune câte o regină pe fiecare rând. O poziție atacată se colorează roșu; când un rând nu mai are nicio poziție bună, algoritmul se întoarce și mută regina de pe rândul de deasupra.

Schema generală a metodei backtracking

Soluția se construiește ca un vector st[1..n], completat poziție cu poziție. Pentru fiecare poziție k:

  1. încerci pe rând fiecare candidat posibil pentru st[k];
  2. verifici dacă e valid împreună cu ce ai pus deja pe pozițiile 1..k-1 (de exemplu, nu se repetă sau regina nu e atacată);
  3. dacă e valid și ai completat toate pozițiile, ai o soluție: o afișezi sau o numeri;
  4. dacă e valid, dar soluția nu e completă, treci la poziția k + 1;
  5. când ai epuizat candidații pentru poziția k, revii la k - 1 și încerci acolo următorul candidat.

Pasul 5 dă numele metodei: back-tracking, întoarcerea pe drumul parcurs. Implementarea recursivă face asta automat: revenirea dintr-un apel este întoarcerea la poziția anterioară.

Permutări prin backtracking în C++, Python și Java

Generarea permutărilor mulțimii {1, 2, …, n}, apoi problema celor N regine în Python.

def permutari(n):
    sol, folosit, rezultat = [], [False] * (n + 1), []

    def bt():
        if len(sol) == n:                # soluție completă
            rezultat.append(sol[:])
            return
        for x in range(1, n + 1):        # încerc fiecare candidat
            if not folosit[x]:           # e valid?
                folosit[x] = True
                sol.append(x)
                bt()                     # merg mai departe
                sol.pop()                # revin (backtrack)
                folosit[x] = False

    bt()
    return rezultat


print(permutari(3))   # [[1, 2, 3], [1, 3, 2], [2, 1, 3], ...]

Încearcă: toate submulțimile, prin backtracking

Problema din lecția 71 a cursului de algoritmi: aceeași schemă ca la permutări, aplicată pe submulțimi. Verificarea e pe loc.

Exercițiu din lecția 71 · cursul de algoritmi

Backtracking: toate submulțimile

Scrie funcția submultimi(lista) care returnează toate submulțimile, în ordinea generării prin backtracking „de la start încolo”: salvezi submulțimea curentă, apoi încerci fiecare element de la start la final. Fără itertools.

  1. Într-o funcție internă backtrack(start): rezultat.append(curenta[:]).
  2. Pentru i de la start: append, backtrack(i + 1), pop().
  3. Trebuie să apară: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]], [[]], 32.
Indiciu: Funcția internă vede lista, rezultat și curenta din funcția exterioară, deci nu trebuie să le trimiți ca parametri.
def submultimi(lista):
    rezultat = []
    curenta = []

    def backtrack(start):
        rezultat.append(curenta[:])
        for i in range(start, len(lista)):
            curenta.append(lista[i])
            backtrack(i + 1)
            curenta.pop()

    backtrack(0)
    return rezultat


print(submultimi([1, 2, 3]))
print(submultimi([]))
print(len(submultimi([1, 2, 3, 4, 5])))
Începe gratuit cursul de algoritmi →
main.pyPython
ConsolăGata de pornire
Apasă „Rulează codul”. Prima dată Python se încarcă în browser în câteva secunde.

Pe tema asta, în cursul de algoritmi

Pagina îți arată metoda. În curs o aplici singur, pe probleme din ce în ce mai grele, cu verificare automată la fiecare.

Ce probleme rezolvi cu backtracking

ProblemăCe se genereazăCondiția de validareNumăr de soluții
Permutăritoate ordinile a n elementeelementul nu e deja folositn!
Aranjamenteșiruri de k elemente distincte din nnu e deja folositn! / (n-k)!
Combinărisubmulțimi de k elementestrict crescător: st[k] > st[k-1]C(n, k)
Submulțimitoate submulțimilefiecare element: îl iei sau nu2ⁿ
N regineo regină pe fiecare rândnu e pe aceeași coloană sau diagonală92 pentru n = 8

Numărul de soluții crește foarte repede, așa că backtracking-ul e potrivit pentru n mic (de obicei sub 10–20). Pentru probleme de optimizare cu n mare, se folosește programarea dinamică sau un algoritm greedy.

Backtracking la BAC

La BAC Informatică, profilul mate-info, backtracking-ul apare aproape mereu la Subiectul I sau II, sub forma: „Utilizând metoda backtracking se generează în ordine lexicografică... Care este a cincea soluție generată?” Nu trebuie să scrii cod; trebuie să înțelegi ordinea în care se generează soluțiile. Scrie primele soluții pe hârtie, ca în animație, și vei vedea regula: ultima poziție se schimbă cel mai des.

4,9 din 5 · 128 de recenzii Google

Ce spun cursanții

Toate recenziile pe Google
Video · 13 minute

Absolvenții noștri, în cuvintele lor

Cursanți care au pornit de la zero povestesc cum au învățat, ce i-a ajutat și unde au ajuns după cursuri.

Vezi pe YouTube

Profesorii si colegii foarte prietenosi,modul in care se preda simplu si usor de inteles cu exemple practice incat oricine poate prinde usor.

Fotografia lui Alex Cristian, cursant al Academiei ProgramatorilorAlex CristianRecenzie pe Google

M-am inscris la cursurile de programare online gratuite, dupa care am achizitionat cursurile de java incepatori si intermediari. Foarte bune

Fotografia lui Madalina Pitrop, cursant al Academiei ProgramatorilorMadalina PitropRecenzie pe Google

Foarte profi si utile cursurile. Practica aplicata si explicata de traineri inarmati cu rabdare si cunostine solide.

Fotografia lui Iulian Pahom, cursant al Academiei ProgramatorilorIulian PahomRecenzie pe Google

Întrebări frecvente

Ce este metoda backtracking?

Backtracking este o metodă de rezolvare care construiește soluția pas cu pas și, când un pas nu poate duce la o soluție validă, se întoarce la pasul anterior și încearcă altă variantă. Se folosește pentru a genera toate soluțiile unei probleme sau pentru a găsi una care respectă anumite condiții.

Când se folosește backtracking?

Când trebuie generate toate configurațiile care respectă niște condiții: permutări, combinări, aranjamente, submulțimi, așezarea reginelor pe tablă, sudoku, drumuri într-un labirint. E potrivit când numărul de elemente e mic, pentru că timpul crește exponențial.

Care este complexitatea backtracking-ului?

Depinde de problemă, dar de obicei e exponențială: O(n!) pentru permutări și O(2ⁿ) pentru submulțimi. Avantajul față de încercarea tuturor variantelor e că renunță devreme la cele care nu pot deveni soluții.

Care e diferența dintre backtracking și recursivitate?

Recursivitatea este o tehnică de programare (o funcție care se apelează pe ea însăși). Backtracking este o metodă de rezolvare a problemelor, care se implementează de obicei recursiv, dar se poate scrie și iterativ, cu un vector folosit ca stivă.

Ce este problema celor N regine?

Trebuie să așezi N regine pe o tablă de șah N × N astfel încât să nu se atace: oricare două să nu fie pe același rând, aceeași coloană sau aceeași diagonală. Pentru tabla de 8 × 8 există 92 de soluții. Este exemplul clasic de backtracking.

Unde exersez backtracking?

În cursul de algoritmi pentru interviuri de la Academia Programatorilor ai lecții despre submulțimi, permutări, combinări și problema celor N regine, cu probleme rezolvate în Python direct în browser. Primele 2 lecții ale cursului sunt gratuite.

Începe azi, gratuit

Primele lecții din fiecare curs sunt gratuite. Fără card, fără instalări: scrii primul cod în câteva minute.