PrEDA

Algoritmos de programación para resolver problemas informáticos: divide y vencerás, voraz, programación dinámica, vuelta atrás y ramificación y poda..

Códigos fuentes en GitHub: https://github.com/jaimenj/preda-algorithms

PrEDA: cálculo empírico del coste temporal de Binomial

2018-02-04 - Categorías: PHP / PrEDA
Números

El coeficiente binomial es una función muy utilizada en combinatoria. Sirve para saber el número de combinaciones de elementos que podemos hacer. Se utiliza mucho en computación para estudiar la estrategia de programación dinámica, porque ejemplifica muy bien la mejora que supone utilizar dicha estrategia. Por ejemplo, la forma de escoger de entre 6 elementos 2 de ellos, es igual al coeficiente binomial (6 2).

Su definición es:

Binomial(n, k) = 1, si k=0 o k=n
Binomial(n, k) = Binomial(n-1, k-1) + Binomial(n-1, k), en otro casi

Partiendo de esta definición tenemos en PHP el siguiente código:

function binomialRecursive($n, $k)
{
    if ($k == 0 or $k == $n) {
        return 1;
    } else {
        return binomialRecursive($n - 1, $k - 1) + binomialRecursive($n - 1, $k);
    }
}

Para números grandes se repiten cálculos muchas veces, con lo que reducimos su coste temporal aplicando programación dinámica:

function binomialDynamic($n, $k)
{
    $tablaNK = array();

    if ($k <= 0 or $k == $n) {
        return 1;
    } else {
        for ($i = 0; $i <= $n; ++$i) {
            $tablaNK[$i][0] = 1;
        }
        for ($i = 1; $i <= $k; ++$i) {
            $tablaNK[$i][$i] = 1;
        }
        for ($i = 2; $i <= $n; ++$i) {
            for ($j = 1; $j < $i; ++$j) {
                if ($j <= $k) {
                    $tablaNK[$i][$j] = $tablaNK[$i - 1][$j - 1] + $tablaNK[$i - 1][$j];
                }
            }
        }

        /*for ($i = 0; $i < $n; ++$i) {
            for ($j = 0; $j < $k; ++$j) {
                if ($j <= $i) {
                    echo str_pad($tablaNK[$i][$j], 3);
                }
            }
            echo PHP_EOL;
        }*/

        return $tablaNK[$n][$k];
    }
}

Entonces iremos recorriendo de izquierda a derecha y de arriba a abajo rellenando la tabla. No tendremos que recalcular de nuevo ningún binomial anterior, con lo que el coste temporal final va a ser lineal.

Igual que en el post anterior, si metemos las dos funciones recursiva y dinámica en un bucle podemos ver cómo evolucionan. El código fuente en PHP queda así:

define('MAX_N', 100);

for ($n = 3; $n <= MAX_N; ++$n) {
    $k = intval($n / 2);
    $timeStart = microtime(true);
    $theNumber = binomialRecursive($n, $k);
    //echo 'binomialRecursive('.$n.', '.$k.') = '.$theNumber.PHP_EOL;
    $timeEnd = microtime(true);
    echo 'RECURSIVE binomial('.$n.','.$k.'): Calculated in '.number_format($timeEnd - $timeStart, 9).' seconds.'.PHP_EOL;

    $timeStart = microtime(true);
    $theNumber = binomialDynamic($n, $k);
    //echo 'binomialDynamic('.$n.', '.$k.') = '.$theNumber.PHP_EOL;
    $timeEnd = microtime(true);
    echo '  DYNAMIC binomial('.$n.','.$k.'): Calculated in '.number_format($timeEnd - $timeStart, 9).' seconds.'.PHP_EOL;
}

Ponemos todo en un fichero y al ejecutarlo podremos ver claramente que tenemos que usar programación dinámica. Para números grandes, no podremos calcular sus binomiales si no es aplicando programación dinámica.

RECURSIVE binomial(6,3): Calculated in 0.000006914 seconds.
 DYNAMIC binomial(6,3): Calculated in 0.000010014 seconds.
RECURSIVE binomial(7,3): Calculated in 0.000009060 seconds.
 DYNAMIC binomial(7,3): Calculated in 0.000010014 seconds.
RECURSIVE binomial(8,4): Calculated in 0.000020981 seconds.
 DYNAMIC binomial(8,4): Calculated in 0.000010014 seconds.
RECURSIVE binomial(9,4): Calculated in 0.000045061 seconds.
 DYNAMIC binomial(9,4): Calculated in 0.000010014 seconds.
RECURSIVE binomial(10,5): Calculated in 0.000081062 seconds.
 DYNAMIC binomial(10,5): Calculated in 0.000010967 seconds.
RECURSIVE binomial(11,5): Calculated in 0.000133038 seconds.
 DYNAMIC binomial(11,5): Calculated in 0.000012159 seconds.
RECURSIVE binomial(12,6): Calculated in 0.000247002 seconds.
 DYNAMIC binomial(12,6): Calculated in 0.000014067 seconds.
RECURSIVE binomial(13,6): Calculated in 0.000452042 seconds.
 DYNAMIC binomial(13,6): Calculated in 0.000015974 seconds.
RECURSIVE binomial(14,7): Calculated in 0.000910997 seconds.
 DYNAMIC binomial(14,7): Calculated in 0.000026941 seconds.
RECURSIVE binomial(15,7): Calculated in 0.001642227 seconds.
 DYNAMIC binomial(15,7): Calculated in 0.000020027 seconds.
RECURSIVE binomial(16,8): Calculated in 0.003252029 seconds.
 DYNAMIC binomial(16,8): Calculated in 0.000024080 seconds.
RECURSIVE binomial(17,8): Calculated in 0.005996943 seconds.
 DYNAMIC binomial(17,8): Calculated in 0.000023842 seconds.
RECURSIVE binomial(18,9): Calculated in 0.013009787 seconds.
 DYNAMIC binomial(18,9): Calculated in 0.000043154 seconds.
RECURSIVE binomial(19,9): Calculated in 0.020354033 seconds.
 DYNAMIC binomial(19,9): Calculated in 0.000036001 seconds.
RECURSIVE binomial(20,10): Calculated in 0.036875963 seconds.
 DYNAMIC binomial(20,10): Calculated in 0.000036955 seconds.
RECURSIVE binomial(21,10): Calculated in 0.061520815 seconds.
 DYNAMIC binomial(21,10): Calculated in 0.000036955 seconds.
RECURSIVE binomial(22,11): Calculated in 0.120537996 seconds.
 DYNAMIC binomial(22,11): Calculated in 0.000041008 seconds.
RECURSIVE binomial(23,11): Calculated in 0.230448008 seconds.
 DYNAMIC binomial(23,11): Calculated in 0.000044107 seconds.
RECURSIVE binomial(24,12): Calculated in 0.459716797 seconds.
 DYNAMIC binomial(24,12): Calculated in 0.000044823 seconds.
RECURSIVE binomial(25,12): Calculated in 0.885799885 seconds.
 DYNAMIC binomial(25,12): Calculated in 0.000042915 seconds.
RECURSIVE binomial(26,13): Calculated in 1.761939049 seconds.
 DYNAMIC binomial(26,13): Calculated in 0.000046015 seconds.
RECURSIVE binomial(27,13): Calculated in 3.628232956 seconds.
 DYNAMIC binomial(27,13): Calculated in 0.000091076 seconds.
RECURSIVE binomial(28,14): Calculated in 7.495334148 seconds.
 DYNAMIC binomial(28,14): Calculated in 0.000072956 seconds.
RECURSIVE binomial(29,14): Calculated in 13.519285917 seconds.
 DYNAMIC binomial(29,14): Calculated in 0.000084877 seconds.
