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

Question

让我们把这个问题称为Slinger-Bird问题(实际上Slinger类似于服务器和鸟类的请求,但我正在思考它,所以我改变它们希望得到不同的观点!).

• 有S石投掷者(slingers)和B鸟.
• 吊索不在彼此的范围内.
• 投掷一次可以杀死所有鸟类在一个抛油者的视线内,并将消耗一次和一次单位

我试图找出最佳解决方案,最大限度地减少了鸟类特定到达模式下杀死鸟类所需的时间和射击次数.让我举一个绝对数字的例子:3个Slingers和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. S1在t = 1,S1在t = 2,S1在t = 3 < - 成本:3个镜头+ 3个时间单位= 6
2. S1在t = 2,S1在t = 3 < - 成本:2次射击+ 3次时间单位= 5
3. S1在t = 1,S3在t = 2 < - 成本:2个镜头+ 2个时间单位= 4
4. S3 = t = 4时 - 成本:1次射击+ 4次时间单位= 5次

对我而言,解决方案3似乎是最佳解决方案.当然,我是手工完成的(所以有可能我可能错过了一些东西)但是我想不出这种可扩展的方式.此外,我担心有一些角落案件,因为一个射击者的决定可能会改变他人的决定,但因为我有全球观点,可能无关紧要.

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

Answer 1

这不是一个最优分配问题，因为投石手会杀死视野中的所有鸟类。

您有一个二维目标函数，因此在镜头和时间之间可能需要进行一些权衡。确定特定时间限制内的最小投篮次数正是布景掩护问题（正如 mhum 所暗示的那样）。集合覆盖问题是 NP 困难且难以近似，但在实践中，使用线性规划公式的对偶的分支定界在找到最优值方面非常有效。