Сортировать матричные элементы по диагонали

Question

Я ищу алгоритм, который может сортировать строки матрицы так, чтобы элементы накапливались по диагонали.У меня будет квадратная матрица (около 80 строк / столбцов), содержащая только значения 0 и 1. Существуют алгоритмы, которые сортируют строки таким образом, что большинство элементов со значением 1 находятся ниже диагонали.Мне нужен алгоритм, который сортирует, чтобы минимизировать среднее расстояние элементов до диагонали.Примерно так: с:

0 1 0
1 0 1
1 1 0

до:

1 1 0
0 1 0
1 0 1

Поскольку я не знаком с этой темой, я надеюсь, что кто-то может мне помочь.Я не ищу полное решение.Имя такого алгоритма, если он существует или псевдокод будет достаточно.

Большое спасибо!

Answer 1

Вероятно, существует более эффективный способ, но вы можете рассматривать эту проблему как проблему присваивания (при попытке присвоить каждую строку диагональному элементу).

Это можно сделать втри шага:

1) Создайте новую матрицу M, где каждая запись M (i, j) содержит стоимость назначения строки i вашей входной матрицы диагональному элементу j.Для вашего примера эта матрица будет следующей (среднее расстояние до диагонального элемента):

1   0   1
1   1   1
1  0.5 1.5

Пример: M(0,0) = 1 - это среднее расстояние при назначении строки 0 входной матрицы (0 1 0) длядиагональный элемент с позицией 0.

2) Запустите алгоритм, чтобы найти наилучшее назначение (например, венгерский алгоритм ).Это даст вам оптимальное соотношение 1: 1 между строками и столбцами, минимизируя сумму затрат в матрице.

The result will be the elements (0,1), (1,2) and (2,0)

3) Переставьте входную матрицу, используя эти знания.Итак

row 0 -> row 1
row 1 -> row 2
row 2 -> row 0