Meet in the Middle

Alcuni problemi hanno N intorno a 40, e provare tutti i 2^N sottoinsiemi è impraticabile. La tecnica meet-in-the-middle risolve questi casi di dimensione intermedia. 🤝

Divida l'input in due metà. Risolva ogni metà con la forza bruta, quindi combini in modo intelligente i due risultati parziali.

Due metà di dimensione N/2 costano 2^(N/2) ciascuna, invece di 2^N in totale. Questa riduzione alla radice quadrata trasforma 2^40 in un più gestibile 2^20.

Si vuole sapere se un sottoinsieme ha somma pari a un obiettivo T. Il problema del subset sum con N vicino a 40 è l'esempio classico per il meet-in-the-middle.

Elenchi tutte le somme dei sottoinsiemi della metà sinistra e le memorizzi. Con N/2 elementi, si tratta semplicemente di 2^(N/2) somme.

Faccia lo stesso per la metà destra, costruendo l'elenco completo delle sue somme dei sottoinsiemi. Ora dispone di due liste gestibili.

Per ogni somma destra r, le serve una somma sinistra uguale a T meno r. Un set o una lista ordinata rende rapido questo controllo.

Per obiettivi esatti usi un hash set. Per contare o trovare le somme più vicine, ordini una metà ed esegua una ricerca binaria al suo interno.

Il lavoro totale è circa 2^(N/2) moltiplicato per un fattore logaritmico dovuto alla ricerca o all'ordinamento. È questa complessità a rendere gestibile un valore di N vicino a 40.

Memorizza una metà completa, quindi la memoria cresce fino a 2^(N/2). Conservi solo ciò che è necessario per rimanere entro il limite.

Oltre al subset sum, lo usi per il massimo sottoinsieme entro un limite, il conteggio di coppie e problemi simili al logaritmo discreto. È ideale quando si può fare uno split pulito.

Applica il meet-in-the-middle a un problema sui sottoinsiemi con N elementi. Qual è all'incirca il costo in tempo?

Divida il problema in due metà, applichi la forza bruta a entrambe e poi abbini le somme sinistra e destra. Ha scambiato una piccola quantità di memoria per un enorme aumento di velocità. 🚀