RECURSIVE binomial(30,15): Calculated in 27.332123995 seconds.
 DYNAMIC binomial(30,15): Calculated in 0.000058174 seconds.
RECURSIVE binomial(31,15): Calculated in 53.179553986 seconds.
 DYNAMIC binomial(31,15): Calculated in 0.000060081 seconds.
RECURSIVE binomial(32,16): Calculated in 107.939800024 seconds.
 DYNAMIC binomial(32,16): Calculated in 0.000065088 seconds.
RECURSIVE binomial(33,16): Calculated in 203.573032141 seconds.
 DYNAMIC binomial(33,16): Calculated in 0.000068903 seconds.
RECURSIVE binomial(34,17): Calculated in 409.646430969 seconds.
 DYNAMIC binomial(34,17): Calculated in 0.000072002 seconds.

PrEDA: cálculo empírico del coste temporal de Fibonacci

- Categorías: PHP / PrEDA
Números

Continuando con post anteriores sobre esquemas algorítmicos. Dejo aquí unas pruebas empíricas sobre cómo calcular el Número de Fibonacci de números grandes. Si vemos la definición de Fibonacci es la siguiente:

Fibonacci(n) = 1, si n=0 o n=1
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2), si n> 1

El código en PHP para resolverlo sería el siguiente:

function fibonacciRecursive($n)
{
    if ($n <= 1) {
        return 1;
    } else {
        return fibonacciRecursive($n - 1) + fibonacciRecursive($n - 2);
    }
}

Observamos que se repiten cálculos, con lo que aplicando programación dinámica tenemos el siguiente código:

function fibonacciDynamic($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];
    }
}

Estas dos funciones, para compararlas empíricamente, las usamos en un bucle que vaya incrementando el número $n para obtener su coste temporal empírico. También en PHP con éste código:

define('MAX_N', 100);

for ($i = 0; $i <= MAX_N; ++$i) {
    $timeStart = microtime(true);
    $theNumber = fibonacciRecursive($i);
    //echo 'fibonacciRecursive('.$i.') = '.$theNumber.PHP_EOL;
    $timeEnd = microtime(true);
    echo 'RECURSIVE fibonacci('.$i.'): Calculated in '.number_format($timeEnd - $timeStart, 9).' seconds.'.PHP_EOL;

    $timeStart = microtime(true);
    $theNumber = fibonacciDynamic($i);
    //echo 'fibonacciDynamic('.$i.') = '.$theNumber.PHP_EOL;
    $timeEnd = microtime(true);
    echo '  DYNAMIC fibonacci('.$i.'): Calculated in '.number_format($timeEnd - $timeStart, 9).' seconds.'.PHP_EOL;
}

Ahora bien, ejecutamos todo junto. Así podemos ver cómo, para números grandes, se convierte en imposible resolver el Número de Fibonacci con programación recursiva:

RECURSIVE fibonacci(22): Calculated in 0.002473116 seconds.
  DYNAMIC fibonacci(22): Calculated in 0.000002861 seconds.
RECURSIVE fibonacci(23): Calculated in 0.004077911 seconds.
  DYNAMIC fibonacci(23): Calculated in 0.000005007 seconds.
RECURSIVE fibonacci(24): Calculated in 0.006484985 seconds.
  DYNAMIC fibonacci(24): Calculated in 0.000003815 seconds.
RECURSIVE fibonacci(25): Calculated in 0.010952950 seconds.
  DYNAMIC fibonacci(25): Calculated in 0.000016928 seconds.
RECURSIVE fibonacci(26): Calculated in 0.017073154 seconds.
  DYNAMIC fibonacci(26): Calculated in 0.000005960 seconds.
RECURSIVE fibonacci(27): Calculated in 0.027941942 seconds.
  DYNAMIC fibonacci(27): Calculated in 0.000008106 seconds.
RECURSIVE fibonacci(28): Calculated in 0.045236111 seconds.
  DYNAMIC fibonacci(28): Calculated in 0.000008106 seconds.
RECURSIVE fibonacci(29): Calculated in 0.073548079 seconds.
  DYNAMIC fibonacci(29): Calculated in 0.000009060 seconds.
RECURSIVE fibonacci(30): Calculated in 0.118798018 seconds.
  DYNAMIC fibonacci(30): Calculated in 0.000012159 seconds.
RECURSIVE fibonacci(31): Calculated in 0.202280998 seconds.
  DYNAMIC fibonacci(31): Calculated in 0.000010967 seconds.
RECURSIVE fibonacci(32): Calculated in 0.310992002 seconds.
  DYNAMIC fibonacci(32): Calculated in 0.000011921 seconds.
RECURSIVE fibonacci(33): Calculated in 0.506221056 seconds.
  DYNAMIC fibonacci(33): Calculated in 0.000011921 seconds.
RECURSIVE fibonacci(34): Calculated in 0.834569931 seconds.
  DYNAMIC fibonacci(34): Calculated in 0.000009060 seconds.
RECURSIVE fibonacci(35): Calculated in 1.305525780 seconds.
  DYNAMIC fibonacci(35): Calculated in 0.000010014 seconds.
RECURSIVE fibonacci(36): Calculated in 2.117379189 seconds.
  DYNAMIC fibonacci(36): Calculated in 0.000010014 seconds.
RECURSIVE fibonacci(37): Calculated in 3.495128870 seconds.
  DYNAMIC fibonacci(37): Calculated in 0.000009060 seconds.
RECURSIVE fibonacci(38): Calculated in 5.618491888 seconds.
  DYNAMIC fibonacci(38): Calculated in 0.000010014 seconds.
RECURSIVE fibonacci(39): Calculated in 9.390465975 seconds.
  DYNAMIC fibonacci(39): Calculated in 0.000010014 seconds.
RECURSIVE fibonacci(40): Calculated in 14.963202953 seconds.
  DYNAMIC fibonacci(40): Calculated in 0.000010014 seconds.

La función Fibonacci recursiva, crece exponencialmente, mientras que la dinámica es lineal. Es decir, que más nos vale usar la función de programación dinámica.


PrEDA: esquemas de programación genéricos avanzados

2018-02-03 - Categorías: PHP / PrEDA
PrEDA algoritmos genericos

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.


PrEDA: minimizando tiempo en el sistema con varios agentes

2017-11-23 - Categorías: PHP / PrEDA
Gantt

Continuando con el post anterior, y de nuevo a modo de code-kata, vengo a traer el siguiente paso al algoritmo. Si en el post anterior teníamos cómo minimizar el tiempo en el sistema de varias tareas con un sólo agente, ahora le añadimos la posibilidad de tener varios.

Seguimos teniendo una estrategia voraz para resolver el órden en que se ejecutan las tareas. También voraz para asignar a los agentes dichas tareas, porque se seleccionan las tareas sin tener que volver atrás en la selección. La estrategia de selección es ordenar las tareas por orden creciente de tiempo necesario, y vamos alternando entre los agentes para distribuirles las tareas, distribuyendo también así la carga entre los agentes.

Igual que en la versión anterior, suponemos que todas las tareas tienen el mismo beneficio o importancia, no habría ninguna razón para priorizar tareas de más tiempo. La prioridad la tendrán entonces las tareas de menos tiempo en este caso..

El código

Un poco más elaborado que el anterior:

<?php 

define('NUMBER_OF_TASKS', 30);
define('NUMBER_OF_AGENTS', 3);

$tasksTime = array();

for ($i = 0; $i < NUMBER_OF_TASKS; ++$i) { 
    $tasksTime[$i] = rand(1, 10); 
} 
$totalTimeClientsWaiting = printTasks($tasksTime, $maxTimeWaiting); 
echo 'TIME IN SYSTEM OF TASKS: '.$totalTimeClientsWaiting.' WITH A MAX WAITING TIME OF '.$maxTimeWaiting.PHP_EOL; 

