这是最低限度的套盖问题吗？

Question

我有以下场景(对长度的初步道歉，但我希望尽可能地描述)：

我收到了一份“食谱”(Ri)的列表，必须按照提交的顺序完成它，以完成给定的任务。每个菜谱包含完成它所需的部件列表(Pj)。一个菜谱通常需要多达3或4部分，但可能需要多达16部分。

• R1 = {P1}
• R2 = {P4}
• R3 = {P2，P3，P4}
• R4 = {P1，P4}
• R5 = {P1，P2，P2} //注意，可能需要一个给定部分中的一个以上。(在这里，P2)
• R6 = {P2，P3}
• R7 = {P3，P3}
• R8 = {P1} //注意菜谱可能会在列表中重复出现。(与R1相同)

最长的列表可能包含几百个菜谱，但通常包含一些菜谱的许多递归，因此删除相同的菜谱通常会将列表减少到少于50个唯一的菜谱。

我有一组机器(Mk)，每台机器都经过预先编程(在列表处理开始之前，这种情况只发生一次)来生产一些(或全部)可用的部件。

实现过程的迭代如下所示：

• 列表中的下一个菜谱是提交给机器银行的。
• 在每台机器上，都会选择它的一个可用程序来生产此菜谱所需的部件之一，或者，如果该菜谱不需要，则将其设置为“脱机”。
• 一个“曲柄”被转动，每台机器(没有被“划掉”)都会喷出一个部件。
• 将曲柄的一圈所产生的部件组合在一起，就能达到配方的要求。顺序是无关紧要的，例如，实现配方{P1，P2，P3}与实现配方{P1，P3，P2}相同。

这些机器可以即时、并行地运行，并且拥有无限的原材料，因此没有资源或时间/调度限制。机器库的大小k必须至少等于最长配方中的元素数，因此与上面提到的菜谱长度大致相同(通常为3-4，可能高达16)。因此，在上面的示例中，k=3 (由R3和R5的大小决定)似乎是一个合理的选择。

当前的问题是如何对机器进行预编程，以便银行能够完成给定列表中的所有菜谱。机器库共享一个公共的内存池，因此我正在寻找一种算法，该算法产生一种程序配置，可以消除(完全或尽可能多的)机器之间的冗余，从而最小化总内存负载的数量。机器库大小k是灵活的，也就是说，如果增加机器数量超过给定列表中最长菜谱的长度，则对列表产生一个更理想的解决方案(但将硬限制保持在16)，这很好。

现在，我认为这是一个独角兽问题，也就是说，每个程序都需要相同的内存，尽管我希望将来能够灵活地增加每个程序的权重。在上面的示例中，考虑到所有菜谱，P1最多发生一次，P2最多发生两次( R5)，P3最多发生两次( R7)，P4最多发生一次，所以理想情况下，我希望实现一种与此相匹配的配置--只有一台配置为生成P1，两台配置为生成P2，两台配置为生成P3，另一台配置为生成P4。对于上面的示例，使用机库大小k=3的一个可能的最小配置是：

• M1被编程来产生P1或P3
• M2被编程来产生P2或P3
• M3被编程来产生P2或P4

由于这里没有作业车间类型的限制，我的直觉告诉我，这应该减少到一个套盖问题--就像在设计数字系统时发现的最小的单一设置覆盖问题一样。但是，我似乎无法使我对这些算法的知识(诚然有限)适应这种情况。有人能确认或否认这种方法的可行性吗?在任何一种情况下，都能指出一些有用的算法吗？我正在寻找可以集成到现有代码块中的东西，而不是像Berkeley的Espresso这样预先打包的代码块。

谢谢!

Answer 1

这让我想起了编译器中用于寄存器分配的图着色问题。

步骤1:如果在食谱中重复相同的部分，将其重命名；例如，R5 = {P1，P2，P2'}

第二步:将所有零件插入到一个图中，在同一菜谱中各部分之间有边。

步骤3:给图涂上颜色，使两个连接的节点(部分)没有相同的颜色。

颜色是制造零件的机器标识。

这是次优，因为重命名的部分会在其他菜谱中创建假约束。您可以通过“合并”来解决这个问题。见布里格斯。