Un sitio personal para aprender desarrollo web

Programación dinámica: camino mínimo entre los nodos 1 y 3

Este problema trata de descubrir los caminos mínimos de todas las parejas de nodos de un un grafo con n nodos. En la imagen puede ver el camino mínimo entre el nodo 1 y el 3. Entre los tres caminos posibles tenemos 1→3 con valor 20, 1→4→3 con valor 13+2=15 y, finalmente, 1→2→4→3 con valor 3+8+2=13, siendo este último el de menor valor.

Vimos algo parecido en el tema del algoritmo de Dijkstra para descubrir el camino mínimo desde un nodo seleccionado, que denominábamos como nodo raíz, al resto de nodos. Podríamos modificar aquel algoritmo para iterar por un bucle de tal forma que en cada iteración designáramos como nodo seleccionado a cada uno de ellos. Aquel era un algoritmo voraz, pero usando programación dinámica podemos utilizar el algoritmo de Floyd que encuentra esos caminos de una forma más simple.

Mochila discreta 0-1

La forma en que podemos seleccionar n objetos con peso pi y valor vi para cargarlos en una mochila con un peso máximo P de tal forma que obtengamos el valor máximo V puede dar lugar a tres tipos de problemas. Uno es la Mochila fraccionable que maximice V donde los objetos no pueden repetirse y pueden fraccionarse para completar el peso máximo P. Se resuelve con un algoritmo voraz. Otro es la Mochila discreta 0-∞ que maximice V donde los objetos SI pueden repetirse y NO pueden fraccionarse para completar un peso que no supere el máximo P. Se resuelve con un algoritmo vuelta atrás. Por último la Mochila discreta 0-1 que maximice V donde los objetos NO pueden repetirse y NO pueden fraccionarse para completar un peso que no supere el máximo P. Se resuelve con programación dinámica, lo que nos ocupará este tema.

Tabla resultados intermedios en programación dinámica

Dividir un problema en subproblemas más sencillos para poder resolverlos y luego combinar sus soluciones para obtener la solución general, es una técnica que usamos para resolver problemas, como por ejemplo en los recursivos. Pero a veces los subproblemas se solapan o se calcula lo mismo en varios subproblemas, restando eficiencia a la ejecución de la solución final. Otras veces los algoritmos de optimización como los voraces no logran el resultado final óptimo para algunos conjuntos de datos.

La programación dinámica intenta resolver esta falta de eficiencia o eficacia planteándose como una técnica para evitar calcular lo mismo varias veces, siempre de una forma óptima. Usa una tabla de resultados intermedios mientras resolvemos los subproblemas, resultados óptimos que luego se utilizarán posteriormente para alcanzar la solución óptima final.

Editor grafos SVG: Modo matriz de adyacencia

He realizado una mejora en los módulos del Editor de Grafos SVG para que permita introducir la definición de un grafo con una matriz de adyacencia. Se trata de un array de dimensión n×n para un grafo de n nodos. La imagen muestra como introducimos una de 5 × 5 que define un grafo G con 5 nodos.

Cuando G[i][j]=null entonces es que no hay arista en la dirección de los nodos i → j. Si es distinto de nulo ese será el valor de la arista. Por ejemplo, G[0][4]=14 significa que hay una arista con valor 14 en la dirección 0→4. Por otro lado la posición G[4][0]=null nos dice que esa arista sólo va en esa dirección 0→4 y no en la contraria 4→0. Así se configuraría como un grafo dirigido.

Dijkstra: Caminos mínimos

En el problema de los caminos mínimos tenemos un grafo dirigido donde hay un nodo raíz y cada arista tiene una longitud, pudiendo recorrerse el camino desde el nodo raíz a cualquier nodo del grafo. Ese recorrido se hará siguiendo la dirección de las aristas. Se trata de obtener esos caminos a cada nodo cuya longitud es mínima. El algoritmo de Dijkstra es un algoritmo voraz que resuelve el problema de los caminos mínimos.

Árbol de recubrimiento mínimo

Un problema donde aplicar el algoritmo voraz es el de obtener el árbol de recubrimiento mínimo en un grafo conexo no dirigido, como el de la imagen. Ese árbol es un subgrafo que conecta todos los nodos siguiendo un camino cuyo coste de la suma del valor de las aristas es mínimo. En la imagen se representa con las aristas en color rojo.

En este tema veremos los algoritimos de Kruskal y Prim para su resolución. El de Kruskal utiliza una estructura de partición o de conjuntos disjuntos que ya vimos en el tema anterior.

Planificaciones

Planificaciones

Los algoritmos voraces sirven para resolver los problemas de planificación de tareas. Uno es el de la minimización del tiempo en el sistema. El problema se basa en minimizar el tiempo que invierte cada tarea en un sistema.