asort($tasksTime); 
echo 'Tasks sorted, asigning to agents..'.PHP_EOL; 

echo 'Asigning to one agent only..'.PHP_EOL; 
$totalTimeClientsWaiting = printTasks($tasksTime, $maxTimeWaiting); 
echo 'TIME IN SYSTEM OF TASKS: '.$totalTimeClientsWaiting.' WITH A MAX WAITING TIME OF '.$maxTimeWaiting.PHP_EOL;

echo 'Asigning to '.NUMBER_OF_AGENTS.' agents..'.PHP_EOL; 
$agentsTasks = array(); 
$ptrAgent = 0; 
foreach ($tasksTime as $task => $time) {
    $agentsTasks[$ptrAgent][$task] = $time;
    ++$ptrAgent;
    if ($ptrAgent == NUMBER_OF_AGENTS) {
        $ptrAgent = 0;
    }
}
$totalTimeWaiting = 0;
foreach ($agentsTasks as $number => $agentTasks) {
    echo 'Tasks for agent number '.$number.PHP_EOL;
    $timeSpent = printTasks($agentTasks, $maxTimeWaiting);
    $totalTimeWaiting = $totalTimeWaiting + $timeSpent;
    echo 'TIME IN SYSTEM OF TASKS: '.$timeSpent.' WITH A MAX WAITING TIME OF '.$maxTimeWaiting.PHP_EOL;
}
echo 'TOTAL TIME IN SYSTEM OF TASKS WITH '.NUMBER_OF_AGENTS.' AGENTS: '.$totalTimeWaiting.PHP_EOL;

function printTasks($tasksTime, &$maxTimeWaiting)
{
    $total = $maxTimeWaiting = 0;
    $tasksRemaining = count($tasksTime);

    echo 'Tasks:  ';
    foreach ($tasksTime as $task => $time) {
        echo str_pad($task, 4, ' ');
        $total = $total + $time * $tasksRemaining;
        $maxTimeWaiting = $maxTimeWaiting + $time;
        --$tasksRemaining;
    }
    echo PHP_EOL.'Time:   ';
    foreach ($tasksTime as $task => $time) {
        echo str_pad($time, 4, ' ');
    }
    echo PHP_EOL;

    return $total;
}

He marcado en negrita las variables principales. Siguiéndolas se puede ver cómo almacenar los tiempos de espera en el sistema de todas las tareas ($total) o el máximo tiempo que espera la última tarea ($maxTimeWaiting). Esta función printTasks simplemente pinta por pantalla calculando estos tiempos. No es necesario ningún cálculo extra porque la estrategia de selección es muy simple: sólo hay que ordenar las tareas por tiempo que consumen y elegir crecientemente en orden de tiempo.

Es curioso ver cómo se reduce considerablemente el tiempo, y se equipara la carga de trabajo entre los agentes. No habiendo así ninguno de los agentes cargado en exceso, ni ninguno de los agentes ocioso.

PrEDA minimizando tiempo en el sistema con varios agentes



PrEDA: minimizando tiempo en el sistema

2017-11-22 - Categorías: PHP / PrEDA
Gantt

La gestión de los proyectos es la clave: puede marcar la diferencia entre el éxito o el desastre. La gestión de las tareas no se puede hacer de cualquier forma. Por esto que se han estudiado y se han establecido muchas estrategias. No cualquier software puede ser un buen gestor de proyectos. Por esto que existen estudios que lo integran, técnicas de programación.. y sobretodo en informática, que existen multitud de estrategias, ya que dentro de los ordenadores esto se aplica constantemente.

Los pasos clásicos a seguir son los siguientes:

  • Se establecen las tareas, fijando especificaciones.
  • Se estudian bien los tiempos que va a llevar cada tarea.
  • Se establece la estrategia para proceder.
  • Se resuelve el órden, con lo cual, aquí se obtienen las fechas de finalización de cada tarea y el tiempo total.
  • Se ejecuta el proyecto.

Como es obvio, en el primer paso se cierran especificaciones y cualquier modificación posterior invalida el algoritmo, y hay que recalcular todo.

A modo de code-kata traigo hoy una estrategia voraz para organizar un proyecto con el objetivo de minimizar el tiempo de espera de las tareas en el sistema. Suponiendo que todas las tareas son igual de importantes, se trata de hacer que esperen en total lo mínimo posible. Se trata de una estregia voraz porque simplemente se elige la siguientes tareas que menos tiempo se tarde en terminar, sin rectificar ni volver atrás. Así se terminarán primero las que menos se tarde, y más rápido se irán entregando las tareas. Otra cosa es el beneficio o la importancia que pueda tener cada tarea, pero para esto hay otro algoritmo 😉

Continuar leyendo..

PrEDA: grafos, el algoritmo de Dijkstra mejorado

2017-11-04 - Categorías: PHP / PrEDA
Grafos, mapas y matrices de adyacencia

Vengo a traer una revisión del post anterior. Sobre el algoritmo de Dijkstra para cálculo de caminos mínimos entre nodos de un grafo, a modo de code-kata. Son unas modificaciones para hacer que se pueda elegir el nodo inicial desde el que arrancamos. Y una sencilla ordenación de los nodos de la lista de adyacencia.

Así de esta forma se puede poner en la variable global definida como INITIAL_NODE el nodo desde el que buscaremos los caminos mínimos.

El código

He marcado en negrita las modificaciones con respecto del anterior post.

<?php 
define('NUMBER_OF_NODES', 17); 
define('INITIAL_NODE', 3); 
define('NUMBER_OF_EDGES_PER_NODE', 3); 
define('IS_DIRECTED_GRAPH', true); 

$adjacencyList = array(); 
fillRandomCosts($adjacencyList); 
printToScreen($adjacencyList); 

$special = $predecessor = array(); 
dijkstra($adjacencyList, $special, $predecessor); 
echo 'FINAL> Special: '.implode('-', $special).PHP_EOL
    .'FINAL> Predecessor: '.implode('-', $predecessor).PHP_EOL;

function dijkstra($adjacencyList, &$special, &$predecessor)
{
    // Fill C with not used nodes.
    $C = array();
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        if ($i != INITIAL_NODE) {
            $C[] = $i;
        }
    }

    // Fill special distances.
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        if ($i != INITIAL_NODE) {
            $special[$i] = distanceFromTo($adjacencyList, INITIAL_NODE, $i);
            if ($special[$i] < INF) { 
                $predecessor[$i] = INITIAL_NODE; 
            } else { 
                $predecessor[$i] = '#'; 
            } 
        } else { 
            $special[$i] = 'I'; 
            $predecessor[$i] = 'I'; 
        } 
    } 
    
    echo 'INITIAL_NODE = '.INITIAL_NODE.PHP_EOL 
        .'INITIAL> Not used nodes: '.implode('-', $C).PHP_EOL
        .'INITIAL> Special: '.implode('-', $special).PHP_EOL
        .'INITIAL> Predecessor: '.implode('-', $predecessor).PHP_EOL;

    // Study nodes in C to update $special and predecessor vectors.
    while (count($C) > 1) {
        $v = selectNextNodeThatMinimizesSpecial($adjacencyList, $C, $special);
        $C = array_diff($C, array($v));

        if ($v == -1) {
            echo 'IMPOSSIBLE TO FIND DIJKSTRA WITH ALL NODES! Cannot achieve all nodes!'.PHP_EOL;
            exit;
        }

        foreach ($C as $w) {
            if ($special[$w] > $special[$v] + distanceFromTo($adjacencyList, $v, $w)) {
                $special[$w] = $special[$v] + distanceFromTo($adjacencyList, $v, $w);
                $predecessor[$w] = $v;
            }
        }

        echo 'Not used nodes: '.implode('-', $C).PHP_EOL
            .'Special: '.implode('-', $special).PHP_EOL
            .'Predecessor: '.implode('-', $predecessor).PHP_EOL;
    }
}

