Otro HOWTO, code-kata, a traer vengo hoy..
XDD vengo con este post cargado de esquemas algorítmicos para programar. Estos esquemas algorítmicos son los que nos ayudan a programar las mejores soluciones. Así conseguimos llegar a las soluciones que a veces tenemos que encontrar, pero quizá no vemos en un principio cómo. Quizá el problema lo tenemos en que tarda mucho, o necesitamos demasiado espacio de almacenamiento.
La mayoría de las veces, podemos recorrer todas las posibles soluciones a lo bruto hasta encontrar la solución. Es decir, muchos problemas se pueden resolver de muchas formas, pero no todas las formas de resolver el mismo problema son la mejor forma. Sólo hay una mejor forma para cada problema. Es decir, algunas soluciones son eficaces porque simplemente encuentran la solución, pero quizás no son la forma más eficiente. Incluso podemos tener problemas, que por no resolverlos eficientemente, se convierten en imposibles de resolver.
Se trata de estos esquemas:
- Voraz.
- Divide y vencerás.
- Programación dinámica.
- Vuelta atrás.
- Ramificación y poda.
Vamos al grano hermano..
Esquema voraz
Este esquema o estrategia se utiliza para optimizar el funcionamiento cuando tenemos una única solución, y además, podemos establecer un algoritmo de selección de los elementos que forman la solución. Si estas selecciones no se vuelven a reconsiderar, entonces esta es la estrategia que debemos usar.
En estos problemas solemos tener un conjunto de elementos, que pueden formar parte de la solución o no. Por ejemplo, si estamos construyendo el camino más corto entre dos nodos de un grafo, tendremos que las aristas son las partes que podremos añadir o no a la solución. Si por ejemplo estamos eligiendo entre un conjunto de cosas, cada cosa podrá formar parte de la solución o no. Es crítico que debe de existir una función de selección y que no se vuelva a reconsiderar. Se puede usar para problemas de grafos, recorridos mínimos o máximos, el algoritmo de Dijkstra, Kruskal, Prim, mochila fraccionable..
Este esquema genérico en PHP queda así:
function Voraz($conjuntoCandidatos)
{
$solucion = array();
while (count($conjuntoCandidatos) != 0 and !esSolucion($solucion)) {
$x = seleccionarSiguiente($conjuntoCandidatos);
$conjuntoCandidatos = array_diff($conjuntoCandidatos, array($x));
if (esFactible(array_merge($solucion, array($x)))) {
$solucion = array_merge($solucion, array($x));
}
}
if (esSolucion($solucion)) {
return $solucion;
} else {
echo 'No hay solución.'.PHP_EOL;
}
}
Fíjate que aquí no tenemos recursión, es una función iterativa. Se va estudiando el problema mientras que haya candidatos pendientes de estudio. De igual forma, se repite una y otra vez el bucle principal while mientras que no hemos encontrado la solución. Fíjate también en que si hubiéramos encontrado la solución se sale del bucle.
Esquema divide y vencerás
Ésta estrategia es la que se aplica cuando tenemos un problemón que podemos dividirlo en subproblemas más pequeños. Debemos de poder divirlo en problemas más pequeños, y estos a su vez, debemos poder subdividirlos una y otra vez, tantas veces como consideremos. Así sucesivamente hasta llegar a problemas muy pequeños de fácil solución. Es decir, tendremos una recursión hasta llegar a uno o varios casos base que pararán la recursión. Finalmente volveremos a construir la solución uniendo las soluciones parciales, hasta llegar a la solución del problema inicial.
En esta estrategia, suele ser más complicado combinar las soluciones una vez que hemos llegado a los casos base, y vamos subiendo combinando todas las soluciones. Tenemos aquí problemas como por ejemplo: la multiplicación de grandes números con el algoritmo de Karatsuba, Euclides para el máximo común divisor, Mergesort o Quicksort, Torres de Hanoi, exponenciales..
Nos queda así el esquema genérico en PHP:
function divideYVenceras($problema)
{
if (esTrivial($problema)) {
return solucionTrivial($problema);
} else {
$subproblemas = descomponer($problema);
foreach ($subproblemas as $subproblema) {
$subsoluciones[] = divideYVenceras($subproblema);
}
}
return componer($subsoluciones);
}
Esquema de programación dinámica
Este esquema se debe usar cuando tenemos que hacer cálculos, que se repiten más de una vez. Es decir, si podemos almacenar los resultados parciales para luego reutilizarlos, así no tendremos que calcular varias veces lo mismo. Entonces, mejoraremos el coste de tiempo, aunque gastemos en espacio para almacenar estas soluciones.
Se suele utilizar una tabla en donde se van almacenando los valores calculados.
No existe un esquema genérico para esta estrategia, porque depende mucho de la forma en que necesitamos almacenar los datos y luego consultarlos. Es decir, el esquema de estas soluciones depende mucho del problema. Dichos problemas se suelen poder resolver mediante el esquema de divide y vencerás. Además, suelen ser recursivos, en donde hay más de una recursión por vez que se llama a la función principal. El caso más sencillo para estudiarlo es la función de Fibonacci, que en PHP queda así:
function fibonnaci($n)
{
$tabla = array();
if ($n <= 1) {
return 1;
} else {
$tabla[0] = $tabla[1] = 1;
for ($i = 2; $i <= $n; ++$i) {
$tabla[$i] = $tabla[$i - 1] + $tabla[$i - 2];
}
return $tabla[n];
}
}
Fíjate que si usáramos una función recursiva quedaría de la siguiente forma, que es menos eficiente. He marcado las recursiones abajo y los accesos a la tabla arriba para ver el paralelismo:
function fibonnaciRecursiva($n)
{
if ($n <= 1) {
return 1;
} else {
return fibonnaci($n - 1) + fibonnaci($n - 2);
}
}
El punto que deja claro que fibonnaci mejor calcularlo con programación dinámica, es que cada valor se calcula con sus dos anteriores. Si lo pensamos un poco, queda claro que cada valor se va a recalcular 2 veces si lo hacemos recursivamente. Realmente, la función recursiva tiene un coste exponencial, mientras que la dinámica es lineal. Es decir, que la forma buena de resolverlo es mediante programación dinámica. Si no utilizamos programación dinámica llegaremos tarde o temprano a valores altos que son imposibles de calcular por su coste temporal.
Esquema de vuelta atrás
Esta estrategia se utiliza cuando tenemos que recorrer todas las posibles soluciones, o más bien cuando tenemos que hacer una búsqueda exhaustiva de todas las posibles soluciones. Normalmente la solución puede darse en forma de vector, árbol, matriz.. de forma que, en cada iteración, vamos estudiando cada ramificación. Comienza como si fueramos a resolver el problema por fuerza bruta. Pero se le añaden una serie de comprobaciones o lógica para disminuir el árbol de posibilidades que recorremos.
Se puede usar para recorrer grafos, moverte por escenarios planos como tableros de ajedrez, construir palabras o hacer operaciones sobre ellas, etc.. Casi cualquier problema que implique un estudio de todas las posibles soluciones.
Aquí es esquema general en PHP:
function vueltaAtras($secuencia, $k)
{
iniciarExploracionNivel($secuencia, $k);
while (opcionesPendientes($secuencia, $k)) {
extenderConSiguienteOpcion($secuencia, $k);
if (solucionCompleta($secuencia)) {
procesarSolucion($secuencia);
} else {
if (completable($secuencia)) {
vueltaAtras($secuencia, $k + 1);
}
}
}
}
Un variante de este esquema, para que el algoritmo deje de buscar si le basta con sólo una solución:
function vueltaAtras1solucion($secuencia, $k)
{
$encontrado = false;
iniciarExploracionNivel($secuencia, $k);
while (opcionesPendientes($secuencia, $k) and !$encontrado) {
extenderConSiguienteOpcion($secuencia, $k);
if (solucionCompleta($secuencia)) {
procesarSolucion($secuencia);
$encontrado = true;
} else {
if (completable($secuencia)) {
vueltaAtras1solucion($secuencia, $k + 1);
}
}
}
}
Lo más importante de ver en este algoritmo son dos cosas: una que se trata de un algoritmo recursivo, la otra que se lleva un contador de nivel $k para ir sabiendo el nivel en curso de la solución que estamos estudiando.
Esquema de ramificación y poda
Este último esquema es una evolución del anterior. Pero se trata de obtener una de las soluciones óptimas, no se trata de encontrar todas las posibles soluciones. La diferencia con respecto al anterior, es que vamos a ir calculando unas estimaciones de las ramificaciones que podemos tomar. Si estas ramificaciones no pueden mejorar la mejor solución encontrada, se poda dicha ramificación. Por otro lado llevamos un coste mejor encontrado que iremos actualizando para refinar las ramificaciones. Así con este coste mejor no ramificaremos si no es mejorable, y lo actualizaremos si el coste peor ya lo mejora.
Está el punto crítico de poder encontrar una fución de estimación peor y otra mejor. También es importante ver que es un algoritmo iterativo, para lo cual se vale de un montículo en donde almacena las posibles soluciones para luego estudiarlas. Aquí el esquema genérico:
function ramificacionYPoda($nodoRaiz, $mejorSolucion)
{
$monticulo = new Monticulo();
$cota = estimacionPesimista($nodoRaiz);
$monticulo->insertar($nodoRaiz);
while (!esVacio($monticulo) and estimacionOptimista($monticulo->getPrimero()) <= $cota) {
$nodo = $monticulo->getCima();
foreach (hijosValidos($nodo) as $hijo) {
if (esSolucion($hijo)) {
if (coste($hijo) <= $cota) {
$cota = coste($hijo);
$mejorSolucion = $hijo;
}
} else {
if (estimacionOptimista($hijo) <= $cota) {
$monticulo->insertar($hijo);
if (estimacionPesimista($hijo) < $cota) {
$cota = estimacionPesimista($hijo);
}
}
}
}
}
}
En el montículo deberemos de tener arriba el nodo siguiente mejor. Es decir, tendremos un montículo de mínimos o máximos según lo que se estime que será mejor.
