Làm cách nào để thêm số trong ma trận vào kết quả tối thiểu lợi nhuận?

Question

Đây là một vấn đề về thuật toán/toán học nhưng tôi hy vọng sẽ triển khai một giải pháp trong C++.

Giả sử tôi có một ma trận như vậy mà chấm đại diện cho số nguyên:

W X Y Z 
A . . . . 
B . . . . 
C . . . . 
D . . . . 

Làm thế nào tôi sẽ mang lại kết quả tối thiểu nếu tôi phải chọn một số từ mỗi cột như rằng có ít nhất một số từ từng hàng?

Ví dụ, tôi có thể chọn AW BX CY DZ hoặc AZ BX CY DW nhưng KHÔNG AW BW CZ DZ

Phương pháp brute force sẽ dường như mất n! tính toán. Có cách nào nhanh hơn không? Cuối cùng tôi muốn thêm số vào ma trận có kích thước ~ 60.

Ngoài ra, tất cả các số nằm trong khoảng từ 0 đến 256.

Answer 1

Và nếu bạn không muốn mã đó cho mình, bạn luôn có thể sử dụng của người khác làm việc chăm chỉ và xuất bản loại. Điều này trong Haskell, giải quyết một ma trận ngẫu nhiên 60x60 trong ít hơn hai phần mười của một giây trên máy tính xách tay cũ của tôi. Thật là một thuật toán tuyệt vời!

import Data.Algorithm.Munkres 
import Data.Array.Unboxed 
import Data.List (transpose) 

solve n matrix = 
    hungarianMethodInt (listArray ((1,1),(n,n)) $ concat $ transpose matrix)