Как добавить числа в матрице для достижения минимального результата?

Это скорее алгоритмическая/математическая проблема, но я надеюсь реализовать решение на С++.

Предположим, что у меня есть такая матрица, где точки представляют целые числа:

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

Как бы я дал минимальный результат, если мне нужно было выбрать один номер из каждого столбца, чтобы было не более одного номера из каждой строки?

Например, я мог бы выбрать AW BX CY DZ или AZ BX CY DW, но NOT AW BW CZ DZ

Подход грубой силы, казалось бы, займет n! расчеты. Есть ли более быстрый путь? В конце концов я хотел бы добавить числа в матрицах размером ~ 60.

Кроме того, все числа варьируются от 0 до 256.

Ответы

Ответ 1

И если вы предпочитаете не кодировать его самостоятельно, вы всегда можете использовать чужую "трудолюбие" и "печатную публикацию". Этот в Haskell решает 60x60 случайную матрицу менее чем за две десятых доли секунды на моем старом ноутбуке. Какой отличный алгоритм!

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

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