function selectNextNodeThatMinimizesSpecial($adjacencyList, &$C, &$special)
{
    $minCost = INF;
    $minNode = -1;

    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        foreach ($C as $node) {
            if (!in_array($i, $C)
            and isset($adjacencyList[$i][$node])
            and $adjacencyList[$i][$node] < $minCost) { 
                echo '>>>> Found min edge! $adjacencyList['.$i.']['.$node.']='.$adjacencyList[$i][$node].PHP_EOL;
                $minCost = $adjacencyList[$i][$node];
                $minNode = $node;
            }
        }
    }

    echo '>>>> Next min node to use is '.$minNode.PHP_EOL;

    return $minNode;
}

function distanceFromTo($adjacencyList, $from, $to)
{
    if (isset($adjacencyList[$from][$to])) {
        return $adjacencyList[$from][$to];
    } else {
        return INF;
    }
}

function fillRandomCosts(&$adjacencyList)
{
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        $added = false;
        while (!$added) {
            for ($j = 0; $j < NUMBER_OF_EDGES_PER_NODE; ++$j) {
                $adjacentNode = rand(0, NUMBER_OF_NODES - 1);
                if ($adjacentNode != $i and $adjacentNode != $j) {
                    $adjacentNodeCost = rand(1, 5);
                    $adjacencyList[$i][$adjacentNode] = $adjacentNodeCost;
                    if (!IS_DIRECTED_GRAPH) {
                        $adjacencyList[$adjacentNode][$i] = $adjacentNodeCost;
                    }
                    $added = true;
                }
            }
        }
        ksort($adjacencyList[$i]);
    }
}
function printToScreen($adjacencyList)
{
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) { 
        echo $i; 
        foreach ($adjacencyList[$i] as $key => $value) {
            echo ' --> '.$key.'('.$value.')';
        }
        echo PHP_EOL;
    }
}

Puedes encontrar este código junto con otros en:
https://github.com/jaimenj/preda-algorithms


PrEDA: grafos, el algoritmo de Dijkstra

2017-10-29 - Categorías: PHP / PrEDA
Grafos, mapas y matrices de adyacencia

Después de haber repasado los fundamentos de los grafos: cómo se almacenan mediante matrices o listas de adyacencia, cómo se mantienen conectados mediante el algoritmo de Prim o Kruskal.. llegamos al algoritmo de Dijkstra.

Con este algoritmo, que nos sirve tanto para grafos dirigidos como no dirigidos, podemos saber cuál es el camino de menor coste desde un nodo origen a todos los demás. Usa la estrategia de programación voraz, mediante la cual, vamos construyendo la solución sin tener que volver atrás en cada decisión que vamos tomando.

Las aplicaciones de este algorimo son muchas más que los algoritmos predecesores. Por ejemplo, para calcular rutas en un mapa de carreteras, para conectar llamadas telefónicas mediante circuitos virtuales, enrutamiento de paquetes de red, coger varios autobuses/trenes/aviones minimizando coste o tiempo, buscar el mejor camino hasta el punto de recarga de un robot aspiradora, y un largo etcétera..

Estructura del algoritmo

Se basa en la selección arbitraria de un nodo origen, en el uso de un conjunto de nodos pendientes de estudiar, un vector especial que almacena el coste de llegar a cada nodo, y un vector de predecesores que guarda el nodo anterior para llegar a cada posición.

Mediante estas estructuras de datos, vamos estudiando las aristas entre nodo y nodo. Así de esta manera, se van recalculando el vector de los costes y el de los predecesores. En este ejemplo se parte del nodo inicial 0. Y se van estudiando nodo a nodo, los caminos posibles hasta el siguiente nodo en estudio. Cuando ya hemos estudiado todos los nodos, tendremos el camino de menor coste a cualquier nodo desde el nodo origen.

Por ejemplo

En este caso está configurado el script para generar grafos dirigidos:

0 --> 1(3)
1 --> 3(4) --> 2(1)
2 --> 5(2) --> 3(1)
3 --> 1(1) --> 4(4)
4 --> 6(1)
5 --> 3(5)
6 --> 4(1)
INITIAL> Not used nodes: 1-2-3-4-5-6
INITIAL> Special: 3-INF-INF-INF-INF-INF
INITIAL> Predecessor: 0-#-#-#-#-#
>>>> Found min edge! $adjacentList[0][1]=3
>>>> Next min node to use is 1
Not used nodes: 2-3-4-5-6
Special: 3-4-7-INF-INF-INF
Predecessor: 0-1-1-#-#-#
>>>> Found min edge! $adjacentList[1][2]=1
>>>> Next min node to use is 2
Not used nodes: 3-4-5-6
Special: 3-4-5-INF-6-INF
Predecessor: 0-1-2-#-2-#
>>>> Found min edge! $adjacentList[1][3]=4
>>>> Found min edge! $adjacentList[2][3]=1
>>>> Next min node to use is 3
Not used nodes: 4-5-6
Special: 3-4-5-9-6-INF
Predecessor: 0-1-2-3-2-#
>>>> Found min edge! $adjacentList[2][5]=2
>>>> Next min node to use is 5
Not used nodes: 4-6
Special: 3-4-5-9-6-INF
Predecessor: 0-1-2-3-2-#
>>>> Found min edge! $adjacentList[3][4]=4
>>>> Next min node to use is 4
Not used nodes: 6
Special: 3-4-5-9-6-10
Predecessor: 0-1-2-3-2-4
FINAL> Special: 3-4-5-9-6-10
FINAL> Predecessor: 0-1-2-3-2-4

El resultado final son los dos vectores de las dos últimas líneas. El vector especial, nos indica el coste hasta el nodo i. Por ejemplo, veamos el camino desde el nodo 0 al 4. Tiene un coste de 9 unidades y su camino se construye de atrás a adelante 4-3-2-1-0, mediante el vector predecesor. Es decir, el camino de mínimo coste posible es el 0-1-2-3-4. Si estudiamos las opciones podemos ver que así es.

El código

<?php define('NUMBER_OF_NODES', 7);
define('NUMBER_OF_EDGES_PER_NODE', 2); 
define('IS_DIRECTED_GRAPH', true); 

$adjacentList = array(); 
fillRandomCosts($adjacentList); 
printToScreen($adjacentList); 

$special = $predecessor = array(); 
dijkstra($adjacentList, $special, $predecessor); 

echo 'FINAL> Special: '.implode('-', $special).PHP_EOL
    .'FINAL> Predecessor: '.implode('-', $predecessor).PHP_EOL;

