Búsqueda marginal

En informática , la búsqueda de franjas es un algoritmo de búsqueda en grafos que encuentra el camino de menor coste desde un nodo inicial dado hasta un nodo objetivo .

En esencia, la búsqueda marginal es un punto intermedio entre A* y la variante de profundización iterativa de A* (IDA*).

Si g ( x ) es el costo de la ruta de búsqueda desde el primer nodo hasta el actual, y h ( x ) es la estimación heurística del costo desde el nodo actual hasta el objetivo, entonces ƒ ( x )  = g ( x ) + h ( x )    , y h * es el costo real de la ruta hasta el objetivo. Considere IDA*, que realiza una búsqueda recursiva en profundidad de izquierda a derecha desde el nodo raíz, deteniendo la recursión una vez que se ha encontrado el objetivo o los nodos han alcanzado un valor máximo ƒ . Si no se encuentra ningún objetivo en el primer umbral ƒ , entonces el umbral se incrementa y el algoritmo busca de nuevo. IE Itera sobre el umbral.

IDA* presenta tres ineficiencias principales. En primer lugar, repite estados cuando existen múltiples rutas (a veces no óptimas) hacia un nodo objetivo; esto se suele solucionar manteniendo una caché de los estados visitados. Esta versión modificada de IDA* se denomina IDA* con memoria mejorada (ME-IDA*), ya que utiliza almacenamiento. Además, IDA* repite todas las operaciones anteriores en una búsqueda al iterar en un nuevo umbral, lo cual es necesario para operar sin almacenamiento. Al almacenar los nodos hoja de una iteración anterior y utilizarlos como posición inicial de la siguiente, la eficiencia de IDA* mejora significativamente (de lo contrario, en la última iteración tendría que visitar todos los nodos del árbol).

La búsqueda de frontera implementa estas mejoras en IDA* mediante una estructura de datos que consiste básicamente en dos listas para iterar sobre la frontera o el borde del árbol de búsqueda. Una lista, `now` , almacena la iteración actual, y la otra, `later`, almacena la siguiente iteración inmediata. Así, desde el nodo raíz del árbol de búsqueda, `now` será la raíz y `later` estará vacía. A continuación, el algoritmo realiza una de dos acciones: si `ƒ` (cabeza) es mayor que el umbral actual, elimina `head` de `now` y lo añade al final de `later` ; es decir, guarda `head` para la siguiente iteración. De lo contrario, si `ƒ` (cabeza) es menor o igual que el umbral, expande `head` y descarta `head` , considera sus hijos y los añade al principio de ` now` . Al final de una iteración, el umbral aumenta, la lista `later` se convierte en la lista `now` , y `later` se vacía.

Una diferencia importante entre Fringe y A* es que el contenido de las listas en Fringe no tiene por qué estar ordenado, lo que supone una ventaja significativa sobre A*, que requiere el mantenimiento, a menudo costoso, del orden en su lista abierta. Sin embargo, a diferencia de A*, Fringe tendrá que visitar los mismos nodos repetidamente, pero el coste de cada visita es constante en comparación con el tiempo logarítmico máximo que supone ordenar la lista en  A*.

Implementando ambas listas en una lista doblemente enlazada, donde los nodos que preceden al nodo actual forman la parte posterior y el resto la lista actual . Al usar un arreglo de nodos preasignados en la lista para cada nodo en la cuadrícula, el tiempo de acceso a los nodos en la lista se reduce a un valor constante. De manera similar, un arreglo de marcadores permite que la búsqueda de un nodo en la lista se realice en tiempo constante. g se almacena como una tabla hash, y un último arreglo de marcadores se almacena para la búsqueda en tiempo constante de si un nodo ha sido visitado previamente y si una entrada de caché es válida.

init ( inicio , objetivo ) fringe F = s caché C [ inicio ] = ( 0 , null ) flimit = h ( inicio ) encontrado = falsomientras ( encontrado == falso ) Y ( F no está vacío ) fmin = ∞ para nodo en F , de izquierda a derecha ( g , padre ) = C [ nodo ] f = g + h ( nodo ) si f > flimit fmin = min ( f , fmin ) continuar si nodo == objetivo encontrado = verdadero romper para hijo en hijos ( nodo ), de derecha a izquierda g_hijo = g + costo ( nodo , hijo ) si C [ hijo ] != nulo ( g_cached , padre ) = C [ hijo ] si g_hijo >= g_cached continuar si hijo en F eliminar hijo de F insertar hijo en F nodo pasado C [ hijo ] = ( g_hijo , nodo ) eliminar nodo de F flimit = fminsi reachedgoal == true reverse_path ( goal )

Pseudocódigo inverso.

ruta_inversa ( nodo ) ( g , padre ) = C [ nodo ] si padre != null ruta_inversa ( padre ) imprimir nodo

En pruebas realizadas en entornos basados ​​en cuadrículas, típicos de los videojuegos, que incluyen obstáculos infranqueables, Fringe superó a A* entre un 10 % y un 40 %, dependiendo del uso de teselas u óctiles. Entre las posibles mejoras futuras se incluye el uso de una estructura de datos que se adapte mejor a las cachés.

• Björnsson, Yngvi; Enzenberger, Markus; Holte, Robert C.; Schaeffer, Johnathan. Búsqueda en la frontera: Superando a A* en la búsqueda de rutas en mapas de juegos. Actas del Simposio IEEE de 2005 sobre Inteligencia Computacional y Juegos (CIG05). Universidad de Essex, Colchester, Essex, Reino Unido, 4-6 de abril de 2005. IEEE 2005. https://web.archive.org/web/20090219220415/http://www.cs.ualberta.ca/~games/pathfind/publications/cig2005.pdf

• Implementación de Fringe Search en C por Jesús Manuel Mager Hois https://github.com/pywirrarika/fringesearch