Algoritmes de retrocés són com estratègies de resolució de problemes que ajuden a explorar diferents opcions per trobar la millor solució. Treballen provant diferents camins i si un no funciona, fan marxa enrere i intenten un altre fins a trobar el correcte. És com resoldre un trencaclosques provant diferents peces fins que encaixin perfectament.
Fes marxa enrere
hashmap en java
Taula de contingut
- Què és l'algoritme de retrocés?
- Com funciona un algorisme de retrocés?
- Exemple d'algoritme de retrocés
- Quan utilitzar un algorisme de retrocés?
- Aplicacions de l'algoritme de retrocés
- Bàsic de l'algoritme de retrocés
- Problemes estàndard en l'algoritme de retrocés
- Problemes fàcils en l'algoritme de retrocés
- Problemes mitjans en l'algoritme de retrocés
- Problemes difícils en l'algoritme de retrocés
Què és l'algoritme de retrocés?
Fes marxa enrere és una tècnica algorítmica de resolució de problemes que consisteix a trobar una solució de manera incremental provant diferents opcions i desfer ells si porten a a carreró sense sortida .
S'utilitza habitualment en situacions en què necessiteu explorar múltiples possibilitats per resoldre un problema, com ara buscar un camí en un laberint o resoldre trencaclosques com ara Sudoku . Quan s'arriba a un carreró sense sortida, l'algoritme torna enrere al punt de decisió anterior i explora un camí diferent fins que es troba una solució o s'han esgotat totes les possibilitats.
control del programa emmagatzemat
Com funciona un algorisme de retrocés?
A algorisme de retrocés funciona explorant de manera recursiva totes les solucions possibles a un problema. Comença escollint una solució inicial i després explora totes les possibles extensions d'aquesta solució. Si una extensió condueix a una solució, l'algorisme retorna aquesta solució. Si una extensió no condueix a una solució, l'algoritme torna a la solució anterior i prova una extensió diferent.
El següent és un esquema general de com funciona un algorisme de retrocés:
- Trieu una solució inicial.
- Exploreu totes les extensions possibles de la solució actual.
- Si una extensió condueix a una solució, retorneu aquesta solució.
- Si una extensió no condueix a una solució, torneu a la solució anterior i proveu una extensió diferent.
- Repetiu els passos 2-4 fins que s'hagin explorat totes les solucions possibles.
Exemple d'algoritme de retrocés
Exemple: Trobar el camí més curt a través d'un laberint
Entrada: Un laberint representat com una matriu 2D, on 0 representa un espai obert i 1 representa una paret.
Algorisme:
- Comenceu pel punt de partida.
- Per a cadascuna de les quatre direccions possibles (amunt, avall, esquerra, dreta), proveu de moure's en aquesta direcció.
- Si moure's en aquesta direcció condueix al punt final, torneu pel camí seguit.
- Si moure's en aquesta direcció no condueix al punt final, retrocedeix a la posició anterior i prova una altra direcció.
- Repetiu els passos 2-4 fins que s'arribi al punt final o s'hagin explorat tots els camins possibles.
Quan utilitzar un algorisme de retrocés?
Els algorismes de retrocés s'utilitzen millor per resoldre problemes que tenen les característiques següents:
- Hi ha múltiples solucions possibles al problema.
- El problema es pot dividir en subproblemes més petits.
- Els subproblemes es poden resoldre de manera independent.
Aplicacions de l'algoritme de retrocés
Els algorismes de retrocés s'utilitzen en una gran varietat d'aplicacions, com ara:
java analitza la cadena a int
- Resolució de trencaclosques (per exemple, sudoku, mots encreuats)
- Trobar el camí més curt a través d'un laberint
- Problemes de programació
- Problemes d'assignació de recursos
- Problemes d'optimització de la xarxa
Bàsic de l'algoritme de retrocés:
- Diferència entre la tècnica de Backtracking i Branch-N-Bound
- Quina diferència hi ha entre Backtracking i Recursion?
Problemes estàndard en l'algoritme de retrocés:
- El problema de la gira del cavaller
- Rata en un laberint
- N Queen problema | Retrocés-3
- Problema de la suma del subconjunt
- m Problema per pintar
- Cicle Hamiltonià
- Sudoku | Retrocés-7
- Trencaclosques magnètics
- Elimina els parèntesis no vàlids
- Un enfocament de retrocés per generar codis gris de n bits
- Escriu un programa per imprimir totes les permutacions d'una cadena determinada
Problemes fàcils amb l'algoritme de retrocés:
- Tornar enrere per trobar tots els subconjunts
- Comproveu si una cadena donada és suma-cadena
- Compta tots els camins possibles entre dos vèrtexs
- Troba tots els subconjunts diferents d'un conjunt donat
- Busca si hi ha un camí de més de k de longitud des d'una font
- Imprimeix tots els camins des d'una font determinada fins a una destinació
- Imprimeix totes les cadenes possibles que es poden fer col·locant espais
Problemes mitjans amb l'algoritme de retrocés:
- Estira i estira
- 8 problema de la reina
- Suma combinacional
- Algorisme de Warnsdorff per al problema de la gira de Knight
- Trobeu camins des de la cel·la de la cantonada a la cel·la del mig al laberint
- Trobeu el nombre màxim possible fent com a màxim K intercanvis
- Rata en un laberint amb múltiples passos o salts permesos
- N Reina a l'espai O(n).
Problemes difícils amb l'algoritme de retrocés:
- Power Set en ordre lexicogràfic
- Problema de trencament de paraules utilitzant el seguiment enrere
- Partició d'un conjunt en K subconjunts amb la mateixa suma
- La ruta més llarga possible en una matriu amb tanques
- Trobeu la ruta segura més curta en un camí amb mines terrestres
- Imprimeix totes les particions palindròmiques d'una cadena
- Impressió de totes les solucions a N-Queen Problem
- Imprimeix totes les subseqüències habituals més llargues en ordre lexicogràfic
Links ràpids :
- Apreneu l'estructura de dades i els algorismes | Tutorial DSA
- Les 20 principals preguntes d'entrevista sobre l'algoritme de retrocés
- 'Vídeos' en marxa enrere