function dijkstra($adjacentList, &$special, &$predecessor)
{
    // Fill C with not used nodes.
    $C = array();
    for ($i = 1; $i < NUMBER_OF_NODES; ++$i) {
        $C[] = $i;
    }

    // Fill special distances.
    for ($i = 1; $i < NUMBER_OF_NODES; ++$i) {
        $special[$i] = distanceFromTo($adjacentList, 0, $i);
        if ($special[$i] < INF) { 
            $predecessor[$i] = 0; 
        } else { 
            $predecessor[$i] = '#'; 
        } 
    } 
    
    echo 'INITIAL> Not used nodes: '.implode('-', $C).PHP_EOL
        .'INITIAL> Special: '.implode('-', $special).PHP_EOL
        .'INITIAL> Predecessor: '.implode('-', $predecessor).PHP_EOL;

    // Study nodes in C to update $special and predecessor vectors.
    while (count($C) > 1) {
        $v = selectNextNodeThatMinimizesSpecial($adjacentList, $C, $special);
        $C = array_diff($C, array($v));

        if ($v == -1) {
            echo 'IMPOSSIBLE TO FIND DIJKSTRA WITH ALL NODES! Cannot achieve all nodes!'.PHP_EOL;
            exit;
        }

        foreach ($C as $w) {
            if ($special[$w] > $special[$v] + distanceFromTo($adjacentList, $v, $w)) {
                $special[$w] = $special[$v] + distanceFromTo($adjacentList, $v, $w);
                $predecessor[$w] = $v;
            }
        }

        echo 'Not used nodes: '.implode('-', $C).PHP_EOL
            .'Special: '.implode('-', $special).PHP_EOL
            .'Predecessor: '.implode('-', $predecessor).PHP_EOL;
    }
}

function selectNextNodeThatMinimizesSpecial($adjacentList, &$C, &$special)
{
    $minCost = INF;
    $minNode = -1;

    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        foreach ($C as $node) {
            if (!in_array($i, $C)
            and isset($adjacentList[$i][$node])
            and $adjacentList[$i][$node] < $minCost) { 
                echo '>>>> Found min edge! $adjacentList['.$i.']['.$node.']='.$adjacentList[$i][$node].PHP_EOL;
                $minCost = $adjacentList[$i][$node];
                $minNode = $node;
            }
        }
    }

    echo '>>>> Next min node to use is '.$minNode.PHP_EOL;

    return $minNode;
}

function distanceFromTo($adjacentList, $from, $to)
{
    if (isset($adjacentList[$from][$to])) {
        return $adjacentList[$from][$to];
    } else {
        return INF;
    }
}

function fillRandomCosts(&$adjacentList)
{
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        $added = false;
        while (!$added) {
            for ($j = 0; $j < NUMBER_OF_EDGES_PER_NODE; ++$j) {
                $adjacentNode = rand(0, NUMBER_OF_NODES - 1);
                if ($adjacentNode != $i and $adjacentNode != $j) {
                    $adjacentNodeCost = rand(1, 5);
                    $adjacentList[$i][$adjacentNode] = $adjacentNodeCost;
                    if (!IS_DIRECTED_GRAPH) {
                        $adjacentList[$adjacentNode][$i] = $adjacentNodeCost;
                    }
                    $added = true;
                }
            }
        }
    }
}
function printToScreen($adjacentList)
{
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) { echo $i; foreach ($adjacentList[$i] as $key => $value) {
            echo ' --> '.$key.'('.$value.')';
        }
        echo PHP_EOL;
    }
}

PrEDA: grafos, el algoritmo de Kruskal

2017-10-28 - Categorías: PHP / PrEDA
Grafos, mapas y matrices de adyacencia

Otro code-kata que vengo a traer.. Siguiendo con la serie de los relacionados con los grafos, el algoritmo de Kruskal. Es parecido al algoritmo de Prim del post anterior pero con distinto rendimiento según el tipo de grafo que tengamos. Si tenemos un grafo denso es más eficiente el algoritmo de Prim, pero si es un grafo disperso el de Kruskal.

Este algoritmo busca conseguir el árbol de recubrimiento mínimo de un grafo. Es decir, cada arista que une vértices del grafo tiene un coste. Entonces, se busca el árbol de coste mínimo que conecte a todos los nodos. Este algoritmo se puede aplicar para construcción de redes con coste mínimo, por ejemplo: Internet, redes locales, eléctricas, de agua, etc..

Se utiliza la estrategia de programación voraz. Se van eligiendo las siguientes aristas de forma que no hay que volver atrás en la construcción de la solución. Se basa en el concepto de componente conexa y en el ordenamiento previo de las aristas. Vamos a ver..

Los pasos del algoritmo

  1. Se ordenan todas las aristas en orden creciente de coste.
  2. Se parte de un vector de componentes conexas que inicialmente es 1 componente por nodo.
  3. Cada vez que se añade una nueva arista al árbol final, se tienen que unir dos componentes conexas.
  4. Se repite el paso 3 hasta que sólo hay 1 componente conexa que contiene todos los nodos o nos hayamos quedado sin aristas.

Un ejemplo

Viéndolo queda claro el funcionamiento. Primero se lista la lista de adyacencia y luego una traza del funcionamiento:

0 --> 4(5) --> 5(1) --> 1(3)
1 --> 8(5) --> 0(3)
2 --> 5(1) --> 11(3)
3 --> 8(2)
4 --> 0(5) --> 11(5) --> 8(4)
5 --> 0(1) --> 2(1) --> 10(5) --> 9(4)
6 --> 8(2) --> 9(5)
7 --> 10(2) --> 11(2)
8 --> 1(5) --> 3(2) --> 4(4) --> 6(2) --> 9(3)
9 --> 5(4) --> 8(3) --> 6(5)
10 --> 5(5) --> 7(2)
11 --> 2(3) --> 4(5) --> 7(2)
0-5(1) {0}{1}{2}{3}{4}{5}{6}{7}{8}{9}{10}{11} N1=0 N2=5 using this edge!
5-0(1) {0,5}{1}{2}{3}{4}{6}{7}{8}{9}{10}{11} N1=0 N2=0 not using..
5-2(1) {0,5}{1}{2}{3}{4}{6}{7}{8}{9}{10}{11} N1=0 N2=2 using this edge!
2-5(1) {0,5,2}{1}{3}{4}{6}{7}{8}{9}{10}{11} N1=0 N2=0 not using..
8-3(2) {0,5,2}{1}{3}{4}{6}{7}{8}{9}{10}{11} N1=8 N2=3 using this edge!
8-6(2) {0,5,2}{1}{4}{6}{7}{8,3}{9}{10}{11} N1=8 N2=6 using this edge!
11-7(2) {0,5,2}{1}{4}{7}{8,3,6}{9}{10}{11} N1=11 N2=7 using this edge!
3-8(2) {0,5,2}{1}{4}{8,3,6}{9}{10}{11,7} N1=8 N2=8 not using..
10-7(2) {0,5,2}{1}{4}{8,3,6}{9}{10}{11,7} N1=10 N2=11 using this edge!
6-8(2) {0,5,2}{1}{4}{8,3,6}{9}{10,11,7} N1=8 N2=8 not using..
7-10(2) {0,5,2}{1}{4}{8,3,6}{9}{10,11,7} N1=10 N2=10 not using..
7-11(2) {0,5,2}{1}{4}{8,3,6}{9}{10,11,7} N1=10 N2=10 not using..
0-1(3) {0,5,2}{1}{4}{8,3,6}{9}{10,11,7} N1=0 N2=1 using this edge!
1-0(3) {0,5,2,1}{4}{8,3,6}{9}{10,11,7} N1=0 N2=0 not using..
8-9(3) {0,5,2,1}{4}{8,3,6}{9}{10,11,7} N1=8 N2=9 using this edge!
2-11(3) {0,5,2,1}{4}{8,3,6,9}{10,11,7} N1=0 N2=10 using this edge!
11-2(3) {0,5,2,1,10,11,7}{4}{8,3,6,9} N1=0 N2=0 not using..
9-8(3) {0,5,2,1,10,11,7}{4}{8,3,6,9} N1=8 N2=8 not using..
4-8(4) {0,5,2,1,10,11,7}{4}{8,3,6,9} N1=4 N2=8 using this edge!
5-9(4) {0,5,2,1,10,11,7}{4,8,3,6,9} N1=0 N2=4 using this edge!
Final edges: 0-5 5-2 8-3 8-6 11-7 10-7 0-1 8-9 2-11 4-8 5-9

