Vấn đề chuyển nhượng, một chức năng gọn gàng?

Question

Vì một số assignment problem có thể được đặt dưới dạng một ma trận đơn lẻ, tôi đang lang thang nếu có nhiều chức năng để giải quyết một ma trận như vậy. Cho đến nay tôi đã không tìm thấy. Có lẽ một trong các bạn biết nếu numpy/scipy có một hàm phân công-giải quyết vấn đề?

Chỉnh sửa: Trong khi đó, tôi đã tìm thấy triển khai trăn (không phải là vất vả/scipy) tại http://www.clapper.org/software/python/munkres/. Tôi vẫn cho rằng việc triển khai gọn gàng/scipy có thể nhanh hơn nhiều, đúng không?

Answer 1

Không, NumPy không chứa hàm nào như vậy. Tối ưu hóa kết hợp nằm ngoài phạm vi của NumPy. Có thể làm điều đó với một trong các trình tối ưu hóa trong scipy.optimize nhưng tôi có cảm giác rằng các ràng buộc có thể không có dạng đúng.

NetworkX cũng có thể bao gồm thuật toán cho các sự cố gán.

Answer 2

Có một triển khai thực hiện Munkres' algorithm làm mô-đun mở rộng trăn có hỗ trợ gọn gàng. Tôi đã sử dụng nó thành công trên máy tính xách tay cũ của tôi. Tuy nhiên, nó không hoạt động trên máy tính mới của tôi - tôi cho rằng có một vấn đề với các phiên bản "mới" gọn gàng (hoặc vòm 64bit).

Answer 3

Hiện tại, việc triển khai gọn gàng thuật toán munkres trong scikit-learn theo sklearn/utils/linear_assignment_.py phụ thuộc duy nhất của nó là yếu tố. Tôi đã thử nó với một số ma trận khoảng 20x20, và nó có vẻ nhanh gấp 4 lần so với ma trận liên kết trong câu hỏi. cProfiler hiển thị 2.517 giây so với 9.821 giây cho 100 lần lặp.

Answer 4

Tôi đã hy vọng rằng phiên bản mới hơn scipy.optimize.linear_sum_assignment sẽ là nhanh nhất, nhưng (có lẽ không đáng ngạc nhiên) các Cython library (mà không có hỗ trợ pip) là nhanh hơn đáng kể, ít nhất là đối với trường hợp sử dụng của tôi:

$ python -m timeit -s 'from scipy.optimize import linear_sum_assignment; import numpy as np; np.random.seed(0); c = np.random.rand(20,30)' 'a,b = linear_sum_assignment(c)' 
100 loops, best of 3: 3.43 msec per loop 
$ python -m timeit -s 'from munkres import munkres; import numpy as np; np.random.seed(0); c = np.random.rand(20,30)' 'a = munkres(c)' 
10000 loops, best of 3: 139 usec per loop 
$ python -m timeit -s 'from scipy.optimize import linear_sum_assignment; import numpy as np; np.random.seed(0);' 'c = np.random.rand(20,30); a,b = linear_sum_assignment(c)' 
100 loops, best of 3: 3.01 msec per loop 
$ python -m timeit -s 'from munkres import munkres; import numpy as np; np.random.seed(0)' 'c = np.random.rand(20,30); a = munkres(c)' 
10000 loops, best of 3: 127 usec per loop 

tôi thấy kết quả tương tự cho các kích thước giữa 2x2 và 100x120 (10-40x nhanh hơn).

Answer 5

Tuy nhiên, một triển khai nhanh khác, như đã được gợi ý bởi @Matthew: scipy.optimize có chức năng được gọi là linear_sum_assignment. Từ tài liệu:

Phương pháp được sử dụng là thuật toán Hungary, còn được gọi là thuật toán Munkres hoặc Kuhn-Munkres.

https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html