cách sắp xếp tập hợp khi các phần tử có nhiều mối quan hệ với nhau

Question

Tôi đang tìm một thuật toán để thực hiện một số loại sắp xếp mảng mở rộng khi mối quan hệ giữa các phần tử có thể mâu thuẫn với nhau.

vì vậy chúng tôi có một bộ tôi (bài) gồm n mục i1 ... trong

Có một bộ R (mối quan hệ) gồm m mối quan hệ được xác định giữa các mục trong số I

các mối quan hệ có thể mâu thuẫn với nhau sao cho, ví dụ: một mối quan hệ nói rằng A>B và một mối quan hệ khác tại A<B.

ví dụ:

r1:i1<i35 

r2:i100<i4 

... 

rm:i45>i3 

thường, r và m (kích thước của bộ) có thể là bất kỳ số nguyên dương.

nhiệm vụ là để sắp xếp tôi nên các mặt hàng đi trong đó một cách mà tốt những người thấp hơn (dựa trên các mối quan hệ) đi trước khi những người cao hơn ...

Tôi đang tìm một thuật toán sẽ sắp xếp tập hợp sao cho nó gần với thứ tự "tối ưu" nhất có thể. Tôi đoán phải có một thuật toán nổi tiếng để giải quyết vấn đề như thế này.

Cảm ơn!

Answer 1

Tôi nghĩ rằng cách hợp lý nhất để đo lường chất lượng của một đơn hàng cụ thể là số lượng các mối quan hệ đã cho mà nó vi phạm. Nếu bạn quyết định sử dụng biện pháp này, thì vấn đề tương đương với (Minimum) Feedback Arc Set. Thật không may, vấn đề này là NP-hard, vì vậy không có thuật toán hiệu quả (đa thức) có thể tồn tại.

Trong vấn đề Bộ phản hồi Arc Set, bạn được cung cấp đồ thị được chỉ dẫn và được yêu cầu tìm một bộ cạnh kích thước tối thiểu, nếu bị xóa, sẽ hủy tất cả các chu kỳ trong biểu đồ.

Để xem điều này tương ứng với vấn đề của bạn như thế nào, hãy quan sát chúng tôi có thể biểu diễn từng mục như một đỉnh trong biểu đồ và mỗi mối quan hệ như một cạnh được chỉ đạo giữa hai đỉnh (chỉ đến, nhỏ hơn). Có xung đột nếu và chỉ khi có một chu kỳ trong biểu đồ này - tức là, nếu có một danh sách có thứ tự gồm 2 hoặc nhiều đỉnh riêng biệt v_1, v_2, ..., v_k sao cho v_i < v_ (i +1) cho tất cả i < k và cũng v_k < v_1. Không thể sắp xếp các đỉnh k này mà không vi phạm ít nhất một ràng buộc. Ngược lại, nếu không có chu kỳ tồn tại - tức là, nếu biểu đồ là directed acyclic graph - thì topological sort có thể nhanh chóng (theo thời gian tuyến tính) tìm một thứ tự hợp lệ không vi phạm ràng buộc. Do đó kích thước của bộ hồ quang phản hồi là số cạnh nhỏ nhất mà bạn cần loại bỏ để có được một đồ thị có thể được đặt hàng mà không vi phạm bất kỳ ràng buộc nào - hoặc tương đương, số cạnh nhỏ nhất phải được vi phạm trong mọi yêu cầu.