Сортировка бинарной 2D-матрицы?

Question

Я ищу здесь несколько указателей, поскольку я не совсем знаю, с чего начать исследование этого.

У меня есть 2D матрицу с 0 или 1 в каждой ячейке, например:

1 2 3 4 
A 0 1 1 0 
B 1 1 1 0 
C 0 1 0 0 
D 1 1 0 0 

И я хотел бы, чтобы отсортировать его так, как «верхний треугольный», насколько это возможно, например, так:

4 3 1 2 
B 0 1 1 1 
A 0 1 0 1 
D 0 0 1 1 
C 0 0 0 1 

Строки и столбцы должны оставаться неповрежденными, т.е. элементы нельзя перемещать индивидуально и их можно заменить только «целыми».

Я понимаю, что там, вероятно, будет патологические случаи, когда матрица имеет несколько возможных отсортированных результатов (то есть ту же самую форму, но различаются по идентичности «первоначальных» строк/столбцов.)

Так, может кто-нибудь подскажите, где я могу найти некоторые отправные точки для этого? Существующая библиотека/алгоритм будет замечательной, но я соглашусь узнать имя проблемы, которую я пытаюсь решить!

Я сомневаюсь, что это проблема линейной алгебры как таковая, и, возможно, есть какая-то техника обработки изображений, которая применима.

Любые другие идеи в сторону, мое первоначальное предположение просто написать простой вставки сортировку строк, то столбцы и перебирать, что до тех пор, пока не стабилизируется (и надеемся, что обнаружение патологических случаев не слишком сложно.)

Подробнее: Дополнительная информация о том, что я пытаюсь сделать, может помочь прояснить. Каждая строка представляет участника, каждый столбец представляет собой вызов. Каждый 1 или 0 представляет «успех» для участника по конкретной задаче.

Сортируя матрицу так, чтобы все 1s находились в правом верхнем углу, я надеюсь затем предоставить рейтинг внутренней сложности каждой задачи и ранжирования конкурентов (что будет учитывать сложность проблем, которые они испытывают удалось добиться успеха не только по количеству успехов.)

Замечание об принятом ответе: Я принял Имитированный отжиг как «ответ» с предостережением о том, что этот вопрос не имеет правильного ответа. Это похоже на хороший подход, хотя на самом деле мне не удалось найти функцию подсчета очков, которая работает для моей проблемы.

Answer 1

Алгоритм, основанный на simulated annealing, может обрабатывать такие вещи без слишком много проблема. Невероятно, если у вас есть маленькие матрицы, которые, скорее всего, имеют фиксированное решение, но отлично, если ваши матрицы становятся больше и проблема становится более сложной.

(Тем не менее, это также не ваше желание, что вставки могут быть сделаны постепенно.)

Отборочных

1. Разработайте функцию производительности, что «оценка» а матрица - матрицы, которые ближе к ваша трехгранность должна получить лучший результат, чем те, которые меньше треугольника.

2. Придумать набор операций, которые разрешено на матрице. Ваше описание было немного неоднозначным, но если вы можете поменять строки, то один op будет SwapRows(a, b). Другой может быть SwapCols(a, b).

при отжиге петля

Я не буду давать полную экспозицию здесь, но идея проста. Вы выполняете случайные преобразования на матрице, используя свои операции. Вы измеряете, насколько «лучше» матрица после операции (с использованием функции производительности до и после операции). Затем вы решаете, следует ли совершить это преобразование. Вы повторяете этот процесс много.

Решение о том, следует ли совершать преобразование, является интересной частью: вам нужно решить, выполнять ли эту операцию или нет. К концу процесса отжига вы принимаете только преобразования, улучшающие оценку матрицы. Но раньше, в более хаотичное время, вы допускаете преобразования, которые не улучшают оценку. Вначале алгоритм «горячий», и все идет. В конце концов, алгоритм охлаждается и допускаются только хорошие преобразования. Если вы линейно охладиться алгоритм, то выбор, принять ли преобразование является:

public bool ShouldAccept(double cost, double temperature, Random random) { 
    return Math.Exp(-cost/temperature) > random.NextDouble(); 
} 

Вы должны прочитать отличную информацию, содержащуюся в Numerical Recipes для получения дополнительной информации по этому алгоритму.

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

алгоритм Scoring

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

Как вы измеряете «идеальное решение» - треугольность? Вот наивный и легкий бомбардир: для каждой точки вы знаете, должно ли оно быть 1 или 0.Добавьте +1 к оценке, если матрица правильная, -1, если это неправильно. Вот код, так что я могу быть явным (не тестировался! Ознакомьтесь!)

