相关疑难解决方法(0)

让我们把这个问题称为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 = …

在对我在这里的原始问题进行了大量讨论后，我为贪婪的集封面想出了以下实现。从我得到的帮助，我编码的问题转化为“贪婪的集合覆盖”，并得到了一些更多的帮助后，在这里，我想出了下面的实现。我感谢所有帮助我解决这个问题的人。以下实现工作正常，但我想使其可扩展/更快。

通过可扩展/更快，我的意思是说：

• 我的数据集在 S 中包含大约 50K-100K 集
• U 本身的元素数量非常少，在 100-500 的数量级
• S 中每个集合的大小可以是 0 到 40

这是我的尝试：

U = set([1,2,3,4])
R = U
S = [set([1,2]), 
     set([1]), 
     set([1,2,3]), 
     set([1]), 
     set([3,4]), 
     set([4]), 
     set([1,2]), 
     set([3,4]), 
     set([1,2,3,4])]
w = [1, 1, 2, 2, 2, 3, 3, 4, 4]

C = []
costs = []

def findMin(S, R):
    minCost = 99999.0
    minElement = -1
    for i, s in enumerate(S):
        try:
            cost = w[i]/(len(s.intersection(R)))
            if cost < minCost:
                minCost = cost …