Я уже спрашивал название задачи, в которой мы ищем некую матрицу с заданными суммами каждой строки и столбца в Math StackExchange:
Она называется Проблема транспортировки с фиксированным зарядом и также связана с теорией графов и целочисленным программированием.
Я также реализовал некоторые алгоритмы для решения этой проблемы в javascript, но они медленные. По сути, он проверяет все возможности.
Кто-нибудь уже реализовал или знает какую-нибудь js-библиотеку с этим (и, возможно, более) доступным алгоритмом графа?
РЕДАКТИРОВАТЬ 1
Учитывается только фиксированная стоимость, равная единице. Этого достаточно, чтобы решить мою проблему. Сначала я ищу любое решение, поскольку можно поменять местами количества в прямоугольных ячейках, чтобы найти локальный минимум.
Это мой текущий рекурсивный алгоритм (имена переменных взяты из португальского языка, поэтому для ясности я добавил несколько комментариев):
var gra; //desired sums for rows
var dem; //desired sums for columns
var x; //current solution being built (bidimensional array); will be returned when one is found
var [iMax, jMax] = [gra.length, dem.length];
function passo(i, j) {
if (j == jMax - 1) { //if last column
var m = gra[i];
if (m > max[i][j]) {
return;
}
x[i][j] = m;
gra[i] -= m;
dem[j] -= m;
if (i == iMax - 1) {
if (gra[i] == 0 && dem[j] == 0) {
return true;
}
} else {
if (passo(i + 1, j)) return true;
}
gra[i] += m;
dem[j] += m;
} else {
if (i == iMax - 1) { //if last row
var m = dem[j];
if (m <= max[i][j] && m <= gra[i]) {
x[i][j] = m;
gra[i] -= m;
dem[j] -= m;
if (passo(0, j + 1)) return true;
gra[i] += m;
dem[j] += m;
}
} else {
for (var m = Math.min(max[i][j], gra[i], dem[j]); m >= 0; m--) {
x[i][j] = m;
gra[i] -= m;
dem[j] -= m;
if (passo(i + 1, j)) return true;
gra[i] += m;
dem[j] += m;
}
}
}
}
passo(0, 0);