Estrategias para resolver problemas de programación

En este episodio de Code Time continuamos con el camino de la programación explicando estrategias para resolver problemas. Gracias a estas técnicas es posible ir de un problema a una de las posibles soluciones.

Un poco de léxico

En la literatura de ciencias de la computación suele ser común encontrar términos como:

• Greedy.
• Dinámica.
• Divide and conquer.
• Backtracking.

Estos términos hacen referencia a maneras de resolver problemas. De esta manera forman un léxico, una jerga, que permite explicar la forma de resolución de un problema sin ahondar en detalles.
Listen to “Code Time (62): Estrategias para resolver problemas” on Spreaker.
Conocer el léxico nos ayuda a entender a los demás cuando utilizan estos términos. Pero además, nos ayuda para que nosotros pensemos también en estos términos. Al asignar una palabra a una idea o concepto, nos resulta más fácil pensar en términos de estos.

Problemas de optimización

Un problema de optimización apunta a encontrar la mejor solución de un conjunto de soluciones posibles. En muchos casos se trata de encontrar el máximo o el mínimo de una función, sujetos a un conjunto de restricciones posibles.

Geedy

Un algoritmo greedy busca el óptimo global mediante la búsqueda de óptimos locales en varias etapas. Suelen utilizarse para la resolución de problemas de optimización.

En cada etapa:

1. Computamos el óptimo local, sin importarnos el futuro (carpe diem).
2. Agregamos el óptimo local a nuestra solución final.
3. Preparamos el problema para la siguiente etapa.

Un ejemplo simple es un algoritmo  de cajero automático que entrega la menor cantidad de billetes posible con lo que tiene. Haremos una pequeña traza de un posible programa greedy que resuelve este problema. Antes que nada aclararemos que asumimos una existencia ilimitada de billetes de 500, 100, 50, 20, 10, 5 y 2 pesos.

Si queremos obtener $762 encontraremos el óptimo local, es decir el billete más grande que nos ayude a resolver el problema. En nuestro caso sería uno de 500. En el siguiente paso y no nos tenemos que preocupar por la cifra original sino que por entregar $262. Como podemos ver usar billetes de 500 no es opción así que no los utilizaremos más. En cambio podemos entregar uno de 100 así nos quedan $152. Repetimos el paso anterior usando otro de 100 y vemos que no podemos seguir usando este billete por lo que lo descartamos de entre las opciones. A esta altura debemos resolver el problema de los $62. Si seguimos con este algoritmo debemos entregar un billete de 50 y uno de 2.

De esta manera podemos ver que es bastante sencillo trabajar. Cabe destacar también que no siempre los algoritmos greedy son óptimos. Esto se debe a que resuelven los problemas pero no siempre con la mejor solución. Cuando veamos dinámica explicaremos un caso.

Divide et Impera

Un algoritmo divide et impera (también conocido como divide and conquer o divide y vencerás) busca la resolución de un problema dividiéndolo en sub-problemas del mismo tipo, solucionando cada uno, y luego combinándolos para obtener una solución al problema original.

El funcionamiento suele ser: si el problema es sencillo de resolver (pequeño), lo resolvemos de manera directa. En caso contrario:

1. Dividimos el problema en subproblemas del mismo tipo.
2. Resolvemos recursivamente cada uno.
3. Combinamos las resoluciones para obtener una solución.

El mejor ejemplo de esta estrategia es el algoritmo de ordenamiento mergesort:

1. Si al arreglo tiene un solo elemento, ya está ordenado, y solucionamos el problema.
2. En caso contrario:
   1. Dividimos el arreglo en dos mitades.
   2. Ordenamos recursivamente cada mitad.
   3. Combinamos las mitades ordenadas.

Dinámica

Un algoritmo dinámico busca la resolución la resolución mediante la combinación de sub-problemas del mismo tipo. A diferencia de divide et impera, pediremos que los sub-problemas se solapen. Esto quiere decir que el problema lo dividimos en sub-problemas que son reutilizados varias veces, o que estos sub-problemas comparten sub-sub-problemas.

