Các vấn đề về thuật toán Munkres cho bài tập không chuẩn

Question

Tôi có một biến thể của bài toán gán rằng thuật toán Munkres/Hungary thông thường dường như không được trang bị để giải quyết.

Trong bài tập phân bổ truyền thống, có n công nhân cần được chỉ định cho n công việc và ma trận có chứa chi phí phân công mỗi công nhân cho mỗi công việc.

Trong biến thể này, chúng tôi chỉ có công nhân m (m < n). Vì thuật toán Munkres yêu cầu số lượng công nhân và công ăn việc làm tương đương chúng tôi tạo ra (n - m) "công nhân giả" có thể được chỉ định cho các công việc rảnh rỗi. Ngoài ra, bản thân các công việc được tổ chức trong một số lượng lớn các thể loại rời rạc.

Chúng tôi muốn áp đặt ràng buộc rằng ít nhất 1 công việc từ mỗi danh mục được gán cho một công nhân thực sự (không giả). Điều này rất khó thực hiện một cách tao nhã: bạn có thể chọn một công việc ngẫu nhiên từ mỗi thể loại và giả tạo xói mòn từng chi phí liên quan đến công nhân thực, nhưng đây là một giải pháp rất thô lỗ làm tổn hại đến tính toàn vẹn của nhiệm vụ cuối cùng.

Điều chúng tôi hiện đang chạy thuật toán nhiều lần, mỗi lần đánh giá phân bổ đầu ra và sau đó sửa đổi ma trận chi phí sao cho chi phí cho tất cả các công việc trong bất kỳ danh mục nào được chỉ gán công nhân giả được giảm nhẹ. Điều này hoạt động đầy đủ, nhưng đối với các tập dữ liệu lớn vừa phải (n ~ = 500), quá trình này có thể mất một thời gian (mỗi phép gán Munkres có thể mất 10 giây để tính toán, và với đủ loại có thể là số lần lặp lại không quan trọng).

Có thuật toán Munkres đã sửa đổi hoặc một thuật toán khác hoàn toàn, điều đó sẽ giải quyết vấn đề này hiệu quả hơn không?

Answer 1

Các danh mục có phân tách không? Mỗi công việc có chính xác một danh mục? Sau đó, Làm thế nào về dòng chảy chi phí tối thiểu?

loại Node:

SRC - source 
SNK - sink 
C - a node or each category 
J - a node for each job 
W - a node for each worker 

các kết nối:

1) from SRC to C, capacity 1, cost 0 
2) from SRC to C, capacity infinite, cost a high number 
3) from C to J, capacity 1, cost 0 
4) from J to W, capcity 1, the cost of job J done by worker W 
5) from W to SNK, cost 0, capacity 1 

Sau đó, thuật toán sẽ điền vào liên kết loại 1 đầu tiên, có nghĩa là mỗi thể loại sẽ nhận được ít nhất một nhân viên (nếu có thể).