Selles õpetuses saate teada, mis on tagasitee algoritm. Samuti leiate näite tagasiteele lähenemisest.
Tagasiotsingu algoritm on probleemide lahendamise algoritm, mis kasutab soovitud väljundi leidmiseks toore jõu lähenemist .
Brute force lähenemine proovib läbi kõik võimalikud lahendused ja valib soovitud / parimad lahendused.
Mõiste tagasitee viitab sellele, et kui praegune lahendus ei sobi, siis pöörduge tagasi ja proovige muid lahendusi. Seega kasutatakse selles lähenemises rekursiooni.
Seda lähenemist kasutatakse probleemide lahendamiseks, millel on mitu lahendust. Kui soovite optimaalset lahendust, peate kasutama dünaamilist programmeerimist.
Riigiruumi puu
Kosmoseseisundipuu on puu, mis tähistab probleemi kõiki võimalikke olekuid (lahendust või lahendamatust) alates juurest kui algseisundist kuni leheni kui terminali olek.
Riigiruumi puu
Tagasiotsingu algoritm
Tagasirada (x), kui x ei ole lahendus, tagastab vale, kui x on uus lahendus, lisage lahenduste loend tagasi (laienda x)
Tagasijõudmise lähenemise näide
Probleem: soovite leida kõik võimalikud viisid, kuidas korraldada 2 poissi ja 1 tüdruk kolmele pingile. Piirang: Tüdruk ei tohiks olla keskmisel pingil.
Lahendus: neid on kokku 3! = 6 võimalust. Proovime kõiki võimalusi ja saame võimalikud lahendused. Proovime rekursiivselt kõiki võimalusi.
Kõik võimalused on:
Kõik võimalused
Järgmine olekuruum näitab võimalikke lahendusi.
Riigipuu koos kõigi lahendustega
Algoritmirakenduste tagasirakimine
- Kõigi graafikus olevate Hamiltoni radade leidmiseks.
- N Queeni probleemi lahendamiseks.
- Labürindi lahendamise probleem.
- Rüütli tuuri probleem.
