Hércules y la Hydra
Descripción
El Castor Hércules tiene un árbol en su jardín. Desafortunadamente, el árbol tiene una enfermedad y todas sus hojas murieron y se pusieron cafés. Ahora Hércules quiere cortar todas las ramas que tienen hojas muertas para que puedan crecer nuevas ramas sanas.
En la imagen, los números indican el tiempo que se requiere para cortar cada rama. Cuando Hércules corta una rama más grande, por ejemplo la que tiene el número 5 dentro de la elipse verde, todas las hojas que estaban después de ahí se caen y no necesita cortar las ramas marcadas con 1 y 3 por separado.
Pregunta
¿Cuál es el tiempo mínimo que necesita Hércules para cortar todas las ramas con hojas secas?
Ver soluciónOcultar solución
Solución
La respuesta es 20. Podemos trabajar desde las hojas hacia la raíz. Para cada grupo de ramas comparamos dos opciones: cortar las ramas pequeñas que ya habíamos seleccionado o cortar una sola rama más grande que las elimina a todas. En cada punto conservamos la opción con menor costo.
Tras simplificar los grupos inferiores, los costos equivalentes quedan en 1 + 3 + 4 + 4 + 3 + 5. En el siguiente nivel, el lado izquierdo cuesta min(9, 1 + 3 + 4) = 8 y el grupo central cuesta min(8, 4 + 3) = 7; el grupo derecho cuesta 5. Por tanto, el mínimo total es 8 + 7 + 5 = 20.
La informática detrás del desafío
El árbol del dibujo puede verse también como una estructura de datos llamada árbol, que a su vez es un tipo de grafo. El problema consiste en elegir cortes con el menor costo posible para separar todas las hojas de la raíz. En teoría de grafos este tipo de idea se relaciona con el problema de corte mínimo o min-cut. La fuente también conecta el corte mínimo con el problema de flujo máximo, que aparece en situaciones de logística donde queremos determinar cuánto puede transportarse a través de una red con capacidades limitadas.
Para el aula
Dibuja un árbol pequeño con una raíz y seis hojas. Escribe un costo en cada rama. Para cada rama grande, compara su costo con la suma de los cortes necesarios en sus ramas hijas y conserva la opción más barata. Después cambia un solo costo y observa si cambia la estrategia óptima.
Recursos del desafío