Lo que hay entre llaves {} son las componentes conexas. Lo que hay entre paréntesis () son costes o pesos de las aristas.

El algoritmo

<?php

define('NUMBER_OF_NODES', 12);
define('NUMBER_OF_EDGES_PER_NODE', 2);
define('MAX_COST', 5);

$adjacentList = array();
fillRandomCosts($adjacentList);
printToScreenAdjacentList($adjacentList);

$finalEdges = kruskal($adjacentList);

// Printing solution.
if (count($finalEdges) < NUMBER_OF_NODES - 1) {
    echo 'Not full connected graph!!'.PHP_EOL;
} else {
    echo 'Final edges: ';
    foreach ($finalEdges as $edge) {
        echo $edge['n1'].'-'.$edge['n2'].' ';
    }
    echo PHP_EOL;
}

function kruskal($adjacentList)
{
    $orderedEdges = orderEdgesWithCosts($adjacentList);
    $finalEdges = array();

    // Init each set with each node.
    $sets = array();
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        $sets[] = array($i);
    }

    // Finding edges.
    while (count($finalEdges) < NUMBER_OF_NODES - 1 and count($orderedEdges) > 0) {
        $nextEdge = array_shift($orderedEdges);

        $componentN1 = searchConnectedComponent($nextEdge['n1'], $sets);
        $componentN2 = searchConnectedComponent($nextEdge['n2'], $sets);

        echo $nextEdge['n1'].'-'.$nextEdge['n2'].'('.$nextEdge['cost'].') ';
        foreach ($sets as $set) {
            echo '{'.implode(',', $set).'}';
        }
        echo ' N1='.$componentN1.' N2='.$componentN2;

        if ($componentN1 != $componentN2) {
            // Fuse component 2 into 1.
            foreach ($sets[$componentN2] as $node) {
                $sets[$componentN1][] = $node;
            }
            unset($sets[$componentN2]);

            // Adds this edge to solution.
            $finalEdges[] = array(
                'n1' => $nextEdge['n1'],
                'n2' => $nextEdge['n2'],
            );

            echo ' using this edge!';
        } else {
            echo ' not using..';
        }

        echo PHP_EOL;
    }

    return $finalEdges;
}

function searchConnectedComponent($node, $sets)
{
    foreach ($sets as $key => $set) {
        if (in_array($node, $set)) {
            return $key;
        }
    }
}

function orderEdgesWithCosts($adjacentList)
{
    $orderedEdges = array();
    for ($i = 1; $i <= MAX_COST; ++$i) { foreach ($adjacentList as $nodeFromNumber => $nodeFromValues) {
            foreach ($nodeFromValues as $nodeToNumber => $nodeToCost) {
                if ($nodeToCost == $i) {
                    $orderedEdges[] = array(
                        'cost' => $nodeToCost,
                        'n1' => $nodeFromNumber,
                        'n2' => $nodeToNumber,
                    );
                }
            }
        }
    }

    return $orderedEdges;
}

function fillRandomCosts(&$adjacentList)
{
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        $added = false;
        while (!$added) {
            for ($j = 0; $j < NUMBER_OF_EDGES_PER_NODE; ++$j) {
                $adjacentNode = rand(0, NUMBER_OF_NODES - 1);
                if ($adjacentNode != $i and $adjacentNode != $j) {
                    $adjacentNodeCost = rand(1, MAX_COST);
                    $adjacentList[$i][$adjacentNode] = $adjacentNodeCost;
                    $adjacentList[$adjacentNode][$i] = $adjacentNodeCost;
                    $added = true;
                }
            }
        }
    }
}

function printToScreenAdjacentList($adjacentList)
{
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) { echo $i; foreach ($adjacentList[$i] as $key => $value) {
            echo ' --> '.$key.'('.$value.')';
        }
        echo PHP_EOL;
    }
}

PrEDA: grafos, el algoritmo de Prim

2017-10-26 - Categorías: PHP / PrEDA
Grafos, mapas y matrices de adyacencia

Hoy vuelvo a traer otro code-kata, siguiendo con la serie de algoritmos de programación relacionados con los grafos. Esta vez se trata del algoritmo de Prim, que sirve para calcular el árbol de recubrimiento de mínimo coste de un grafo.

Es decir, tenemos un grafo que se compone de nodos, que se interconectan mediante aristas. Dichas conexiones entre nodo y nodo, tienen un coste. Entonces queremos hallar la forma de interconectar todo con el mínimo coste. Una aplicación directa de esto puede ser para una red de ordenadores, eléctrica, tuberías, carreteras, etcétera.. mediante este algoritmo puedes obtener la forma de mantener conectados todos los nodos del grafo con el mínimo coste.

Este algoritmo usa la estrategia de programación voraz. Mediante ésta se elige una forma de ir creando la solución sin rectificar volviendo atrás.

Pasos del algoritmo de Prim

Se divide en los siguientes:

  1. Se crean dos vectores, uno con los nodos que ya están en el árbol de recubrimiento mínimo (vector usados), y los que no (vector no usados).
  2. Se elige arbitrariamente el nodo raíz, se pone en el vector de los nodos del árbol usados. El resto de nodos en el vector de no usados.
  3. Se elige el siguiente nodo, de los no usados, que se conecta con alguno de los nodos usados. Pero tiene que ser el que se una a los usados con mínimo coste de la arista. Este nodo elegido se mueve del vector de los no usados al de los usados.
  4. Así sucesivamente se repite el paso 3 hasta que todos los nodos están en el vector de usados.

El paso principal es el 3, que es el que aplica la estrategia voraz.

Código

<?php

define('NUMBER_OF_NODES', 20);
define('NUMBER_OF_EDGES_PER_NODE', 2);

$adjacentList = array();
fillRandomCosts($adjacentList);
printToScreen($adjacentList);

prim($adjacentList);

function prim($adjacentList)
{
    $nodesInTree = array(0);
    $nodesNotInTree = array();
    for ($i = 1; $i < NUMBER_OF_NODES; ++$i) { $nodesNotInTree[] = $i; } while (count($nodesNotInTree) > 0) {
        $nextNodeToAdd = getNextEdge($adjacentList, $nodesInTree, $nodesNotInTree);
        $nodesInTree[] = $nextNodeToAdd;
        unset($nodesNotInTree[array_search($nextNodeToAdd, $nodesNotInTree)]);
    }
}

function getNextEdge($adjacentList, $nodesInTree, $nodesNotInTree)
{
    $minCost = 100;
    $nextNode = null;
    $edge = '';

    foreach ($nodesInTree as $node) {
        foreach ($adjacentList[$node] as $key => $value) {
            if (in_array($key, $nodesNotInTree)) {
                if ($value < $minCost) {
                    $nextNode = $key;
                    $minCost = $value;
                    $edge = $node.'-'.$key;
                }
            }
        }
    }

    echo 'IN '.implode(',', $nodesInTree)
        .' NOT IN '.implode(',', $nodesNotInTree)
        .' NEXT EDGE TO ADD '.$edge.'('.$minCost.')'.PHP_EOL;

    return $nextNode;
}

function fillRandomCosts(&$adjacentList)
{
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        $added = false;
        while (!$added) {
            for ($j = 0; $j < NUMBER_OF_EDGES_PER_NODE; ++$j) {
                $adjacentNode = rand(0, NUMBER_OF_NODES - 1);
                if ($adjacentNode != $i and $adjacentNode != $j) {
                    $adjacentNodeCost = rand(1, 5);
                    $adjacentList[$i][$adjacentNode] = $adjacentNodeCost;
                    $adjacentList[$adjacentNode][$i] = $adjacentNodeCost;
                    $added = true;
                }
            }
        }
    }
}
function printToScreen($adjacentList)
{
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) { echo $i; foreach ($adjacentList[$i] as $key => $value) {
            echo ' --> '.$key.'('.$value.')';
        }
        echo PHP_EOL;
    }
}

