Algoritmos de búsqueda en grafos

Los algoritmos de búsqueda en grafos nacen por la necesidad de crear un mecanismo de navegación autónoma, bien sea de robots, coches, o personajes en un videojuego. Algunos de los más conocidos son DFS, BFS, A*, IDA*, Fringe Search o D*.

Descripción

Un grafo, representa un conjunto de nodos unidos en una red. Si dos nodos están unidos, al viajar de uno a otro se considerara sucesor el nodo al que nos movemos, y predecesor el nodo del que venimos. Además, normalmente existirá un coste vinculado al desplazamiento entre nodos. Un algoritmo de búsqueda tratará de encontrar un camino óptimo entre dos nodos como por ejemplo un camino que minimice el coste de desplazamiento, o el número de pasos a realizar. La principal diferencia entre los algoritmos es la información que guardan acerca del grafo. Algunos de ellos no guardan información alguna, simplemente expanden la búsqueda desde el nodo inicial, hasta que se llega al nodo final, otros guardan el coste de viajar desde el origen hasta ese nodo, o incluso una estimación de lo prometedor que es un nodo para conducir el camino a su objetivo. La expansión de la búsqueda se realiza en forma de árbol. Partiendo del nodo inicial, se extenderá la búsqueda a sus nodos vecinos, de cada uno de estos nodos vecinos, a sus respectivos nodos vecinos, y así hasta que uno de los nodos a los que se expande la búsqueda es el nodo objetivo. En esta página se desarrollará un algoritmo de búsqueda lo suficientemente general para trabajar en la mayoría de los grafos, y que da paso a otros métodos de búsqueda más complejos.

Notación

El algoritmo consta de dos listas, Abierta, y Cerrada. En la lista Abierta se guardan los nodos que aún no se han expandido para la búsqueda, que en otras palabras, serían las hojas de un árbol. En la lista Cerrada, se guardan los nodos que ya se han procesado y expandido, estos nodos se guardan porque la expansión de la búsqueda podría intentar volver a pasar por uno de esos nodos y de estar almacenados, se tiene constancia de los nodos que ya se han procesado. Además, cada nodo, almacenará información a cerca de quien es su nodo predecesor.

Ejemplo de algoritmo simple

Pseudocódigo de búsqueda

${\color {BlueViolet}Busqueda\;en\;grafo()}$
${\color {Blue}Crear\;\color {Sepia}dos\;listas\;vacias,\;\color {OliveGreen}Abiertos\;\color {Sepia}y\;\color {OliveGreen}Cerrados}$
${\color {Blue}Meter\;\color {Sepia}el\;nodo\;origen\;\color {OliveGreen}O\;\color {Sepia}en\;la\;lista\;\color {OliveGreen}Abiertos}$
${\color {Blue}Repetir}$

${\color {Sepia}Si\;\color {OliveGreen}(Abiertos\;esta\;vacia)\;\color {Sepia}entonces}$

${\color {Red}Devolver\;error}$

${\color {Sepia}Seleccionar\;el\;primer\;nodo,\;\color {OliveGreen}N\;\color {Sepia}de\;\color {OliveGreen}Abiertos\;\color {Sepia}y\;ponerlo\;en\;\color {OliveGreen}Cerrados}$

${\color {Sepia}Si\;\color {OliveGreen}(N==Destino)\;\color {Sepia}entonces}$

${\color {Magenta}Devolver\;N}$

