找到最小化约束的最佳解决方案？ [英] Finding an optimal solution that minimizes a constraint?

问题描述

让我们把这个问题斯林格鸟的问题（实际上斯林格是类似于一个服务器和鸟的请求，但我有一个精神崩溃思考，所以我改变了他们希望得到一个不同的角度！） 。

Let us call this problem the Slinger-Bird problem (actually the Slinger is analogous to a server and the bird to a request but I was having a nervous breakdown thinking about it so I changed them hoping to get a different perspective!).

• 有石投掷（索具）和B鸟类。
• 的索具不是彼此的范围内。
• 在吊索一次可以杀死一个抛油环的视线之内所有的鸟，会消耗一杆和一个时间单元

我想弄清楚，最大限度地减少了时间和花费杀鸟鸟给出的特定到达模式拍摄张数的最优解。让我举一个例子以绝对的数字：3索具和4个小鸟。

I am trying to figure out the optimal solution that minimizes the time and the number of shots it takes to kill the birds given a particular arrival pattern of birds. Let me give an example with absolute numbers: 3 Slingers and 4 birds.

        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]}
  }
]

有一些解决方案，我能想到的（SX在t = K意味着斯林格Sx的需要一个镜头在时间k）：

There are a number of solutions I could think of (Sx at t=k implies that slinger Sx takes a shot at time 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

1. S1 at t=1, S1 at t=2, S1 at t=3 <- Cost: 3 shots + 3 time units = 6
2. S1 at t=2, S1 at t=3 <- Cost: 2 shots + 3 time units = 5
3. S1 at t=1, S3 at t=2 <- Cost: 2 shots + 2 time units = 4
4. S3 at t=4 <- Cost: 1 shot + 4 time units = 5

要我看来，解决办法 3 是最优的在此。当然，我的手这样做（这样有可能我可能错过了一些东西），但我想不出这样做的一个可伸缩的方式。另外，我很担心还有其他的情况，因为一个射手的决定可能改变其他人的决定，但因为我有全局观，可能也没关系。

To me it appears that solution 3 is the optimal one in this. Of course, I did this by hand (so there is a possibility I may have missed something) but I cannot think of a scalable way of doing this. Also, I am worried there are corner cases because the decision of one shooter might alter the decision of others but because I have the global view, may be it does not matter.

什么是快速和良好的方法来解决蟒蛇这个问题呢？我有一个很难拿出一个很好的数据结构，做到独此留下的算法来做到这一点。我想到的是用动态规划，因为这似乎涉及国家太空探索，但我就如何开展有点混乱。有什么建议？

What is a fast and good way to solving this problem in python? I am having a hard time coming up with a good data structure to do this leave alone the algorithm to do it. I am thinking of using dynamic programming because this seems to involve state space exploration but am a bit confused on how to proceed. Any suggestions?

推荐答案

这是不是最佳的分配问题，因为索具杀灭考虑到所有的鸟。

This is not an optimal assignment problem, because slingers kill all birds in view.

您有一个二维目标函数，所以有可能是一个数字拍摄和时间之间的权衡。确定拍摄数量的最小值为特定的时间限制是完全集合覆盖问题（如mhum建议）。的集合覆盖问题是NP硬和硬来近似，但在实践中，分支定界使用双线性规划制剂是相当有效地找到最佳

You have a two-dimensional objective function, so there can be a number of tradeoffs between shots and time. Determining the minimum number of shots for a particular time limit is exactly the set cover problem (as mhum suggests). The set cover problem is NP-hard and hard to approximate, but in practice, branch and bound using the dual of the linear programming formulation is quite effective in finding the optimum.

这篇关于找到最小化约束的最佳解决方案？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！