Comparando algoritmos de búsqueda en grafos • JnjSite.com

Comparando el AGBG con anchura, profundidad, BF y A*..

Aquí puedes encontrar un howto o codekata en PHP, en el que se comparan algunos algoritmos de recorridos de grafos. Este post es continuación del post anterior sobre el algoritmo general de recorrido en grafos.

A partir del algoritmo general, tenemos derivados cuatro algoritmos más. Dos de estos algoritmos son de los básicos, y dos aplican técnicas heurísticas. Los heurísticos tratan de predecir qué camino usar primero para alcanzar antes el nodo meta.

Partiendo del post anterior, simplemente se va modificando la forma en que los algoritmos usan OPEN_SET y CLOSED_SET..

Generando una clase común con el tipo de objeto grafo

Ahora simplemente por cumplir el principio DRY encapsulamos el objeto Graph con algunas funciones que se usa comunmente en todos estos algorimos del codekata:

<?php

class Graph
{
    private $numberOfNodes;
    private $adjacentMatrix;

    public function __construct($numberOfNodes)
    {
        $this->numberOfNodes = $numberOfNodes;
        $this->adjacentMatrix = [];
    }

    public function getNumberOfNodes()
    {
        return $this->numberOfNodes;
    }

    public function generateRandomGraph()
    {
        for ($from = 0; $from < $this->numberOfNodes; ++$from) {
            for ($to = 0; $to < $this->numberOfNodes; ++$to) {
                $this->adjacentMatrix[$from][$to] = 0 == rand(0, (int) $this->numberOfNodes / 10) ? rand(0, 9) : 0;
            }
        }
    }

    public function getArc($i, $j)
    {
        return $this->adjacentMatrix[$i][$j];
    }

    public function printAdjacentMatrix()
    {
        echo 'ADJACENT MATRIX'.PHP_EOL;
        echo '  | ';
        for ($col = 0; $col < $this->numberOfNodes; ++$col) {
            echo $col % 10;
        }
        echo PHP_EOL;
        echo '----';
        for ($col = 0; $col < $this->numberOfNodes; ++$col) {
            echo '-';
        }
        echo PHP_EOL;
        for ($from = 0; $from < $this->numberOfNodes; ++$from) {
            echo($from % 10).' | ';
            for ($to = 0; $to < $this->numberOfNodes; ++$to) {
                echo $this->adjacentMatrix[$from][$to];
            }
            echo PHP_EOL;
        }
    }

    public function getChildrenNodes($currentNode)
    {
        $childrenNodes = [];
        for ($i = 0; $i < $this->numberOfNodes; ++$i) {
            if ($i != $currentNode and $this->adjacentMatrix[$currentNode][$i] > 0) {
                $childrenNodes[] = $i;
            }
        }

        return $childrenNodes;
    }

    public function returnTheWay($CLOSED_SET, $finalNode)
     {
        echo 'GOAL NODE FOUND!'.PHP_EOL;
        $current = $finalNode;
        $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;
    }
}

El algoritmo general de recorrido en grafos refactorizado

Con respecto al post anterior, ha cambiado que ahora el conjunto OPEN_SET almacena una variable ‘n’ para hacerlo más legible. Además, al añadir nodoso a OPEN_SET se hace una mezcla aleatoria para que varíe con respecto a los siguientes algoritmos. Luego en este conjunto OPEN_SET se almacenan más variables para variar los recorridos:

<?php

///////////////
// MAIN
echo 'GENERAL SEARCH IN GRAPHS:'.PHP_EOL;

// Initially adding the starting node 0..
$OPEN_SET = [
    0 => [
        'n' => 0,
    ],
];
$CLOSED_SET = [
    0 => [
        'father' => null,
        'children' => [],
        'cost' => 0,
    ],
];

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

    echo $currentExpandingNode.'-';

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

class General
{
    public static 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;
            General::fixClosedSetList($childNode);
        }
    }

    public static function fixClosedSetList($node)
    {
        global $CLOSED_SET, $graph;

        foreach ($CLOSED_SET[$node]['children'] as $child) {
            General::fixClosedSet($child, $node, $graph->getArc($node, $child));
        }
    }

    public static function orderOpenSet()
    {
    }

    public static function mixOpenSet($childNode)
    {
        global $OPEN_SET;

        $OPEN_SET[] = ['n' => $childNode];
        shuffle($OPEN_SET);
    }
}

El algoritmo de búsqueda en anchura

En éste algorimo sólo cambia que al añadir nodos en OPEN_SET se añaden en forma de cola FIFO. Así se consigue un recorrido por niveles:

<?php

///////////////
// MAIN
echo 'IN WIDTH:'.PHP_EOL;

// Initially adding the starting node 0..
$OPEN_SET = [
    0 => [
        'n' => 0,
    ],
];
$CLOSED_SET = [
    0 => [
        'father' => null,
        'children' => [],
        'cost' => 0,
    ],
];

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

    echo $currentExpandingNode.'-';

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

class InWidth
{
    public static 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;
            InWidth::fixClosedSetList($childNode);
        }
    }

    public static function fixClosedSetList($node)
    {
        global $CLOSED_SET, $graph;

        foreach ($CLOSED_SET[$node]['children'] as $child) {
            InWidth::fixClosedSet($child, $node, $graph->getArc($node, $child));
        }
    }

    public static function orderOpenSet()
    {
    }

    public static function mixOpenSet($childNode)
    {
        global $OPEN_SET;

        array_push($OPEN_SET, ['n' => $childNode]);
    }
}

