Tra*_*man 3 algorithm semantic-analysis genetic-algorithm
假设C引用一组容器{c1,c2,c3....cn},其中每个容器包含一组有限的整数{i1,i2,i3...im}.此外,假设整数可能存在于多个容器中.给定一组有限的整数S {s1,s2,s3...sz},找到C包含所有整数的最小子集的大小S.
请注意,可能有数千个容器,每个容器有数百个整数.因此,蛮力很难解决这个问题.
我尝试使用Greedy算法解决问题.也就是说,每次我选择集合中整数最多的容器时S,我都失败了!
有谁能建议这个问题的快速算法？
这是众所周知的套装问题.它是NP难的 - 实际上,它的决策版本是规范的NP完全问题之一,并且是Karp 1972年论文中包含的21个问题之一- 因此没有有效的算法.除非您能够识别问题的某些特殊额外结构,否则您必须对近似结果感到满意:即C的子集,其并集包含S,但其不一定是C 的最小此类子集.
该贪婪算法可能是你最好的赌注:它找到的集的集合是不超过O(登录| C |)与最小这种集合的大小.
你说你无法让贪婪算法发挥作用.我想这可能是因为你没能正确实现它.您可以像这样描述算法:
每次我选择集合S中具有最大整数数的容器
但是,通常的贪婪算法中的规则是在每个阶段选择集合S中具有最大整数数量的容器,这些容器不在目前为止选择的任何容器中.