El Sendero de la Codicia

Se dice que la codicia no es solo una debilidad de dragones y hombres: bien entendida, también puede ser una estrategia. Este sendero recorre tres problemas donde la mejor decisión en cada paso (la más inmediata, la más voraz) resulta ser también la mejor decisión posible para el problema completo. No hace falta mirar atrás ni reconsiderar lo ya elegido: alcanza con, en cada instante, tomar lo mejor que el momento ofrece.

Vas a conocer a un dragón que no puede cargar más de lo que su fuerza le permite, a un consejero que debe repartir un día que no alcanza para todos, y a esa misma bestia bajo la montaña, ahora del otro lado, intentando defenderse en lugar de atacar. En los tres casos, ordenar bien antes de decidir es la mitad del problema resuelto.

---

El Tesoro de Smaug

Dificultad: ★☆☆☆☆

Tras siglos dormido sobre su tesoro, Smaug debe abandonar temporalmente su guarida en la Montaña Solitaria: los enanos han comenzado a horadar un nuevo túnel y el dragón, prudente a su manera, prefiere trasladar lo que pueda antes de que lo descubran. El problema es que ni siquiera un dragón puede cargar todo el oro de Erebor de una sola vez: sus garras y su lomo soportan, como mucho, un peso máximo $W$. Ante Smaug hay $n$ sacos de tesoro, cada uno con su propio peso $w_i$ y su propio valor $v_i$ (las esmeraldas pesan poco y valen mucho, el oro en bruto pesa como el oro en bruto). A diferencia de un ladrón cualquiera, Smaug puede desgarrar un saco con sus garras y llevarse solo una fracción de su contenido, si eso le permite aprovechar mejor el espacio que le queda.

Enunciado

El problema es la variante fraccionaria de la mochila: dada una capacidad $W$ y $n$ sacos, cada uno con peso $w_i$ y valor $v_i$, se puede tomar cualquier fracción $x_i\in [0,1]$ de cada saco, no solo el saco entero, maximizando ${\sum }_i{x}_i{v}_i$ sujeto a ${\sum }_i{x}_i{w}_i\le W$.

1. Explicar por qué ordenar los sacos por su razón valor/peso $\frac{v_i}{w_i}$, de mayor a menor, y tomarlos en ese orden hasta completar la capacidad $W$, produce siempre una solución óptima en la variante fraccionaria. Justificar con un argumento de intercambio: ¿qué pasaría si Smaug tomara primero una unidad de peso de un saco con menor razón valor/peso, existiendo todavía unidades disponibles de un saco con mayor razón?

2. Diseñar el algoritmo paso a paso, indicando qué ocurre cuando el peso restante de la capacidad es menor que el peso completo del siguiente saco en el orden.

3. Trazar a mano la ejecución con capacidad $W=50$ y los siguientes sacos:

   Saco	Peso ($w_i$)	Valor ($v_i$)
   Esmeraldas	10	60
   Oro amonedado	20	100
   Oro en bruto	30	120
   Gemas talladas	15	90

   Mostrar el orden elegido, qué fracción de cada saco toma Smaug y el valor total transportado.

4. Determinar la complejidad temporal del algoritmo en función de $n$, identificando qué paso domina el costo total.

Abrir artículo

---

El Consejo de Elrond

Dificultad: ★★★☆☆

Rivendel se ha llenado de visitantes. Elfos, enanos, hombres y hasta algún mago han llegado con noticias urgentes y quieren ser escuchados por el Consejo antes de que termine el día. Cada delegación $i$ necesita hablar durante un intervalo $[s_i,f_i)$ específico (algunas deben esperar a que termine cierto rito, otras necesitan la luz del atardecer para desplegar sus mapas) y ese intervalo no se puede interrumpir ni negociar. Elrond preside el Consejo, pero el día tiene las horas que tiene: dos delegaciones no pueden hablar si sus intervalos se superponen, y una vez que una delegación empieza a exponer hay que dejarla terminar. Elrond quiere decidir a cuáles delegaciones va a recibir, de forma de escuchar a la mayor cantidad posible antes de que caiga la noche.

Enunciado

Dadas $n$ delegaciones, cada una con un intervalo $(s_i,f_i)$ de inicio y fin, se busca el subconjunto más grande de intervalos mutuamente compatibles (sin superposición).

