Algoritmul de backtracking

Ce este algoritmul de backtracking?

Backtracking este un algoritm care caută combinații posibile de rezolvat probleme de calcul. Acesta construiește în mod incremental candidații și îi îndepărtează pe cei care nu satisfac constrângerile date. Această tehnică este foarte utilă în situațiile în care trebuie să alegeți o soluție fezabilă dintre multiplele rezultate posibile.

Acest algoritm este considerat mai bun și mai eficient decât abordarea Brute Force. Spre deosebire de Bruteforce, care încearcă toate soluțiile posibile, Backtracking se concentrează pe găsirea unei singure soluții finale, conform date constrângeri. De asemenea, economisește timp și memorie prin anularea ultimului pas (backtrack) și încercând o altă opțiune după ce se ajunge într-un punct mort. În plus, se oprește imediat ce se găsește o soluție validă.

Backtracking este o tehnică utilizată pe scară largă deoarece poate rezolva probleme complexe fără un consum exhaustiv de resurse. Este util în special pentru problemele în care trebuie îndeplinite numeroase constrângeri, cum ar fi Sudoku, problema n Queen și programarea. Prin navigarea inteligentă prin potențiale soluții, backtracking poate găsi un răspuns care să satisfacă toate condițiile. Acest lucru îl face de neprețuit pentru sarcini care necesită atât precizie, cât și eficiență.

Cum funcționează algoritmul de backtracking?

Algoritmii de backtracking sunt o tehnică de rezolvare a problemelor care implică găsirea soluțiilor valide pas cu pas. Dacă constrângerile unui pas nu îndeplinesc anumite condiții, algoritmul revine la pasul anterior.

Se continuă apoi cu alte combinații posibile care satisfac constrângerile date. Deoarece există numeroase combinații posibile, selectează una dintre cele mai satisfăcătoare opțiuni și rezolvă problema secvenţial. Această tehnică algoritmică este utilă atunci când trebuie să rezolvați una sau mai multe opțiuni posibile. Retragerea înseamnă anularea alegerii dumneavoastră ori de câte ori apare o situație care nu oferă o soluție validă.

Algoritmul de backtracking are următorii pași în general pentru a rezolva o problemă:

Pasul 1) Inițializare: Începeți cu o soluție inițială goală/parțială.

Pasul 2) Selectare: Pe baza unor criterii și constrângeri specifice, selectați o opțiune pentru a extinde soluția curentă.

Pasul 3) Explorare: Rezolvați recursiv luând în considerare candidatul ales și avansând în procesul de rezolvare a problemelor.

Pasul 4) Verificarea constrângerii: Verificați dacă soluția parțială curentă încalcă orice constrângere la fiecare pas. Dacă se întâmplă, întoarceți-vă la pasul anterior și încercați un alt candidat.

Pasul 5) Încetarea: Procesul de backtracking se oprește atunci când fie se găsește o soluție validă, fie când toate combinațiile au fost epuizate.

Pasul 6) Backtracking: Dacă opțiunea curentă nu rezolvă problema dată, aceasta revine la starea anterioară. Apoi ia în considerare noua opțiune pentru a rezolva problema dată.

Pasul 7) Repetați: Continuați cu acești pași până când problema este rezolvată sau sunt explorate toate opțiunile.

Natura recursiva a algoritmului de backtracking

Algoritmii de backtracking sunt recursivi în natură. Aceasta înseamnă că algoritmul se autoinvocă cu diferiți parametri până când găsește o soluție sau a testat toate posibilitățile:

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

Termeni obișnuiți legați de problemele de backtracking

Aceștia sunt câțiva termeni de bază legați de tehnica Backtracking:

Vector soluție: Reprezintă soluțiile ca n-tupluri, cum ar fi (X1, X2, …, Xn).
Constrângerile: Reguli care limitează valorile X, implicite și explicite.
Spațiu de soluții: Toate valorile X valide care satisfac constrângeri explicite.
Arborele spațiului de stat: Reprezintă spațiul soluției ca arbore.
Spațiul de stat: Descrie căile într-un arbore de spațiu de stare.
Starea problemei: Nodurile din arborele de căutare reprezentând soluții parțiale.
Statele de soluție: State care formează tupluri de soluție valide în S.
Răspuns State: Satisfaceți constrângerile implicite și obțineți soluțiile dorite.
Nodul promițător: conduce la soluțiile dorite și rămâne fezabilă.
Nod nepromițător: conduce la stări imposibil de realizat, neexplorate mai departe.
Live Node: Generat cu copii neexplorați.
E-Node: Nod live cu generare continuă de copii.
Nodul Mort: Nu s-a generat o extindere suplimentară a tuturor copiilor.
Adâncimea-Primul Nod Generare: Folosește cel mai recent nod live ca următor E-nod.
Funcția de limitare: Maximizează sau minimizează B(x1, x2, …, Xa) pentru optimizare.
Copaci Statici: Formularea arborelui independent de instanța problemei.
Copaci dinamici: Formularea arborelui variază în funcție de instanța problemei.

Când să utilizați un algoritm de backtracking?

Putem alege tehnica Backtracking pentru a rezolva o problemă complexă atunci când:

Există multe opțiuni: Backtracking este potrivit dacă există multe opțiuni la fiecare pas al procesului de rezolvare a problemelor. Aceste opțiuni se pot referi la selecția elementelor și mișcărilor.
Nicio alegere clară cea mai bună: Când există informații insuficiente pentru a determina cea mai bună alegere dintre opțiunile disponibile, poate fi utilizat un algoritm de backtracking.
Decizia conduce la mai multe alegeri: Puteți alege tehnica de backtracking pentru a revizui alegerile în mod sistematic.
Trebuie să explorezi toate soluțiile posibile: Backtracking explorează sistematic toate soluțiile luând o serie de decizii construite una pe cealaltă.

Tipuri de probleme de backtracking

Există trei tipuri de probleme în algoritmii de backtracking: probleme de decizie, probleme de optimizare și probleme de enumerare. Să aflăm mai jos despre ele.

Problema de decizie: În acest tip de problemă, scopul este de a determina dacă există o soluție fezabilă. Verificăm răspunsurile „da” și „nu”. De exemplu, problema n-reginelor. Este o problemă de decizie care examinează probabilitatea de a plasa n regine pe o tablă de șah n × n fără a se ataca reciproc.
Problema de optimizare: În problemele de optimizare, scopul este de a găsi cea mai bună soluție posibilă dintre multe opțiuni. Aceasta poate implica determinarea valorilor maxime și minime ale unei anumite funcții sau variabile. De exemplu, luați în considerare problema rucsacului, în care obiectivul este de a maximiza valoarea totală a articolelor din geantă, respectând în același timp limita de greutate.
Problemă de enumerare: Obiectivul său este de a găsi toate soluțiile posibile la o anumită problemă. Enumerăm fiecare opțiune valabilă fără omisiuni. Un exemplu ar fi generarea tuturor combinațiilor posibile de litere dintr-un anumit set de caractere.

Aplicații de backtracking și exemple

Există diverse aplicații ale Backtracking. Unele dintre ele sunt explicate mai jos cu pseudocodul lor.

Sudoku Solver: Această problemă conține o subgrilă 3×3 cu numere duplicate. Tehnica de backtracking va arăta că soluția returnează false, indicând necesitatea unei plasări diferite a numărului.

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

Problema N-Regina: Abordarea backtracking determină modul de prezentare a reginelor pe o tablă de șah N × N, astfel încât niciuna dintre ele să nu se amenințe reciproc.

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

Problema sumei subsetului: este folosit pentru a găsi subsetul de numere dintr-un anumit set care se adună la o anumită sumă țintă.

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

Problema ciclului Hamiltonian: Backtracking poate fi aplicat pentru a găsi un tur închis într-un grafic care vizitează fiecare vârf exact o dată.
Problema șobolanului în labirint: Tehnica backtracking este folosită pentru a găsi calea unui șobolan de la punctul de plecare al labirintului până la ieșire.

Avantajele și dezavantajele algoritmului de backtracking

Avantajele algoritmului de backtracking

Tehnicile de backtracking sunt folosite pentru a rezolva probleme complexe. Are multe avantaje precum:

Tehnica backtracking este eficientă pentru gestionarea constrângerilor.
Această metodă este bună pentru rezolvarea problemelor de optimizare.
Tehnica funcționează pentru diferite tipuri de probleme.
Această procedură poate ajuta la revizuirea tuturor soluțiilor posibile.
Deoarece dă înapoi, economisește mai multă memorie decât tehnica Bruteforce.

Dezavantajele algoritmului de backtracking

Tehnicile de backtracking au și unele limitări, cum ar fi complexitatea timpului. Această tehnică are următoarele dezavantaje:

Nu există o soluție garantată.
Este mai lent din cauza multor combinații.
Are o complexitate mare de timp din cauza multor posibilități.
Este nepotrivit pentru constrângerile în timp real, deoarece găsirea celei mai bune soluții poate dura mult timp.
Eficiența depinde de nivelul de complexitate al problemei.

Diferența dintre backtracking și recursivitate

Recursivitate	Întoarcerea înapoi
Se autoapelează până când se ajunge la cazul de bază.	Utilizează recursiunea pentru a examina toate posibilitățile până când este găsit cel mai bun rezultat fezabil.
Abordarea de jos în sus.	Abordare de sus în jos.
Nicio valoare nu este eliminată.	Soluțiile neviabile sunt respinse.

Concluzie

Backtracking este o strategie algoritmică utilă pentru rezolvarea problemelor complexe prin explorarea sistematică a soluțiilor fezabile și backtracking atunci când este necesar. Ne putem aștepta ca tehnicile de backtracking să se îmbunătățească cu îmbunătățiri ale puterii de calcul și ale eficienței algoritmice. Aceste progrese le vor permite să abordeze probleme mai mari și mai complexe în mod eficient.

În plus, modelele de învățare automată pot ghida deciziile de backtracking pe baza modelelor învățate anterior.

Toate aceste inovații tehnologice vor revoluționa algoritmii de backtracking, făcându-i un instrument puternic și versatil pentru abordarea problemelor complicate din diferite domenii.