PrEDA

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 😉

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.

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;
    }
}

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.

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.

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.