Thuật toán để đối sánh các đối tác được ưu tiên thành các nhóm ba số

Question

Thuật toán tốt để giải quyết vấn đề này là gì?

Tôi có ba nhóm người - nhóm A, nhóm B và nhóm C. Có cùng số người trong mỗi nhóm. Họ từng có một danh sách những người trong các nhóm khác mà họ sẵn sàng hợp tác. Tôi muốn nhóm tất cả những người này lại với nhau theo nhóm 3 (một từ A, một từ B và một từ C) sao cho mọi người trong nhóm muốn làm việc với những người khác trong nhóm của họ.

Làm cách nào để tìm các nhóm này một cách nhanh chóng? Nếu không có cách nào để làm cho mọi người hạnh phúc, thì thuật toán đầu tiên sẽ làm cho nhiều nhóm có ba người muốn làm việc với nhau, và sau đó làm cho nhiều người trong các nhóm khác hạnh phúc.

Điểm cuối cùng: mọi người đồng ý về người mà họ muốn làm việc (nếu người x muốn làm việc với người y, thì y cũng muốn làm việc với x). Nếu bạn cũng có thể cung cấp cho một big-O của thời gian chạy của thuật toán của bạn, đó sẽ là tuyệt vời!

Answer 1

Điều này giống như vấn đề hôn nhân ổn định, nhưng với 3 bên thay vì hai.

Hãy xem giải pháp hiệu quả cho vấn đề cũ (kết hợp đồ thị hai bên) và điều chỉnh chúng theo nhu cầu của bạn.

http://en.wikipedia.org/wiki/Stable_marriage_problem

Một sự thích nghi có thể là đầu tiên xây dựng làm việc cặp từ nhóm A và B mà thôi. Sau đó, các cặp này phải được ghép nối với một công nhân từ nhóm C mỗi. Hãy để các cặp chỉ thích công nhân mà cả hai thành viên của cặp đồng ý (đưa ra danh sách của họ). Lưu ý rằng điều này sẽ chỉ cung cấp cho một địa phương tối ưu.

Một giải pháp tối ưu để k-partite khớp là NP-khó tìm:

http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps

Xem giấy này cho một giải pháp không tối ưu cho vấn đề phù hợp với k-partite:

http://books.google.com/books?id=wqs31L1MF4IC&pg=PA309&lpg=PA309&dq=k-partite+matching&source=bl&ots=kgBuvi7ym_&sig=j3Y-nyo51y8qp0-HwToyUlkao4A&hl=de&sa=X&oi=book_result&resnum=1&ct=result

Tôi chắc chắn rằng bạn có thể tự tìm thấy những người khác trên Google ngay bây giờ mà bạn biết các cụm từ cần tìm kiếm. Tôi không biết liệu có một thuật toán hiệu quả đưa ra giải pháp tối ưu cho k = 3 hay không.

Answer 2

Điều này khác với phần mở rộng của vấn đề hôn nhân ổn định, vì tôi hiểu câu hỏi của OP, những người trong mỗi nhóm không có danh sách theo thứ tự những người mà họ muốn làm việc từ ít nhất; đó là một mối quan hệ nhị phân (sẵn sàng/không sẵn sàng).

Điều này có thể được xây dựng như một vấn đề lập trình số nguyên có thể được giải quyết khá nhanh chóng. Tôi đưa ra công thức toán học của vấn đề dưới đây; bạn có thể sử dụng một gói như glpk hoặc AMPL/CPLEX để xử lý dữ liệu.

Xác định các ma trận sau:

M1 = |A| x |B| ma trận, nơi

M1(a,b) = 1 nếu một (thành viên nhất định A) sẵn sàng hợp tác với b (cho thành viên của B), và 0 nếu ngược lại

M2 = |A| x |C| ma trận, trong đó M2(a,c) = 1 nếu (thành viên được cấp A) sẵn sàng làm việc với c (thành viên là C) và 0 khác

M2 = |B| x |C| ma trận, wh ere

M3(b,c) = 1 nếu b (cho thành viên của B) sẵn sàng hợp tác với c (thành viên nhất định C), và 0 nếu ngược lại

Bây giờ xác định một ma trận mới, chúng tôi sẽ sử dụng cho tối đa hóa của chúng tôi:

X = |A| x |B| x |C| ma trận, trong đó

X(a,b,c) = 1 nếu chúng ta tạo a, b và c hoạt động cùng nhau.

Bây giờ, xác định hàm mục tiêu của chúng tôi:

// Tối đa hóa số lượng các nhóm

tối đa hóa Sum[(all a, all b, all c) X(a,b,c)]

chịu sự ràng buộc sau:

// Để đảm bảo rằng không ai được đặt trong hai nhóm

Đối với tất cả các giá trị của một: Sum[(all j, k) X(a, j, k)] <= 1

Đối với tất cả các giá trị của b: Sum[(all i, k) X(i, b, k)] <= 1

Đối với tất cả các giá trị của c: Sum[(all i, j) X(i, j, c)] <= 1

// Để đảm bảo rằng tất cả các nhóm bao gồm các cá nhân tương thích

Đối với tất cả a, b, c: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3

Answer 3

Để bắt đầu, bạn có thể loại bỏ bất kỳ sự kiện nào mà hai bên có các danh sách rời rạc của những người mà họ sẽ làm việc trong nhóm thứ ba. Sau đó, bắt đầu một lực lượng vũ phu, tìm kiếm đầu tiên chiều sâu, luôn luôn chọn từ ít phổ biến nhất đến phổ biến nhất.

Cách khác, tương đương với việc loại bỏ ở trên, tạo thành danh sách tất cả các bộ ba có thể và làm việc từ đó thay thế.

Answer 4

Chỉ cần lưu ý nhanh về vấn đề này. Đầu tiên, nó không phải là một ví dụ về vấn đề hôn nhân ổn định, cũng không phải là một sự mở rộng của nó (tức là vấn đề kết hợp ổn định 3D). Mặc dù, nó là một vấn đề phù hợp với 3D được biết đến là NP-hard (xem Garey và Johnson). Để giải quyết một vấn đề như vậy một cách hợp lý, có khả năng là bạn sẽ cần sử dụng một số dạng ràng buộc, số nguyên hoặc lập trình tuyến tính (các phương thức khác tồn tại). Một cái gì đó có thể được sử dụng là Microsoft mới Solver Foundation, vì vậy hãy kiểm tra xem nó ra.

Answer 5

Tôi đã gặp phải sự cố tương tự và chỉ viết một tập lệnh tạo sức mạnh cho nó ...http://grouper.owoga.com/

Suy nghĩ ban đầu của tôi là: đối với một nhóm lớn hơn quá lớn đến sức mạnh vũ phu, một số loại thuật toán di truyền? Thực hiện N hoán đổi ngẫu nhiên M lần. Điểm số mỗi sắp xếp mới bằng một số chức năng 'hạnh phúc'. Lấy ít nhất, giống, lặp lại. Đối với các nhóm nhỏ, tôi đã nhận được kết quả tốt hơn bằng cách lặp lại một vài nhóm, tìm kiếm sự trao đổi 'tốt nhất' (một nhóm đã tạo ra mức tăng hạnh phúc cao nhất), làm cho điều đó, sau đó lặp đi lặp lại.