寻找最小化约束的最佳解决方案？

  • Z时代
  • 2024-01-10
  • 分类：问答

让我们将此问题称为Slinger-

Bird问题（实际上，Slinger类似于服务器，而Bird类似于请求，但我对此感到神经崩溃，因此我更改了它们，希望获得不同的观点！）。

  • 有S枚投石器（投掷器）和B枚鸟。

  • 抛石线不在彼此的范围内。

  • 一次抛射会杀死一名抛射者视线内的所有鸟类，并且消耗一杆一时间

我正在尝试找出最佳解决方案，在给定特定的鸟类到达模式的情况下，可以最大程度地减少杀死鸟类的时间和射击次数。让我举一个绝对数字的例子：3个投石者和4个鸟。

        Time        1            2            3           4             5
Slinger
S1                B1, B2     B1, B2, B3       B4
S2                               B1         B1, B2      B3,B4     
S3                  B1         B3, B4                 B1,B2,B3,B4

我的数据如下所示：

>> print t
[
  {
    1: {S1: [B1, B2], S2: [], S3: [B1]}, 
    2: {S1: [B1, B2, B3], S2: [B1], S3: [B3, B4]},
    3: {S1: [B4], S2: [B1,B2], S3: []},
    4: {S1: [], S2: [B3, B4], S3: [B1, B2, B3, B4]}
  }
]

我可以想到许多解决方案（t = k处的Sx表示投掷者Sx在时间k出手）：

  1. t = 1时的S1，t = 2时的S1，t = 3时的S1 <- ：3张照片+ 3个时间单位= 6

  2. t = 2时的S1，t = 3时的S1 <- ：2张照片+ 3个时间单位= 5

  3. t = 1时的S1，t = 2时的S3 <- ：2张照片+ 2个时间单位= 4

  4. S3在t = 4 <- ：1张+ 4时间单位= 5

在我看来，解决方案

是其中的最佳方案。当然，我是手工完成的（因此有可能我错过了一些东西），但我想不出一种可扩展的方法来做到这一点。另外，我担心会有一些极端的情况，因为一个射手的决定可能会改变其他射手的决定，但是因为我有全局视野，也许这并不重要。

用python解决此问题的快速，好方法是什么？我很难想出一个好的数据结构来做到这一点，更不用说算法了。我正在考虑使用动态编程，因为这似乎涉及状态空间探索，但对如何进行操作有些困惑。有什么建议？

回答：

这不是最佳分配问题，因为投掷者杀死了所有可见的鸟类。

您具有二维目标函数，因此在镜头和时间之间可能需要权衡取舍。确定特定时间限制的最小拍摄数量正是所设置的掩盖问题（如mhum所建议的）。设置覆盖问题是NP难的，很难估计，但是在实践中，使用线性规划公式的对偶进行分支定界对于找到最优解非常有效。

以上是 寻找最小化约束的最佳解决方案？ 的全部内容， 来源链接： utcz.com/qa/410709.html

回到顶部