int Score(Matrix m) { 
    var score = 0; 
    for (var r = 0; r < m.NumRows; r++) { 
     for (var c = 0; c < m.NumCols; c++) { 
      var val = m.At(r, c); 
      var shouldBe = (c >= r) ? 1 : 0; 
      if (val == shouldBe) { 
       score++; 
      } 
      else { 
       score--; 
      } 
     } 
    } 
    return score; 
} 

При этом алгоритм подсчета баллов, случайным полем 1s и 0s даст оценку 0. «противоположный» треугольник даст самый отрицательный результат, и правильное решение даст самый положительный результат. Разница в двух баллах даст вам стоимость.

Если этот бомбардир не работает для вас, вам нужно будет «настроить его», пока он не выдает нужные вам матрицы.

Этот алгоритм основан на предпосылке, что настройка этого счетчика намного проще, чем разработка оптимального алгоритма для сортировки матрицы.

Answer 2

Вот отправная точка:

Преобразование каждой строки из двоичных бит в число

Сортировки чисел в порядке убывания.

Затем преобразуйте каждую строку обратно в двоичную.

Answer 3

Базовый алгоритм:

1. Определить суммы строк и хранить значения. Определите суммы столбцов и сохраните значения.
2. Сортируйте суммы строк в порядке возрастания. Сортировка столбца сумм в порядке возрастания.

Надеюсь, у вас должна быть матрица с максимально приближенной к верхней правой треугольной области.

Answer 4

Я придумал алгоритм ниже, и, похоже, он работает правильно.

Фаза 1: перемещение строк с наиболее 1 ы вверх и столбцы с большинством 1 с правой.

1. Сначала строки. Сортируйте строки, посчитав их 1 s. Нам все равно , если 2 строки имеют одинаковое количество 1 s.
2. Теперь столбцы. Сортируйте cols по , считая их 1 s. Нам все равно , если 2 cols имеют одинаковое количество 1 s.

Фаза 2: повтор фаза 1, но с дополнительными критериями, так что мы удовлетворяем треугольную матрицу морфа.
Критерий для строк: если 2 строки имеют одинаковое число 1 s, мы перемещаем до строку, начинающуюся с меньшего числа 0 s.

Критерий перевалы: если 2 перевалов имеют одинаковое количество 1 с, мы перемещаем правой седловины, что имеет меньше 0 сек в нижней части.

---

Пример:

Фаза 1

1 2 3 4      1 2 3 4     4 1 3 2 
A 0 1 1 0     B 1 1 1 0     B 0 1 1 1 
B 1 1 1 0 - sort rows-> A 0 1 1 0 - sort cols-> A 0 0 1 1 
C 0 1 0 0     D 1 1 0 0     D 0 1 0 1 
D 1 1 0 0     C 0 1 0 0     C 0 0 0 1 

Фаза 2

4 1 3 2      4 1 3 2 
B 0 1 1 1     B 0 1 1 1 
A 0 0 1 1 - sort rows-> D 0 1 0 1 - sort cols-> "completed" 
D 0 1 0 1     A 0 0 1 1 
C 0 0 0 1     C 0 0 0 1 

Edit: получается, что мой алгоритм не дает правильные треугольные матрицы всегда.
Например:

Фаза 1

1 2 3 4     1 2 3 4     
A 1 0 0 0     B 0 1 1 1     
B 0 1 1 1 - sort rows-> C 0 0 1 1 - sort cols-> "completed" 
C 0 0 1 1     A 1 0 0 0     
D 0 0 0 1     D 0 0 0 1     

Фаза 2

1 2 3 4     1 2 3 4     2 1 3 4 
B 0 1 1 1     B 0 1 1 1     B 1 0 1 1 
C 0 0 1 1 - sort rows-> C 0 0 1 1 - sort cols-> C 0 0 1 1 
A 1 0 0 0     A 1 0 0 0     A 0 1 0 0 
D 0 0 0 1     D 0 0 0 1     D 0 0 0 1 
          (no change) 

(*) Возможно фаза 3 увеличит хорошие результаты. На этой фазе мы помещаем строки, начинающиеся с меньшего числа 0 s в верхней части.

Answer 5

Treat строка в виде двоичных чисел, с крайним левым столбцом в качестве самого старшего бита, и отсортировать их в порядке убывания, сверху вниз

Treat столбцов в виде двоичных чисел с самой нижней строкой в ​​качестве наиболее значимого бита и сортируйте их по возрастанию, слева направо.

Повторяйте, пока не достигнете фиксированной точки. Доказательство того, что алгоритм заканчивается слева как упражнение для читателя.

Answer 6

Ищите бумагу 1987 года Анны Любив на тему «Двусторонние лексические обозначения матриц».

Приведено цитирование ниже. Заказ не идентичен тому, что вы ищете, но довольно близко. Если ничего другого, вы должны быть в состоянии получить довольно хорошую идею оттуда.

http://dl.acm.org/citation.cfm?id=33385