Frodo lleva el Anillo desde la Comarca, y cada tramo del camino tiene un costo que no siempre se mide en kilómetros: a veces es tiempo, a veces es peligro, y cerca del final hasta la voluntad de quien lo lleva empieza a pesar en contra. Este sendero recorre tres problemas distintos sobre la misma pregunta de fondo: ¿cuál es el camino que menos cuesta, cuando “costo” puede significar varias cosas a la vez, y qué pasa cuando esa cuenta deja de tener sentido?
El Camino a Bree
Dificultad: ★☆☆☆☆
Los Jinetes Negros ya cruzaron el Bosque de Tejones buscando el Anillo, y la Compañía todavía no sabe cuántos días de ventaja tiene antes de que la búsqueda llegue a Bree. Por ahora, cada sendero entre dos puntos de la Comarca toma exactamente un día: la pregunta es simplemente cuántos días hacen falta, no cuáles convienen más.
Enunciado
Se modela la red de senderos como un grafo no dirigido , donde cada vértice es un punto de interés de la Comarca y cada arista es un sendero transitable en un día, sin importar el sentido.
- Explicar por qué, si todos los tramos cuestan lo mismo, buscar el camino más corto es un caso particular de Dijkstra, y relacionarlo con el algoritmo que ya conocen para este tipo de grafos (BFS).
- Resolver con BFS: indicar en qué día se llega a cada ubicación desde Hobbiton, mostrando la frontera de nodos alcanzados en cada ronda.
- Correr Dijkstra sobre la misma red (con peso 1 en cada arista) y comprobar que el vector de distancias coincide exactamente con el del punto 2. Trazar sobre la siguiente red, empezando en Hobbiton:
Extremo 1 Extremo 2 Hobbiton Delagua Hobbiton Los Gamos Delagua Bosque Viejo Los Gamos Bosque Viejo Los Gamos Túmulos Bosque Viejo Túmulos Túmulos Bree Además de estos puntos, existe una ubicación llamada “La Guarida de los Tejones” sin ninguna conexión con el resto de la red. Indicar cuántos días tarda en llegarse a Bree y qué ocurre con la Guarida.
Abrir artículo
- Si un tramo, por ejemplo cruzar el Bosque Viejo, tomara más de un día por lo denso de la vegetación, ¿dejaría de poder resolverse con BFS solamente? Explicar qué cambiaría.
Caradhras o Moria
Dificultad: ★★☆☆☆
La Compañía llega a las puertas de las Montañas Nubladas con dos caminos posibles hacia Lothlórien: subir por Caradhras, expuestos a la tormenta, o bajar a las Minas de Moria, a oscuras y sin saber qué los espera. Gandalf recuerda, además, un desvío más largo que bordea la ladera y sale directo frente al Salón de Piedra, sin pasar por las Puertas de Moria. Necesita algo más que instinto para decidir: necesita saber, con números, cuál combinación sale más barata de verdad.
Enunciado
Se modela la ruta como un grafo dirigido , donde cada vértice es un punto del camino y el peso de cada arista combina tiempo y peligro en una sola cifra (cuanto más alto, peor).
- Trazar Dijkstra a mano desde Rivendel sobre la siguiente red, mostrando en cada iteración los conjuntos y , el nodo elegido, y los vectores de distancias y de predecesores:
Desde Hasta Peso Rivendel Caradhras 1 Rivendel Puertas de Moria 2 Rivendel Salón de Piedra 6 Puertas de Moria Salón de Piedra 3 Salón de Piedra Puerta Este 2 Puerta Este Lothlórien 1 Caradhras Lothlórien 8
- A partir de la traza, indicar qué conviene: cruzar Caradhras o entrar a Moria, y reconstruir el camino completo usando el vector de predecesores.
- Lothlórien recibe una distancia tentativa muy temprano en la traza, que varias iteraciones después termina mejorándose. Explicar, apoyándose en la propiedad vista en el Bloque 3 (), por qué Dijkstra puede dejarlo sin cerrar durante todo ese tiempo, y qué hubiera pasado si se lo hubiera cerrado apenas recibió esa primera distancia.
- Si un explorador élfico les avisara de un sendero directo entre Puertas de Moria y Lothlórien, ¿en qué cambiaría la traza? (No hace falta rehacerla completa: alcanza con explicar qué pasos se verían afectados).
Abrir artículoVer solución
Numeramos los nodos igual que en el ejemplo del algoritmo visto en clase:
Nodo Lugar 0 Rivendel (origen) 1 Caradhras 2 Puertas de Moria 3 Salón de Piedra 4 Puerta Este 5 Lothlórien Y las aristas del enunciado quedan:
Desde Hasta Peso 0 1 1 0 2 2 0 3 6 2 3 3 3 4 2 4 5 1 1 5 8 1. Traza de Dijkstra
En cada iteración elegimos, entre los nodos de , el de menor acumulada, lo cerramos (lo pasamos a ), y relajamos sus sucesores con
Iteración S V-S w D[0]/P[0] D[1]/P[1] D[2]/P[2] D[3]/P[3] D[4]/P[4] D[5]/P[5] Inicial {0} {1,2,3,4,5} 0 0/− 1/0 2/0 6/0 ∞/− ∞/− 1 {0,1} {2,3,4,5} 1 0/− 1/0 2/0 6/0 ∞/− 9/1 2 {0,1,2} {3,4,5} 2 0/− 1/0 2/0 5/2 ∞/− 9/1 3 {0,1,2,3} {4,5} 3 0/− 1/0 2/0 5/2 7/3 9/1 4 {0,1,2,3,4} {5} 4 0/− 1/0 2/0 5/2 7/3 8/4 5 {0,1,2,3,4,5} ∅ 5 0/− 1/0 2/0 5/2 7/3 8/4 Dos celdas cambian a mitad de camino:
- : arranca en (el desvío directo desde Rivendel) y en la iteración 2 baja a , porque pasar primero por Puertas de Moria () resulta más barato que el atajo directo.
- : recibe su primer valor tentativo muchísimo antes de cerrarse: en la iteración 1, al cerrar Caradhras, se fija en . Recién en la iteración 4, al cerrar Puerta Este, se relaja (), mejor que el anterior, y se actualiza a .
2. ¿Caradhras o Moria?
La distancia final a Lothlórien es . Reconstruyendo con el vector de predecesores:
es decir, Rivendel → Puertas de Moria → Salón de Piedra → Puerta Este → Lothlórien, con costo .
La alternativa por Caradhras es Rivendel → Caradhras → Lothlórien, con costo . Conviene Moria, aunque por muy poco: apenas punto de diferencia.
3. ¿Por qué Lothlórien no se cierra apenas recibe su primera distancia tentativa?
La propiedad garantiza que, cuando Dijkstra cierra un nodo , ningún nodo todavía abierto puede después ofrecerle una mejora. Pero esa garantía es sobre el nodo que se cierra, no sobre uno que apenas recibió una distancia tentativa: mientras el nodo sigue en , todavía puede bajar.
Eso es justo lo que pasa acá: en la iteración 1, Lothlórien queda con , pero en ese mismo momento el nodo 2 sigue abierto con , muchísimo menor a . Como los pesos son positivos, no hay ninguna garantía todavía de que sea lo mejor posible, así que Dijkstra lo deja esperando tres iteraciones más, hasta que efectivamente aparece un camino mejor por Puerta Este.
Si se lo hubiera cerrado apenas llegó esa primera distancia tentativa, el algoritmo se hubiera quedado para siempre con (la ruta por Caradhras), sin enterarse nunca de que existía un camino de costo atravesando Moria.
4. ¿Y si hubiera un sendero directo de Puertas de Moria a Lothlórien?
Agregar una arista de peso solo puede cambiar el resultado si mejora el mejor camino ya encontrado (). Como el nodo 2 se cierra muy temprano (iteración 2, con ), esta arista daría una candidata de . Cambia algo únicamente si , es decir, si el nuevo sendero pesara menos de 6. En ese caso Lothlórien recibiría una distancia mejor bastante antes en la traza (incluso antes que la propia tentativa por Caradhras), y el camino final ya no pasaría ni por Salón de Piedra ni por Puerta Este. Si pesara o más, la traza no cambia: la cadena completa por Moria sigue siendo al menos tan buena.
La Sombra del Anillo
Dificultad: ★★★☆☆
Cerca de Cirith Ungol, Gollum promete un atajo. Frodo, cada vez más rendido al peso del Anillo, siente que aceptarlo cuesta menos de lo que debería, y ese es exactamente el problema: en esta red, algunos tramos “restan” en lugar de sumar, y hay un rincón cerca del túnel de Ella-Laraña del que, una vez adentro, cuesta muchísimo salir.
Enunciado
Se modela la situación como un grafo dirigido con pesos que pueden ser negativos: un peso negativo representa un tramo que el Anillo hace sentir “más liviano” de lo que en verdad es.
- Sobre la siguiente red, intentar correr Dijkstra a mano desde las Escaleras de Cirith Ungol:
Desde Hasta Peso Escaleras de Cirith Ungol Túnel de Ella-Laraña 4 Escaleras de Cirith Ungol Paso de los Espías 10 Túnel de Ella-Laraña Atajo de Gollum -3 Atajo de Gollum Túnel de Ella-Laraña -2 Túnel de Ella-Laraña Paso de los Espías 6 Paso de los Espías Torre de Cirith Ungol 3 Indicar en qué punto exacto se rompe el argumento de la propiedad de corte: cuál sería el nodo que Dijkstra cerraría de más, y qué nodo tiene, en realidad, un camino más corto que Dijkstra nunca llegaría a encontrar.
Abrir artículo
- Identificar el ciclo negativo de la red: cuáles son sus aristas y cuánto vale su peso total. Explicar, en términos de la historia, qué representa quedar atrapado en un ciclo negativo en este contexto.
- ¿Qué algoritmo sí permite detectar este problema? Explicar a alto nivel, sin trazarlo a mano, qué tendría que hacer distinto de Dijkstra para lograrlo.
- Si el ciclo negativo no existiera pero igual hubiera algún tramo con peso negativo, ¿alcanzaría con ignorar esos tramos y correr Dijkstra normalmente sobre el resto? Justificar.
Si este sendero te dejó pensando en qué pasa cuando el costo deja de sumar y empieza a restar: eso es exactamente lo que resuelve Bellman-Ford, más lento que Dijkstra pero capaz de tolerar pesos negativos y hasta detectar cuando un ciclo negativo hace que la pregunta “¿cuál es el camino más corto?” directamente deje de tener respuesta. Y en el otro extremo, cuando lo que hay que optimizar no es cómo llegar de un punto a otro sino cómo conectar toda una red gastando lo menos posible (unir cada reino de la Tierra Media con el menor número de puentes, por ejemplo), ahí empiezan Kruskal y Prim.