2

我目前正在尝试解决以下问题，但不确定我应该使用哪种算法。它在大众识别领域。

我有一系列“权重”，*w_i*，它们可以总计为总重量。测得的总重量有一个与之相关的误差，因此是不准确的。

在给定总权重T的情况下，我需要找到最接近的k个可能的权重组合，这些组合可以总计为总数，其中k是来自用户的输入。每个砝码可以多次使用。

现在，这听起来有点像有界整数多重背包问题，然而

  • 有可能超过重量，并且
  • 我还想要所有在错误方面排名的解决方案

我可能可以使用背包问题的多次扫描来解决它，从重量误差->重量+误差，通过以足够小的增量步进，但是如果增量太大而无法错过某些可以使用的重量组合，这是可能的。

权重的数量通常很少（4 -> 10 个权重），总权重与平均权重的比率通常在 2 或 3 左右

有谁知道可能适合这里的算法的名称？

4

2 回答 2

1

您的问题实际上类似于背包问题，这是一个 NP 完全问题。

对于非常有限数量的权重，您可以通过重复来遍历每个组合，然后进行排序，从而为您提供相当多的操作；充其量：(n + k - 1)! / ((n - 1)! · k!)用于组合和n·log(n)排序部分。

现在最好通过进化算法在合理的时间内解决这类问题。

如果您从 Python 中的进化算法框架 deap 中获取以下示例： ga_knapsack.py，您会意识到通过修改第 58-59 行自动丢弃超重解决方案以获得更平滑的东西（例如线性关系），它将给出您的解决方案在比蛮力更短的时间内接近最佳解决方案。根据您的要求，最后已经为您整理好解决方案。

于 2013-07-04T13:43:16.173 回答
0

作为第一次尝试，我会进行约束编程（但后来我几乎总是这样做，所以请用一点盐来接受这个建议）：

  1. 给定 W=w_1, ..., w_i 权重和 E=e_1,.., e_i 误差（你也可以使它不对称），和 T.
  2. 查找所有集合 S（如果权重是唯一的，或者是一个列表） st sum w_1+e_1,..., w_k+e_k （其中 w_1, .., w_k \elem 和 e_1, ..., e_k \elem E） \approx T 在你从 k 派生的某个 delta 内。或者只是将其设置为某个相当大的值并在解决约束时减小它。

我只是意识到您还想将表达式 w_n op e_m 参数化为 op \elem +, - （权重和误差项的任何组合）并且我不知道哪个约束求解器会允许您这样做那。无论如何，您总是可以退回到 prolog。它可能不会飞，特别是如果你有很多重量，但它会很快给你解决方案。

于 2013-07-04T14:35:36.817 回答