寻找最小化约束条件的最优解？

Question

寻找最小化约束条件的最优解？

7

让我们称这个问题为“弹弓鸟”问题（实际上，弹弓类似于服务器，而鸟则是请求，但我一直在紧张崩溃，所以我改变了它们，希望能获得不同的视角！）。

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

我能想到几种解决方案（Sx在t=k时表示Slinger Sx在k时刻射击）：

S1在t=1，S1在t=2，S1在t=3 <- 成本：3次射击+ 3个时间单位= 6
S1在t=2，S1在t=3 <- 成本：2次射击+ 3个时间单位= 5
S1在t=1，S3在t=2 <- 成本：2次射击+ 2个时间单位= 4
S3在t=4 <- 成本：1次射击+ 4个时间单位= 5

对我来说，解决方案 3 似乎是最佳的。当然，我是手动计算的（所以有可能会漏掉某些情况），但我无法想出一种可扩展的方法来解决这个问题。此外，我担心会出现特殊情况，因为一个射手的决定可能会改变其他人的决定，但因为我有全局视图，也许这并不重要。

有什么快速有效的方法可以使用Python解决这个问题吗？我很难想出一个好的数据结构来解决这个问题，更不用说解决它的算法了。我考虑使用动态规划，因为这似乎涉及状态空间探索，但我有点困惑该如何继续。有什么建议吗？

- Legend

供您参考：只有一个时间段，您的问题等同于最小集合覆盖问题。 - mhum

@mhum：我再仔细想了想，我认为这个问题实际上可以通过将时间概念移除并给每个集合附加成本函数来编码成最小集合覆盖。当然，我不确定如何将slinger编码到问题中。你对这种方法有什么建议吗？ - Legend

3个回答

1

我建议使用位图(bitmap)来呈现弹弓手和鸟的图像，例如：

S1 = B1 = 1, S2 = B2 = 2, S3 = B3 = 4, B4 = 8

那么输入数据可以写成：

bird_data = [[3, 0, 1], [7, 1, 12], [8, 3, 0], [0, 12, 15]]

现在可以这样编写成本函数：

def cost(shots):
    hit = units = 0
    for show, shot in zip(bird_data, shots):
        units += 1
        for n, birds in enumerate(show):
            if shot & 1:
                units += 1
                hit |= birds
                if hit == 15: # all are hit
                    return units
            shot >>= 1
    return 99 # penalty when not all are hit

现在通过计算成本函数的最小值，轻松找到最佳镜头：

from itertools import product

shot_sequences = product(*([range(7)]*len(bird_data)))

print min((cost(shots), shots) for shots in shot_sequences)

这将打印

(4, (0, 5, 0, 0))

这意味着最佳方案是在S1和S3（5 = 1 + 4）在t=2时同时触发4个单位。当然，您的解决方案也是可行的，其中S1在t=1时触发，S3在t=2时触发，两者成本相同。

然而，由于算法使用暴力方法，运行所有可能的射击序列，只有在数据集非常小的情况下才能快速且可行，就像您的示例一样。

- Cito

谢谢您提供这个。我还不太确定我理解编码的方式，但我会再试一次。乍一看，这可能不可行，因为在我的实际问题中，时间长度约为10000，我认为这将使运行时间爆炸。 - Legend

1

我假设您在开始算法时已经知道了所有给出的数字，并且在完成t1后不会得到t2等。

我还假设两个弹弓可以同时发射，虽然这不应该有太大影响。

在第一个选择时，您可以为每个单元格分配一个值，即amountOfBirdsInCell-time。

这给您带来了两个值为1的单元格，即S1t1、S1t2，其余单元格的值较低。

只有最后一个单元格的时间对您的得分有影响，因此选择最早的单元格将为下一轮删除其上的时间，使其成为最有价值的时间。这是第一个选择。

现在，从所有单元格中删除那个第一个选择中杀死的鸟。

重复剩余单元格的值确定过程。在您的示例中，单元格S3t2将给出最高结果，即0。

