Bertemu-di-tengah
Bertemu-di-tengah - cara untuk mengoptimumkan penyelesaian, yang terdiri daripada memecahkan masalah asal kepada dua bahagian, menyelesaikan setiap satu secara bebas, dan kemudian mendapatkan penyelesaian kepada masalah asal dengan menggabungkan penyelesaian bahagian tersebut.
Sehubungan itu, masuk akal untuk menggunakan
meet-in-the-middle jika dua syarat dipenuhi.
1) Masa yang diperlukan untuk menyelesaikan separuh daripada masalah adalah secara asimptotik kurang daripada masa untuk menyelesaikan keseluruhan masalah.
2) Dengan menyelesaikan separuh masalah, seseorang boleh mendapatkan penyelesaian kepada keseluruhan masalah asal dan, pada masa yang sama, secara asimptotik lebih cepat daripada menyelesaikan keseluruhan masalah.
Contoh
Biarkan terdapat empat tatasusunan integer
A,
B,
C dan
D. Anda perlu memilih tepat satu nombor daripada setiap tatasusunan supaya jumlah nombor ini sama dengan sifar. Anda boleh menggunakan penyelesaian naif, iaitu, hanya menghitung semua pilihan yang mungkin. Ini akan berfungsi untuk
O(n4).
Walau bagaimanapun, kita boleh menggunakan
meet-in-the-middle.
Ambil perhatian bahawa
a + b + c + d = 0 adalah bersamaan dengan
(a + b) = -(c + d).
Mari bahagikan tugasan kepada dua bahagian, iaitu pada separuh masa pertama kita hanya akan menggunakan tatasusunan
A dan
B, dan pada separuh kedua hanya
C dan
D.
Mari kita ulangi semua pilihan (a + b) yang mungkin pada separuh pertama dan simpan semua nilai dalam jadual cincang (unordered_map, HashMap atau sebagainya. ). Ini berfungsi dalam O(n2).
Sekarang kita akan mengulangi semua pilihan yang mungkin (c + d) pada separuh masa kedua. Apabila mempertimbangkan pilihan tertentu, kami akan menyemak sama ada terdapat nilai dalam jadual cincang yang dikaitkan dengan jumlah semasa tanda bertentangan (kemudian kami menemui dua salingan yang menambah hingga sifar). Bahagian ini juga berfungsi dalam O(n2).
Kami tidak mempunyai fasa "answer merge" yang berasingan di sini; dalam satu, kami melakukan ini semasa menyelesaikan setiap bahagian. Kebanyakan tugasan akan mempunyai situasi yang sama.
Kami akhirnya mendapat penyelesaian dalam O(n2) menggunakan bertemu-di-tengah.
Perlu diingat bahawa meet-in-the-middle paling kerap digunakan apabila mengoptimumkan penyelesaian eksponen, yang memberi kesan ketara kepada masa berjalan.