El algoritmo general de b煤squeda en grafos

2021-05-17 - Categor铆as: Inteligencia Artificial / PHP

Este post es sobre una algoritmo que es la madre del cordero de muchos algoritmos de b煤squeda 馃ぃ Se puede considerar un algoritmo base para b煤squedas, sobre el que se puede evolucionar hacia otros algoritmos. No he encontrado su implementaci贸n en PHP, as铆 que aqu铆 estoy compartiendo, a modo de codekata, este howto.

Este algoritmo general de b煤squeda en grafos, es un algoritmo elaborado para solucionar problemas inteligentemente representados mediante grafos. No aplica ninguna predicci贸n sobre los siguientes caminos a seguir mientras se hace la b煤squeda, pero tampoco es un algoritmo de fuerza bruta.

Lo propuso Nilsson en 1971, as铆 que tiene ya su recorrido. A partir de 茅ste se han generado todo tipo de mejoras, heur铆sticas, desembocando en todo tipo de variantes que mejorar谩n el rendimiento como por ejemplo el A*, IDA, SMA*, Dijkstra, etc茅tera..

Porqu茅 los grafos, d贸nde se usan

Los grafos pueden representar muchas cosas, como por ejemplo el recorrido de laberintos, la navegaci贸n por mapas, la b煤squeda de soluciones a juegos de tablero, el c贸mo generar comportamientos inteligentes en videojuegos, robots que se mueven por escenarios conocidos o desconocidos, b煤squeda de soluciones a problemas que implican desgranar 谩rboles (que son un tipo de grafos), etc茅tera..

Hay muchas variantes seg煤n los nodos o los arcos. Pueden ser dirigidos o no, seg煤n sus arcos tengan direcci贸n o no. Tambi茅n dichos arcos pueden tener pesos o costes, los nodos tambi茅n. Adem谩s de que en cada nodo podemos tener toda la informaci贸n que se necesite.

Con todo esto junto, y atendiendo a los algoritmos para resolver los problemas, tendremos sus variantes.

C贸mo representar escenarios en grafos

Como caso general, este codekata plantea un escenario simple, en el que hay que ir de un punto A a un punto B. Lo siguiente para comprender el funcionamiento, es comprender c贸mo representar un escenario en un grafo. Por ejemplo, supongamos este escenario en el que tenemos que alcanzar el punto B con el menor coste. Se puede pasar por las casillas en blanco mientras que las X representan muros:

AXXXXXXXXX
XXXXXXXXX
XXXXXXXX
XXXXXXXXXX
XXXB

Una de las formas de elaborar este grafo podr铆a ser simplemente numerar las casillas y crear una matriz de adyacencia. En esta matriz de adyacencia tendr铆amos desde qu茅 nodo podemos ir a qu茅 otro nodo. Para el caso del escenario anterior tendr铆amos que tenemos 5 filas por 30 columnas, son 150 casillas, es decir, 150 nodos.

0510XXXXXXX
1611XXXXXXXX
2712XXXXXXX
3813XXXXXXXXX
49EtcXXXB

As铆 de esta manera se podr铆a ver que de la casilla 0 se puede saltar a la casilla 1, pero no a la 5 ni la 6 seg煤n el mapa anterior. As铆 de esta manera, esta matriz de adyacencia para la fila de la casilla 0 quedar铆a en todos ceros menos un 1 en la casilla 1. Entonces, desde la casilla 1 se puede volver a la 0, o ir a la 2. As铆 sucesivamente:

$casilla[0] = [0,1,0,0,0,0,0..0];
$casilla[1] = [1,0,1,0,0,0,0..0];
..

En el siguiente apartado ya con c贸digo se puede ver m谩s sencillo.

Generando grafos aleatoriamente en PHP

Recapitulando, la representaci贸n de muchos problemas se puede hacer mediante grafos. As铆 que el siguiente paso ser铆a generar un sencillo script para generar grafos aleatorios. Eligiendo como sistema de representaci贸n una matriz de adyacencia podr铆a quedar algo tal que as铆:

define('NUMBER_OF_NODES', 30);

$adjacentMatrix = [];
for ($from = 0; $from < NUMBER_OF_NODES; ++$from) {
    for ($to = 0; $to < NUMBER_OF_NODES; ++$to) {
        $adjacentMatrix[$from][$to] = 0 == rand(0, (int) NUMBER_OF_NODES / 10) ? rand(0, 9) : 0;
    }
}

