V tej vadnici boste izvedeli, kaj je algoritem za povratno sledenje. Prav tako boste našli primer pristopa za povratno sledenje.
Algoritem povratnega sledenja je algoritem za reševanje težav, ki za iskanje želenega rezultata uporablja pristop surove sile .
Pristop Brute Force preizkuša vse možne rešitve in izbere želene / najboljše rešitve.
Izraz povratno sledenje nakazuje, da če trenutna rešitev ni primerna, se vrnite in poskusite z drugimi rešitvami. Tako se pri tem pristopu uporablja rekurzija.
Ta pristop se uporablja za reševanje problemov, ki imajo več rešitev. Če želite optimalno rešitev, se morate odločiti za dinamično programiranje.
Državno vesoljsko drevo
Drevo vesoljskega stanja je drevo, ki predstavlja vsa možna stanja (rešitev ali nerešitev) problema od korena kot začetnega stanja do lista kot končnega stanja.
Državno vesoljsko drevo
Algoritem za nazaj
Backtrack (x), če x ni rešitev, vrni false, če je x nova rešitev, dodaj na seznam backtrack rešitev (razširi x)
Primer pristopa za povratno sledenje
Težava: Poiskati želite vse možne načine razporeditve 2 fantov in 1 punčke na 3 klopi. Omejitev: Dekle ne sme biti na srednji klopi.
Rešitev: Skupaj jih je 3! = 6 možnosti. Preizkusili bomo vse možnosti in dobili možne rešitve. Rekurzivno preizkusimo vse možnosti.
Vse možnosti so:
Vse možnosti
Naslednje drevo vesolja stanja prikazuje možne rešitve.
Državno drevo z vsemi rešitvami
Aplikacije za algoritem za nazaj
- Če želite poiskati vse Hamiltonove poti v grafu.
- Za rešitev problema N Queen.
- Reševanje problema z labirintom.
- Problem viteške turneje.
