решено - Найти по столбцу максимальные элементы из матрицы с учетом ограничений максимизации

Question

У меня есть N x N квадратная матрица A, состоящая из случайных положительных чисел. У меня есть функция, которую нужно максимизировать (для простоты рассмотрим, что она суммирует все входные данные), чьи входные данные представляют собой один элемент из каждого столбца матрицы. Ограничение состоит в том, что положение каждого из этих входов должно быть различным. Например, с N = 5

A =
      0.43207      0.53996      0.68063      0.70952       0.6297
       0.9656      0.72609      0.88174      0.50072      0.41381
      0.47571      0.99827     0.061184      0.93099      0.88015
      0.98318      0.42879      0.56813       0.3835    0.0039668
      0.30498      0.30033      0.76003      0.80426      0.84147
best =
     4     3     2     1     5
bestA =
      0.98318      0.99827      0.88174      0.70952      0.84147

Сейчас я проверяю все возможные комбинации. Но с увеличением размера матрицы, например, N = 10, пространство поиска становится равным 10! что слишком дорого для моих требований. Я пытался отсортировать матрицу и искать шаблоны, но я застрял в тех случаях, когда есть повторения, которые можно увидеть в этом случае после сортировки.

>> [Asorted,I] = sort(A,1,'descend')
Asorted =
      0.98318      0.99827      0.88174      0.93099      0.88015
       0.9656      0.72609      0.76003      0.80426      0.84147
      0.47571      0.53996      0.68063      0.70952       0.6297
      0.43207      0.42879      0.56813      0.50072      0.41381
      0.30498      0.30033     0.061184       0.3835    0.0039668
I =
     4     3     2     3     3
     2     2     5     5     5
     3     1     1     1     1
     1     4     4     2     2
     5     5     3     4     4

Есть ли какой-либо алгоритм или какая-либо интуиция, которую я можете следовать?

Я использую MATLAB, но вы можете использовать любой популярный язык программирования для объяснения.

Редактировать : Матрица уже задана, и она генерируется случайным образом. Основная цель - максимизировать выход заданной функции, о которой я упоминал выше, и найти, для каких входов максимальный выход.

Редактировать 2 : пример кода MATLAB для Приведенный выше пример

N=5;
A = rand(N,N)
combs = perms(1:N);
Sbest = -1;
for i=1:size(combs,1)
    x = combs(i,:);
    S = 0;
    for i=1:N
        S=S + A(x(i),i); 
    end
    if S>Sbest
        Sbest=S; best = x;
    end
end
best
[Asorted,I] = sort(A,1,'descend')

Решение : Как указано @ גלעד ברקן в комментариях, это можно решить с помощью венгерского алгоритма. Некоторые ресурсы здесь , код Matlab

Answer 1

Что касается алгоритма, я подозреваю, что может потребоваться go через все комбинации, чтобы найти лучшее, то есть грубую силу. Я не уверен, что какой-либо алгоритм теории графов напрямую применим к этой проблеме, но, возможно, некоторые модифицированные могут работать.

С точки зрения ускорения, возможно, вы можете ускорить процесс, заменив внутренний for l oop с sum, т. Е.

for i=1:size(combs,1)
    x = combs(i,:);
    S = sum(A(((1:N)-1)*N + x));
    if S > Sbest
      Sbest=S; 
      best = x;
    end
end