El algoritmo de búsqueda en profundidad

Para conseguir este recorrido de primero en profundidad sólo cambia que ahora OPEN_SET se usa como una pila, como una lista LIFO (Last In First Out):

<?php

///////////////
// MAIN
echo 'IN DEPTH:'.PHP_EOL;

// Initially adding the starting node 0..
$OPEN_SET = [
    0 => [
        'n' => 0,
    ],
];
$CLOSED_SET = [
    0 => [
        'father' => null,
        'children' => [],
        'cost' => 0,
    ],
];

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

    echo $currentExpandingNode.'-';

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

class InDepth
{
    public static 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;
            InDepth::fixClosedSetList($childNode);
        }
    }

    public static function fixClosedSetList($node)
    {
        global $CLOSED_SET, $graph;

        foreach ($CLOSED_SET[$node]['children'] as $child) {
            InDepth::fixClosedSet($child, $node, $graph->getArc($node, $child));
        }
    }

    public static function orderOpenSet()
    {
    }

    public static function mixOpenSet($childNode)
    {
        global $OPEN_SET;

        array_unshift($OPEN_SET, ['n' => $childNode]);
    }
}

El algoritmo primero el mejor o coste uniforme

En éste algoritmo cambia que ahora tenemos una predicción de qué siguiente nodo será mejor elegir. Entonces en OPEN_SET almacenamos un valor de f, que representará esa idoneidad. De esta manera con este valor de f se ordenará OPEN_SET para extraer primero los mejores nodos a expandir.

Arbitrariamente tenemos elegido el valor de f como el coste de llegar desde el nodo anterior, pero se podría haber elegido cualquier otro valor en función del problema. Si se elige que el valor de f sea el coste desde el nodo inicial al actual entonces tendríamos el algoritmo de coste uniforme.

<?php

///////////////
// MAIN
echo 'BEST FIRST:'.PHP_EOL;

// Initially adding the starting node 0..
$OPEN_SET = [
    0 => [
        'n' => 0,
        'f' => null,
    ],
];
$CLOSED_SET = [
    0 => [
        'father' => null,
        'children' => [],
        'cost' => 0,
    ],
];

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

    echo $currentExpandingNode.'-';

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

class BestFirst
{
    public static 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;
            BestFirst::fixClosedSetList($childNode);
        }
    }

    public static function fixClosedSetList($node)
    {
        global $CLOSED_SET, $graph;

        foreach ($CLOSED_SET[$node]['children'] as $child) {
            BestFirst::fixClosedSet($child, $node, $graph->getArc($node, $child));
        }
    }

    public static function orderOpenSet()
    {
        global $OPEN_SET;

        usort($OPEN_SET, function ($node1, $node2) {
            return $node1['f'] > $node2['f'];
        });
    }

    public static function mixOpenSet($childNode, $f)
    {
        global $OPEN_SET;

        $OPEN_SET[] = [
            'n' => $childNode,
            'f' => $f,
        ];

        BestFirst::orderOpenSet();
    }
}

El algoritmo A*

Este algoritmo es otra variante del AGBG en el que tenemos un valor para predecir siguientes nodos mejores a expandir. En este algoritmo tenemos también una función f, que ordenará OPEN_SET para expandir primero los mejores nodos.

La función f en A* se llena con dos valores g y h. El valor de g corresponde al coste desde el nodo inicial hasta el nodo en curso, mientras que el valor de h es una predicción de coste hasta el nodo final. Para el valor heurístico de h tenemos arbitrariamente el coste del siguiente salto, pero se podría haber construido como quisiéramos:

<?php

///////////////
// MAIN
echo 'A*:'.PHP_EOL;

// Initially adding the starting node 0..
$OPEN_SET = [
    0 => [
        'n' => 0,
        'f' => null,
    ],
];
$CLOSED_SET = [
    0 => [
        'father' => null,
        'children' => [],
        'cost' => 0,
    ],
];

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

    echo $currentExpandingNode.'-';

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

class AStar
{
    public static 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;
            AStar::fixClosedSetList($childNode);
        }
    }

    public static function fixClosedSetList($node)
    {
        global $CLOSED_SET, $graph;

        foreach ($CLOSED_SET[$node]['children'] as $child) {
            AStar::fixClosedSet($child, $node, $graph->getArc($node, $child));
        }
    }

    public static function orderOpenSet()
    {
        global $OPEN_SET;

        usort($OPEN_SET, function ($node1, $node2) {
            return $node1['f'] > $node2['f'];
        });
    }

    public static function mixOpenSet($childNode, $g, $h)
    {
        global $OPEN_SET;

        $OPEN_SET[] = [
            'n' => $childNode,
            'f' => $g + $h,
        ];

        AStar::orderOpenSet();
    }
}

Uniendo todo en un mismo script

Ya sólo queda el script que los prueba todos los algoritmos con un mismo Grafo. Si todo va bien debería de verse algo como en la imagen del principio.

<?php

include 'Graph.php';

$graph = new Graph(200);
$graph->generateRandomGraph();
$graph->printAdjacentMatrix();

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

echo PHP_EOL;
include 'algorithmGeneral.php';
echo PHP_EOL;
include 'algorithmInWidth.php';
echo PHP_EOL;
include 'algorithmInDepth.php';
echo PHP_EOL;
include 'algorithmBestFirst.php';
echo PHP_EOL;
include 'algorithmAStar.php';