重复此过程，您将获得最早时间的最有价值的单元格。

您的示例没有涵盖的一个重要部分：如果您的第一个最有价值的选择是在t2，那么下一个最有价值的选择可能在t1或t2，因此您应该考虑它们。但是，由于t2已经确认，您不应该考虑它们的时间对其价值的影响。

我从未写过Python，只是因为算法标签而来，所以这里是一些类似于Java/C的伪代码：

highestCellTime = 0;
while(birdsRemain)
{
    bestCell;

    for(every cell that has not been picked yet)
    {
        currentCellValue = amountOfBirds;
        if(currentCellTime > highestCellTime)
        {
            currentCellValue = currentCellValue - currentCellTime;
        }

        if(currentCellValue < bestCellValue)
        {
            bestCell = thisCell;
        }
        else if(currentCellValue == bestCellValue && currentCellTime < bestCellTime)
        {
            bestCell = thisCell;
        }
    }
    addCellToPicks(bestCell);
    removeBirdsFromOtherCells(bestCellBirds);
}

除非我忘了什么，否则您现在在选择集合中拥有最佳单元的组合。

我希望这段代码对Python程序员有意义。如果有人能翻译一下，请务必这样做！当您这样做时，请删除此文本和早期提到的Java / C伪代码。

编辑者注：这是第一个版本，没有得到最好的单元。我猜这一定是我的代码中的错误，但无论如何我都会在这里发布。

import math

cellsNotPicked = range(0,12)
cellToBird = {
    0: [1, 2],
    1: [],
    2: [1],
    3: [1,2,3],
    4: [1],
    5: [3,4],
    6: [4],
    7: [1,2],
    8: [],
    9: [],
    10: [3,4],
    11: [1,2,3,4]
}

picks = []

def getCellValue(cell):
    return len(cellToBird[cell])

def getCellTime(cell):
    return int(math.floor(cell / 3)) + 1

birdsRemain = 4

while(birdsRemain > 0):

    bestCell = 0;

    for thisCell in cellsNotPicked:

        currentCellValue = getCellValue(thisCell);

        currentCellTime = getCellTime(thisCell)
        highestCellTime = getCellTime(bestCell)

        if(currentCellTime > highestCellTime):
            currentCellValue = currentCellValue - currentCellTime;

        if(currentCellValue < getCellValue(bestCell)):
            bestCell = thisCell
        elif (currentCellValue == getCellValue(bestCell)) and (currentCellTime < getCellTime(bestCell)):
            bestCell = thisCell

    picks.append(bestCell)
    cellsNotPicked.remove(bestCell)

    birdsToRemove = cellToBird[bestCell]

    for key in cellToBird:
        for bird in birdsToRemove:
            try:
                cellToBird[key].remove(bird)
                birdsRemain -= 1
            except:
                pass

print picks

- Aberrant

首先，感谢您的时间。我已将算法转换为实际代码，但是当然，我的代码中可能存在错误，因为它给出的答案是选择的单元格[9,10]。我正在尝试调试它，如果我找到问题，我会回复您。代码本身相当简单，我尝试使用与您在算法中使用的相同单词，以便我们可以使用共同的语言进行交流 :) - Legend

@Legend 不用谢，谢谢你的谜题！它非常有趣。不管怎样，我已经跑了好几遍代码，我看不出第9个单元格有什么特别之处，以至于它会选择那个。它首先选择哪一个？顺便说一句，似乎你正在删除每只重复的鸟减少一只剩余鸟的数量。这让我怀疑它首先选择9，没有删除任何鸟，然后选择10，使amountOfBirds变为-2。但也许我还不太了解python代码。^^' - Aberrant

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- just a guy · Accepted Answer

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

你有一个二维目标函数，因此在射击和时间之间可能存在多种权衡。确定特定时间限制下的最小射击次数正是集合覆盖问题（正如mhum所建议的那样）。集合覆盖问题是NP难问题且难以近似，但在实践中，使用线性规划的对偶形式进行分支定界法非常有效，可以找到最优解。