En informática , la búsqueda marginal es un algoritmo de búsqueda de gráficos que encuentra la ruta de menor costo desde un nodo de inicio dado hasta un solo nodo de destino .
En esencia, la búsqueda de bordes es el término medio entre el algoritmo de búsqueda A* y la variante de profundización iterativa A* ( IDA* [1] ).
Si g ( x ) es el costo de la ruta de búsqueda desde el primer nodo hasta el actual, y h ( x ) es la heurística de costo desde el nodo actual hasta el destino, entonces ƒ ( x ) = g ( x ) + h ( x ) es el costo real del camino hacia las metas. Considere un IDA* que realiza una búsqueda recursiva de izquierda a derecha en profundidad desde el nodo raíz, deteniendo la recursividad tan pronto como se encuentra el objetivo o los nodos alcanzan su valor máximo de ƒ . Si el objetivo no se encuentra en la primera iteración ƒ, la iteración se incrementa y el algoritmo busca de nuevo. Es decir, se repite en iteraciones.
IDA* tiene tres inconvenientes principales. En primer lugar, IDA* repetirá los estados cuando haya varias rutas (a veces subóptimas) al nodo de destino; esto a menudo se resuelve manteniendo una memoria caché de los estados visitados. Un IDA* modificado de esta manera se denomina IDA* con memoria extendida ( ME-IDA* [2] ) porque utiliza algo de memoria. Además, IDA* repite todas las búsquedas anteriores una y otra vez, lo cual es necesario para trabajar sin almacenamiento. Al mantener los nodos hoja de la iteración anterior y usarlos como la posición inicial de la siguiente, la eficiencia de IDA* mejora considerablemente (de lo contrario, siempre tendría que visitar todos los nodos del árbol en la última iteración).
Edge Search implementa estas mejoras en IDA* mediante el uso de una estructura de datos que consta de más o menos dos listas para iterar sobre el límite o borde del árbol de búsqueda. Una lista "ahora" almacena la iteración actual, y la otra lista "posterior" almacena la siguiente iteración más cercana. Por lo tanto, el nodo raíz del árbol de búsqueda "ahora" es la raíz y "después" está vacío. Luego, el algoritmo hace una de dos cosas: si ƒ ( cabeza ) es mayor que el valor de umbral, elimina la cabeza de "ahora" y la agrega al final de "más tarde" , es decir, guarda la cabeza para la próxima iteración. En caso contrario, si ƒ ( cabeza ) es menor o igual que el umbral, despliega y descarta cabeza , considera sus descendientes, agregándolos al principio de "ahora" . Al final de la iteración, el umbral se incrementa, la lista "más tarde" se convierte en la lista "ahora" y se vacía.
Una diferencia importante entre la búsqueda perimetral y A* es que los contenidos de las listas en la búsqueda perimetral no tienen que ordenarse, una ventaja significativa sobre A* , que requiere el mantenimiento del orden, a menudo costoso, en su lista abierta. Sin embargo , la búsqueda de borde tendrá que visitar, a diferencia de A* , los mismos nodos repetidamente, pero el costo de cada visita es constante en comparación con el tiempo de clasificación logarítmica de la lista en A* en el peor de los casos.
La implementación de ambas listas en una sola lista doblemente enlazada, donde los nodos que preceden al nodo actual son la parte "posterior" , y todo lo demás es la lista "ahora" . Mediante el uso de una matriz de nodos preasignados en la lista para cada nodo de la cuadrícula, el tiempo de acceso a los nodos de la lista se reduce a una constante. De manera similar, una matriz de marcadores le permite buscar un nodo en una lista en tiempo constante. g se almacena como una tabla hash , y la última matriz de tokens se almacena para buscar constantemente si el nodo ha sido visitado previamente y si la entrada de caché es válida .
init ( comienzo , objetivo ) franja F = s caché C [ inicio ] = ( 0 , nulo ) flimit = h ( inicio ) encontrado = falso while ( encontrado == falso ) Y ( F no vacío ) fmín = ∞ para el nodo en F , de izquierda a derecha ( g , padre ) = C [ nodo ] f = g + h ( nodo ) si f > límite fmin = min ( f , fmin ) Seguir si nodo == objetivo encontrado = verdadero descanso para niño en niños ( nodo ), de derecha a izquierda g_child = g + costo ( nodo , hijo ) si C [ hijo ] != nulo ( g_cached , padre ) = C [ hijo ] si g_child >= g_cached Seguir si niño en F eliminar niño de F insertar niño en F pasado nodo C [ hijo ] = ( g_hijo , nodo ) quitar nodo de F límite = fmín si alcanzó la meta == verdadero camino inverso ( objetivo )Pseudocódigo inverso.
camino inverso ( nodo ) ( g , padre ) = C [ nodo ] si padre ! = nulo ruta_inversa ( padre ) nodo de impresiónCuando se probó en un entorno de cuadrícula típico de los juegos de computadora, incluidos los obstáculos impenetrables, la búsqueda de bordes superó a A* en aproximadamente un 10-40 % , según el uso de mosaicos u octiles. Otras posibles mejoras incluyen el uso de una estructura de datos que es más fácil de almacenar en caché .