Algoritmo
Realice un primer procedimiento de búsqueda de amplitud a partir del primer nodo “u”. Para comenzar, coloque el nodo de inicio en una cola de primero en entrar, primero en salir.
Mientras haya un nodo en la cola, despliegue el siguiente nodo en la cola. Si está a la profundidad correcta, finalice el bucle y realice el procesamiento posterior a continuación. De lo contrario, inserte todas las conexiones al nodo en la cola y continúe en bucle.
Termine en el primer nodo que esté a la profundidad correcta “n” (longitud del camino). Propongo que el número o las rutas únicas con “n” bordes / profundidad “n” es igual al número de nodos en su cola + uno para el que sacó.
- ¿En qué tipo de índices de búsqueda y enfoque se debe trabajar para un sitio web con búsqueda basada en la ciudad (y localidad) de una palabra clave, un ejemplo típico es un directorio web?
- ¿Cuánto trabaja un analista de datos / científico de datos en un día? ¿Cuánto tiempo tienes para estudiar nuevos algoritmos y técnicas?
- Si un gráfico G contiene un puente, e, ¿es posible construir un árbol de expansión que no incluya este borde?
- ¿Cuál es la diferencia básica entre loop y recursividad en C?
- Encontré un problema algorítmico y no sé cómo resolverlo. ¿Alguien me puede ayudar?
Prueba de corrección del algoritmo mediante invariante de bucle:
Bucle invariante :
Al comienzo de cada ciclo, si hay nodos en la cola, los primeros nodos “a” en la cola serán de profundidad x, y los nodos restantes serán de profundidad x + 1. Tenga en cuenta que “a” puede ser 1 para len (cola).
Inicializacion :
Antes de la primera iteración del bucle, hay un nodo en la cola, el nodo de inicio en profundidad 0. “a” == 1, y los primeros nodos “a” son de profundidad x == 0 y el resto (todos los 0 nodos) son x + 1. El bucle invariante se sostiene.
Continuación :
Para una iteración de bucle arbitrario, ahora podemos ver si la operación del bucle proporcionará o no la configuración correcta para el siguiente bucle. El primer nodo se elimina y será de profundidad “x”. Agregamos todos sus nodos conectados en profundidad x + 1 a la cola. Suponiendo que la cola se haya ordenado correctamente antes, en función del bucle invariante, el orden seguirá siendo correcto. O bien el nodo de profundidad “x” fue el último a esa profundidad y todos los nodos son ahora x + 1 (la nueva “x”) o hay algunos nodos de profundidad “x” y algún número de nodos x + 1. A partir del estado de inicialización, esto significa que la propiedad invariante de bucle se mantendrá para todos los bucles.
Terminación :
En el caso de terminación, usaré el bucle invariante para mostrar que mi algoritmo dará la cantidad correcta de rutas únicas. Hasta que se alcance la condición de terminación, la cola mantiene su orden de nodos de profundidad x y x + 1. Al final del primer nodo “n” de profundidad, solo quedarán n nodos de profundidad en la cola o posiblemente n + 1 nodos. Sin embargo, si hubo n + 1 nodos de profundidad en la cola, entonces debe haber habido una profundidad de nodo parental n. Por lo tanto, existe una contradicción, ya sea que ya había una profundidad de nodo “n” que sustituiremos por nuestro nodo como el primer nodo de terminación correcto, o no habrá nodos de profundidad n + 1. Por lo tanto, la cola + 1 nodo emergente contendrá solo nodos de profundidad “n” al final del algoritmo.
Prueba de que el algoritmo cuenta correctamente las rutas únicas con nodos de profundidad “n “:
Para cualquier nodo que se esté procesando: la ruta que condujo a esta ruta representa una ruta única. Puede haber otras formas de llegar al nodo, pero requieren diferentes rutas únicas y estarán representadas por una referencia diferente al nodo en la cola. Por lo tanto, cada conexión representa una ramificación de la ruta única original en tantas rutas únicas nuevas como bordes a otros nodos. Por lo tanto, una vez que estos nodos se agregan a la cola, representan rutas únicas a los nodos alcanzados de longitud 1 + la primera longitud de ruta. Nota: Esto considera múltiples aristas de nodo a nodo como rutas únicas.
Si consideramos la ruta original de longitud 0 bordes al nodo inicial, esta lógica se extenderá inductivamente a todas las rutas únicas de longitud “n” que estarán juntas en la cola cuando el primer nodo de profundidad “n” salga de la cola por la prueba anterior de la corrección.
Edición 1: He actualizado mi respuesta para aclarar el método que estoy sugiriendo y para profundizar en la corrección del algoritmo.
