Búsqueda por franjas

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.

También se utiliza una variable de portal que permitirá clasificar a los nuevos nodos en potencialmente buenos o malos.

La expansión se hace en la lista now (posterior al puntero cabecera).

Esta es mayor o igual a f(n) que es el costo del camino óptimo.

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

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

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.

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.
Comparación del tiempo de ejecución entre Fringe Search y A* con respecto al número de nodos que componen un grafo.