Consideremos una generalización de BFS bidireccional, porque la respuesta será más esclarecedora. Normalmente, un BFS bidireccional explora distancias iguales desde cada nodo, pero esto no es necesario para que sea correcto. Considere una versión de BFS bidireccional que además toma una cadena de consejos que es una secuencia de símbolos A y B que le dice en qué orden buscar desde los nodos A y B.
Una cadena de consejos de ABABAB … etc. le dice al algoritmo que busque un nivel desde A, luego un nivel desde B, luego otro nivel desde A (ahora encuentra todos los nodos a una distancia 2 de A), luego un nivel más desde B, y así sucesivamente. Esta cadena de consejos corresponde al BFS bidireccional típico. Una cadena de consejos de AAAAA … correspondería a BFS unidireccional simple de A, y AABAABAAB…. buscaría dos niveles de A para cada nivel de B.
En todos los casos, después de cada nuevo nivel que busca el algoritmo, todos los nodos recién descubiertos se cruzan con el conjunto acumulativo de nodos que alguna vez se descubrieron desde el otro vértice, y si se encuentra una intersección, el algoritmo se detiene e informa la distancia entre origen y destino como el número de símbolos de cadena de consejos procesados hasta ahora (también contando el actual).
- ¿Son los sentimientos la función del costo del algoritmo de aprendizaje automático de los humanos?
- ¿Cuáles son algunos problemas del mundo real que podrían resolverse con la programación / codificación?
- ¿Cuáles son las ventajas de desarrollar algoritmos de PNL frente al uso de API?
- Cómo calcular la suma de dígitos de cada número entre 1 y n
- ¿Cuándo puede el paralelismo hacer que sus algoritmos se ejecuten más rápido? ¿Cuándo podría hacer que sus algoritmos funcionen más lentamente?
Ahora aquí está la afirmación interesante: ¡la corrección del algoritmo es independiente de la cadena de consejos que usa!
Esto es bastante fácil de ver. Si dos nodos están separados por una distancia d, para cuando se procese el símbolo d-ésimo en la cadena de aviso, se han procesado algunos niveles de número k desde A, y se han procesado niveles d-k desde B. Un nodo que se conecta el conjunto de nodos de A y el conjunto de nodos de B definitivamente se encontrarán en este punto, porque si examinamos la ruta más corta (de longitud d) de A a B, veremos que necesariamente debe contener un nodo (es decir , el nodo k + 1-th en la ruta) que es una distancia k de A y una distancia d – k de B.
En otras palabras, no importa qué cadena de consejos tenga, si piensa en la ruta más corta de A a B, está visitando un nodo adicional a lo largo de esa ruta con cada nuevo símbolo en la cadena. Por lo tanto, si la ruta más corta tiene longitud d, se descubrirá a más tardar en el símbolo de cadena de consejos d-ésimo.
Todavía tenemos que argumentar que el nodo de conexión no se descubrirá antes que en el símbolo d-ésimo, pero esto también es fácil. Si se encontrara antes, la suma de distancias exploradas desde A y B sería menor que d. Luego usaríamos el nodo de conexión C y la ruta A -> … -> C -> … -> B como ejemplo de una ruta más corta que d, lo que contradice la hipótesis de que A y B están a una distancia d, por lo que esto puede No suceda
El algoritmo devuelve que los nodos no están conectados si ha explorado todos los nodos desde cualquier punto final y no ha encontrado ningún nodo de conexión con el otro componente conectado. Dado que la mera ausencia de B en el componente conectado de A (o viceversa) es suficiente para garantizar que A y B no estén conectados, esto es correcto.
