1

我正在尝试开发一种算法来从更大的列表中选择活动的子集。如果选中，每个活动都会使用一定数量的固定资源（即所选活动的总和必须保持在总预算之下）。可能有多个可行子集，从中选择的方法将基于计算未选择活动的机会成本。

编辑：这不是0-1 背包问题有两个原因：

  • 背包需要整数值作为重量（即消耗的资源），而我的资源消耗（即背包用语中的质量）是一个连续变量。（显然，可以选择某种程度的精度并量化所需的资源，但我的 bin 大小必须非常小，并且 KnapsackO(2^n)在 W 中。
  • 我无法先验地计算机会成本；也就是说，我不能独立评估每个人的适合度，尽管我可以评估给定一组选定活动的效用或向现有列表添加额外任务的边际效用。

我所做的研究表明了一种幼稚的方法：

定义幂集
对于幂集的每个元素，根据不在集合中的项目计算它的效用
选择效用最高的元素

但是，我知道有一些方法可以加快执行时间和所需的内存。例如：

  • 完全枚举 powerset 是O(2^n)，但我不需要完全枚举列表，因为一旦我发现一组超出预算的任务，我知道任何添加更多任务的集合都是不可行的并且可以被拒绝。也就是说，如果{1,2,3,4}是不可行的，那么是不可行的{1,2,3,4} U {n}，其中 n 是剩余在较大列表中的任何一项任务。
  • 由于我只是在总结职责，因此任务的顺序并不重要（即，如果{1,2,3}可行，那么{2,1,3},{3,2,1}等）。
  • 最后我需要的只是选定的集合，所以我可能只需要迄今为止找到的最佳效用值来进行比较。
  • 我不需要保留列表枚举，只要我可以确定我已经查看了所有可行的枚举。（尽管我认为保留先前计算的可行子集的占空比可能会加快运行时间。）

我已经说服自己一个好的递归算法会起作用，但我不知道如何定义它，即使是在伪代码中（这可能是最有意义的，因为它将用几种语言实现——可能Matlab 用于原型设计，然后是编译语言）。

4

3 回答 3

2

背包问题是NP完全的，这意味着没有解决问题的有效方法。然而，有一个使用动态规划的伪多项式时间解决方案。有关更多详细信息，请参阅Wikipedia 部分。

但是，如果最大效用很大，您应该坚持使用近似算法。一种这样的近似方案是贪婪地选择具有最大效用/成本的项目。如果预算大，每个项目的成本小，那么这可以很好地解决。

编辑：由于您是根据不在集合中的项目来定义实用程序，因此您可以简单地重新定义成本。否定成本，然后转移一切，使您的所有价值观都是积极的。

于 2011-07-29T15:05:21.673 回答
1

正如其他人所提到的，您正在尝试解决背包问题的某些实例。虽然从理论上讲，你注定要失败，但在实践中，你仍然可以做很多事情来提高算法的性能。这里有一些（各种各样的）想法：

  • 注意回溯。{1, 2, 3, 4}这对应于您的观察，即一旦您作为解决方案划掉，{1, 2, 3, 4} u {n}就不值得一看。
  • 应用动态编程技术。
  • 明确您的实际要求：
    • 也许你不需要最好的套装？一个好的会做吗？我不知道是否有一种算法可以在多项式时间内提供良好的解决方案，但很可能有。
    • 也许您并不总是需要最好的套装？使用随机算法，您可以NP在多项式时间内解决一些问题，所有执行的失败风险为 1%（或任何您认为“足够安全”的）。

（请记住：知道停止问题无法解决是一回事，但构建一个程序来确定“hello world”实现是否会无限期运行是另一回事。）

于 2011-07-29T15:25:55.590 回答
0

我认为下面的迭代算法将遍历整个解决方案集并存储任务列表、执行它们的总成本以及未执行任务的机会成本。

看起来它会在伪多项式时间内执行：活动数量呈多项式，符合预算的活动数量呈指数级增长。

ixCurrentSolution = 1

initialize empty set solution {
    oc(ixCurrentSolution)        = opportunity cost of doing nothing
    tasklist(ixCurrentSolution)  = empty set
    costTotal(ixCurrentSolution) = 0
    }

for ixTask = 1:cActivities
    for ixSolution = 1:ixCurrentSolution 
        costCurrentSolution = costTotal(ixCurrentSolution) + cost(ixTask)
        if costCurrentSolution < costMax
             ixCurrentSolution++
             costTotal(ixCurrentSolution) = costCurrentSolution 
             tasklist(ixCurrentSolution)  = tasklist(ixSolution) U ixTask 
             oc(ixCurrentSolution)       = OC of tasks not in tasklist(ixCurrentSolution)
        endif
    endfor
endfor
于 2011-08-09T19:38:40.400 回答