Sản xuất một đơn hàng toàn bộ hoặc một phần từ một mối quan hệ không nhất quán
Hãy tưởng tượng tôi muốn xây dựng một đơn hàng tổng số từ một tập hợp các phần tử, $E$, nhưng hàm so sánh tạo ra kết quả không xác định. Tôi tạo ra một danh sách các cặp phần tử (e, e) thông qua ứng dụng lặp đi lặp lại của hàm so sánh, sao cho mỗi phần tử trong tập hợp được biểu diễn ít nhất một lần.
Làm cách nào tôi có thể sử dụng thông tin đầu vào này để tạo ra một đơn đặt hàng tổng? Lớp thuật toán có thể được áp dụng ở đây là gì?
Để rõ hơn, tôi sẽ cung cấp một ví dụ cụ thể.
Những loại bánh pizza toppings ngon nhất là gì?
Tập hợp các phần tử của tôi $E$ bao gồm một số lớp phủ trên bánh pizza phổ biến: pepperoni, pho mát, nấm, dứa, quả chuông, ô liu.
Sau đó, đối với từng người bạn của tôi, tôi chọn các tập hợp con có kích thước ngẫu nhiên của lớp trên cùng và yêu cầu bạn tôi xếp chúng theo thứ tự từ tốt nhất đến xấu nhất. Bạn bè của tôi trả lời một cách nghiêm túc và tạo đầu vào cho thuật toán của tôi:
- pho mát, pepperoni, ô liu
- phô mai, dứa, nấm, ô liu
- chuông, nấm, ô liu
- pepperoni, pho mát, ô liu
- pho mát, quả chuông
Có vẻ như có một thứ tự không rõ ràng ở đây (mọi người đều đồng ý ô liu là tồi tệ nhất) nhưng bạn bè của tôi đã không đi đến thống nhất về việc đâu là lớp phủ trên bánh pizza tốt hơn: pho mát hoặc pepperoni. Xem xét vị trí các mặt hàng xuất hiện trong đầu vào và tần suất chúng xảy ra, tôi có thể sẽ sản xuất một đơn hàng như thế này.
- phô mai> pepperoni> quả chuông> dứa> nấm> ô liu
Tôi chỉ không chắc làm thế nào để chính thức hóa điều này và làm cho nó hoạt động cho các đầu vào lớn hơn nhiều.
Tôi nghĩ rằng giải pháp có thể liên quan đến đồ thị và các cạnh có trọng số, nhưng tôi không đủ hiểu biết về các thuật toán đồ thị để nhận ra liệu đây có phải là lĩnh vực nghiên cứu đã đặt tên hay không. Tôi đã xem qua "sắp xếp tôpô" nhưng điều đó chỉ hoạt động đối với đồ thị xoay chiều có hướng và tôi đặc biệt quan tâm đến các đầu vào không thể tạo ra DAG.
Tôi cũng nhận thấy rằng vấn đề này có vẻ tương tự như bỏ phiếu cho các đại diện dân cử. Trên thực tế, nó có phải là cùng một loại vấn đề không?
Trả lời
Thật khó để nói nếu không có nhiều bối cảnh hơn và nhiều mô hình hơn. Nó sẽ yêu cầu một số giả định về cách kết quả của hàm so sánh liên quan đến thứ tự tổng mong muốn (ẩn).
Có thể bạn muốn mô hình Bradley-Terry-Luce . Nếu vậy, có rất nhiều thuật toán tiêu chuẩn. Xem thêmhttps://cs.stackexchange.com/a/85204/755.
Có thể bạn muốn một số hệ thống xếp hạng, như Elo, v.v.
Có thể bạn muốn một hệ thống bỏ phiếu được xếp hạng , chẳng hạn như IRV, phương pháp Condorcet, số lượng Borda hoặc bất kỳ hệ thống nào khác. Tất cả chúng đều có những sai sót và sự đánh đổi khác nhau. Có một bằng chứng cho thấy rằng không hệ thống nào có tất cả các thuộc tính mà chúng ta có thể muốn - hãy xem, ví dụ, định lý Arrow và vấn đề không chuyển đổi (ngay cả khi mỗi sở thích cá nhân của bạn bè của bạn là bắc cầu, tức là một tổng số thứ tự, thì không có gì đảm bảo rằng tồn tại một đơn đặt hàng toàn cầu nhất quán với tất cả chúng).