Luis H.
Herrera
II-2023
Análisis y Desarrollo de Algoritmos
Guı́a 2
Parte 1: Verdadero o Falso
Ŗesponda verdadero o falso a las siguientes preguntas y justifique ambas.
1—– Polinomial: malo, exponencial: bueno.
2—– Los algoritmos de backtracking usan una forma de recorrer el árbol de soluciones usando ¿búsqueda
en anchura?
3—– El método maestro sirve para solucionar la siguiente recurrencia: T (n) = T (n/4) + n/ log(n).
4—– Los algoritmos de fuerza bruta enumeran todas las posibles soluciones de un problema de
optimización y escogen la mejor.
5—– Los algoritmos codiciosos tienen 3 propiedades importantes: subestructura optimal, change local
subproblems y la propiedad de greedy-choice.
6—– Programación dinámica usa un esquema de memoriación para guardar la solución a los subproblemas.
7—– En programación dinámica vimos el concepto de orden topológico el cual era un grafo no dirigido,
conexo sin ciclos.
8—– ¿Todo problema de optimización se puede resolver con una técnica codiciosa?
9—– ¿La siguiente desigualdad es cierta? T (n) = T (n/2) + O(n) = T (n/3) + O(n) = T (n/4) + O(n).
10—– f (n) + g(n) = Θ(max{f (n), g(n)}).
Parte 2: Nooo!! Knapsack again?
El algoritmo de ”Least Cost Branch and Bound” (LCBB) es una técnica utilizada en el contexto del problema
de la mochila (también conocido como el problema de la mochila 0/1) para encontrar la solución óptima de
una manera eficiente. Esta técnica combina estrategias de ramificación y poda para explorar el espacio de
soluciones de manera inteligente y determinar la mejor combinación de objetos que se pueden colocar en
una mochila, teniendo en cuenta restricciones de capacidad y valores asociados a los objetos.
Sele pide que investigue sobre el algoritmo LCBB para el problema de la mochila y presenta una descripción
general de cómo funciona el algoritmo LCBB en el contexto del problema de la mochila con un ejemplo
ilustrado.
Página 1
Luis H. Herrera
II-2023
Análisis y Desarrollo de Algoritmos
Parte 3: Balls can solve some problems
k-center Problem: Dado un conjunto P de n puntos en el espacio y un entero k ≥ n, encuentra un conjunto
C ⊆ P de k puntos con el fin de minimizar la distancia máxima entre cualquier punto de P y su centro más
cercano en C.
Podemos ver el problema del k-centro como un problema de cobertura mediante bolas. Dado un punto
x en el espacio y un radio r, definimos la bola B(x, r) como la bola (cerrada) de radio r centrada en x. Dada
cualquier solución C al problema del k-centro, denotemos ∆(C) como la distancia máxima desde cualquier
punto de P a su centro más cercano. Si ahora colocamos bolas de radio ∆(C) alrededor de cada punto en
C, es fácil ver que cada punto de P se encuentra dentro de la unión de estas bolas. Según la definición de
∆(C), uno de los puntos de P estará en el lı́mite de una de estas bolas (ya que de lo contrario podrı́amos
hacer ∆(C) más pequeño). El vecindario de cada clúster estará dentro de su bola asociada (ver Figura 2(b)).
Dada esta perspectiva, podemos ver que el problema del k-centro es equivalente al siguiente problema:
Dado un conjunto P de n puntos en el espacio y un entero k ≥ n, encuentra el radio mı́nimo ∆ y un
conjunto de bolas de radio ∆ centradas en k puntos de P de manera que P quede dentro de la unión de estas
bolas.
Algoritmo propuesto: Dado un conjunto C = {c1 , ..., ck } de centros y para cualquier ci ∈ C, definimos la
distancia de cuello de botella de ci como la distancia a su punto más lejano en N (ci ), es decir,
∆(ci ) = maxv∈N (ci ) δ(v, ci ).
Claramente, la distancia máxima de cuello de botella entre todos los centros es simplemente ∆(C). De
manera intuitiva, si pensamos en los centros de clúster como las ubicaciones de Starbucks (o tu lugar
Página 2
Luis H. Herrera
II-2023
Análisis y Desarrollo de Algoritmos
favorito), entonces cada cliente (punto en P ) está asociado con el Starbucks más cercano. El conjunto
N (ci ) son los clientes que van a la ubicación i-ésima de Starbucks, y ∆(ci ) es la distancia máxima que
cualquiera de estos clientes necesita viajar para llegar a ci . ∆(C) es la distancia máxima que cualquiera
necesita viajar para llegar a su Starbucks más cercano.
El algoritmo comienza seleccionando cualquier punto de P como el centro inicial g1 . Luego, repetimos
el siguiente proceso hasta que tengamos k centros. Sea Gi = {g1 , ..., gi } el conjunto actual de centros.
Recordemos que ∆(Gi ) es la distancia máxima de cualquier punto de P a su centro más cercano. Sea u
el punto que alcanza esta distancia. De manera intuitiva, u es el cliente más insatisfecho, ya que él/ella
tiene que conducir más lejos para llegar al Starbucks más cercano. La forma de satisfacer a u es colocar el
próximo centro directamente en u. (Ası́ que ponemos el próximo Starbucks justo encima de la casa de u.
¿Estás satisfecho ahora?) En otras palabras, establecemos
gi+1 ← u
Gi+1 ← Gi ∪ gi+1
.
• ¿El algoritmo propuesto usa una estrategia greedy?
• ¿El algoritmo propuesto siempre encunetra una solución óptima?
• Construya el pseudocódigo del algoritmo.
• ¿Cual serı́a la cantidad de operaciones del algoritmo?
Parte 4: Cutting and cutting everywhere
Rectangle Cutting Problem: Dado un rectángulo de tamaño a x b, lo que se necesita es cortarlo en
cuadrados. En cada movimiento, puedes seleccionar un rectángulo y cortarlo en dos subrectángulos de
tal manera que todas las longitudes de los lados sigan siendo números enteros. ¿Cuál es el número mı́nimo
posible de cortes que se pueden realizar? Diseñe un algoritmo de programación dinámica para resolver el
problema.
Página 3
