нахождение максимальной суммы в матрице

Question

Вход: 2-мерный NxN -симметричная матрица - с NxN положительные элементы.

Выход: 2-мерная матрица NxN размера с N выбранных элементами таким образом, что его суммированием является максимальным среди все возможного выбора. Другие элементы, которые не выбраны, равны нулю. Другими словами, мы должны выбрать N элементов из матрицы для возврата максимум сумма.

Требование: Если размерность матрицы 4*4, мы должны выбрать целое. Каждая строка и столбец в матрице не должны использоваться больше, чем раз. Например, если мы имеем 4*4 матрицу, следующий элемент может быть выбран:

(1,2) 
(2,3) 
(3,4) 
(4,1) 

но если мы выбираем (1,2) и (4,1), мы не можем выбрать (1,3), потому что мы использовали 1 два раза.

Есть ли эффективный алгоритм для этой проблемы?

Answer 1

Эта проблема заключается в том странном месте, где не очевидно, что существует многогранник решения с целыми вершинами, и все же его сходство с общим соглашением препятствует мне искать снижение твердости NP. Алгоритмы общего сопоставления достаточно сложны, так что модификация одной из них была бы непростой перспективой, даже если бы был способ сделать это, поэтому я бы посоветовал использовать целочисленный программный решатель. Там же формулировка, как

maximize sum_{ij} w_{ij} x_{ij} 
subject to 
sum_{ij} x_{ij} = n 
forall k, sum_i x_{ik} + sum_j x_{kj} ≤ 2 
forall ij, x_{ij} in {0, 1}, 

где w_{ij} является ij й элемент весовой матрицы.