Jak dodać liczby w macierzy, aby uzyskać minimalny wynik?

Question

Jest to bardziej problem algorytmiczny/matematyczny, ale mam nadzieję, że zaimplementuję rozwiązanie w C++.

Załóżmy, że ma matrycę, jak następuje, gdy kropki oznaczają liczby całkowite:

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

Jak poddaję minimalny efekt jeśli było wybrać jeden numer z każdej kolumnie tak, że przynajmniej jedna liczba od każdy rząd?

Na przykład, mogę wybrać AW BX CY DZ lub AZ BX CY DW ale NIE AW BW CZ DZ

Podejście brute force wydaje się brać n! obliczenia. Czy jest szybsza droga? Ostatecznie chciałbym dodać liczby w macierzach o rozmiarze ~ 60.

Ponadto, wszystkie liczby w zakresie od 0 do 256.

Answer 1

A jeśli nie chcesz kodować go samodzielnie, zawsze można użyć kogoś innego twardego pracy i rodzaju publikacji. Ten w Haskell rozwiązuje losową matrycę 60x60 w mniej niż dwie dziesiąte sekundy na moim starym laptopie. Co za świetny algorytm!

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

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