La búsqueda bidireccional es un algoritmo de búsqueda de gráficos que encuentra la ruta más corta desde un vértice inicial hasta un vértice de meta en un gráfico dirigido . Ejecuta dos búsquedas simultáneas: una hacia adelante desde el estado inicial y una hacia atrás desde la meta, deteniéndose cuando los dos se encuentran. La razón de este enfoque es que en muchos casos es más rápido: por ejemplo, en un modelo simplificado de complejidad del problema de búsqueda en el que ambas búsquedas expanden un árbol con factor de ramificación b , y la distancia desde el inicio hasta la meta es d , cada uno de los dos búsquedas tiene complejidad O ( b d / 2 ) (enNotación Big O ), y la suma de estos dos tiempos de búsqueda es mucho menor que la complejidad O ( b d ) que resultaría de una sola búsqueda desde el principio hasta la meta.
Andrew Goldberg y otros explicaron las condiciones de terminación correctas para la versión bidireccional del algoritmo de Dijkstra . [1]
Al igual que en la búsqueda A * , la búsqueda bidireccional puede guiarse por una estimación heurística de la distancia restante hasta la meta (en el árbol de avance) o desde el principio (en el árbol de retroceso).
Ira Pohl ( 1971 ) fue el primero en diseñar e implementar un algoritmo de búsqueda heurística bidireccional. Los árboles de búsqueda que emanan desde el inicio y los nodos de objetivo no se encontraron en el medio del espacio de la solución. El algoritmo BHFFA solucionó este defecto Champeaux (1977).
Una solución encontrada por el algoritmo unidireccional A * usando una heurística admisible tiene una longitud de ruta más corta; la misma propiedad es válida para la versión heurística bidireccional BHFFA2 descrita en de Champeaux (1983). BHFFA2 tiene, entre otras, condiciones de terminación más cuidadosas que BHFFA.
Descripción
Una búsqueda heurística bidireccional es una búsqueda en el espacio de estado de algún estado a otro estado , buscando desde a y de a simultaneamente. Devuelve una lista válida de operadores que si se aplica a nos dará .
Si bien puede parecer que los operadores tienen que ser invertibles para la búsqueda inversa, solo es necesario poder encontrar, dado cualquier nodo , el conjunto de nodos padres de tal que exista algún operador válido de cada uno de los nodos padres para . Esto a menudo se ha comparado con una calle de un solo sentido en el dominio de búsqueda de rutas: no es necesario poder viajar en ambas direcciones, pero es necesario cuando está parado al final de la calle para determinar el comienzo de la calle. como una ruta posible.
De manera similar, para aquellas aristas que tienen arcos inversos (es decir, arcos que van en ambas direcciones) no es necesario que cada dirección tenga el mismo costo. La búsqueda inversa siempre usará el costo inverso (es decir, el costo del arco en la dirección de avance). Más formalmente, si es un nodo con padre , luego , definido como el costo de a . (Auer Kaindl 2004)
Terminología y notación
- el factor de ramificación de un árbol de búsqueda
- el costo asociado con la mudanza del nodo al nodo
- el costo desde la raíz hasta el nodo
- la estimación heurística de la distancia entre el nodo y la meta
- el estado de inicio
- el estado objetivo (a veces , no confundir con la función)
- la dirección de búsqueda actual. Por convención, es igual a 1 para la dirección de avance y 2 para la dirección de retroceso (Kwa 1989)
- la dirección de búsqueda opuesta (es decir )
- el árbol de búsqueda en la dirección d. Si , la raíz es , Si , la raíz es
- las hojas de (a veces denominado ). Es de este conjunto que se elige un nodo para la expansión. En la búsqueda bidireccional, a veces se les denomina "fronteras" o "frentes de onda" de búsqueda, en referencia a cómo aparecen cuando una búsqueda se representa gráficamente. En esta metáfora, se produce una "colisión" cuando, durante la fase de expansión, un nodo de un frente de onda tiene sucesores en el frente de onda opuesto.
- los nodos no foliares de . Este conjunto contiene los nodos ya visitados por la búsqueda.
Enfoques para la búsqueda heurística bidireccional
Los algoritmos bidireccionales se pueden dividir en tres categorías: de adelante hacia atrás, de adelante hacia atrás (o de adelante hacia atrás) y búsqueda de perímetro (Kaindl Kainz 1997). Estos se diferencian por la función utilizada para calcular la heurística.
Desde el frente hacia atras
Los algoritmos de adelante hacia atrás calculan valor de un nodo utilizando la estimación heurística entre y la raíz del árbol de búsqueda opuesto, o .
De adelante hacia atrás es la más investigada de las tres categorías. El mejor algoritmo actual (al menos en el dominio de los quince rompecabezas ) es el algoritmo BiMAX-BS * F, creado por Auer y Kaindl (Auer, Kaindl 2004).
De adelante hacia adelante
Los algoritmos de frente a frente calculan el valor h de un nodo n utilizando la estimación heurística entre n y algún subconjunto de. El ejemplo canónico es el del BHFFA ( algoritmo bidireccional heurístico de frente a frente ), [2] donde la función h se define como el mínimo de todas las estimaciones heurísticas entre el nodo actual y los nodos del frente opuesto. O, formalmente:
dónde devuelve una estimación heurística admisible (es decir, no sobreestimada) de la distancia entre los nodos n y o .
Front-to-Front adolece de ser excesivamente exigente desde el punto de vista informático. Cada vez que un nodo n se coloca en la lista abierta, sudebe calcularse el valor. Esto implica calcular una estimación heurística de n para cada nodo en el conjunto OPEN opuesto , como se describió anteriormente. Los conjuntos ABIERTOS aumentan de tamaño exponencialmente para todos los dominios con b > 1 .
Referencias
- ^ Algoritmos de ruta más corta punto a punto eficientes
- ↑ de Champeaux, 1977/1983
- de Champeaux, Dennis; Sint, Lenie (1977), "Un algoritmo de búsqueda heurística bidireccional mejorado", Journal of the ACM , 24 (2): 177-191, doi : 10.1145 / 322003.322004.
- de Champeaux, Dennis (1983), "Búsqueda heurística bidireccional de nuevo", Journal of the ACM , 30 (1): 22–32, doi : 10.1145 / 322358.322360.
- Pohl, Ira (1971), "Búsqueda bidireccional", en Meltzer, Bernard; Michie, Donald (eds.), Machine Intelligence , 6 , Edinburgh University Press, págs. 127–140.
- Russell, Stuart J .; Norvig, Peter (2002), "3.4 Estrategias de búsqueda no informadas", Inteligencia artificial: un enfoque moderno (2ª ed.), Prentice Hall.