多维背包问题的启发式算法

Question

多维背包问题的启发式算法

javascriptalgorithmdynamic-programmingmathematical-optimizationknapsack-problem

3

这是一个关于IT技术的翻译问题。以下是需要翻译的内容：

这是对于之前问题Finding max value of a weighted subset sum of a power set的跟进问题。虽然之前的问题可以在合理的时间内解决规模小于等于15的问题（达到最优解），但我想解决规模约为2000的问题，接近最优解。

作为一个小例子，我会给出一定范围内的节点：

var range = [0,1,2,3,4];

一个函数会为范围内所有节点创建幂集，并为每个组合分配一个数字分数。负分将被移除，结果形成以下数组S。S[n][0]是所有包含节点的按位OR运算，S[n][1]是得分：

var S = [
  [1,0], //0
  [2,0], //1
  [4,0], //2
  [8,0], //3
  [16,0], //4
  [3,50], //0-1 
  [5,100], //0-2
  [6,75], //1-2
  [20,130], //2-4
  [7,179] //0-1-2 e.g. combining 0-1-2 has a key of 7 (bitwise `1|2|4`) and a score of 179.
];

最佳解决方案，最大化分数，应该是：

var solution = [[8,3,20],180]

其中solution[0]是由S中的组合数组，solution[1]是得分结果。请注意，按位8 & 3 & 20 == 0，表示每个节点仅使用一次。

问题具体描述：每个节点必须恰好使用一次，单节点组合的得分始终为0，如上面的S数组所示。

我的当前解决方案（在这里查看）使用动态规划，并适用于小问题。我已经看到了涉及动态规划的启发式方法，例如https://youtu.be/ze1Xa28h_Ns，但无法弄清如何将其应用于多维问题。鉴于问题约束条件，应用什么样的合理启发式方法？

编辑：我尝试过的事情

贪心方法（将score从大到小排序，选择下一个可行的候选项）
与上述相同，但按score/cardinality(combo)排序
GRASP（将每个score编辑高达10％，然后排序，在x秒内重复，直到找到更好的解决方案为止）

- Matt K

你所说的“size”是指15还是2000？是最大重量吗？还是物品数量？如果是后者，并且如果你实际上在内存中生成了完整的幂集，那么即使在编译语言中，你也可能无法超过30个。另外，为什么不先删除所有负元素，因为它们永远不可能成为任何最优解？（除非我误解了。） - j_random_hacker

啊，好问题。我所说的“大小”是范围的长度。生成“幂集”的函数实际上也是一种启发式方法，并且只给我一个通常小于10倍大小的幂集子集（例如，大小为1000的问题将生成一个大小为10,000的“S”）。 - Matt K

2个回答

1

这个问题实际上是一个整数优化问题，二进制变量 x_i 表示是否选择了 S 中的第 i 个元素，限制条件表明每个位只使用一次。目标是最大化所选元素的得分。如果我们定义 S_i 为 S 的第 i 个元素，L_b 为在 S 中设置了位 b 的元素的索引，w_i 为与元素 i 相关联的分数，并假设集合 S 中有 n 个元素和 k 位，则可以用数学符号表示为：

min_{x} \sum_{i=1..n} w_i*x_i
s.t.    \sum_{i \in L_b} x_i = 1  \forall b = 1..k
        x_i \in {0, 1}            \forall i = 1..n

在许多情况下，线性规划求解器比穷举搜索更有效地解决这些问题。不幸的是，我不知道任何JavaScript线性规划库（谷歌查询结果包括SimplexJS和glpk.js以及node-lp_solve -- 我对它们没有任何经验，也无法立即使用任何一个）。因此，我将使用lpSolve软件包在R中进行实现。

w <- c(0, 0, 0, 0, 0, 50, 100, 75, 130, 179)
elt <- c(1, 2, 4, 8, 16, 3, 5, 6, 20, 7)
k <- 5
library(lpSolve)
mod <- lp(direction = "max",
          objective.in = w,
          const.mat = t(sapply(1:k, function(b) 1*(bitwAnd(elt, 2^(b-1)) > 0))),
          const.dir = rep("=", k),
          const.rhs = rep(1, k),
          all.bin = TRUE)
elt[mod$solution > 0.999]
# [1]  8  3 20
mod$objval
# [1] 180

请注意，这是您问题的确切表述。但是，通过设置超时时间（您实际上需要使用R中的lpSolveAPI软件包而不是lpSolve软件包来完成此操作），您可以在达到指定的超时时间之前获得求解器找到的最佳解。这可能不是最优解，您可以控制启发式算法尝试查找更好解决方案的时间长度。如果求解器在超时之前终止，则保证该解决方案是最优的。

- josliber

拍摄，我认为你是正确的，尽管我希望不要使用LP，因为这意味着需要进行spooling R进程来处理LP（我也没有找到可靠的JS求解器）。虽然我还没有尝试过需要使用位集的大型问题（我的R语言很生疏），但对于小实例，它确实可以完成任务。 - Matt K

除了R语言，还有许多其他语言可以使用（几乎每种主要语言都有一个或三个LP求解库）。它比任何DP解决方案都要快得多，我认为这是正确的方法。不幸的是，JavaScript在运行LP时效率非常低，因为它被限制在浏览器中。您能否在非JavaScript语言上进行服务器优化，然后将结果发送回来？ - josliber

是的，我想那就是我必须要做的（服务器正在运行node，所以JS更可取）。你列出的那个node包对我来说是新的...看起来它使用了一个带有JS包装器的C++二进制文件，所以在用“正确”的方法之前，我可能会先尝试一下。 - Matt K

@MattK听起来像是最自然的解决方案。祝你好运！ - josliber

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- josliber · Accepted Answer

一个合理的启发式算法（我首先想到的）是迭代地选择具有最高分数的可行元素，消除所有与所选元素重叠位的元素。

我会通过先按得分降序排序，然后迭代地添加第一个元素并过滤列表来实现这一点，删除任何与所选元素重叠的元素。

在javascript中：

function comp(a, b) {
  if (a[1] < b[1]) return 1;
  if (a[1] > b[1]) return -1;
  return 0;
}
S.sort(comp);  // Sort descending by score

var output = []
var score = 0;
while (S.length > 0) {
  output.push(S[0][0]);
  score += S[0][1];
  newS = [];
  for (var i=0; i < S.length; i++) {
    if ((S[i][0] & S[0][0]) == 0) {
      newS.push(S[i]);
    }
  }
  S = newS;
}

alert(JSON.stringify([output, score]));

这会选择元素7、8和16，得分为179（而不是最优得分180）。