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

让我们将此问题称为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

回到顶部