Retrocés recursiu per a algorismes combinatoris, de cerca de camins i de solucionadors de Sudoku

Bloc

Retrocés recursiu per a algorismes combinatoris, de cerca de camins i de solucionadors de Sudoku

Aquesta lliçó es va publicar originalment a https://algodaily.com , on mantinc un curs d’entrevistes tècniques i escric idees per a desenvolupadors ambiciosos.

El seguiment enrere és senzill

Backtracking és un concepte molt important en informàtica i s’utilitza en moltes aplicacions. En general, l’utilitzem quan cal explorar totes les solucions possibles d’un problema. També s’utilitza sovint per identificar solucions que satisfan un determinat criteri també anomenat | | + _ |.

En aquest tutorial, parlaré d'aquesta tècnica i la demostraré. Aconseguirem la comprensió a través d’uns quants exemples simples que impliquen l’enumeració de totes les solucions o l’enumeració de solucions que satisfacin determinades constraint.

Imatge per publicar

Comencem pel següent pas.

Retrocés i cerca de profunditat

Imatge per publicar

En termes molt senzills, podem pensar en constraint com construir i explorar un backtracking en una primera manera de profunditat. El node arrel de l'arbre o el camí cap al node fulla representa un search tree que es pot avaluar. Així, a mesura que recorrem cada camí, anem provant una solució. Així doncs, al diagrama següent, candidate solution és una possible solució.

Si el A -> B -> D es qualifica com a solució de treball i es conserva com a alternativa. En cas contrari, la cerca continua amb profunditat. En altres paraules, un cop trobada una solució, l'algorisme candidate path (retrocedeix un pas i explora un altre camí des del punt anterior) per explorar altres branques d’arbres per trobar més solucions.

Guanys d'eficiència

Per als problemes de satisfacció de restriccions, l’arbre de cerca es poda abandonant branques de l’arbre que no conduirien a una solució potencial. Per tant, estem constantment reduir el temps de cerca i fer-lo més eficient que una cerca exhaustiva o completa. Passem ara directament a com es fa tot això a través d’exemples que podríeu veure el dia de l’entrevista.

Problema combinatori: trobar N combinacions

Com a primer problema, fem servir un problema molt simple de backtracks - podeu trobar tot el possible combinatorics combinacions d’elements d’un conjunt?

En altres paraules, es dóna un conjunt N i un {1, 2, 3, 4, 5} valor de N, estaríem buscant totes les combinacions / subconjunts de longitud / mida 3. En aquest cas, serien 3, {1, 2, 3}, etc.

Tingueu en compte que l'ordre no és important en un {1, 2, 4}. doncs combination i {1, 2, 3} es consideren el mateix.

Vegem ara el pseudocodi d’aquest {3, 2, 1} problema:

N-combination

Implementació de la solució combinatòria

Imatge per publicar

El diagrama següent mostra com funciona aquest pseudocodi per a un conjunt d'entrada routine: combos input: set output: display N combinations assumption: position of the first item is zero and result set is empty at start base case: 1. If all combinations starting with items in positions <(size-N) have been printed. Stop recursive case: Combos(set,result) 1. Repeat for each items i in the set: a. Put the item i in the result set b. if the result set has N items, display it else recursively call combos with (the input set without item i) and (the result set) c. Remove the item i from result set i {1, 2, 3, 4}.

Fixeu-vos en com es construeix l'arbre de cerca a partir de N=3 (conjunt buit), a {} a {1} a {1, 2}.

reaccionar amb la notificació nativa a l'aplicació

Quan {1, 2, 3} es troba, l'algorisme retrocedeix a {1, 2, 3} per trobar totes les combinacions que comencen per {1, 2}. Un cop acabat, el mètode retrocedeix a {1, 2} per trobar altres combinacions que comencin per {1}.

En aquest cas, no es guarda tot l'arbre de cerca , sinó que es construeix implícitament . Alguns camins, on la possibilitat de trobar més combinacions no és possible, estan abandonats . El mètode és elegant i la seva implementació C ++ es mostra aquí.

Fixeu-vos com a 1 del codi, l'exploració de combinacions s'atura aviat quan l'índex del conjunt supera un nivell determinat. Així doncs, a l’arbre superior, les solucions base case 2 i {3} no s’explorarà. Això és el que fa que l'algorisme sigui eficient.

Problema combinatori amb una restricció: trobar N combinacions amb suma

Afegim ara una restricció al nostre {4} problema de combinacions! La restricció és que tot estableix on N (sum sent un paràmetre determinat) s'hauria d'imprimir.

Tot el que hem de fer és modificar el S codi, de manera que totes les combinacions la suma de les quals excedeixi S no s’explorin més i no es generin altres combinacions d’aquest tipus. Suposant que la matriu està ordenada, es torna encara més eficient.

windows 10 debloater 2021

Hem il·lustrat el retrocés mitjançant matrius per simplificar les coses. Aquesta tècnica funcionaria molt bé per a _ _ + _ | no ordenats, on l'accés aleatori als elements no és possible.

L'arbre següent mostra els camins abandonats combosN i linked lists.

Imatge per publicar

Enumeració de camins a través d’una quadrícula quadrada

El nostre següent problema combinatori és el d’imprimir tots els camins possibles des d’un {3, 10} ubicació a {5, 8} ubicació.

Suposem que tenim una quadrícula rectangular amb un robot situat en alguna cel·la inicial. Després ha de trobar tots els camins possibles que condueixen a la cel·la objectiu. El robot només es pot moure start o al target. Per tant, el següent estat es genera fent un moviment cap amunt o bé cap a la dreta.

El retrocés torna a salvar-nos. Aquí teniu el pseudocodi que permet l’enumeració de tots els camins a través d’una quadrícula:

up

Implementació de quadrícula quadrada

Imatge per publicar

Per veure com funciona el pseudocodi anterior, he pres un exemple d'una quadrícula de 3x3 i he mostrat la meitat esquerra de l'arbre. Podeu veure que des de cada cel·la només hi ha dos moviments possibles, és a dir, cap amunt o cap a la dreta.

El node de fulla representa el right cel·la. Cada branca de l'arbre representa un camí. Si es troba l'objectiu (cas base 1), s'imprimeix el camí. En cas contrari, majúscules i minúscules routine: enumeratePaths input: Grid m*n output: Display all paths assumption: result is empty to begin with Base case 1: 1. If target is reached then print the path Base case 2: 2. If left or right cell is outside the grid then stop Recursive case: 1. Add the current cell to path 2. Invoke enumeratePaths to find all paths that are possible by doing an 'up' move 3. Invoke enumeratePaths to find all paths that are possible by doing a 'right' move 4. Remove the current cell from path es manté cert (és a dir, la cel·la es troba fora de la quadrícula), aleshores el camí s’abandona i l’algorisme retrocedeix per trobar un camí alternatiu.

Nota: només uns pocs goal/target els moviments es mostren a la figura. Tot i això, després de trobar la cel·la objectiu, el sistema torna a fer marxa enrere per trobar altres camins. Això continua fins que es busquen i enumeren tots els camins.

El codi adjunt és una implementació C ++ simple d’enumerar tots els camins a través d’un 2 quadrícula.

#recursion # data-structures #backtracking # coding-interviews #algorithms #interview

medium.com

Retrocés recursiu per a algorismes combinatoris, de cerca de camins i de solucionadors de Sudoku

Aquesta lliçó es va publicar originalment a https://algodaily.com, on mantinc un curs d’entrevistes tècniques i escric idees per a desenvolupadors ambiciosos.