Gặp gỡ trung gian
Meet-in-the-middle - một cách để tối ưu hóa các giải pháp, bao gồm chia vấn đề ban đầu thành hai nửa, giải quyết từng vấn đề một cách độc lập và sau đó thu được giải pháp cho vấn đề ban đầu bằng cách kết hợp các giải pháp của các nửa.
Theo đó, bạn nên sử dụng
meet-in-the-middle nếu hai điều kiện được đáp ứng.
1) Thời gian cần thiết để giải một nửa bài toán nhỏ hơn thời gian để giải toàn bộ bài toán.
2) Bằng cách giải một nửa bài toán, người ta có thể thu được lời giải cho toàn bộ bài toán ban đầu, đồng thời, nhanh hơn một cách tiệm cận so với việc chỉ giải toàn bộ bài toán.
Ví dụ
Giả sử có bốn mảng số nguyên
A,
B,
C và
D. Cần phải chọn chính xác một số từ mỗi mảng sao cho tổng của các số này bằng 0. Bạn có thể sử dụng một giải pháp ngây thơ, cụ thể là chỉ cần liệt kê tất cả các tùy chọn có thể. Điều này sẽ hoạt động cho
O(n4).
Tuy nhiên, chúng ta có thể sử dụng
meet-in-the-middle.
Lưu ý rằng
a + b + c + d = 0 tương đương với
(a + b) = -(c + d).
Hãy chia nhiệm vụ thành hai nửa, cụ thể là trong nửa đầu chúng ta sẽ chỉ sử dụng các mảng
A và
B, và trong nửa sau chỉ sử dụng
C và
D.
Hãy lặp lại tất cả các tùy chọn
(a + b) có thể có trong nửa đầu và lưu trữ tất cả các giá trị trong bảng băm (
unordered_map,
HashMap hoặc tương tự. ). Điều này hoạt động trong O(n2).
Bây giờ chúng ta sẽ lặp lại tất cả các tùy chọn có thể có (c + d) trong nửa sau. Khi xem xét một tùy chọn nhất định, chúng tôi sẽ kiểm tra xem có một giá trị nào trong bảng băm được liên kết với tổng hiện tại của dấu hiệu ngược lại hay không (sau đó chúng tôi tìm thấy hai nghịch đảo có tổng bằng 0). Phần này cũng hoạt động trong O(n2).
Chúng tôi không có giai đoạn "hợp nhất câu trả lời" riêng ở đây; trong một, chúng tôi đã làm điều này trong quá trình giải quyết từng nửa. Hầu hết các nhiệm vụ sẽ có tình trạng tương tự.
Chúng tôi đã tìm ra giải pháp trong O(n2) bằng cách sử dụng meet-in-the-middle.
Điều đáng chú ý là meet-in-the-middle thường được sử dụng nhất khi tối ưu hóa các giải pháp hàm mũ, điều này ảnh hưởng đáng kể đến thời gian chạy.