Ortada Buluşma
Meet-in-the-middle - optimize etmenin bir yolu orijinal problemi ikiye bölmek, her birini bağımsız olarak çözmek ve daha sonra bu yarıların çözümlerini birleştirerek orijinal probleme bir çözüm elde etmekten oluşan çözümler.
Buna göre, iki koşul karşılanırsa
ortada buluş kullanmak mantıklıdır.
1) Problemin yarısını çözmek için gereken süre, asimptotik olarak tüm problemi çözmek için gereken süreden daha azdır.
2) Yarım problemleri çözerek, orijinal problemin tamamına çözümler elde edilebilir ve aynı zamanda asimptotik olarak tüm problemi çözmekten daha hızlıdır.
Örnek
A,
B,
C ve
D tamsayılarından oluşan dört dizi olsun. Bu sayıların toplamının sıfıra eşit olması için her diziden tam olarak bir sayı seçmek gerekir. Safça bir çözüm kullanabilir, yani tüm olası seçenekleri sıralayabilirsiniz. Bu,
O(n4) için çalışacak.
Ancak,
ortada buluş kullanabiliriz.
a + b + c + d = 0'ın
(a + b) = -(c + d)'ye eşdeğer olduğuna dikkat edin.
Görevi ikiye bölelim, yani ilk yarıda sadece
A ve
B dizilerini, ikinci yarıda sadece
C dizilerini kullanacağız. > ve
D.
İlk yarıdaki tüm olası
(a + b) seçeneklerini tekrarlayalım ve tüm değerleri bir karma tabloda (
unordered_map,
HashMap veya benzeri. ). Bu, O(n2) içinde çalışır.
Şimdi ikinci yarıda tüm olası (c + d) seçeneklerini tekrarlayacağız. Belirli bir seçeneği göz önünde bulundururken, hash tablosunda karşıt işaretin mevcut toplamıyla ilişkili bir değer olup olmadığını kontrol edeceğiz (sonra toplamı sıfıra ulaşan iki karşılıklı bulduk). Bu kısım O(n2) içinde de çalışır.
Burada ayrı bir "yanıt birleştirme" aşamamız yok; birinde, bunu her bir yarım için çözme sürecinde yaptık. Çoğu görevde benzer bir durum olacaktır.
meet-in-the-middle kullanarak O(n2) içinde bir çözüm bulduk.
meet-in-the-middle'ın çoğunlukla, çalışma süresini önemli ölçüde etkileyen üstel çözümleri optimize ederken kullanıldığını belirtmekte fayda var.