Tipos de resoluciones con dinámica

Top – down

El funcionamiento suele ser: si el problema es sencillo de resolver (pequeño), lo resolvemos de manera directa, y memorizamos la solución. En caso contrario:

1. Dividimos el problema en subproblemas del mismo tipo.
2. Resolvemos recursivamente cada uno.
3. Combinamos las sub-soluciones para obtener una solución.
4. Memorizamos la solución.

    De tener que resolver un caso ya resuelto, buscamos la solución memorizada.

Bottom – up

Existe otra manera de funcionamiento para estos algoritmos:

• Resolvemos los problemas pequeños.
• Resolvemos los problemas que se solucionan combinando solo los problemas pequeños.
• Resolvemos los problemas que se solucionan combinando los problemas ya resueltos.
• …

Un ejemplo típico es Fibonacci, donde al resolver fib(50) recursivamente, se termina computando muchísimas veces fib(3) por ej.

Recordemos que Fibonacci se comporta de la siguiente manera

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (si n > que 1)

Así pues F(5) = F(4) + F(3) = F(3) + F(2) + F(3) =  F(2) + F(1) + F(2) + F(2) + F(1) = F(1) + F(1) + F(1) + F(1) + F(1) + F(1) + F(1) + F(1) + F(1) …

Podemos notar que al calcular F (5) es necesario recomputar muchas veces cosas que ya tendríamos que saber. Si utilizamos el algoritmo recursivo llegaremos al resultado pero el tiempo que puede tomar el cálculo dependiendo el valor será considerable. Utilizando dinámica esto se hace mucho más óptimo.

Otro ejemplo clásico es el cálculo del número combinatorio de n y k. Este también se puede resolver con recursión pero el problema es que habrá que calcular n! Y este muchas veces puede hacer overflow.

Backtracking

Un algoritmo de backtracking busca una solución avanzando por pasos, y retrocede parcialmente en caso de que notar que las elecciones realizadas no llegan a una solución:

1. Si el nodo en el que estamos constituye una solución, entonces terminamos con soluci ́on.
2. Si se puede avanzar en alguna direcci ́o
   1. Avanzamos en alguna de estas direcciones
   2. Si recursivamente se termina con solución, entonces
   3. terminamos con solución.
   4. Si no, continuamos con otra dirección posible.
3. Si agotamos las direcciones, terminamos con fallo.

Entre los problemas que podemos resolver tenemos el de las ocho reinas.. Este consiste en posicionar ocho reinas en un tablero de ajedrez, de manera que ninguna reina ataque a la otra. Otro ejemplo podría ser resolver un sudoku, laberintos, etc.

¿Qué no puede optimizar greedy?

Existen muchos problemas que requieren una solución óptima y greedy no puede garantizar eso. Tenemos por ejemplo el problema del viajante (una de las tantas variantes). En este una persona quiere atravesar el país minimizando el costo del viaje. Cada estación cobra un cierto monto por llevar a otras estaciones que no necesariamente están relacionados con la distancia.

El algoritmo greedy calculará el viaje recorriendo las estacione que a priori están más baratas pero esto puede desembocar en una en donde todos los precios superen en mucho a las demás siendo así contraproducente.

Un algoritmo que usa dinámica, por su parte, resolverá todos los viajes y encontrará el más económico. Para hacer este cálculo, eso sí, se tendrá que conservar cierta información en memoria durante la ejecución, muchas veces una tabla. De esta manera el procesamiento puede ser más lento y ocupa bastante memoria pero será óptimo, que es lo que queríamos en un principio.

Para finalizar…

BandaGeek no almacena ni distribuye el software aquí expuesto y la responsabilidad de su uso recae en el usuario.

   Gmail

Spreaker    iTunes    Ivoox    Canal de Telegram    Soundcloud