- Buenas. Tengo dudas sobre el ejercicio 4.6.40, según el cual deberíamos
poder encontrar los enlaces swap óptimos (optimal swap edges) para cada
enlace de PT(s) en orden O(n×h(s)).
Supongamos que el grafo de la red es un K_n y que PT(s) es un grafo estrella de centro s (el nodo s conectado a cada otro nodo). Supongamos que queremos encontrar el swap edge para el enlace entre s y un nodo x. El swap edge tendría que ser el enlace (x,y) para cualquier nodo y != s. Supongamos que uno de esos enlaces tiene costo 1 y el resto tiene costo 2. ¿Me equivoco al pensar que eso nos obligaría a recorrer todos los n-2 enlaces que conectan al nodo x con los nodos y?
Si estoy en lo correcto, y tenemos que hacer lo mismo para encontrar el swap edge de cada enlace, terminaríamos requiriendo (n-2)×(n-1), o sea, orden n² (mientras que O(n×h(n)) sería de orden n para este caso). No sé si es que estoy haciendo o entendiendo algo mal, pero no logro conseguir nada que no tenga un O(m) o un O(n²). ¿Algún consejo?
Ejercicio 4.6.40 - Orden de algoritmo para determinar optimal swap edges
Número de respuestas: 1
En respuesta a Jose Diego Suarez Hernandez
Re: Ejercicio 4.6.40 - Orden de algoritmo para determinar optimal swap edges
Buenas, lograste encontrar una solución a tu problema?
Porque yo hasta este momento sigo teniendo el mismo inconveniente que estas planteando.
No veo como es posible que un nodo del árbol logre determinar su enlace de swap sin consultar con todos sus vecinos, cuyo enlace que los conecta no pertenece al árbol, cual es su costo para alcanzar la raíz, lo cual me genera un orden mayor al solicitado.
Saludos!