Thuật toán cho tập hợp tối đa không bị chi phối

Question

Chạy thuật toán cho vấn đề tiếp theo: Đặt S của n điểm trong mặt phẳng 2D, điểm (x1, y1) chiếm ưu thế điểm khác (x2, y2) nếu x1> x2 và y1> y2. Tìm tập hợp điểm M lớn nhất sao cho M là một tập hợp con của S và không có điểm nào của M bị chi phối bởi một điểm khác của S.

Answer 1

Sắp xếp tất cả các điểm bằng cách tăng x tọa độ. Nếu hai điểm có cùng toạ độ x, hãy sắp xếp chúng bằng cách giảm tọa độ y. Bây giờ, có thể chỉ ra rằng một tập hợp con của các điểm không bị chi phối nếu và chỉ khi tọa độ y của chúng không tăng theo thứ tự sắp xếp của chúng ta, nghĩa là mỗi toạ độ y nhỏ hơn hoặc bằng tọa độ trước đó trong chuỗi tiếp theo.

Vì vậy, các thuật toán sẽ là:

1. Sắp xếp các điểm như mô tả ở trên. Thời gian: O (n * logn).
2. Tìm các đoạn tọa độ y không tăng dần dài nhất. Thời gian: O (n * logn). Điều này có thể được thực hiện bằng cách điều chỉnh thuật toán để tìm kiếm longest increasing subsequence.

Điều này cho phép có thể đặt lớn nhất trong O (n * logn).

Answer 2

Có thuật toán phân chia và chinh phục thực hiện điều này trong thời gian O (n * logn).

Hãy chia các điểm thành hai nửa, có kích thước n/2 mỗi điểm dựa trên toạ độ x của chúng. Chúng tôi tìm thấy điểm không bị chi phối trong cả hai nửa. Bạn cần phải quan sát rằng tất cả các điểm không bị chi phối trong nửa bên phải sẽ tồn tại trong danh sách cuối cùng của chúng tôi.

Với quan sát này chúng ta có thể viết bước kết hợp của chúng ta, loại bỏ tất cả các điểm không bị chi phối ở nửa bên trái có y phối hợp nhỏ hơn toạ độ y cao nhất của điểm trong tập không được chi phối ở bên phải một nửa. Chúng ta có tập hợp các điểm không bị chi phối.

Thuật toán:

Find the median along x axis - O(n) time 
Find non-dominated points in the right half - T(n/2) 
Find non-dominated points in the right half - T(n/2) 
set of non-dominated points could be on O(n) so, the combine step might have to check O(n) points 

phương trình cho thời gian:

T(n) = 2T(n/2) + O(n) which is O(n*logn) 

Bạn có thể cải thiện điều này hơn nữa để O (n * logH) nơi H là số điểm không chiếm ưu thế , nó đòi hỏi cái nhìn sâu sắc hơn về vấn đề và nó là một phần mở rộng tốt cho bạn để làm việc trên.