Búsqueda por franjas

Una lista luego, ahora (later, now) con sus tres punteros, uno hacia el inicio de la lista, otro hacia el nodo actual a analizar y una al final. La función Gamma evalúa los vecinos de la cabeza y a los nodos prometedores los inserta en now, mientras que a los poco prometedoras al inicio de la lista, en el campo later.

En ciencias de la computación, la búsqueda por franjas (fringe search en inglés) es un algoritmo heurístico de búsqueda sobre grafos, creado por Böjrnsson, Enzenberger, Holte y Schaeffer, que encuentra una ruta desde un nodo inicial dado a un nodo objetivo. La búsqueda por franjas es un punto medio entre A* y la variante de profundización iterativa A* (IDA*).

Descripción del Algoritmo

El algoritmo requiere dos tablas hash para guardar g*(n) y h*(n), donde g*(n) es el costo del camino desde el origen hasta el nodo actual y h(n) es el costo estimado del nodo actual al destino. Para cada nodo visitado se guardará este valor con el objetivo de mantener una memoria para mejorar la estimación del mejor camino. El costo de consultar cada nodo es reducido, dado que la complejidad de una búsqueda en una tabla hash es de O(1). También se requiere una lista now-later la cual es una lista doblemente ligada con tres punteros: uno hacia el nodo inicial, otro al nodo actual y uno al nodo final. También se utiliza una variable de portal que permitirá clasificar a los nuevos nodos en potencialmente buenos o malos. Con estas estructuras itera sobre la lista, donde la cabecera estará al inicio de la lista. Se recorre toda la lista, pero únicamente se expande los nodos vecinos al nodo que es su costo esté por arriba de la variable portal. La expansión se hace en la lista now (posterior al puntero cabecera). Cuando la lista se finaliza y no se ha encontrado al nodo objetivo, se vuelve a comenzar desde el inicio.

Para estimar costos se utiliza heurísticas, donde f*(n) es el costo estimado del nodo actual desde el camino más corto desde el inicio al fin pasando por n. Este se compone por: g(n) es el costo de la ruta de búsqueda desde el primer nodo al actual, y h*(n) es la estimación heurística del costo desde el nodo actual al objetivo. La suma f*(x) = g*(x) + h*(x), es el costo de la ruta estimada al nodo objetivo. Esta es mayor o igual a f(n) que es el costo del camino óptimo.

Diferencias con A* e IDA*

Considere IDA*, que hace una búsqueda recursiva de izquierda a derecha primero en profundidad desde el nodo raíz, deteniendo la recursividad una vez que el objetivo se ha encontrado o los nodos han alcanzado un máximo valor ƒ. Si ningún objetivo se encuentra en el primer umbral f, este se incrementa y el algoritmo busca de nuevo, es decir, itera sobre el umbral.

IDA* presenta tres grandes ineficiencias: En primer lugar, IDA* repetirá estados cuando existen múltiples (a veces no óptimos) caminos a un nodo objetivo - esto a menudo se resuelve manteniendo una caché de los estados visitados. IDA* de este modo alterado se denota como memoria- mejorada IDA* (ME-IDA*), ya que utiliza algún grado de almacenamiento. Además, IDA* repite todas las operaciones previas en una búsqueda cuando se itera en un nuevo umbral, lo que es necesario cuando se opera sin almacenamiento. Mediante el almacenamiento de los nodos hoja de una iteración anterior y su uso como nodos de partida de la siguiente, la eficiencia de IDA * se incrementa significativamente (de lo contrario, en la última iteración siempre se tendría que visitar cada nodo en el árbol).

Búsqueda por Franjas implementa estas mejoras en IDA*, haciendo uso de una estructura de datos que consiste, esencialmente, en dos listas para iterar sobre la frontera o franja del árbol de búsqueda. Una lista ahora almacena la iteración actual y la otra lista luego la iteración que le sigue de manera inmediata. De esta forma, desde el nodo raíz del árbol de búsqueda, ahora será la raíz y luego estará vacía. A continuación, el algoritmo toma una de dos acciones: Si ƒ (cabeza) es mayor que el umbral actual, se elimina la cabeza de la lista ahora y se añade al final de la lista luego; es decir, se guarda la cabeza para la siguiente iteración. De lo contrario, si ƒ (cabeza) es menor o igual al umbral, se expande la cabeza y posteriormente se descarta (añadiendo sus nodos hijos al comienzo de la lista ahora). Al final de una iteración se incrementa el umbral, la lista ahora pasa a ser la anterior lista luego, y la lista luego se vacía.

Una diferencia importante entre la Búsqueda por Franjas y A* es que el contenido de las listas en la primera no necesariamente tiene que estar ordenado - una ventaja sobre A*, que requiere el, a menudo, costoso mantenimiento de orden en su lista abierta. No obstante, a diferencia de A*, la Búsqueda por Franjas tendrá que visitar los mismos nodos en varias ocasiones pero, incluso así, el costo de cada visita es constante en comparación con el tiempo logarítmico que invierte A*, en el peor de los casos, para ordenar la lista.

Sin embargo, a pesar de ser no utilizar una lista ordenada de nodos la mejora en el tiempo promedio de ejecución no disminuye de manera drástica, ni representa una diminución de la complejidad de A*. Por el otro lado, la Búsqueda por Franjas no garantiza un camino óptimo en un espacio euclidiano a diferencia de A* que si lo garantiza.

Pseudocódigo

La implementación de las dos listas se realiza en una lista doblemente enlazada, donde los nodos siguientes al nodo actual son la parte luego y los restantes la lista ahora que le sigue. Usando un array de nodos pre-asignados en la lista por cada nodo de la red, el tiempo de acceso a los nodos de la lista se reduce a una constante. Del mismo modo, un array marcador permite la búsqueda de un nodo de la lista en tiempo constante. g se almacena como una tabla hash, y un último array marcador se utiliza para la búsqueda en tiempo constante de si un nodo ha sido visitado o no con anterioridad, y si una entrada de caché es válida. 

init(start, goal)
    fringe F = s
    cache C[start] = (0, null)
    flimit = h(start)
    found = false

    while (found == false) AND (F not empty)
        fmin = ∞
        for node in F, from left to right
            (g, parent) = C[node]
            f = g + h(node)
            if f > flimit
                fmin = min(f, fmin)
                continue
            if node == goal
                found = true
                break
            for child in children(node), from right to left
                g_child = g + cost(node, child)
                if C[child] != null
                    (g_cached, parent) = C[child]
                    if g_child >= g_cached
                        continue
                if child in F
                    remove child from F
                insert child in F past node
                C[child] = (g_child, node)
            remove node from F
        flimit = fmin

    if reachedgoal == true
        reverse_path(goal)

reverse_path(node)
    (g, parent) = C[node]
    if parent != null
        reverse_path(parent)
    print node

Experimentos

Comparación del tiempo de ejecución entre Fringe Search y A* con respecto al número de nodos que componen un grafo.

Al realizar pruebas en entornos basados en la red, típicos de los juegos de ordenador, incluyendo obstáculos infranqueables, Búsqueda por Franjas superó a A* en un 10 a 40 por ciento. Posibles mejoras adicionales incluyen el uso de una estructura de datos que funcione más fácilmente como caché.


Referencias

Enlaces externos