Chia người thành các nhóm để có sự hài lòng nhất

Question

Chỉ là một câu hỏi tò mò. Hãy nhớ khi trong lớp học nhóm giáo sư sẽ chia người thành các nhóm của một số lượng nhất định (n)?

Một số giáo sư của tôi sẽ có được một danh sách các n người ai muốn làm việc với và n người ta không muốn làm việc với từ mỗi học sinh, và sau đó kỳ diệu biến ra các nhóm n nơi học sinh sẽ được kết hợp với những người họ thích và tránh làm việc với những người mà họ không thích.

Với tôi thuật toán này nghe có vẻ giống như một vấn đề Knapsack, nhưng tôi nghĩ tôi sẽ hỏi xung quanh về cách tiếp cận của bạn cho loại vấn đề này sẽ là gì.

EDIT: Tìm thấy an ACM article mô tả chính xác điều gì đó giống như câu hỏi của tôi. Đọc đoạn thứ hai cho deja vu.

Answer 1

Với tôi, âm thanh có vẻ giống như một số loại sự cố clique.

Con đường tôi nhìn thấy được vấn đề, tôi đã thiết lập như sau graph:

• Đỉnh sẽ là sinh viên
• Hai sinh viên sẽ được nối với nhau bằng một cạnh nếu cả hai điều sau đây giữ:
  1. Ít nhất một trong hai sinh viên muốn làm việc với người khác.
  2. Không ai trong số hai sinh viên không muốn làm việc với người khác.

Sau đó, phân chia đồ thị thành các đồ thị có kích thước n. (Giả sử số sinh viên chia hết cho n)

Nếu điều này là không thể, tôi có thể để ràng buộc đầu tiên trên phiếu trượt, và có cạnh giữa hai người miễn là không ai trong số họ nói rõ ràng không muốn làm việc với người khác.

Đối với một cách tiếp cận để giải quyết điều này hiệu quả, tôi không có ý tưởng, nhưng điều này hy vọng sẽ giúp bạn gần gũi hơn với một số cái nhìn sâu sắc vào vấn đề.

Answer 2

Vấn đề này có thể bị đe doạ, do đó cách tiếp cận của tôi sẽ là lực lượng vũ phu đầu tiên, sau đó sửa nó khi tôi có ý tưởng tốt hơn.

Answer 3

Bạn có thể mô hình này khá dễ dàng như một vấn đề phân nhóm và bạn sẽ thậm chí không thực sự cần phải xác định một không gian, bạn có thể thực sự chỉ xác định khoảng cách:

Làm cho hai người rất gần nếu cả hai đều muốn làm việc cùng với nhau. Đóng nếu một trong số họ muốn làm việc với người khác. Khoảng cách trung bình nếu chỉ có sự thờ ơ. Cách xa nếu một người không muốn làm việc với người kia.

Sau đó, bạn chỉ có thể tìm các cụm, yay. Sau đó phân chia bất kỳ cụm nào có kích thước quá lớn, với sự tự tin rằng mọi người trong các cụm sẽ ổn khi làm việc cùng nhau.

Answer 4

Có một vài thuật toán bạn có thể sử dụng. Một ví dụ tuyệt vời là cái gọi là "vấn đề hôn nhân ổn định", có một giải pháp hoàn hảo.Bạn có thể đọc thêm về nó ở đây:

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

Vấn đề hôn nhân ổn định chỉ làm việc với hai nhóm người (nam/nữ trong trường hợp kết hôn). Nếu bạn muốn hình thành cặp bạn có thể sử dụng một biến thể, vấn đề bạn cùng phòng ổn định. Trong trường hợp này bạn tạo cặp nhưng mọi người đến từ một hồ bơi duy nhất.

Nhưng bạn đã yêu cầu một nhóm (mà tôi dịch thành> 2 người cho mỗi nhóm). Trong trường hợp này, bạn có thể để mọi người lấp đầy tốt nhất trong trận đấu tồi tệ nhất và sau đó chạy