Javascript 固定费用运输问题的算法
Javascript algorithm for the Fixed-Charge Transportation Problem
我已经问过一个问题的名称,在该问题中我们在 Math StackExchange 中搜索具有给定的每行和每列总和的特定矩阵:
它的名字是Fixed-Charge Transportation Problem并且它还与图论和整数规划.
我也在 javascript 中实现了一些算法来解决它,但它们很慢。基本上,它会测试所有可能性。
是否有人已经实现或知道一些 js 库可以使用这种(可能还有更多)图算法?
编辑 1
只考虑等于 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);
得到了一个库。
它是 glpk.js,具有 json 接口的 GLPK 包装器。
https://github.com/jvail/glpk.js
问题可以用(混合)整数线性规划求解。
我已经问过一个问题的名称,在该问题中我们在 Math StackExchange 中搜索具有给定的每行和每列总和的特定矩阵:
它的名字是Fixed-Charge Transportation Problem并且它还与图论和整数规划.
我也在 javascript 中实现了一些算法来解决它,但它们很慢。基本上,它会测试所有可能性。
是否有人已经实现或知道一些 js 库可以使用这种(可能还有更多)图算法?
编辑 1
只考虑等于 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);
得到了一个库。
它是 glpk.js,具有 json 接口的 GLPK 包装器。
https://github.com/jvail/glpk.js
问题可以用(混合)整数线性规划求解。