Búsqueda bidireccional

La búsqueda bidireccional de amplitud (o profundidad) [1] [2] es un sofisticado algoritmo de búsqueda de amplitud (o profundidad ) , cuya idea es formar un proceso de búsqueda desde el vértice inicial ( búsqueda hacia adelante ) y desde el vértice final ( búsqueda hacia atrás ). búsqueda ) del gráfico .

Idea

Encontrar el camino deseado se reduce a determinar los caminos desde el inicial hasta algún intermedio, y desde este hasta el vértice final. Se implementa comprobando uno o ambos procesos cuando una hoja de un árbol de búsqueda coincide con una hoja de otro, después de lo cual se extraen las rutas a ese elemento. Conectando los caminos obtenemos el camino deseado. Si se realizan dos búsquedas en paralelo  , se ahorra aún más tiempo para obtener la ruta deseada en comparación con una búsqueda unidireccional.

Ventajas y desventajas

• Mayor rendimiento;
• Necesita memoria para almacenar el árbol de búsqueda para que pueda verificar si una hoja pertenece a otro árbol.

Puntuación de dificultad

La complejidad de todo el algoritmo se estima como la suma de la complejidad de las búsquedas hacia adelante y hacia atrás, verificación de membresía igual a una operación, tiempo constante (O (n)), acceso a la tabla hash .

Contando el número de operaciones

Demasiado dependiente de la situación específica si la búsqueda no está en un árbol n-ario .

Complejidad asintótica del número creciente de operaciones

• Si se conocen los únicos elementos inicial y objetivo específicos, entonces la complejidad temporal asintótica de las búsquedas hacia adelante y hacia atrás es igual a , por lo tanto, el total - + , que es mucho menor que . Complejidad asintótica espacial , en lugar de la directa, ya que necesita almacenarse en la memoria.
• Si se conocen un elemento de inicio específico y un conjunto de elementos, de los cuales uno es el elemento de destino.

Evaluación estadística

La búsqueda bidireccional, dado un solo elemento inicial y final, puede mejorar la búsqueda unidireccional en amplitud, generalmente por un factor de 2. El caso más difícil para una búsqueda bidireccional es un problema en el que solo se proporciona una descripción implícita de algún conjunto (posiblemente muy grande) de estados objetivo para verificar el objetivo, por ejemplo, todos los estados correspondientes al jaque mate del objetivo "Ajedrez". " en el ajedrez . En la búsqueda inversa, sería necesario crear descripciones compactas de todos los estados que permitan el jaque mate con jugadas , etc.; y estas descripciones tendrían que cotejarse con los estados generados por la búsqueda directa. No existe una forma general de resolver de manera efectiva tal problema.

Algoritmo de búsqueda bidireccional

El algoritmo consta de:

• búsqueda directa, similar a la búsqueda única;
• búsqueda inversa;
• operaciones para determinar si una hoja pertenece a otro árbol de búsqueda.

Complejidad de implementación

La complejidad de la implementación radica en el algoritmo de búsqueda inversa.

Ejemplos de implementación

Aplicación práctica

Véase también

• Primera búsqueda en amplitud
• Primera búsqueda en profundidad

Notas

1. ↑ Otro: búsqueda de elemento bidireccional - realizada en listas bidireccionales o circulares desde el elemento deseado en ambas direcciones.
2. ↑ [1]  (enlace descendente) Este algoritmo es completo y óptimo (con costos de paso uniformes) si ambos procesos de búsqueda son primero en amplitud; otras combinaciones de métodos pueden carecer de integridad, de optimización o de ambas.

Enlaces

• Algoritmos de búsqueda de caminos en pmg.org.ru
• Modelos y métodos para resolver problemas en Mari El.ru
• Implementación de C++ (aisearch.tgz) en www.cs.cmu.edu

Literatura

• Stuart Russel y Peter Norvig. Parte 2. Resolución de problemas // Inteligencia artificial (enfoque moderno) = Inteligencia artificial (un enfoque moderno). - 2ª ed. - FGUP. "Patio de impresión" A.M. Gorky: Williams, 2006. - S. 135-136. — ISBN 5-8459-0887-6 .