Esta técnica consiste en resolver un problema dividiendolo en subproblemas mas chicos del mismo tipo, resolviendo cada parte, y luego combinando las soluciones de cada parte.
Por ejemplo, si tenemos que calcular la suma de una lista de 8 elementos, podemos hacerlo dividiendo la lista en dos partes mas o menos iguales, calculando la suma de cada parte y despues sumando las dos sumas.
suma(1, 5, 3, 6, 3, 7, 4, 6) = suma(1, 5, 3, 6) + suma(3, 7, 4, 6)
La observación clave es que está misma idea se puede aplicar a cada subproblema.
En el ejemplo de la suma podemos observar que para calcular la suma de cada parte, que tiene 4 elementos, podemos volver a divider en partes iguales, de 2 elementos cada una, y sumar las sumas.
suma(1, 5, 3, 6) = suma(1, 5) + suma(3, 6)
suma(3, 7, 4, 6) = suma(3, 7) + suma(4, 6)
Al repetir esta división terminamos llegando a un problema tan chico que su resolución es trivial.
Por ejemplo, la suma de dos elementos se puede resolver en C usando el operador
+.
suma(1, 5) = 1 + 5 = 6
suma(3, 6) = 3 + 6 = 9
suma(3, 7) = 3 + 7 = 10
suma(4, 6) = 4 + 6 = 10
Una vez que se lograron resolver todos los subproblemas triviales (llamados “casos base”), procedemos a combinar las soluciones.
suma(1, 5, 3, 6) = 6 + 9 = 15
suma(3, 7, 4, 6) = 10 + 10 = 20
suma(1, 5, 3, 6, 3, 7, 4, 6) = 15 + 20 = 35
Si bien podemos frenar la división al alcanzar un subproblema “suficientemente fácil” (por ejemplo con dos elementos), muchas veces es conveniente seguir dividiendo hasta llegar a un subproblema aún más fácil (por ejemplo, con un elemento), ya que esto puede simplificar bastante la implementación y el razonamiento.
En el ejemplo de la suma, observemos que la regla de dividir en dos partes y sumar funciona bien incluso cuando solo hay dos elementos, si definimos que la suma de una lista con un solo elemento es igual a ese elemento.
suma(1, 5) = suma(1) + suma(5)
suma(1) = 1
suma(5) = 5
suma(1, 5) = 1 + 5 = 6
La implementación de este algoritmo sería una cosa así:
// calcula la suma de arr[l..r]
int suma(int arr[], int l, int r) {
int elementos = r - l;
if (elementos == 1) {
return arr[l];
} else {
int mitad = elementos / 2;
int punto_medio = l + mitad;
return suma(arr, l, punto_medio) + suma(arr, punto_medio, r);
}
}
Como se explica en la sección sobre arreglos, el rango
l..rrepresenta todos los elementos desdelhastar, sin incluirr.
En cambio, si quisieramos definir el caso de dos elementos, sería así:
// calcula la suma de arr[l..r]
int suma(int arr[], int l, int r) {
int elementos = r - l;
if (elementos == 1) {
return arr[l];
} else if (elementos == 2) {
return arr[l] + arr[l+1];
} else {
int mitad = elementos / 2;
int punto_medio = l + mitad;
return suma(arr, l, punto_medio) + suma(arr, punto_medio, r);
}
}
Notemos que igual hay que definir el caso de un elemento por dos motivos.
- Nos pueden pasar como argumento una lista de un solo elemento
- Al calcular la suma de una lista de tamaño 3, la dividimos en dos: una de tamaño 1 y otra de tamaño 2.
Si bien esta es una fórma válida de calcular la suma de una lista, hay formas mucho más fáciles e igual de eficientes (con un for).
Ahora veamos un ejemplo más realista: ordenar un arreglo de menor a mayor.
Los algoritmos de ordenamiento más simples usan bucles anidados y tienen costo cuadrático. Veamos un algoritmo mucho más rápido aplicando la idea de divide & conquer.
El algoritmo se llama merge sort y parte de la observación de que, dadas dos listas ordenadas, es posible combinarlas en tiempo lineal.
Esto da pie a un posible divide & conquer: Para ordenar una lista la dividimos en dos, ordenamos cada una (también usando merge sort) y después las combinamos.
El caso base es completamente trivial: Si una lista tiene un solo elemento ya está ordenada y no hace falta hacer ninguna operación.
// ordena el rango arr[l..r]
void sort_aux(int arr[], int l, int r) {
int n = r - l;
if (n <= 1) return;
int m = l + n / 2;
sort_aux(arr, l, m); // ordeno la primera mitad
sort_aux(arr, m, r); // ordeno la segunda mitad
merge(arr, l, m, r); // combino las dos mitades
}
// ordena el arreglo arr, de n elementos
void sort(int arr[], int n) {
sort_aux(arr, 0, n);
}
Ahora veamos en detalle cómo combinar dos listas ordenadas.
La primera observación es que el primer elemento de la lista combinada es el primer elemento de alguna de las dos listas. En particular, va a ser el menor de los dos.
combinar([1, 5, 7], [2, 4, 6, 9]) = [1, ...]
Una vez que decidimos el primer elemento, podemos quitarlo de la lista en la que estaba y repetir el proceso:
combinar([1, 5, 7], [2, 4, 6, 9])
= [1] + combinar([5, 7], [2, 4, 6, 9])
= [1] + [2] + combinar([5, 7], [4, 6, 9])
= [1] + [2] + [4] + combinar([5, 7], [6, 9])
= [1] + [2] + [4] + [5] + combinar([7], [6, 9])
= [1] + [2] + [4] + [5] + [6] + combinar([7], [9])
= [1] + [2] + [4] + [5] + [6] + [7] + combinar([], [9])
= [1] + [2] + [4] + [5] + [6] + [7] + [9] + combinar([], [])
= [1] + [2] + [4] + [5] + [6] + [7] + [9] + []
= [1, 2, 4, 5, 6, 7, 9]
En la realidad, no creamos todas las listas intermedias si no que implementamos la idea usando un algoritmo de dos punteros.
int temp[MAXN];
// suponiendo que
// - arr[l..m] está ordenado
// - arr[m..r] está ordenado
// - l <= m <= r
// ordena el rango arr[l..r]
int merge(int arr[], int l, int m, int r) {
// combinamos las dos listas y queda el resultado en temp
int i = l, j = m, k = 0;
while (i < m && j < r) {
if (arr[j] < arr[i]) temp[k++] = arr[j++];
else temp[k++] = arr[i++];
}
while (i < m) temp[k++] = arr[i++];
while (j < r) temp[k++] = arr[j++];
// ahora ponemos todos los numeros ordenados en arr
i = l, k = 0;
while (i < r) arr[i++] = temp[k++];
}
Este algoritmo tiene costo O(N log N) mas adelante veremos cómo calcular el costo de este algoritmo. Por ahora se puede convencer corriendolo en arreglos de distintos tamaños y comparandolo con algoritmos cuadráticos como bubble sort e insertion sort.
En programación competitiva hay muchos problemas que nos piden encontrar el mejor rango que cumple alguna propiedad. Por ejemplo, encontrar la maxima suma en un rango de un arreglo.
max_suma_en_rango([2, 3, -8, 7, -1, 2, 3]) = suma([7, -1, 2, 3]) = 11
Muchos de estos problemas se pueden encarar con divide and conquer. La idea típica es separar los rangos en tres grupos:
Los primeros dos grupos se resuelven recursionando. El tercero se resuelve de alguna forma ad-hoc especifica al problema, donde aprovechamos que el rango cruza el punto medio del arreglo.
En el problema de ejemplo, podemos observar que el máximo rango que cruza el corte está compuesto por un sufijo de la primera mitad y un prefijo de la segunda. Aparte, estas dos partes se pueden elegir de forma independiente: serán el máximo sufijo de la primer mitad y máximo prefijo de la segunda.
int msr_aux(int arr[], int l, int r) {
int n = r - l;
if (n == 1) return max(0, arr[l]);
int m = l + n / 2;
int a = msr_aux(arr, l, m); // maximo rango contenido en la primera mitad
int b = msr_aux(arr, m, r); // maximo rango contenido en la segunda mitad
int ls = 0, mls = 0; // maximo sufijo de la primera mitad
for (int i = 0; i < m; ++i) mls = max(mls, ls += arr[m-i-1]);
int rp = 0, mrp = 0; // maximo prefijo de la segunda mitad
for (int i = 0; i < n-m; ++i) mrp = max(mrp, rp += arr[m+i]);
return max({a, b, mls + mrp}); // combino soluciones
}
int max_suma_en_rango(int arr[], int n) {
return msr_aux(arr, 0, n);
}
Los algoritmos divide & conquista mas sencillos (que separan el problema en partes que no se solapan y hacen procesamientos en tiempo lineal) tienen costo a lo sumo O(N log N).
Pero hay algoritmos un poco mas complicados donde esto no vale.
Para estos casos usamos el teorema maestro