Otro problema importante es el de la planificación con plazo fijo. Se basa en que tenemos un número de tareas, donde cada tarea se ejecuta en una unidad de tiempo y tiene un beneficio si se lleva a cabo antes de un plazo máximo. Seleccionamos aquellas tareas que se ejecuten en plazo y con el objetivo final de maximizar el beneficio.

Para reducir el coste del problema anterior, se define la estructura de partición o de conjuntos disjuntos. Tenemos n elementos numerados como 0, 1, 2, ..., n-1. Hemos de ubicarlos en conjuntos disjuntos, de tal forma que un elemento se encuentre en cada momento en un único conjunto. Definiendo dos operaciones para buscar un elemento y fusionar dos conjuntos, podemos reducir el coste del problema de la planificación con plazo fijo. Y de otros problemas que veremos en un tema posterior.

Devolver cambio

Devolver cambio

En este problema, que también se resuelve con un algoritmo voraz, tenemos un conjunto de monedas y hemos de seleccionar la menor cantidad de monedas para devolver un cierto valor. La optimización es precisamente obtener una selección con el menor número de monedas. Aplicaríamos un algoritmo siguiendo la misma lógica que haríamos manualmente: seleccionar una o más monedas de mayor tamaño de forma iterativa hasta que completemos todo el cambio. Vease que empezamos por las de mayor tamaño, pues si empezamos con las de menor tamaño no optimizaremos el objetivo de devolver el menor número posible de monedas.

Mochila fraccionable

Los algoritmos voraces se utilizan para resolver problemas de optimización. Suelen considerar un conjunto de candidatos que se van analizando, tomando en cada iteración el que a corto plazo resulte más aceptable para conseguir la optimalidad que se espera del resultado final. Una vez seleccionado un candidato se incorpora al resultado, no reconsiderándose más adelante dicha decisión y permaneciendo en la solución hasta el final.

Como primer ejemplo veremos el problema de la mochila fraccionable. Se plantea que tenemos una mochila que puede cargar un peso máximo P y que tenemos n objetos fraccionables con un peso p y un valor v cada uno. Se trata de cargar la mochila sin pasarnos del peso máximo y maximizando el valor total, seleccionando un objeto de cada clase en fracciones 0 ≤ x ≤ 1, donde x es un número real, es decir, podemos no seleccionar un objeto, seleccionarlo o tomar una fracción.

Editor grafos SVG

Esta Herramienta de Web Tool Online sirve para crear grafos usando exclusivamente elementos SVG. Puede interactuar con el editor SVG traspasando el código SVG generado en la gráfica a ese editor y así poder realizar modificaciones en los elementos SVG de la gráfica. Otra posibilidad es traspasar el código al Parseador XML con objeto de verificar la corrección del SVG, pues en cualquier caso un SVG es un XML.

La información del grafo se introduce en formato JSON. La disposición gráfica de los nodos y aristas se realiza de forma automática. Aunque es posible desplazar las líneas de las aristas usando alguna configuración para el nodo.

Calculadora

Calculadora

Esta aplicación es una calculadora que tiene por objeto probar el funcionamiento del módulo calc.js, cuya finalidad es ser un motor de cálculo de expresiones. Permite ese módulo calcular expresiones usando una pila con métodos de Array, dado que es la estructura de pila la que utiliza el algoritmo para transformar una expresión infija en notación polaca inversa (RPN).

Por otra parte el módulo calcui.js se encarga de construir una interfaz para generar y manejar esta aplicación calculadora. Dispone de varias vistas que pueden modificarse desde el botón de configuración .

Problema 8 reinas

El problema de las 8 reinas se plantea cómo ubicar en un tablero de ajedrez ocho reinas de tal forma que no se amenacen entre ellas. Esto quiere decir que no puede haber más de una en cada fila, columna o diagonal.

Este tipo de problemas no puede solucionarse aplicando las técnicas de reducción por substracción o división (divide y vencerás), puesto que no hay una evidencia clara de como reducir el problema a uno de menor tamaño. Esto significa que no queda más remedio que ir probando todas las combinaciones hasta que demos con la primera solución. Hay 64 casillas posibles y 8 piezas, por lo que existen 4.426165368 × 109 combinaciones posibles. Hay que tratar de reducir el número de posibilidades. Y este es el objetivo de los algoritmos recursivos del tipo vuelta atrás o backtracking.

DOM: ejemplo de árbol

En los temas anteriores hemos visto que los recursivos sirven para resolver problemas reduciendo el tamaño del mismo hasta alcanzar un caso trivial. En esos recursivos el objetivo era alcanzar la solución con el menor número de llamadas. Pero además los recursivos sirven para recorrer una estructura de árbol, donde el objetivo no es reducir las iteraciones, sino iterar por todas las hojas del árbol.

La estructura de árbol se utiliza en muchos casos, como en el que observa en la imagen. Se trata del árbol DOM que sirve para estructurar los elementos en un documento HTML. En un apartado al final de este tema veremos un ejemplo usando un recursivo para recorrer el DOM.


...Ver más en el histórico