${\color {Gray}//Recuerda\;que\;este\;es\;un\;algoritmo\;de\;busqueda\;en\;un\;grafo}$

${\color {Gray}//Para\;obtener\;el\;camino\;que\;une\;el\;nodo\;origen\;y\;destino\;se\;utilizara\;otro\;algoritmo}$

${\color {Blue}Expandir\;\color {OliveGreen}(N)\;\color {Sepia}obteniendo\;un\;conjunto\;de\;sucesores\;}$

${\color {Sepia}Para\;cada\;(S\in \{\color {Blue}Sucesores\color {OliveGreen}(N)\color {Sepia}\})}$

${\color {Sepia}Si\;(\color {OliveGreen}S\color {Sepia}\notin \color {OliveGreen}Abierta\color {Sepia}\;y\;\color {OliveGreen}S\color {Sepia}\notin \color {OliveGreen}Cerrada)\;\color {Sepia}entonces}$

${\color {Blue}Guardar\;\color {OliveGreen}N\;\color {Sepia}como\;el\;predecesor\;de\;\color {OliveGreen}S}$

${\color {Blue}Meter\;\color {OliveGreen}S\;\color {Sepia}en\;la\;lista\;\color {OliveGreen}Abiertos}$

${\color {Blue}Hasta\;\color {Sepia}que\;el\;nodo\;destino\;se\;haya\;encontrado}$

Explicación del algoritmo

Primero se crean dos listas que almacenarán nodos, la lista Abiertos, que contiene los nodos que se tienen que expandir, y la lista Cerrados que contiene los que ya han sido expandidos. El nodo de origen, llamado O en este caso, se mete en la lista de Abiertos para ser expandido. En este punto, se inicia la propagación de la búsqueda, se crea un bucle que acabará en dos posibles ocasiones: Cuando la lista Abiertos este vacía, o cuando se encuentre el nodo destino. El bucle consiste en varios pasos: Primero se obtiene el primer nodo de la lista Abiertos. El nodo a coger el arbitrario, en otros algoritmos se cogería un nodo que cumpliera ciertas propiedades, pero no es lo que se busca aquí. Si esta lista está vacía, quiere decir que no quedan más candidatos para la expansión, y aun así no se encontró el destino, el algoritmo ha fallado. Por otra parte, si el nodo que cogimos de la lista Abiertos es el destino, el algoritmo habrá acabado, ya que hemos encontrado el destino. El camino entre el origen y el destino es un conjunto de nodos que se obtendrán guardando cada predecesor del nodo destino. En otro caso, se seguirá expandiendo la lista, obteniendo una lista de sucesores del nodo actual, y guardando en la lista Abiertos, aquellos nodos que no estuvieran antes en una lista, o con otras palabras, aquellos nodos a los que aún no se había llegado. De esta forma, el algoritmo acabará encontrando el destino, o recorriendo todo el mapa.

Efectividad

Nota: La animación tiene un fallo, ya que el camino debería de haber empezado en dirección norte en vez de en dirección oeste. Esto ha pasado porque no se metió el cuadro destino en la lista abierta en el momento oportuno (se metió dos turnos más tarde). El algoritmo trata de llegar desde el cuadro verde (el origen), hasta el cuadro rojo (el destino). La zona negra es un nodo por el que no puede pasar. Siguiendo el algoritmo, el nodo inicial se irá expandiendo, pasando a estar el nodo actual en la lista Cerrados (color violeta) y metiendo otros nodos en la lista de Abiertos (color azul). Además cada nodo almacenará quien es su predecesor, que está simbolizado con las muescas en los bordes de los cuadrados. Una vez que la expansión alcanza el nodo destino, se genera un camino siguiendo la cadena de predecesores.

Como se aprecia, la expansión se realiza sin orientación alguna, a lo largo y ancho del espacio. Esto aumentará considerablemente el tiempo de computación, ya que se procesan muchos más nodos que si la expansión estuviera orientada en la dirección del destino. Otro factor a tener en cuenta es que a pesar de haber alcanzado el nodo destino, el algoritmo no finaliza hasta que lo procesa, o en otras palabras, hasta que pasa a ser el primer nodo de la lista Abiertos. Estas dos taras, están relacionadas con la prioridad de búsqueda, y en algoritmos más avanzados se corrige mediante el uso de estimadores heurísticos como la distancia manhattan, o la distancia euclídea. Usando estos estimadores el algoritmo procesará primero los nodos de la lista abierta que tengan una menor distancia al origen, evitando así expansiones innecesarias.

Otra desventaja importante del algoritmo, es que no tiene capacidad para resolver cambios inesperados en el mapa. Una vez calculada la ruta, si un obstáculo se interpone en el camino obtenido no se hará absolutamente nada por evitarlo. Esto se resuelve en algoritmos como D*, que si tienen en cuenta estas variaciones.

Referencias

Programa en Java que ilustra el uso de algoritmos de búsqueda.

Código fuente de ese mismo programa.

Datos: Q5668333