擅长:python、mysql、java
<p>不幸的是,考虑到问题实际上是<a href="http://en.wikipedia.org/wiki/NP-hard">NP-hard</a>(但甚至不是<a href="http://en.wikipedia.org/wiki/NP-complete">NP-complete</a>),找到一个比暴力强得多的算法几乎没有希望。在</p>
<p>这个问题的NP硬度的一个证明是最小<a href="http://en.wikipedia.org/wiki/Vertex_cover">vertex cover</a>问题(众所周知是NP难而不是NP完全的)很容易被简化为:</p>
<p>给出一个图表。让我们为图的每个顶点创建包<em>P<sub>v</sub></em>。同时为图的每个边(u,v)</em>创建“and”所需的包(<em>P<sub>u</sub></em>或<em>P<sub>v</sub></em>)。找到要安装的最小软件包集,以满足<em>X</em>的要求。那么<em>v</em>在图的最小顶点覆盖中<a href="http://en.wikipedia.org/wiki/If_and_only_if">iff</a>相应的包<em>P<sub>v</sub></em>在安装集中。在</p>