No es correcto describir el tiempo de ejecución de BFS bidireccional como [math] \ Theta (\ sqrt N) [/ math], donde N es el número de vértices.
Primero, comencemos por comprender que, en el peor de los casos, ningún algoritmo para encontrar una ruta entre dos vértices puede ser mejor que [math] \ Theta (V + E) [/ math]. Supongamos que hay algún borde que no has mirado y que aún no has encontrado una ruta de A a B. Por lo que sabes, ese borde podría ser instrumental en la conexión de A a B. Por lo tanto, ningún algoritmo, ya sea unidireccional, bidireccional o lo que sea, puede evitar mirar todos los vértices y bordes en el peor de los casos.
Sin embargo, en muchos gráficos, es probable que A y B estén conectados por muchas rutas diferentes, y estamos interesados en encontrar la ruta más corta. Por lo tanto, queremos una búsqueda que priorice la búsqueda de vértices que puedan formar el camino más corto. Además, en muchos casos esperamos que la distancia sea pequeña, por ejemplo en LinkedIn, donde una conexión se clasifica como 1er, 2do o 3+ grado. Más allá de cierta distancia, es posible que no nos importe exactamente cuál es la distancia. En los casos en que la distancia es pequeña, podemos esperar la mayor parte del tiempo para descubrir el camino en mejor que [matemática] \ Theta (V + E) [/ matemática].
- ¿Debería entrenarme para implementar estructuras de datos y algoritmos, excepto los simples programas tipo 'Hola mundo'?
- Cómo diseñar una estructura de datos que pueda almacenar 1-1000 números
- ¿Puede un programa escribir un programa (es decir, el programa x puede identificar un algoritmo para escribir el programa y, a pesar del algoritmo z)?
- ¿Cómo calculamos la complejidad espacio-temporal de un algoritmo?
- ¿Cuál es la explicación intuitiva para agregar flujo en bordes inversos en el algoritmo de flujo máximo? ¿Por qué necesitamos eso?
Aunque no siempre podemos hacerlo mejor que [matemática] \ Theta (V + E) [/ matemática], la búsqueda bidireccional es una heurística útil para encontrar el camino más corto en tales casos. Puede que no siempre haga menos trabajo que visitar todos los nodos, pero puede hacerlo, y es probable que lo haga si la distancia es pequeña.
Habiendo llegado a esta heurística, queremos comparar su rendimiento probable con el rendimiento de BFS unidireccional. No podemos decir mucho sobre cómo le va en general en los gráficos, por lo que consideraremos un cierto tipo de gráfico común.
Muchos gráficos tienen un grado bastante bajo para cada vértice, lo que significa que cada vértice solo se conecta a un número bastante limitado de otros vértices. Además, el gráfico está altamente interconectado y exhibe una especie de fenómeno de “seis grados de separación” (aunque no específicamente con el número 6), donde los nodos aparentemente no relacionados y distantes están realmente conectados por caminos bastante cortos. Estos tipos de gráficos a menudo se ven en las redes sociales, pero también para otras cosas como conexiones de vuelo, etc.
Para analizar el rendimiento de este tipo de gráficos, elaboramos un cálculo aproximado. Asumimos que cada vértice tendrá vecinos [matemáticos] b [/ matemáticos] (o promediará vecinos [matemáticos] b [/ matemáticos]). Llamamos [math] b [/ math] al factor de ramificación .
En una búsqueda unidireccional, esperamos tener nodos [matemáticos] b [/ matemáticos] a la distancia 1 de la fuente, [nodos matemáticos] b ^ 2 [/ matemáticos] a la distancia 2, hasta [matemáticos] b ^ k [ / math] nodos a distancia [math] k [/ math]. Tenga en cuenta que este es un cálculo muy aproximado e impreciso porque, por supuesto, muchos de los vecinos se superpondrán entre nodos, y este cálculo supone que no se superponen (la cantidad probable de superposición sería difícil de cuantificar). Con base en este cálculo, decimos que si el origen y el destino están a una distancia [matemática] d [/ matemática] aparte, probablemente buscaremos [matemática] 1 + b + b ^ 2 +… + b ^ d = \ Theta ( b ^ d) [/ math] nodos antes de encontrar la ruta.
En una búsqueda bidireccional, se encuentra un nodo intermedio de conexión entre el conjunto de nodos accesibles desde la fuente y el conjunto de nodos accesibles desde el destino cuando todos los nodos dentro de una distancia de [math] d / 2 [/ math] desde ambos puntos finales tienen sido visitado Por lo tanto, el número de nodos que se examinarán se aproxima a [matemáticas] 2 \ cdot (1 + b + b ^ 2 +… + b ^ {d / 2}) = \ Theta (b ^ {d / 2}) [ /mates].
Si dejamos que [math] S [/ math] sea el tamaño del conjunto de nodos visitados con búsqueda unidireccional en esta aproximación (es decir, [math] S = \ Theta (b ^ d) [/ math]), entonces bidireccional la búsqueda solo visita los nodos [math] \ Theta (\ sqrt S) [/ math].