Marco en negrita lo principal del algoritmo que lo hace voraz, el modo de elegir el siguiente nodo que añadimos al árbol de recubrimiendo mínimo. En la variable $edge es donde vamos poniendo las siguientes aristas. En éste código simplemente se imprimen para ver cómo funciona el algoritmo y comprenderlo.

Un ejemplo

0 --> 7(4) --> 3(4)
1 --> 7(3) --> 6(3)
2 --> 14(2) --> 6(5)
3 --> 0(4) --> 9(5) --> 12(1) --> 18(1)
4 --> 8(2) --> 15(1) --> 17(5) --> 19(1)
5 --> 19(5) --> 13(4)
6 --> 2(5) --> 1(3) --> 9(5) --> 16(3)
7 --> 0(4) --> 1(3) --> 12(2) --> 16(2) --> 8(2) --> 10(2)
8 --> 4(2) --> 7(2) --> 19(2)
9 --> 3(5) --> 6(5) --> 18(1) --> 16(5)
10 --> 19(1) --> 7(2) --> 15(3)
11 --> 12(5) --> 16(3)
12 --> 7(2) --> 11(5) --> 18(4) --> 3(1)
13 --> 5(4) --> 18(3)
14 --> 2(2) --> 19(5)
15 --> 4(1) --> 10(3)
16 --> 7(2) --> 9(5) --> 11(3) --> 6(3)
17 --> 4(5)
18 --> 9(1) --> 12(4) --> 13(3) --> 3(1) --> 19(5)
19 --> 5(5) --> 8(2) --> 10(1) --> 14(5) --> 18(5) --> 4(1)
IN 0 NOT IN 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19 NEXT EDGE TO ADD 0-7(4)
IN 0,7 NOT IN 1,2,3,4,5,6,8,9,10,11,12,13,14,15,16,17,18,19 NEXT EDGE TO ADD 7-12(2)
IN 0,7,12 NOT IN 1,2,3,4,5,6,8,9,10,11,13,14,15,16,17,18,19 NEXT EDGE TO ADD 12-3(1)
IN 0,7,12,3 NOT IN 1,2,4,5,6,8,9,10,11,13,14,15,16,17,18,19 NEXT EDGE TO ADD 3-18(1)
IN 0,7,12,3,18 NOT IN 1,2,4,5,6,8,9,10,11,13,14,15,16,17,19 NEXT EDGE TO ADD 18-9(1)
IN 0,7,12,3,18,9 NOT IN 1,2,4,5,6,8,10,11,13,14,15,16,17,19 NEXT EDGE TO ADD 7-16(2)
IN 0,7,12,3,18,9,16 NOT IN 1,2,4,5,6,8,10,11,13,14,15,17,19 NEXT EDGE TO ADD 7-8(2)
IN 0,7,12,3,18,9,16,8 NOT IN 1,2,4,5,6,10,11,13,14,15,17,19 NEXT EDGE TO ADD 7-10(2)
IN 0,7,12,3,18,9,16,8,10 NOT IN 1,2,4,5,6,11,13,14,15,17,19 NEXT EDGE TO ADD 10-19(1)
IN 0,7,12,3,18,9,16,8,10,19 NOT IN 1,2,4,5,6,11,13,14,15,17 NEXT EDGE TO ADD 19-4(1)
IN 0,7,12,3,18,9,16,8,10,19,4 NOT IN 1,2,5,6,11,13,14,15,17 NEXT EDGE TO ADD 4-15(1)
IN 0,7,12,3,18,9,16,8,10,19,4,15 NOT IN 1,2,5,6,11,13,14,17 NEXT EDGE TO ADD 7-1(3)
IN 0,7,12,3,18,9,16,8,10,19,4,15,1 NOT IN 2,5,6,11,13,14,17 NEXT EDGE TO ADD 18-13(3)
IN 0,7,12,3,18,9,16,8,10,19,4,15,1,13 NOT IN 2,5,6,11,14,17 NEXT EDGE TO ADD 16-11(3)
IN 0,7,12,3,18,9,16,8,10,19,4,15,1,13,11 NOT IN 2,5,6,14,17 NEXT EDGE TO ADD 16-6(3)
IN 0,7,12,3,18,9,16,8,10,19,4,15,1,13,11,6 NOT IN 2,5,14,17 NEXT EDGE TO ADD 13-5(4)
IN 0,7,12,3,18,9,16,8,10,19,4,15,1,13,11,6,5 NOT IN 2,14,17 NEXT EDGE TO ADD 19-14(5)
IN 0,7,12,3,18,9,16,8,10,19,4,15,1,13,11,6,5,14 NOT IN 2,17 NEXT EDGE TO ADD 14-2(2)
IN 0,7,12,3,18,9,16,8,10,19,4,15,1,13,11,6,5,14,2 NOT IN 17 NEXT EDGE TO ADD 4-17(5)

Como tenemos 20 nodos, para tenerlos todos conectados nos salen 19 aristas.


PrEDA: grafos y mapas, ahora guardando en una lista de adyacencia..

2017-10-23 - Categorías: PHP / PrEDA
Grafos, mapas y matrices de adyacencia

Continuando con el post de ayer sobre cómo crear una matriz de adyacencia a partir de un mapa aleatorio, traigo otro code-kata. Es el mismo ejercicio de ayer, pero hoy para sacar en claro cómo almacenar un grafo en una lista de adyacencia.

¿Porqué una lista o matriz de adyacencia va a ser mejor o peor? Dependerá de cada grafo. Si el grafo es muy denso, porque tiene muchas aristas entre nodo y nodo, está demostrado que es mejor usar una matriz. Pero si el grafo es poco denso es mejor usar una lista de adyacencia.

Igual que en el post de ayer, el escenario consiste en un mapa aleatorio, y nos podemos mover de casilla en casilla haciendo movimientos de peón de ajedrez. El coste de hacer cada movimiento, es el número que ponga en la casilla de destino. La interpretación de estos datos del mapa puede variar según lo que necesites.

Al grano

Un mapa generado aleatoriamente:

   |  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  
----------------------------------------------------------------------
0  |  9   3   0   8   1   6   0   7   5   6   9   7   5   9   9   7   
1  |  4   5   2   7   9   5   9   3   0   6   0   6   8   3   7   6   
2  |  9   4   3   7   5   8   2   6   1   0   7   5   5   6   9   4   
3  |  7   3   9   4   5   2   9   9   1   1   8   5   0   6   9   0   
4  |  5   8   7   2   1   2   5   1   7   8   7   1   4   4   8   0   
5  |  0   6   7   6   4   2   6   0   3   6   6   2   4   9   8   6

Igual que en post de ayer, tenemos que numerar cada casilla para orientarnos. Como tenemos 6 filas con 16 columnas nos salen 96 nodos en este grafo:

   |  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  
----------------------------------------------------------------------
0  |  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  
1  |  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  
2  |  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  
3  |  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  
4  |  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  
5  |  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95

Qué es una lista de adyacencia

Es un array/vector/lista en la que cada elemento es a su vez otra lista/vector/array con los elementos adyacentes a dicho nodo. Para este ejemplo, su lista de adyacencia queda así:

