Meet-in-the-middle
Meet-in-the-middle - un modo per ottimizzare soluzioni, che consiste nel suddividere il problema originale in due metà, risolverle ciascuna indipendentemente e quindi ottenere una soluzione al problema originale combinando le soluzioni delle metà.
Di conseguenza, ha senso usare
meet-in-the-middle se sono soddisfatte due condizioni.
1) Il tempo necessario per risolvere metà del problema è asintoticamente inferiore al tempo necessario per risolvere l'intero problema.
2) Risolvendo semiproblemi, si possono ottenere soluzioni all'intero problema originale e, allo stesso tempo, asintoticamente più veloci rispetto alla semplice risoluzione dell'intero problema.
Esempio
Siano quattro array di numeri interi
A,
B,
C e
D. È necessario selezionare esattamente un numero da ciascun array in modo che la somma di questi numeri sia uguale a zero. Puoi usare una soluzione ingenua, ovvero enumerare semplicemente tutte le opzioni possibili. Funzionerà per
O(n4).
Tuttavia, possiamo usare
meet-in-the-middle.
Nota che
a + b + c + d = 0 equivale a
(a + b) = -(c + d).
Dividiamo il compito in due metà, vale a dire, nella prima metà useremo solo gli array
A e
B, e nella seconda metà solo
C e
D.
Iteriamo su tutte le possibili opzioni
(a + b) nella prima metà e memorizziamo tutti i valori in una tabella hash (
unordered_map,
HashMap o simili. ). Funziona in O(n2).
Ora itereremo su tutte le possibili opzioni (c + d) nella seconda metà. Quando si considera una determinata opzione, verificheremo se esiste un valore nella tabella hash associato alla somma corrente del segno opposto (quindi abbiamo trovato due reciproci che si sommano a zero). Questa parte funziona anche in O(n2).
Non abbiamo una fase separata di "unione delle risposte" qui; in uno, lo abbiamo fatto durante la risoluzione di ciascuna delle due metà. La maggior parte delle attività avrà una situazione simile.
Abbiamo ottenuto una soluzione in O(n2) utilizzando meet-in-the-middle.
Vale la pena notare che meet-in-the-middle viene utilizzato più spesso durante l'ottimizzazione di soluzioni esponenziali, il che influisce in modo significativo sul tempo di esecuzione.