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

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

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

Предварительные сведения

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

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

Петля отжига

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

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

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

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

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

Алгоритм подсчета очков

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

Как вы измеряете «идеальное решение» - треугольность? Вот наивный и легкий бомбардир: Для каждой точки вы знаете, должно ли она быть 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;
} 

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

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

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