Как минимизировать след положительной матрицы по всей перестановке столбцов

Question

У меня есть положительная симметричная матрица 10x10 , мне нужно найти оптимальную перестановку столбцов, чтобы минимизировал след .Я не могу попробовать все перестановки, потому что это будет 10!проблема.Любые идеи о том, как решить эту проблему?

Answer 1

Вы можете считать это случаем назначения работников на задачи, когда у вас есть равное количество работников и задач.Проблема состоит в том, чтобы назначить ровно один рабочий для каждой задачи.

Рабочий - это столбец.Задача состоит в том, чтобы оставаться в определенной позиции в матрице.Стоимость - это элемент этого столбца, который находится под диагональю матрицы.

Подробнее о проблеме можно прочитать здесь https://en.wikipedia.org/wiki/Assignment_problem, одно из решений - использование венгерского алгоритма (также упомяните в ответе).связан с JNYC в комментариях).Реализации этого доступны на многих языках.