Алгоритм, основанный на имитированном отжиге , может справиться с подобными вещами без слишком больших проблем. Неплохо, если у вас есть маленькие матрицы, которые, скорее всего, имеют фиксированное решение, но замечательно, если ваши матрицы становятся больше и проблема становится более сложной.
(Однако это также не соответствует вашему желанию, чтобы вставки могли выполняться постепенно.)
Отборочные
Разработайте функцию производительности, которая "оценивает" матрицу - матрицы, которые ближе к вашей треугольности, должны получить лучший результат, чем те, которые меньше треугольника-у.
Разработать набор операций, которые разрешены в матрице. Ваше описание было немного двусмысленным, но если вы можете поменять строки, то одна операция будет 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;
}
С помощью этого алгоритма оценки случайное поле с 1 и 0 даст оценку 0. «Противоположный» треугольник даст наиболее отрицательный результат, а правильное решение даст наиболее положительный результат. Разница между двумя счетами даст вам стоимость.
Если этот бомбардир не работает для вас, вам нужно будет «настроить» его, пока он не произведет нужные вам матрицы.
Этот алгоритм основан на предпосылке, что настройка этого счетчика намного проще, чем разработка оптимального алгоритма сортировки матрицы.