Šajā apmācībā jūs uzzināsiet, kas ir backtracking algoritms. Jūs atradīsit arī atkāpšanās pieejas piemēru.
Atpakaļejošais algoritms ir problēmu risināšanas algoritms, kas izmanto brutālu spēku pieeju vēlamās izejas atrašanai.
Brutālu spēku pieeja izmēģina visus iespējamos risinājumus un izvēlas vēlamos / labākos risinājumus.
Termins backtracking liek domāt, ka, ja pašreizējais risinājums nav piemērots, tad atgriezieties un izmēģiniet citus risinājumus. Tādējādi šajā pieejā tiek izmantota rekursija.
Šo pieeju izmanto, lai atrisinātu problēmas, kurām ir vairāki risinājumi. Ja vēlaties optimālu risinājumu, jums jādodas uz dinamisku programmēšanu.
Valsts kosmosa koks
Kosmosa stāvokļa koks ir koks, kas apzīmē visus iespējamos problēmas stāvokļus (risinājumu vai neatrisinājumu) no saknes kā sākuma stāvokļa līdz lapai kā gala stāvoklim.
Valsts kosmosa koks
Atpakaļceļošanas algoritms
Backtrack (x), ja x nav risinājums, atdodiet false, ja x ir jauns risinājums, pievienojiet risinājumu sarakstam backtrack (izvērsiet x)
Atpakaļceļošanas pieejas piemērs
Problēma: Jūs vēlaties atrast visus iespējamos veidus, kā sakārtot 2 zēnus un 1 meiteni uz 3 soliem. Ierobežojums: meitenei nevajadzētu atrasties uz vidējā soliņa.
Risinājums: Kopā ir 3! = 6 iespējas. Mēs izmēģināsim visas iespējas un iegūsim iespējamos risinājumus. Mēs rekursīvi izmēģinām visas iespējas.
Visas iespējas ir:
Visas iespējas
Nākamais stāvokļa telpas koks parāda iespējamos risinājumus.
Valsts koks ar visiem risinājumiem
Algoritma lietojumprogrammu atkāpšanās
- Lai diagrammā atrastu visus Hamiltona ceļus.
- Lai atrisinātu N Queen problēmu.
- Labirints risināšanas problēma.
- Bruņinieka tūres problēma.