0   --> 1(3) --> 16(4) --> 17(5)
1   --> 0(9) --> 2(0) --> 16(4) --> 17(5) --> 18(2)
2   --> 1(3) --> 3(8) --> 17(5) --> 18(2) --> 19(7)
3   --> 2(0) --> 4(1) --> 18(2) --> 19(7) --> 20(9)
4   --> 3(8) --> 5(6) --> 19(7) --> 20(9) --> 21(5)
5   --> 4(1) --> 6(0) --> 20(9) --> 21(5) --> 22(9)
6   --> 5(6) --> 7(7) --> 21(5) --> 22(9) --> 23(3)
7   --> 6(0) --> 8(5) --> 22(9) --> 23(3) --> 24(0)
8   --> 7(7) --> 9(6) --> 23(3) --> 24(0) --> 25(6)
9   --> 8(5) --> 10(9) --> 24(0) --> 25(6) --> 26(0)
10  --> 9(6) --> 11(7) --> 25(6) --> 26(0) --> 27(6)
11  --> 10(9) --> 12(5) --> 26(0) --> 27(6) --> 28(8)
12  --> 11(7) --> 13(9) --> 27(6) --> 28(8) --> 29(3)
13  --> 12(5) --> 14(9) --> 28(8) --> 29(3) --> 30(7)
14  --> 13(9) --> 15(7) --> 29(3) --> 30(7) --> 31(6)
15  --> 14(9) --> 30(7) --> 31(6)
16  --> 0(9) --> 1(3) --> 17(5) --> 32(9) --> 33(4)
17  --> 0(9) --> 1(3) --> 2(0) --> 16(4) --> 18(2) --> 32(9) --> 33(4) --> 34(3)
18  --> 1(3) --> 2(0) --> 3(8) --> 17(5) --> 19(7) --> 33(4) --> 34(3) --> 35(7)
19  --> 2(0) --> 3(8) --> 4(1) --> 18(2) --> 20(9) --> 34(3) --> 35(7) --> 36(5)
20  --> 3(8) --> 4(1) --> 5(6) --> 19(7) --> 21(5) --> 35(7) --> 36(5) --> 37(8)
..
etcétera

Si nos fijamos en la primera línea, tenemos que a partir del nodo que es el 0 podemos ir al 1, 16 y 17. Con sus costes entre paréntesis. Igualmente para el resto de los nodos.

El código

A partir del otro post, el código es bien sencillo con una pequeña modificación:

<?php
/**
 * This script makes a random map filled with costs of walking throw each box. Moving from
 * a position to an adjacent are the only possible movements. Then, is calculated an adjacent list
 * to represent the graph.
 */
define('NUMBER_OF_ROWS', 6);
define('NUMBER_OF_COLS', 16);
define('NUMBER_OF_NODES', NUMBER_OF_ROWS * NUMBER_OF_COLS);

// Fill random map.
$randomMap = array();
for ($row = 0; $row < NUMBER_OF_ROWS; ++$row) {
    for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
        $randomMap[$row][$col] = rand(0, 9);
    }
}

// Fill adjacent list.
$adjacentList = array();
for ($from = 0; $from < NUMBER_OF_NODES; ++$from) {
    for ($to = 0; $to < NUMBER_OF_NODES; ++$to) {
        if ($from == $to) {
            //$adjacentList[$from][$to] = 0;
        } else {
            $fromRow = floor($from / NUMBER_OF_COLS);
            $fromCol = $from % NUMBER_OF_COLS;
            $toRow = floor($to / NUMBER_OF_COLS);
            $toCol = $to % NUMBER_OF_COLS;

            //echo 'from '.$from.' to '.$to
            //.': fromRow '.$fromRow.' fromCol '.$fromCol
            //.', toRow '.$toRow.' toCol '.$toCol.PHP_EOL;

            // If is adjacent box, save node to list..
            if (abs($fromCol - $toCol) <= 1
            and abs($fromRow - $toRow) <= 1) {
                $adjacentList[$from][$to] = $randomMap[$toRow][$toCol];
            } else {
                //$adjacentList[$from][$to] = 0;
            }
        }
    }
}

// Print map.
echo PHP_EOL;
echo '   |  ';
for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
    echo str_pad($col, 4, ' ');
}
echo PHP_EOL;
echo '------';
for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
    echo '----';
}
echo PHP_EOL;
for ($row = 0; $row < NUMBER_OF_ROWS; ++$row) {
    echo str_pad($row, 3, ' ').'|  ';
    for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
        echo str_pad($randomMap[$row][$col], 4, ' ');
    }
    echo PHP_EOL;
}

// Print map positions.
$currentPosition = 0;
echo PHP_EOL;
echo '   |  ';
for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
    echo str_pad($col, 4, ' ');
}
echo PHP_EOL;
echo '------';
for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
    echo '----';
}
echo PHP_EOL;
for ($row = 0; $row < NUMBER_OF_ROWS; ++$row) {
    echo str_pad($row, 3, ' ').'|  ';
    for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
        echo str_pad($currentPosition, 4, ' ');
        ++$currentPosition;
    }
    echo PHP_EOL;
}

// Print adjacent list.
echo PHP_EOL;
for ($from = 0; $from < NUMBER_OF_NODES; ++$from) { echo str_pad($from, 3, ' '); 
    foreach ($adjacentList[$from] as $node => $cost) {
        echo ' --> '.$node.'('.$cost.')';
    }
    echo PHP_EOL;
}

He marcado en negrita lo principal del algoritmo de llenado de la lista de adyacencia. No necesitamos tener un mapa de nodos numerados, pero sí que necesitamos tener en mente que existe la numeración que comento antes. Así de esta forma, para averiguar si dos nodos son adyacentes, y es posible así moverse de uno a otro, se usa esta numeración.

Es curioso ver que en PHP se trabaja igual una matriz que una lista dinámica. Así sólo con guardar los destinos accesibles nos basta, he dejado comentado el código que ponía a 0 los destinos innaccesibles de la matriz anterior.


PrEDA: grafos, generando mapas aleatorios y su matriz de adyacencia..

2017-10-22 - Categorías: PHP / PrEDA
Grafos, mapas y matrices de adyacencia

Vuelvo de nuevo a traer otro code-kata. Esta vez estoy tratando de sacar en claro cómo generar matrices de adyacencia para trabajar con los grafos asociados a mapas. En este escenario tenemos un mapa, que se genera aleatoriamente. En cada casilla tenemos un coste de movernos a dicha casilla. Sólo podemos movernos a la casilla adyacente, como si se tratara del movimiento de un peón de ajedrez.

Así pues, si estamos en la casilla (0,0) sólo podremos movernos a la (0,1), (1,1) y la de abajo, la (1,0). Así que ese coste de ese movimiento se representa por el valor del mapa generado. Y ese coste se guarda en la matriz de adyacencia como valor de la arista.

Continuar leyendo..

PrEDA: el algoritmo de ordenamiento Mergesort

2017-10-09 - Categorías: PHP / PrEDA
Números

De nuevo con otro code-kata ya estoy por aquí de nuevo. Se trata ahora de un algoritmo más sencillo que los anteriores. El Heapsort se apoya en montículos para su ordenamiento. El Quicksort hace un pivotaje algo complejo para hacer la división del vector en dos más simples. En este caso, el Mergesort, hace un ordenamiento más simple.

Mergesort aplica la estrategia de divide y vencerás para hacer el ordenamiento. Con esto, tenemos que un vector de números desordenado se divide en dos. Estos dos subvectores se ordenan por separado usando Mergesort recursivamente. Y al tenerlos ordenados, se fusionan en un vector final cogiendo elementos de uno u otro vector en orden creciente.

Continuar leyendo..

© 2020 JnjSite.com - MIT license

Sitio hecho con WordPress, diseño y programación del tema por Jnj.