Šioje pamokoje sužinosite, kas yra grįžimo algoritmas. Be to, rasite „backtracking“ metodo pavyzdį.
„Backtracking“ algoritmas yra problemų sprendimo algoritmas, kuris naudoja grubios jėgos metodą norimam išėjimui rasti.
Žiaurios jėgos metodas išbando visus galimus sprendimus ir pasirenka norimus / geriausius sprendimus.
Terminas „grįžimas atgal“ rodo, kad jei dabartinis sprendimas nėra tinkamas, grįžkite atgal ir išbandykite kitus sprendimus. Taigi šiame procese naudojamas rekursija.
Šis metodas naudojamas sprendžiant problemas, kurios turi kelis sprendimus. Jei norite optimalaus sprendimo, turite pasirinkti dinamišką programavimą.
Valstybės kosmoso medis
Erdvės būsenos medis yra medis, vaizduojantis visas galimas problemos būsenas (sprendimą ar neprisprendimą) nuo šaknies kaip pradinės būsenos iki lapo kaip galinės būsenos.
Valstybės kosmoso medis
Atsekimo algoritmas
„Backtrack“ (x), jei „x“ nėra sprendimas, grąžinkite „false“, jei „x“ yra naujas sprendimas, įtraukite į „backtrack“ (išplėskite x) sprendimų sąrašą
Atgalinio kelio metodo pavyzdys
Problema: norite rasti visus galimus 2 berniukų ir 1 mergaitės išdėstymo būdus ant 3 suolų. Apribojimas: mergina neturi būti ant vidurinio suolo.
Sprendimas: Iš viso yra 3! = 6 galimybės. Išbandysime visas galimybes ir gausime galimus sprendimus. Rekursyviai išbandome visas galimybes.
Visos galimybės yra:
Visos galimybės
Šis būsenos erdvės medis rodo galimus sprendimus.
Valstybės medis su visais sprendimais
Algoritmo taikymas atgal
- Norėdami rasti visus Hamiltono kelius, esančius diagramoje.
- Norėdami išspręsti „N Queen“ problemą.
- Labirinto sprendimo problema.
- Riterio turo problema.
