Reunión en el medio
Meet-in-the-middle: una forma de optimizar soluciones, que consiste en dividir el problema original en dos mitades, resolviendo cada una de ellas de forma independiente, y luego obtener una solución al problema original combinando las soluciones de las mitades.
En consecuencia, tiene sentido usar
meet-in-the-middle si se cumplen dos condiciones.
1) El tiempo necesario para resolver la mitad del problema es asintóticamente menor que el tiempo necesario para resolver el problema completo.
2) Al resolver semiproblemas, se pueden obtener soluciones al problema completo original y, al mismo tiempo, asintóticamente más rápido que simplemente resolver el problema completo.
Ejemplo
Sean cuatro matrices de números enteros
A,
B,
C y
D. Es necesario seleccionar exactamente un número de cada matriz para que la suma de estos números sea igual a cero. Puede usar una solución ingenua, es decir, simplemente enumerar todas las opciones posibles. Esto funcionará para
O(n4).
Sin embargo, podemos usar
meet-in-the-middle.
Tenga en cuenta que
a + b + c + d = 0 es equivalente a
(a + b) = -(c + d).
Dividamos la tarea en dos mitades, a saber, en la primera mitad usaremos solo las matrices
A y
B, y en la segunda mitad solo
C y
D.
Repitamos todas las opciones posibles de
(a + b) en la primera mitad y almacenemos todos los valores en una tabla hash (
unordered_map,
HashMap o similar. ). Esto funciona en O(n2).
Ahora vamos a iterar sobre todas las opciones posibles (c + d) en la segunda mitad. Al considerar una determinada opción, verificaremos si hay un valor en la tabla hash asociado con la suma actual de signo opuesto (luego encontramos dos recíprocos que suman cero). Esta parte también funciona en O(n2).
Aquí no tenemos una fase separada de "combinación de respuestas"; en uno, hicimos esto en el curso de la resolución de cada una de las mitades. La mayoría de las tareas tendrán una situación similar.
Terminamos con una solución en O(n2) usando meet-in-the-middle.
Vale la pena señalar que meet-in-the-middle se usa con mayor frecuencia cuando se optimizan soluciones exponenciales, lo que afecta significativamente el tiempo de ejecución.