Archivos mensuales: Sep PM

3 entradas

Heap min max montículos

PrEDA: cómo programar montículos mínimos o máximos de cualquier tipo de objetos

Una de las mejores formas de ordenar objetos es haciendo montículos. Está demostrado matemáticamente cómo mejoran la eficiencia de muchos tipos de algoritmos. Así que aquí traigo a modo de code-kata, de nuevo, otro pequeño script con el que se puede implementar montículos mínimos o máximos de cualquier tipo de objetos. Un montículo es un tipo especial de árbol binario. Son binarios porque cada nodo tiene de máximo dos hijos. Además, éstos árboles están ordenados de arriba a abajo. Si es un montículo de mínimos entonces los elementos de arriba, los padres, siempre tienen un valor menor que los hijos. Si por el contrario es un montículo de máximos, entonces los elementos de arriba, los padres tienen un valor mayor. De esta forma nos aseguramos que siempre tengamos el elemento mayor o menor en el nodo raiz del árbol. Esto es muy útil para utilizarlos en todo tipo de algoritmos de programación. Punto de partida En PHP tenemos una clase, que implementa mediante un vector interno, un montículo. Se trata de la clase SplHeap. Entonces simplemente tenemos que hacer herencia de SplHeap extendiendo la clase SplHeap. El código es bien sencillo: <?php define(‘NUMBER_OF_NODES’, 30); class TNodo { public $cost; public […]

Gantt

PrEDA: priorizando tareas para obtener el máximo de beneficio

Hoy traigo a modo de code-kata otro problema resuelto. Se trata de resolver un problema muy muy común en informática, la gestión de tareas. En este caso, se trata de aplicar la gestión de tareas, o proyectos, con la condición de obtener el máximo de beneficio. Podríamos gestionar las tareas minimizando el tiempo en el sistema, distribuyendo tareas entre varios agentes.. O podríamos aplicarlo a otros ámbitos como la cosecha de cultivos, en donde habría que priorizar en función al tiempo de putrefacción y beneficio, teniendo en cuenta el tiempo necesario para cada cosecha. Es decir, en este caso, se trata de obtener el orden óptimo de tareas de forma que se maximize el beneficio. Tenemos entonces una duración de cada tarea, un beneficio, y un tiempo de entrega. Para resolver este problema, la mejor estrategia es la ramificación y poda. No existe una estrategia voraz, ni de divide y vencerás que podamos usar. Tampoco la vuelta atrás es la mejor solución, porque se trata de obtener la solución óptima en el menor tiempo posible. Entonces, tendremos que generar un árbol de posibilidades, un árbol de combinación de tareas. De forma que mientras que generamos el árbol tenemos que tener […]

php7-logo

PrEDA: algoritmo para encontrar todos los cuadrados latinos de tamaño NxN

Los cuadrados latinos son una aplicación matemática, utilizando combinatoria, para generar cuadrados con ciertos datos en cada casilla cumpliendo unas restricciones. Podemos encontrar cuadrados latinos por ejemplo en los famosos sudokus. También se puede aplicar a la forma de distribuir cultivos o fertilizantes en cuadrados de terrenos. También se pueden usar para generar puzzles, rompecabezas, o simplemente para practicar algorimos de programación.. Traigo entonces a modo de code-kata otro algoritmo, para resolver cuadrados latinos de tamaño NxN. Estos cuadrados latinos tienen la peculiaridad de que: en cada fila no se puede repetir el mismo dato, y en cada columna tampoco se puede repetir el mismo dato. En este caso, he usado números para llenar de datos el cuadrado, y estos números del 1 a N significan un color. Un cero significa que está sin llenar, y los números entonces que llenamos van desde 1 hasta N, siendo N el ancho y alto del cuadrado.