python - 以最小化组总数为目标选择组

Question

我正在编写一个程序，我需要在其中对作业进行分组，以最大限度地减少 CNC 冲床的工具更换。我刚开始的时候问过一个关于它的问题，但是当我编写程序时，方法已经改变了。

我有一份工作 list :

jobs = ['5618', '5612', '5613', '5897', '5589', '5474', 
        '5472', '5470', '5471', '9040']

我的程序已经将这些分类为可以一起完成的有效工作“组”:

['5471', '9040']
['5618', '5612', '5613', '5472']
['5471', '5589', '5897']
['5618', '5612', '5471', '5613']
['5471', '5474']
['5471', '5470', '5589']

现在我需要选择完成所有作业所需的最少组数。猜测是这样的组合:

['5618', '5612', '5613', '5472']
['5471', '5589', '5897']
['5470', '5589'] #this is the last group in the above lists but with 5471 
#removed because it's already been done 
[9040] #same as above except the first group with 5471 already been done. 

我在逻辑上考虑这样做的方式是找到最长的有效组，假设这是第一组，从剩余的作业中删除该组中的作业。重复。但是，当有两个长度相同的组时，这不起作用。也许是一个基于工作在其他组中的次数或其他东西的加权函数？我不知道。想法？蛮力吗？哈哈

Answer 1

此问题称为 set cover problem .本质上，您要求的是最小的组集，以涵盖您想要完成的所有工作。

不幸的是，这个问题是 NP 完全的。因此，不太可能有一种有效的算法来找到解决方案。不过，如果您的作业或群组数量较少，这可能无关紧要(因为您可以暴力破解它)。

你提出的贪心算法其实很好，相当于链接维基百科页面上的贪心算法。它实际上是仍然在多项式时间内运行的“最佳”可能算法。要打破平局，请任意选择(事实证明这无关紧要)。

如果工具更改的成本高到足以保证额外的 CPU 时间，您可以通过考虑所有 2^n 个可能的组集(其中 n 是组数)来强制解决问题。您可能可以使用典型的机器轻松处理最多 n=20，如果您愿意等待一段时间，则最多可以处理 n=30。您可以对蛮力进行优化以减少它将检查的解决方案的数量(值得注意的是，您可以对集合图进行广度优先搜索，以便在找到第一个最小解决方案时停止)，但您仍然会结束做指数级的工作来找到真正的最优解。