Simplemente adjacentMatrix[i][j] representa el coste de ir del nodo i al j. Los valores se generan aleatoriamente, y no es muy denso el grafo, ya que no tiene muchos arcos, porque randomizando los valores s贸lo se rellenan algunos.

Los conjuntos, la l贸gica principal del algoritmo

La l贸gica principal se basa en llevar dos conjuntos de datos. Ya tenemos el grafo definido aleatoriamente, ahora toca ir del punto A al B. Para esto se va a llevar la informaci贸n de dos conjuntos definidos como:

  • Conjunto abierto.
  • Conjunto cerrado.

El conjunto abierto ser谩 el que lleve los nodos que podemos expandir, usar para recorrer, que todav铆a no se hayan usado. La manera de ordenar, o de elegir el siguiente nodo, define variantes del algoritmo general.

De esta forma tendremos entonces que en el conjunto cerrado, almacenaremos los nodos encontrados, con su distancia o coste, nodos anteriores y posteriores posibles. Si un nodo no se ha recorrido, entonces se a帽adir谩 al conjunto abierto cuando se encuentre, si es que no es el nodo objetivo.

Y as铆 sucesivamente se ir谩n sacando nodos del conjunto abierto, mientras que se meten en el conjunto cerrado calculando sus valores y tambi茅n en el conjunto abierto si son nuevos.

* Lo especial del algoritmo es que, si un nodo ya se ha alcanzado anteriormente por lo que ya est谩 en el conjunto cerrado, hay que recalcular sus valores y los de los nodos relacionados, por si hemos llegado con un camino mejor que el que hab铆a almacenado.

Punto de partida

Partiendo de que para este codekata siempre partimos del nodo 0, entonces tenemos que inicializar los conjuntos:

$OPEN_SET = [0];
$CLOSED_SET = [
    0 => [
        'father' => null,
        'children' => [],
        'cost' => 0,
    ],
];

La parte principal del algoritmo

Todo el n煤cleo del algoritmo quedar铆a con algo tal que as铆:

///////////////
// MAIN
// Searching in the graphs.

// Initially adding the starting node 0..
// The format for CLOSED is: node => [$father, [children], cost]
$OPEN_SET = [0];
$CLOSED_SET = [
    0 => [
        'father' => null,
        'children' => [],
        'cost' => 0,
    ],
];

// Get the goal node from the user input..
echo  'Start node is 0..'.PHP_EOL
    .'Which will be the goal node to achieve (1 to '.(NUMBER_OF_NODES - 1).')? ';
$goalNode = readline();

// Start the main search..
$startTime = microtime(true);
echo 'Expanding nodes: ';
while (!empty($OPEN_SET)) {
    $currentExpandingNode = array_shift($OPEN_SET);
    echo $currentExpandingNode.'-';

    if ($currentExpandingNode == $goalNode) {
        returnTheWay($currentExpandingNode);
        echo 'Time spent: '.(microtime(true) - $startTime).'secs.'.PHP_EOL;
        exit;
    }
    $childrenNodes = getChildrenNodes($currentExpandingNode);
    $CLOSED_SET[$currentExpandingNode]['children'] = $childrenNodes;
    foreach ($childrenNodes as $childNode) {
        if (isset($CLOSED_SET[$childNode])) {
            // It's already in closed set..
            fixClosedSet($childNode, $currentExpandingNode, $adjacentMatrix[$currentExpandingNode][$childNode]);
            orderOpenSet();
        } else {
            // It's a new one..
            $CLOSED_SET[$childNode] = [
                'father' => $currentExpandingNode,
                'children' => [],
                'cost' => $CLOSED_SET[$currentExpandingNode]['cost']
                    + $adjacentMatrix[$currentExpandingNode][$childNode],
            ];
            mixOpenSet($childNode);
        }
    }
}
// END MAIN
///////////////////////

Tiene a帽adido el preguntar al usuario por el nodo destino.

Funciones anexas al algoritmo

Una funci贸n que recorrer铆a la matriz de adyacencia para pintarla por pantalla podr铆a ser tal que as铆:

// Print adjacent matrix..
function printAdjacentMatrix()
{
    global $adjacentMatrix;

    echo 'ADJACENT MATRIX'.PHP_EOL;
    echo '   | ';
    for ($col = 0; $col < NUMBER_OF_NODES; ++$col) {
        echo str_pad($col, 3, ' ');
    }
    echo PHP_EOL;
    echo '------';
    for ($col = 0; $col < NUMBER_OF_NODES; ++$col) {
        echo '---';
    }
    echo PHP_EOL;
    for ($from = 0; $from < NUMBER_OF_NODES; ++$from) {
        echo str_pad($from, 3, ' ').'| ';
        for ($to = 0; $to < NUMBER_OF_NODES; ++$to) {
            echo str_pad($adjacentMatrix[$from][$to], 3, ' ');
        }
        echo PHP_EOL;
    }
}

Para sacar los nodos hijos, o lo que es lo mismo, los nodos adyacentes:

function getChildrenNodes($currentNode)
{
    global $adjacentMatrix;

    $childrenNodes = [];
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        if ($i != $currentNode and $adjacentMatrix[$currentNode][$i] > 0) {
            $childrenNodes[] = $i;
        }
    }

    return $childrenNodes;
}

Al a帽adir nuevos nodos al conjunto abierto, simplemente se a帽aden en el algoritmo general, con lo que simplemente se a帽aden al array del conjunto:

// Simply add node now..
function mixOpenSet($childNode)
{
    global $OPEN_SET;
    $OPEN_SET[] = $childNode;
}

La citada anteriormente funci贸n de ordenaci贸n para el conjunto abierto. Aqu铆 se establece el criterio de ordenaci贸n de los nodos siguientes que vamos a elegir para seguir el recorrido. Como se trata del algoritmo general simplemente no se ordenan. En el caso de derivaciones del algoritmo pueden ordenarse. As铆 que:

// Do nothing, not ordering..
function orderOpenSet()
{
}

Estas siguientes dos funciones van juntas, porque se encargan de recalcular los costes de los caminos si llegamos a un nodo, por un arco nuevo, al que ya hab铆amos llegado antes. Si el nuevo camino tiene un coste menor, es decir, que es un mejor camino, entonces hay que recalcular los caminos:

// Recursive function to check and update costs and ways when necessary..
function fixClosedSet($childNode, $currentExpandingNode, $costToNewFromCurrent)
{
    global $CLOSED_SET;

    $currentCost = $CLOSED_SET[$childNode]['cost'];
    $newCost = $CLOSED_SET[$currentExpandingNode]['cost'] + $costToNewFromCurrent;

    if ($currentCost > $newCost) {
        $CLOSED_SET[$childNode]['cost'] = $newCost;
        $CLOSED_SET[$childNode]['father'] = $currentExpandingNode;
        fixClosedSetList($childNode);
    }
}

function fixClosedSetList($node)
{
    global $CLOSED_SET, $adjacentMatrix;

    foreach ($CLOSED_SET[$node]['children'] as $child) {
        fixClosedSet($child, $node, $adjacentMatrix[$node][$child]);
    }
}

Y finalmente, la 煤ltima funci贸n del codekata, que simplemente se usa cuando hemos alcanzado el nodo meta. De la forma en que si hemos llegado al nodo final, recorre hacia atr谩s el camino que hemos ido almacenando en el conjunto cerrado, que ser谩 el mejor camino de menor coste.

// Goes up node by node printing the way..
function returnTheWay($currentExpandingNode)
{
    global $CLOSED_SET;
    //var_dump($CLOSED_SET);

    echo 'GOAL NODE FOUND!'.PHP_EOL;
    $current = $currentExpandingNode;
    $auxStr = $current.'('.$CLOSED_SET[$current]['cost'].')';

    while (0 != $current) {
        $current = $CLOSED_SET[$current]['father'];
        $auxStr = $current.'('.$CLOSED_SET[$current]['cost'].') -> '.$auxStr;
        //echo $auxStr.PHP_EOL;
        //sleep(1);
    }
    echo $auxStr.PHP_EOL;
}

Si el codekata ha ido bien, guardando todo en un fichero y ejecut谩ndolo desde l铆nea de comandos, se deber铆a de ver algo como lo siguiente:

Deja una respuesta

Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *

 

漏 2021 JnjSite.com - MIT license

Sitio hecho con WordPress, dise帽o y programaci贸n del tema por Jnj.