2

我们想为游客计划活动，根据喜欢、不喜欢等从一大堆（大约 10K）可用的活动中选择一些（大约 10 个）一天。我认为它属于“加权活动选择”类问题.

(1) 是否可以使用 OptaPlanner 解决这个问题？（2）我们应该怎么做？(3) 可以参考相关文件吗？

4

1 回答 1

1

使用 OptaPlanner 绝对可以解决这个问题，但在我看来，这并不是最优的：OptaPlanner 尝试使用各种启发式方法来解决 NP 难题 - 本质上，它以一种或另一种方式清除搜索空间。它实际上找到绝对全局最大值（或最小值）是非常不可能的 - 尽管它可能确实非常接近。

据我所知，这个问题不是 NP 难的，因此可以在多项式时间内解决，O(n^k)其中k是常数。

还有伪多项式算法，这里也可能是这种情况——复杂性取决于权重和输入大小。例如最大的重量O(w*n^k)在哪里。w

在这种情况下，您最好使用动态编程解决方案，如您链接到的 wiki 文章中所述。此外，不要忘记在权重中引入某种随机化，否则您将始终确定性地为给定的一天和给定的游客群体选择同一组“最佳”活动。

一些数学总结：

  • 10K 活动一点也不大。每项活动所需的一切是：开始时间、结束时间和体重。
    • 如果所有这些都是 32 位整数并且您创建了一个 Java 对象，那么所需的内存是（大约）3*4B + 8B (object overhead) = 20B/object，总共200 000B是~195kB.
  • 如果您实现了建议的O(n^3)动态规划算法，10K 活动的运行时间大约 10 000^3 / 10^9 (1GHz processor) = 1000 seconds ~ 17 minutes为. 这是一个非常粗略的估计。此外，该O(n log n)算法将通过这种大小的数据（使用相同的估计）在132 ns.
于 2015-09-03T08:42:05.550 回答