1. Explicar por qué ordenar las delegaciones por su hora de finalización $f_i$ (y no por su hora de inicio $s_i$, ni por la duración $f_i-s_i$ de su exposición) y elegir en forma ávida, en cada paso, la primera delegación compatible con las ya elegidas, garantiza el número máximo de delegaciones atendidas. Construir un ejemplo concreto donde ordenar por duración (las exposiciones más cortas primero) elija menos delegaciones que el óptimo.

2. Diseñar el algoritmo paso a paso.

3. Trazar a mano la ejecución con las siguientes delegaciones:

   Delegación	Inicio	Fin
   Hombres de Gondor	0	6
   Istari	8	9
   Enanos de Erebor	3	5
   Hobbits de la Comarca	5	7
   Dúnedain del Norte	6	10
   Elfos de Lórien	1	4
   Rohirrim	5	9

   Indicar en qué orden se evalúan las delegaciones y cuáles quedan finalmente aceptadas.

4. Determinar la complejidad del algoritmo en función de $n$, identificando qué paso domina el costo total.

Ver solución

1. Por qué ordenar por fin de intervalo

Argumento de intercambio (breve): supongamos que una solución óptima no elige, entre todas las delegaciones, a la que termina primero (llamémosla $D_1$, con fin $f_1$ mínimo). Sea $D_j$ la primera delegación que sí eligió esa solución óptima. Como $f_1\le f_j$ y $D_1$ no se superpone con ninguna otra elegida (termina antes que cualquier otra que empiece después de $D_j$), podemos reemplazar $D_j$ por $D_1$ sin perder compatibilidad y sin reducir la cantidad de delegaciones aceptadas. Repitiendo este intercambio se llega a que siempre existe una solución óptima que contiene a la delegación de fin más temprano. Por eso conviene elegirla primero, descartar todo lo que se superponga con ella, y repetir el mismo razonamiento sobre lo que queda: es un problema idéntico, pero más chico.

Por qué falla ordenar por duración: una delegación corta puede “tapar” a dos delegaciones más largas que sí serían compatibles entre sí. Contraejemplo mínimo:

Delegación	Intervalo	Duración
P	(0, 4)	4
Q	(3, 5)	2
R	(4, 8)	4

Ordenando por duración se elige primero Q (duración 2), que se superpone con P y con R, así que quedan descartadas ambas → solo 1 delegación atendida.
Ordenando por fin, en cambio, se elige P (fin 4) y después R (fin 8, compatible porque empieza justo en 4) → 2 delegaciones atendidas, que es el óptimo real.

2. Diseño del algoritmo

1. Ordenar las $n$ delegaciones por su hora de fin, de menor a mayor.
2. Inicializar ultimo_fin = -∞ y aceptadas = [].
3. Para cada delegación $(s_i,f_i)$ en ese orden:
   • Si $s_i\ge$ ultimo_fin: aceptarla (agregar a aceptadas) y actualizar ultimo_fin = f_i.
   • Si no, descartarla (se superpone con la última aceptada).
4. Devolver aceptadas.

3. Traza a mano

Datos originales:

Delegación	Inicio	Fin
Hombres de Gondor	0	6
Istari	8	9
Enanos de Erebor	3	5
Hobbits de la Comarca	5	7
Dúnedain del Norte	6	10
Elfos de Lórien	1	4
Rohirrim	5	9

Paso 1: ordenar por fin (Istari y Rohirrim empatan en fin = 9; el orden entre ellos no afecta el resultado):

Orden	Delegación	Inicio	Fin
1	Elfos de Lórien	1	4
2	Enanos de Erebor	3	5
3	Hombres de Gondor	0	6
4	Hobbits de la Comarca	5	7
5	Rohirrim	5	9
6	Istari	8	9
7	Dúnedain del Norte	6	10

Paso 2: recorrido ávido (ultimo_fin inicial $=-\infty$):

Delegación	Inicio	¿Inicio ≥ último fin?	Decisión	ultimo_fin tras el paso
Elfos de Lórien	1	$1\ge -\infty$	Aceptada	4
Enanos de Erebor	3	$3\ge 4$ → no	Rechazada	4
Hombres de Gondor	0	$0\ge 4$ → no	Rechazada	4
Hobbits de la Comarca	5	$5\ge 4$	Aceptada	7
Rohirrim	5	$5\ge 7$ → no	Rechazada	7
Istari	8	$8\ge 7$	Aceptada	9
Dúnedain del Norte	6	$6\ge 9$ → no	Rechazada	9

