Encontro no meio
Meet-in-the-middle - uma forma de otimizar soluções, que consiste em quebrar o problema original em duas metades, resolvendo cada uma de forma independente, e então obter uma solução para o problema original combinando as soluções das metades.
Da mesma forma, faz sentido usar
meet-in-the-middle se duas condições forem atendidas.
1) O tempo necessário para resolver metade do problema é assintoticamente menor que o tempo para resolver todo o problema.
2) Resolvendo meio-problemas, pode-se obter soluções para o problema todo original e, ao mesmo tempo, assintoticamente mais rápido do que apenas resolver o problema todo.
Exemplo
Sejam quatro arrays de inteiros
A,
B,
C e
D. É necessário selecionar exatamente um número de cada array para que a soma desses números seja igual a zero. Você pode usar uma solução ingênua, ou seja, simplesmente enumerar todas as opções possíveis. Isso funcionará para
O(n4).
No entanto, podemos usar
meet-in-the-middle.
Observe que
a + b + c + d = 0 é equivalente a
(a + b) = -(c + d).
Vamos dividir a tarefa em duas metades, ou seja, na primeira metade usaremos apenas os arrays
A e
B, e na segunda metade apenas
C e
D.
Vamos iterar todas as opções
(a + b) possíveis na primeira metade e armazenar todos os valores em uma tabela hash (
unordered_map,
HashMap ou similar. ). Isso funciona em O(n2).
Agora vamos iterar sobre todas as opções possíveis (c + d) na segunda metade. Ao considerar uma determinada opção, verificaremos se existe um valor na tabela hash associado à soma atual do sinal oposto (então encontramos dois recíprocos que somam zero). Esta parte também funciona em O(n2).
Não temos uma fase separada de "resposta combinada" aqui; em um, fizemos isso durante a resolução de cada uma das metades. A maioria das tarefas terá uma situação semelhante.
Acabamos com uma solução em O(n2) usando meet-in-the-middle.
Vale a pena notar que meet-in-the-middle é usado com mais frequência ao otimizar soluções exponenciais, o que afeta significativamente o tempo de execução.