相关疑难解决方法(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 = …

我的目标是找到尽可能少的子集[af]来组成全集A.

A = set([1,2,3,4,5,6,7,8,9,10]) # full set


#--- below are sub sets of A ---

a = set([1,2])
b = set([1,2,3])
c = set([1,2,3,4])
d = set([4,5,6,7])
e = set([7,8,9])
f = set([5,8,9,10])

实际上,我正在处理的父集A包含15k个独特元素,具有30k个子集,这些子集的长度范围从单个唯一元素到1.5k个唯一元素.

截至目前,我正在使用的代码看起来或多或少像以下一样,并且很慢:

import random


B = {'a': a, 'b': b, 'c': c, 'd': d, 'e': e, 'f': f}
Bx = B.keys()
random.shuffle(Bx)

Dict = {}

for i in Bx: # iterate through shuffled keys.
    z = [i]
    x = B[i]
    L = len(x)

    while L < len(A): …

这个问题来自我在这里发布的相关问题.@mhum建议我的问题属于覆盖问题领域.我尝试将我的问题编码为最小集合覆盖问题,目前我有一个这种形式的数据集:

Set        Cost
(1,2)        1
(1)          1
(1,2,3)      2
(1)          2
(3,4)        2
(4)          3
(1,2)        3
(3,4)        4
(1,2,3,4)    4

目标是找到一个覆盖所有数字的好套装,并试图将总成本降至最低.我的数据集很大,至少有30000套(大小从5-40个元素不等),就像这样.是否有任何好的贪婪实现来解决这个问题,还是我自己实现这个？我不是LP的专家,但任何可以解决这个问题的LP解算器(来自numpy/scipy)都是可以接受的.

我正在尝试解决或实现 R 中的集合覆盖问题的近似值。给定这样的数据框。

  sets n
1   s1 1
2   s1 2
3   s1 3
4   s2 2
5   s2 4
6   s3 3
7   s3 4
8   s4 4
9   s4 5

列中元素的唯一数量n是：

unique(d$n)
[1] 1 2 3 4 5

我想计算sets覆盖 n （宇宙）中所有独特元素的较小数量的集合（列）。在此示例中，有两个集合：s1 {1, 2, 3} 和 s4 {4, 5}。我在维基百科和互联网上读过相关内容，并且我知道可以应用贪婪算法来找到近似值。我也检查了这个链接，其中他们提到了两个包来解决此类问题，LPsolve并且Rsymphony，但我什至不知道如何开始。在我现实生活中的例子中，我有超过 40,000 个集合，每个集合有 1,000 到 10,000 个元素，而无生命或独特的元素有 80,000 个。

任何有关如何开始或继续的帮助或指导将非常感激。

数据

d <- structure(list(sets = structure(c(1L, 1L, 1L, 2L, 2L, …