Resultado: Elrond escucha a Elfos de Lórien (1,4), Hobbits de la Comarca (5,7) e Istari (8,9): 3 delegaciones, y no existe forma de encajar una cuarta sin superposición.

4. Complejidad

• Ordenar las $n$ delegaciones por fin: $O(n\log n)$.
• Recorrer la lista ordenada una sola vez, con trabajo constante por delegación: $O(n)$.

Total: $O(n\log n)+O(n)=O(n\log n)$, dominado por el paso de ordenamiento.

Abrir artículo

---

Las Defensas de Erebor

Dificultad: ★★★★★

Los años pasaron y Smaug, ahora del otro lado del problema, necesita defender lo que le queda de tesoro. La Montaña tiene $n$ accesos conocidos (puertas viejas, chimeneas de ventilación, grietas que los enanos abrieron y nunca sellaron del todo) y cada uno es vulnerable solamente durante un intervalo de tiempo determinado: la puerta oeste solo puede forzarse mientras dura cierto relevo, cierta grieta solo es practicable mientras la luna ilumina cierta piedra, y así con cada acceso. Smaug quiere ubicar trampas o centinelas que actúen en un instante puntual (no durante un intervalo, sino en un momento exacto) de forma que cada acceso quede cubierto por al menos una trampa durante su ventana de vulnerabilidad. Colocar cada trampa tiene un costo, así que Smaug quiere usar la menor cantidad posible.

Enunciado

Dados $n$ accesos, cada uno con un intervalo de vulnerabilidad $[s_i,f_i]$, se busca el menor conjunto de puntos $\{p_1,p_2,\dots \}$ tal que todo intervalo contenga al menos un $p_j$.

Este problema es distinto al de el consejo de elrond: ahí se buscaba elegir la mayor cantidad de intervalos compatibles entre sí; acá se busca elegir la menor cantidad de puntos que, entre todos, toquen a todos los intervalos dados (un punto ubicado dentro de un intervalo lo cubre).

1. Explicar la estrategia voraz: ordenar los accesos por su instante de finalización $f_i$ de vulnerabilidad, de menor a mayor; colocar una trampa exactamente en el instante de finalización del primer acceso sin cubrir; descartar todos los accesos que esa trampa cubre; y repetir con los accesos restantes. Justificar por qué conviene colocar la trampa en el extremo final del intervalo, y no en cualquier otro punto interior, para maximizar la cantidad de accesos adicionales que esa misma trampa puede llegar a cubrir.

2. Argumentar, aunque sea de forma intuitiva, por qué ninguna estrategia puede cubrir todos los accesos con menos trampas que las que propone el algoritmo voraz (pensar qué pasaría si una solución óptima no incluyera ese primer punto de finalización, ni ningún punto anterior a él, para cubrir al acceso que vence primero).

3. Trazar a mano la ejecución con los siguientes accesos, dados como intervalos de vulnerabilidad (inicio, fin):

   Acceso	Inicio	Fin
   Puerta Oeste	1	4
   Chimenea Sur	2	6
   Grieta del Cuervo	4	7
   Túnel de los Enanos	5	9
   Puerta Principal	8	10
   Escalinata Oculta	9	12
   Ventana de la Guardia	11	13

   Mostrar en qué orden se procesan los accesos, dónde se coloca cada trampa y qué accesos cubre cada una.

4. Determinar la complejidad del algoritmo en función de $n$, identificando qué paso domina el costo total.

Abrir artículo

---

Si este sendero te dejó pensando en cómo decidir rápido sin arrepentirse después: la misma idea, elegir siempre lo mejor disponible en cada paso, ordenando bien antes de mirar nada más, es el corazón de algoritmos como Kruskal y Prim (para construir la red más barata posible), Dijkstra (para encontrar el camino más corto) y la codificación de Huffman (para comprimir información sin perder nada). En todos esos casos, igual que en la mochila de Smaug, el Consejo de Elrond o las defensas de Erebor, el desafío no es probar todas las combinaciones posibles: es encontrar el criterio de orden correcto, el que garantiza que decidir de a un paso por vez alcanza para llegar a la mejor solución global.