Técnicas de diseño de algoritmos
Antes de aprender algoritmos concretos conviene conocer las estrategias que hay detrás de casi todos. Ante un problema nuevo, la pregunta no es «¿qué algoritmo me sé?», sino «¿cómo lo ataco?»: ¿se puede partir en trozos más pequeños del mismo tipo? ¿hay que probar combinaciones y deshacer las que no sirven? ¿basta con elegir en cada paso lo que parece mejor? ¿se repiten los mismos cálculos una y otra vez?
Cada técnica responde a una de esas preguntas. La recursividad es la herramienta; divide y vencerás, backtracking y programación dinámica son formas de usarla; los algoritmos voraces son la apuesta rápida que a veces acierta y a veces no. Saber reconocerlas es lo que permite resolver problemas que no has visto nunca.
Los algoritmos
Backtracking (vuelta atrás)
Construye la solución paso a paso, probando cada opción y deshaciendo la última decisión en cuanto un camino no lleva a ninguna parte: las N reinas, sudokus, laberintos y combinaciones.avanzado2 ejerciciosDivide y vencerás
Parte el problema en trozos más pequeños del mismo tipo, resuelve cada uno (casi siempre con recursividad) y combina los resultados: mergesort, quicksort, la potencia rápida o la búsqueda binaria.intermedio2 ejercicios
Cuál elegir
| Técnica | Cuándo encaja | Ejemplos |
|---|---|---|
| Divide y vencerás | Se parte en subproblemas independientes y las soluciones se combinan | Mergesort, quicksort, búsqueda binaria, potencia rápida |
| Backtracking (vuelta atrás) | Hay que explorar combinaciones y se puede descartar pronto las imposibles | N reinas, sudoku, laberintos, subconjuntos |
Divide y vencerás y programación dinámica parten el problema igual; la diferencia es si los subproblemas se repiten. Si se repiten, guardarlos (memoización) convierte un algoritmo exponencial en uno polinómico.