U ovom ćete tutorijalu naučiti što je algoritam povratnog praćenja. Također ćete pronaći primjer povratka unatrag.
Algoritam povratnog praćenja algoritam je za rješavanje problema koji koristi grubu silu za pronalaženje željenog rezultata.
Pristup grube sile iskušava sva moguća rješenja i bira željena / najbolja rješenja.
Izraz vraćanje unatrag sugerira da, ako trenutno rješenje nije prikladno, vratite se i isprobajte druga rješenja. Stoga se u ovom pristupu koristi rekurzija.
Ovaj se pristup koristi za rješavanje problema koji imaju više rješenja. Ako želite optimalno rješenje, morate se odlučiti za dinamičko programiranje.
Državno svemirsko stablo
Stablo svemirskog stanja je stablo koje predstavlja sva moguća stanja (rješenje ili nerazrješenje) problema od korijena kao početnog stanja do lista kao završnog stanja.
Stablo svemira države
Algoritam vraćanja unatrag
Povratak (x) ako x nije rješenje, vrati false ako je x novo rješenje, dodaj na popis rješenja backtrack (proširi x)
Primjer pristupa povratu unatrag
Problem: Želite pronaći sve moguće načine kako rasporediti 2 dječaka i 1 djevojčicu u 3 klupe. Ograničenje: Djevojka ne bi trebala biti na srednjoj klupi.
Rješenje: Ukupno ih ima 3! = 6 mogućnosti. Isprobat ćemo sve mogućnosti i dobiti moguća rješenja. Rekurzivno isprobavamo sve mogućnosti.
Sve mogućnosti su:
Sve mogućnosti
Sljedeće stablo prostora stanja prikazuje moguća rješenja.
Stablo država sa svim rješenjima
Primjene algoritma za povratak
- Da biste pronašli sve Hamiltonove staze prisutne u grafikonu.
- Da bih riješio problem N Queen.
- Rješavanje problema s labirintom.
- Problem viteške turneje.
