我有一个问题，这在下面描述。你有什么好的解决方案，或者这个问题只是任何“经典”或“已解决”问题的另一种形式？有没有可以解决这个数字组序列的算法？
问题是：
有一些数字组，例如，
A（1 8 9）
B（1 4 5）
C（2 4 6）
d（3 4 7）
E（2 10 11） （3 12 13）
有“AF”六组。我们有数字“1,2,3,4,5,6,7,8,9,10,11,12,13”。 现在找到满足每个组的最小数量集合必须至少有一个在这个集合中的数字。例如，我们可以找到A为“1”，B为“1,4”，C为“2,4”，D为“4”，E为“2”的集合“1 4 2 13 12” F有“12,13”。
但是设置“1 2 4”并不是我们发现的，F在集合中没有任何数字。
最好的设置是“1,2,3”，每个组都有一个数字，并且该组的大小是最优的。它只有三个数字。这是我们想要的。如果有很多最好的集合，找到任何一个都可以。谢谢。
这相当于set cover problem。在这种情况下，你的每个集合A，B，...，F都是集合覆盖问题的元素，并且每个数字1,2，...，13都是集合。例如，在映射1中变为{A，B}，并且11变为集合{E}。
设置封面是NP-hard。链接维基百科页面上的整数线性规划公式可能会像你会得到确切的解决方案一样好;贪婪算法对大问题有一个很好的近似。
我觉得很有意思，我们每个人都在约20秒内发现了来自不同NP难题的减少。 :-) – templatetypedef 2012-04-13 02:00:37
@templatetypedef我正准备在你的答案中发布基本相同的东西。 :) – Dougal 2012-04-13 02:00:55
我个人认为设置封面比顶点封面更合适（更直观的缩小），所以我打开了这个答案。 ;） – 2012-04-13 02:19:12
此问题是NP-hard的经由来自NP-hardvertex cover problem的降低（给定的曲线图，可以找到一组k个节点的，使得在图中每个顶点相邻的一些选择的节点？）
的减少如下。以您想要的任何顺序对图1，图2，图3，...，n中的所有节点进行编号。然后，对于图中的每个边，构造只包含两个数字的集合 - 边的端点。如果原始图中有一个k节点顶点覆盖，则可以选择一组k个数字（即顶点覆盖中的节点），以便从每个集合中选择一个数字。这可以用多项式时间来计算。
要知道为什么缩减可行，请注意，如果有一组大小为k的组合，可以选择使构造中的每个组至少有一个元素被选中，那么与这些数字对应的顶点形成一个k元素顶点覆盖在原始图中。
这个减少可以在多项式时间完成，所以我们从NP-硬顶点覆盖问题到您的问题有一个多项式时间减少。因此这个问题是NP难的。所以，除非P = NP，这个问题没有多项式时间算法。
希望这会有所帮助！
你的宇宙的大小是多少？你的例子使用了13个数字，你期望获得更多吗？ – dasblinkenlight 2012-04-13 02:03:23