logo

TechCodeview

Algoritmul de backtracking

Algoritmi de backtracking sunt ca strategiile de rezolvare a problemelor care ajută la explorarea diferitelor opțiuni pentru a găsi cea mai bună soluție. Ei lucrează încercând căi diferite și, dacă una nu funcționează, dau înapoi și încearcă alta până o găsesc pe cea potrivită. Este ca și cum ai rezolva un puzzle testând diferite piese până când se potrivesc perfect.

Întoarcerea înapoi

Cuprins



Ce este algoritmul de backtracking?

Întoarcerea înapoi este o tehnică algoritmică de rezolvare a problemelor care implică găsirea unei soluții în mod incremental prin încercare opțiuni diferite și desfacerea ei dacă duc la a capat de drum .

Este folosit în mod obișnuit în situațiile în care trebuie să explorați mai multe posibilități pentru a rezolva o problemă, cum ar fi căutarea unei căi într-un labirint sau rezolvarea de puzzle-uri precum Sudoku . Când se ajunge la o fundătură, algoritmul se întoarce la punctul de decizie anterior și explorează o cale diferită până când se găsește o soluție sau se epuizează toate posibilitățile.

Cum funcționează un algoritm de backtracking?

A algoritm de backtracking functioneaza prin explorarea recursiva a tuturor solutiilor posibile la o problema. Începe prin a alege o soluție inițială, apoi explorează toate extensiile posibile ale acelei soluții. Dacă o extensie duce la o soluție, algoritmul returnează soluția respectivă. Dacă o extensie nu duce la o soluție, algoritmul se întoarce la soluția anterioară și încearcă o altă extensie.

Următoarea este o schiță generală a modului în care funcționează un algoritm de backtracking:

  1. Alegeți o soluție inițială.
  2. Explorați toate extensiile posibile ale soluției actuale.
  3. Dacă o extensie duce la o soluție, returnați soluția respectivă.
  4. Dacă o extensie nu duce la o soluție, întoarceți-vă la soluția anterioară și încercați o altă extensie.
  5. Repetați pașii 2-4 până când au fost explorate toate soluțiile posibile.

Exemplu de algoritm de backtracking

Exemplu: Găsind calea cea mai scurtă printr-un labirint

Intrare: Un labirint reprezentat ca o matrice 2D, unde 0 reprezintă un spaţiu deschis şi 1 reprezintă un zid.

Algoritm:

  1. Începeți de la punctul de plecare.
  2. Pentru fiecare dintre cele patru direcții posibile (sus, jos, stânga, dreapta), încercați să vă deplasați în acea direcție.
  3. Dacă deplasarea în acea direcție duce la punctul final, întoarceți calea urmată.
  4. Dacă deplasarea în acea direcție nu duce la punctul final, întoarceți-vă înapoi la poziția anterioară și încercați o altă direcție.
  5. Repetați pașii 2-4 până când se ajunge la punctul final sau au fost explorate toate căile posibile.

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

Algoritmii de backtracking sunt cel mai bine folosiți pentru a rezolva probleme care au următoarele caracteristici:

  • Există mai multe soluții posibile la problemă.
  • Problema poate fi împărțită în subprobleme mai mici.
  • Subproblemele pot fi rezolvate independent.

Aplicații ale algoritmului de backtracking

Algoritmii de backtracking sunt utilizați într-o mare varietate de aplicații, inclusiv:

  • Rezolvarea puzzle-urilor (de exemplu, Sudoku, cuvinte încrucișate)
  • Găsind calea cea mai scurtă printr-un labirint
  • Probleme de programare
  • Probleme de alocare a resurselor
  • Probleme de optimizare a rețelei

Elementele de bază ale algoritmului de backtracking:

  • Diferența dintre tehnica Backtracking și Branch-N-Bound
  • Care este diferența dintre Backtracking și Recursion?

Probleme standard la algoritmul de backtracking:

  • Problema turneului Cavalerului
  • Șobolan într-un labirint
  • Problema N Queen | Backtracking-3
  • Problemă cu suma subsetului
  • m Problemă de colorare
  • Ciclul Hamiltonian
  • Sudoku | Backtracking-7
  • Puzzle cu magnet
  • Eliminați parantezele nevalide
  • O abordare de backtracking pentru a genera coduri gri de n biți
  • Scrieți un program pentru a imprima toate permutările unui șir dat

Probleme ușoare la algoritmul de backtracking:

  • Backtracking pentru a găsi toate subseturile
  • Verificați dacă un șir dat este șir-sumă
  • Numărați toate căile posibile între două vârfuri
  • Găsiți toate submulțimile distincte ale unei mulțimi date
  • Aflați dacă există o cale de mai mult de k lungime de la o sursă
  • Imprimați toate căile de la o anumită sursă la o destinație
  • Imprimați toate șirurile posibile care pot fi realizate prin plasarea de spații

Probleme medii la algoritmul de backtracking:

  • remorcheră
  • problema cu 8 regine
  • Sumă combinațională
  • Algoritmul lui Warnsdorff pentru problema turului lui Knight
  • Găsiți căi de la celula de colț la celula din mijloc în labirint
  • Găsiți numărul maxim posibil făcând cel mult K swap
  • Șobolan într-un labirint cu mai mulți pași sau sărituri permise
  • N regină în spațiul O(n).

Probleme grele la algoritmul de backtracking:

  • Set de putere în ordine lexicografică
  • Problemă de întrerupere a cuvintelor folosind Backtracking
  • Împărțirea unei mulțimi în K submulțimi cu sumă egală
  • Cel mai lung traseu posibil într-o matrice cu obstacole
  • Găsiți cea mai scurtă rută sigură pe o potecă cu mine antitermale
  • Tipăriți toate partițiile palindromice ale unui șir
  • Tipărirea tuturor soluțiilor în N-Queen Problem
  • Tipăriți toate cele mai lungi subsecvențe comune în ordine lexicografică

Link-uri rapide:

  • Aflați structura datelor și algoritmi | Tutorial DSA
  • Top 20 de întrebări de interviu cu algoritmul de backtracking
  • „Videoclipuri” pe Backtracking