Найти возможные решения для матрицы с известными суммами строк / столбцов и максимальными значениями ячеек - PullRequest
2 голосов
/ 21 марта 2019

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

Любая помощь или указатели будут оценены.

Суммы строк A, B, C, суммы столбцов X, Y, Z, а также максимальное значение для каждого? известны. Все значения являются положительными целыми числами.

    C1 | C2 | C3 
-----------------
R1 | ? | ?  | ? | A
-----------------
R2 | ? | ?  | ? | B
-----------------
R3 | ? | ?  | ? | C
-----------------
     X | Y | Z

Ответы [ 2 ]

4 голосов
/ 21 марта 2019

Если вы слышали о линейном программировании (LP) и его «двоюродных братьях» (ILP, MILP), это может быть хорошим подходом, чтобы помочь вам решить вашу проблему с большой эффективностью.
AЛинейная программа состоит из набора переменных (ваша матрица неизвестна), ограничений (максимальные значения, сумма строк и столбцов) и целевой функции (здесь нет) для минимизации или максимизации.

Давайте назовем x [i] [j] значения, которые вы ищете.Со следующими данными:

NxM размеры вашей матрицы
max_val[i][j] максимальное значение для переменной x[i][j]
row_val[i] сумма значений в строке i
col_val[j] сумма значений в столбце j

Тогда возможная линейная программа, которая может решить вашу проблему:

// declare variables
int x[N][M] // or eventually float x[N][M] 
// declare constaints
for all i in 1 .. N, j in 1 .. M, x[i][j] <= max_val[i][j]
for all i in 1 .. N, sum[j in 1 .. M](x[i][j]) == row_val[i]
for all j in 1 .. M, sum[i in 1 .. N](x[i][j]) == col_val[j]
// here the objective function is useless, but you still will need one
// for instance, let's minimize the sum of all variables (which is constant, but as I said, the objective function does not have to be useful)
minimize sum[i in 1 .. N](sum[j in 1 .. M](x[i][j]))
// you could also be more explicit about the uselessness of the objective function
// minimize 0

Решатели, такие как gurobi или Cplex (но их гораздо больше, см., например, здесь ), можно решить такие проблемы невероятно быстро, особенно если ваши решения не нужнобыть целым числом, но может быть плавающим (что делает проблему намного, намного легче).Он также имеет преимущество, заключающееся в том, что он не только быстрее выполняется, но и быстрее и проще в коде.У них есть API-интерфейсы на нескольких распространенных языках программирования для упрощения их использования.
Например, вы можете разумно ожидать, что сможете решить эту проблему менее чем за минуту, с сотнями тысяч переменных в целочисленном случае, миллионами в реальномрегистр переменных.

Редактировать: В ответ на комментарий приведен фрагмент кода в OPL (язык, используемый Cplex и другими решателями LP), который решит вашу проблему.Мы рассматриваем случай 3х3.

// declare your problem input
int row_val[1..3] = [7, 11, 8];
int col_val[1..3] = [14, 6, 6];
int max_val[1..3][1..3] = [[10, 10, 10], [10, 10, 10], [10, 10, 10]];

// declare your decision variables
dvar int x[1..3][1..3];

// objective function
minimize 0;

// constraints
subject to {
    forall(i in 1..3, j in 1..3) x[i][j] <= max_val[i][j];
    forall(i in 1..3) sum(j in 1..3) x[i][j] == row_val[i];
    forall(j in 1..3) sum(i in 1..3) x[i][j] == col_val[j];
}

Концепция решателя LP заключается в том, что вы описываете только проблему, которую хотите решить, а затем решатель решает ее за вас.Проблема должна быть описана в соответствии с определенным набором правил.В текущем случае (целочисленное линейное программирование, или ILP) все переменные должны быть целыми числами, а ограничения и целевая функция должны быть линейными равенствами (или неравенствами) по отношению к переменным решения.
Тогда решатель будет работать какчерный ящик.Он проанализирует проблему, запустит алгоритмы, которые могут ее решить, с кучей оптимизаций, и выведет решение.

2 голосов
/ 21 марта 2019

Как вы написали в комментарии, что вы хотите найти собственное решение, вот несколько рекомендаций:

Используйте алгоритм Backtrack , чтобы найти решение.Ваше пространство значений состоит из 3 * 3 = 9 независимых значений, каждое из которых находится между 1 и maxval[i][j].Ваши ограничения будут суммами строк и столбцов (все они должны совпадать)

Инициализируйте ваше пространство всеми 1 с, затем увеличивайте их, пока они не достигнут maxval.Оцените условия только после того, как каждое значение будет охвачено для этого условия (в частности, после 3 значений вы можете оценить первую строку, после 6 второй строки, после 7 первого столбца, после 8 второго столбца и после 9 третьего ряда итретий столбец)

Если вы достигнете 9-го числа, когда все условия пройдут, у вас есть решение.В противном случае попробуйте значения от 1 до maxval, если ни один из них не соответствует, вернитесь назад.Если первое значение было повторено, то решения не существует.

Вот и все.


Более продвинутый возврат:

Ваши движущиеся значения находятся только в верхнем левом углу.2 * 2 = 4 значения.Третий столбец рассчитывается, при условии, что он должен быть между 1 и maxval для этого конкретного элемента.После определения элемента [1][1] необходимо рассчитать индекс [2][2], используя сумму столбца, и проверить его значение по сумме строки (или наоборот).Применяются те же правила обработки, что и выше: переберите все возможные значения, вернитесь назад, если ни одно не соответствует, и проверяйте правила, только если они могут быть применены.

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

PS: 1 используется, потому что у вас есть положительные целые числа.Если у вас есть неотрицательные целые числа, вам нужно начать с 0.

...