Hispanopedia Wiki
Articulo de referencia

Búsqueda bidireccional

La búsqueda bidireccional es un algoritmo de búsqueda en grafos que encuentra el camino más corto desde un vértice inicial hasta un vértice objetivo en un grafo dirigido . Reali...

Hispanopedia WikiContenido en espanolLectura gratuita

La búsqueda bidireccional es un algoritmo de búsqueda en grafos que encuentra el camino más corto desde un vértice inicial hasta un vértice objetivo en un grafo dirigido . Realiza dos búsquedas simultáneas: una hacia adelante desde el estado inicial y otra hacia atrás desde el objetivo, deteniéndose cuando ambas 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 el objetivo es d , cada una de las dos búsquedas tiene una complejidad O ( b d /2 ) (en notació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 inicio hasta el objetivo.

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 el objetivo (en el árbol hacia adelante) o desde el punto de partida (en el árbol hacia atrás).

Ira Pohl fue el primero en diseñar e implementar un algoritmo de búsqueda heurística bidireccional. [ 2 ] Los árboles de búsqueda que se originaban en los nodos de inicio y destino no se encontraban en el centro del espacio de soluciones. El algoritmo BHFFA de de Champeaux corrigió este defecto. [ 3 ]

Una solución encontrada por el algoritmo A* unidireccional usando una heurística admisible tiene una longitud de camino más corto; la misma propiedad se cumple para la versión heurística bidireccional BHFFA2 descrita por de Champeaux. [ 4 ] BHFFA2 tiene, entre otras cosas, 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 estados desde algún estados{\displaystyle s}a otro estadot{\displaystyle t}, buscando desdes{\displaystyle s}at{\displaystyle t}y det{\displaystyle t}as{\displaystyle s}simultáneamente. Devuelve una lista válida de operadores que, si se aplican as{\displaystyle s}nos darát{\displaystyle t}.

Aunque pueda parecer que los operadores tienen que ser invertibles para la búsqueda inversa, solo es necesario poder encontrar, dado cualquier nodonorte{\displaystyle n}, el conjunto de nodos padres denorte{\displaystyle n}de tal manera que exista algún operador válido desde cada uno de los nodos padres hastanorte{\displaystyle n}Esto se ha comparado a menudo con una calle de sentido único en el ámbito de la búsqueda de rutas: no es necesario poder viajar en ambas direcciones, pero sí es necesario, al estar al final de la calle, determinar el comienzo de la misma como una posible ruta.

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 utilizará el costo inverso (es decir, el costo del arco en la dirección directa). Más formalmente, sinorte{\displaystyle n}es un nodo con padrepag{\displaystyle p}, entoncesk1(pag,norte)=k2(norte,pag){\displaystyle k_{1}(p,n)=k_{2}(n,p)}, definido como el costo depag{\displaystyle p}anorte{\displaystyle n}. [ 5 ]

Terminología y notación

b{\displaystyle b}
el factor de ramificación de un árbol de búsqueda
k(norte,metro){\displaystyle k(n,m)}
el costo asociado al traslado de nodonorte{\displaystyle n}al nodometro{\displaystyle m}
gramo(norte){\displaystyle g(n)}
el costo desde la raíz hasta el nodonorte{\displaystyle n}
h(norte){\displaystyle h(n)}
la estimación heurística de la distancia entre el nodonorte{\displaystyle n}y el objetivo
s{\displaystyle s}
el estado inicial
t{\displaystyle t}
el estado objetivo (a vecesgramo{\displaystyle g}(no confundir con la función)
d{\displaystyle d}
la dirección de búsqueda actual. Por convención,d{\displaystyle d}es igual a 1 para la dirección hacia adelante y 2 para la dirección hacia atrás [ 6 ]
d′{\displaystyle d'}
la dirección de búsqueda opuesta (es decir,d′=3−d{\displaystyle d'=3-d})
TRmimid{\displaystyle \mathrm {TREE} _{d}}
el árbol de búsqueda en la dirección d. Sid=1{\displaystyle d=1}, la raíz ess{\displaystyle s}, sid=2{\displaystyle d=2}, la raíz est{\displaystyle t}
OPAGminorted{\displaystyle \mathrm {OPEN} _{d}}
las hojas deTRmimid{\displaystyle \mathrm {TREE} _{d}}(a veces denominado comoFRInorteGRAMOmid{\displaystyle \mathrm {FRINGE} _{d}}Es de este conjunto que se elige un nodo para su expansión. En la búsqueda bidireccional, a estos nodos se les denomina a veces «fronteras» o «frentes de onda» de búsqueda, en referencia a su apariencia al representar gráficamente la búsqueda. En esta metáfora, se produce una «colisión» cuando, durante la fase de expansión, se encuentra que un nodo de un frente de onda tiene sucesores en el frente de onda opuesto.
doLOSmiDd{\displaystyle \mathrm {CLOSED} _{d}}
los nodos no hoja deTRmimid{\displaystyle \mathrm {TREE} _{d}}Este conjunto contiene los nodos ya visitados por la búsqueda.

Los algoritmos bidireccionales se pueden dividir en tres categorías principales: de adelante hacia adelante, de adelante hacia atrás (o de adelante hacia atrás) y búsqueda de perímetro. [ 7 ] Estos se diferencian por la función utilizada para calcular la heurística.

De adelante hacia atrás

Los algoritmos de principio a fin calculan elh{\displaystyle h}valor de un nodonorte{\displaystyle n}mediante el uso de la estimación heurística entrenorte{\displaystyle n}y la raíz del árbol de búsqueda opuesto,s{\displaystyle s}ot{\displaystyle t}.

De adelante hacia atrás es la categoría más investigada de las tres. A partir de 2004, el mejor algoritmo actual (al menos en el dominio del rompecabezas de quince piezas ) es el algoritmo BiMAX-BS*F. [ 5 ]

De frente a frente

Los algoritmos Front-to-Front calculan el valor h de un nodo n utilizando la estimación heurística entre n y algún subconjunto deOPAGminorted′{\displaystyle \mathrm {OPEN} _{d'}}El ejemplo canónico es el del BHFFA (algoritmo heurístico bidireccional de frente a frente), [ 3 ] [ 4 ] donde la función h se define como el mínimo de todas las estimaciones heurísticas entre el nodo actual y los nodos en el frente opuesto. O, formalmente:

hd(norte)=mini{H(norte,oi)|oi∈OPAGminorted′}{\displaystyle h_{d}(n)=\min _{i}\left\{H(n,o_{i})|o_{i}\in \mathrm {OPEN} _{d'}\right\}}

dóndeH(norte,o){\displaystyle H(n,o)}devuelve una estimación heurística admisible (es decir, que no sobreestima) de la distancia entre los nodos n y o .

Front-to-Front sufre de ser excesivamente exigente en términos computacionales. Cada vez que un nodo n se agrega a la lista abierta, suF=gramo+h{\displaystyle f=g+h}El valor debe calcularse. Esto implica calcular una estimación heurística desde n hasta cada nodo en el conjunto OPEN opuesto , como se describió anteriormente. Los conjuntos OPEN aumentan de tamaño exponencialmente para todos los dominios con b > 1 .

Referencias

  1. ↑ Goldberg, Andrew V.; Harrelson, Chris; Kaplan, Haim; Werneck, Renato T. (5 de abril de 2006). "Algoritmos eficientes de ruta más corta punto a punto, material de apoyo de COS423" (PDF) . Universidad de Princeton.
  2. ↑ Pohl, Ira (1971). Meltzer, Bernard; Michie, Donald (eds.). "Búsqueda bidireccional" (PDF) . Inteligencia artificial . 6. Edinburgh University Press: 127–140 .
  3. 1 2 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 .
  4. 1 2 de Champeaux, Dennis (1983). "Búsqueda heurística bidireccional de nuevo" . Journal of the ACM . 30 (1): 22– 32. doi : 10.1145/322358.322360 .
  5. 1 2 Auer, Andreas; Kaindl, Hermann (2004). Un estudio de caso de revisión de la búsqueda primero en amplitud frente a la búsqueda primero en profundidad (PDF) . La 16.ª Conferencia Europea sobre Inteligencia Artificial.
  6. ↑ Kwa, James BH (1989). "BS*: Un algoritmo de búsqueda heurística por etapas bidireccional admisible". Inteligencia Artificial . 38 (1). Elsevier BV: 95–109 . doi : 10.1016/0004-3702(89)90069-6 . ISSN 0004-3702 . 
  7. ↑ Kaindl, H.; Kainz, G. (1997-12-01). "Reconsideración de la búsqueda heurística bidireccional" . Journal of Artificial Intelligence Research . 7. AI Access Foundation: 283–317 . arXiv : cs/9712102 . doi : 10.1613/jair.460 . ISSN 1076-9757 . Recuperado el 2025-01-10 . 

Lecturas adicionales

  • Russell, Stuart J.; Norvig , Peter (2002). "3.4 Estrategias de búsqueda no informadas". Inteligencia artificial: un enfoque moderno (2.ª  ed.). Prentice Hall..