În acest tutorial, veți afla ce este un algoritm de backtracking. De asemenea, veți găsi un exemplu de abordare backtracking.
Un algoritm de backtracking este un algoritm de rezolvare a problemelor care utilizează o abordare cu forță brută pentru a găsi ieșirea dorită.
Abordarea forței brute încearcă toate soluțiile posibile și alege soluțiile dorite / cele mai bune.
Termenul de retrogradare sugerează că, în cazul în care soluția actuală nu este potrivită, atunci retrogradați și încercați alte soluții. Astfel, recursivitatea este utilizată în această abordare.
Această abordare este utilizată pentru a rezolva probleme care au soluții multiple. Dacă doriți o soluție optimă, trebuie să mergeți la programarea dinamică.
Arborele spațial de stat
Un arbore de stare spațială este un arbore care reprezintă toate stările posibile (soluție sau nerezolvare) ale problemei de la rădăcină ca stare inițială până la frunză ca stare terminală.
Arborele spațial de stat
Algoritm de urmărire înapoi
Backtrack (x) dacă x nu este o soluție returnează false dacă x este o soluție nouă adăugați la lista de soluții backtrack (extindeți x)
Exemplu de abordare a urmăririi înapoi
Problemă: doriți să găsiți toate modalitățile posibile de a aranja 2 băieți și 1 fată pe 3 bănci. Constrângere: Fata nu trebuie să fie pe banca de mijloc.
Soluție: sunt în total 3! = 6 posibilități. Vom încerca toate posibilitățile și vom obține soluțiile posibile. Încercăm recursiv toate posibilitățile.
Toate posibilitățile sunt:
Toate posibilitățile
Următorul arbore spațial de stare prezintă soluțiile posibile.
Arborele de stat cu toate soluțiile
Aplicații de algoritm de urmărire înapoi
- Pentru a găsi toate căile hamiltoniene prezente într-un grafic.
- Pentru a rezolva problema N Queen.
- Labirint rezolvarea problemei.
- Problema turneului Cavalerului.
