PHP

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 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.

Continuar leyendo..

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.

Continuar leyendo..

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..

PrEDA: el algoritmo de ordenamiento Heapsort

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

De nuevo traigo a modo de code-kata otro algoritmo de programación. En este caso no se usa ninguna técnica avanzada de programación. Sino que simplemente se usa el algoritmo de ordenamiento Heapsort, que como su nombre indica, se sirve de un heap (montículo) para hacer el ordenamiento.

Como ya hablé en este otro post sobre los montículos, he reutilizado el código para hacer un par de clases genéricas que nos pueden servir para construir algoritmos más avanzados.

PHP ya nos provee de una clase que implementa un montículo, el SplHeap. También tenemos en PHP una clase para un SplMinHeap y SplMaxHeap. Pero no podemos controlar cómo hacemos la valoración de mínimo o máximo para poner arriba del montículo los objetos ordenados. Así que no queda más remedio que extender la clase que nos provee PHP.

Continuar leyendo..

PrEDA: el algoritmo de ordenamiento Quicksort

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

Vuelvo a la carga con los algoritmos de programación. Hoy traigo a modo de code-kata el algoritmo de ordenamiento Quicksort. En este algoritmo se utiliza la estrategia de programación divide y vencerás. Aplicándola, vamos dividiendo un vector inicial no ordenado, en subvectores que vamos a dividir una y otra vez recursivamente, hasta tener todos los elementos ordenados.

Antes de dividir un vector en dos subvectores se aplica una técnica de pivotaje. Con este pivotaje de los elementos, obtendremos el vector dividido en 2 partes, más un elemento central llamado pivote. Este elemento pivote hará que en la parte izquierda del vector todos los elementos sean menores que el pivote. Y a su vez, en la parte derecha, todos los elementos serán mayores que el pivote.

Continuar leyendo..

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

2017-09-06 - Categorías: PHP / PrEDA
Heap min max

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.

Continuar leyendo..

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

2017-09-03 - Categorías: PHP / PrEDA
PrEDA latin square

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.

Continuar leyendo..

PrEDA: el juego de las Torres de Hanói

2017-08-30 - Categorías: PHP / PrEDA
php7-logo

Hoy traigo otro enigma matemático resuelto a modo de code-kata, un rompecabezas llamado las Torres de Hanói. El juego consiste en tres torres compuestas por discos que se apilan de forma decreciente, de forma que los discos de abajo siempre son mayores que los de arriba. Con cada movimiento sólo podemos mover un disco. Y tenemos que conseguir mover todos los discos que inicialmente están todos en la torre A a la torre B.

Haciendo ensayos, pruebas, partiendo de casos fáciles a más difíciles se puede establecer una estrategia por la cual se van moviendo todos los discos. Este problema bien conocido en computación se resuelve mediante la estrategia de divide y vencerás. Dividiendo el problema inicial, todos los discos en una torre, en subproblemas cada vez más sencillos y fáciles de abordar.

Se trata de un algoritmo recursivo. Cuyo caso base es mover un sólo disco. Si no estamos moviendo un sólo disco se subdivide en 2 problemas y se mueve un disco.

Continuar leyendo..

PrEDA: el problema del Salto del Caballo de ajedrez

2017-08-29 - Categorías: PHP / PrEDA
php7-logo

Hoy traigo otro code-kata para practicar con estructuras de datos y algoritmos. El problema del caballo es un clásico problema matemático. Consiste en recorrer todas las casillas de un tablero de ajedrez sin repetirlas y a salto del caballo.

Esta vez, la forma más sencilla de abordarlo es simular el salto del caballo haciendo un árbol de posibles recorridos del caballo hasta conseguir llenar el tablero por completo. Es decir, partimos de una casilla, este será el nodo inicial del árbol. Entonces los hijos de cada nodo son los caminos posibles desde el nodo inicial hasta las casillas posibles siguientes. Si estamos en un tablero de 8×8, y hemos llegado a un nivel de ramificación de 64 quiere decir que hemos recorrido todas las casillas que hay. Entonces habríamos resuelto una de las soluciones.

La mejor forma de resolver este problema es por la estrategia de vuelta atrás. Es decir, se va ramificando mientras que el caballo va saltando. Si llega a una casilla en la que ya no tiene casillas a las que saltar se vuelve atrás, para entonces seguir ramificando por el resto de posibles caminos. Esto con una función recursiva queda bien sencillo.

Continuar leyendo..

© 2024 JnjSite.com - MIT license

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