Phân công nhóm

Question

Tôi gặp sự cố khi gán biến cho các tập hợp. Mỗi tập hợp có một giới hạn các biến có thể được gán cho nó và mỗi biến có thể được gán cho một số tập hợp con của tổng các tập hợp.

Thí dụ:

• acó thể theo bộ AhoặcB
• b có thể ở trong bộ B
• ccó thể theo bộ AhoặcB
• d có thể ở trong bộ A

Do đó, chúng ta có thể có A: a, d; B: b, choặc A: c, d; B: a,b(thứ tự của các biến trong tập hợp không quan trọng) /

Tất nhiên, sẽ có những lúc không thể gán tất cả các biến, những lúc chúng ta có nhiều lựa chọn và những lúc chỉ có 1 lựa chọn.

Tôi cảm thấy như có một phiên bản đơn giản của vấn đề này nhưng dường như tôi không thể đặt ngón tay vào nó. Bất kỳ con trỏ sẽ được đánh giá cao.

Answer 1

Có thể giải quyết hiệu quả bằng cách sử dụng lưu lượng tối đa. Lập mạng dòng có hồ quang công suất đơn vị từ nguồn đến từng biến trở, hồ quang công suất đơn vị từ từng biến trở đến từng bộ mà nó có thể thuộc và hồ quang từ mỗi bộ đến bồn rửa có công suất bằng công suất của bộ. . Ví dụ,

ARCS

tail head capacity
------------------
s    a    1
s    b    1
s    c    1
s    d    1
a    A    1
a    B    1
b    B    1
c    A    1
c    B    1
d    A    1
A    t    2
B    t    2

Sử dụng thuật toán luồng tối đa yêu thích của bạn để tạo luồng tích phân và trích xuất phép gán theo biến nào để thiết lập các cung có luồng.

Answer 2

Vấn đề này là NP-đầy đủ nghĩa là không có giải pháp thời gian đa thức cho điều này. Bạn sẽ phải sử dụng backtracking trong trường hợp này.

Hãy xem các liên kết sau:

https://www.geeksforgeeks.org/vertex-cover-problem-set-1-introduction-approximate-algorithm-2/ https://www.geeksforgeeks.org/set-cover-problem-set-1-greedy-approximate-algorithm/