“2022年08月” 的搜索结果,共9

《算法导论》第三十五章(续3)
《算法导论》第三十五章(续3)

35.4― 随机化和线性规划本节主要研究两种在设计近似算法时非常有用的技术:随机化和线性规划。我们要给出3-CNF可满足性问题最优化版本的一...

《算法导论》第三十五章(续2)
《算法导论》第三十五章(续2)

35.3 集合覆盖问题集合覆盖问题是一个最优化问题,它是许多资源分配问题的模型,其相应的判定问题是NP完全的顶点覆盖问题的推广,因而也是...

《算法导论》第三十五章(续1)
《算法导论》第三十五章(续1)

35.2旅行商问题34.5.4节介绍的旅行商问题中,输人是一个完全无向图G=(V,E),其中每条边(u,v)∈E都有一个非负的整数代价cu,v),我们希望...

《算法导论》第三十五章
《算法导论》第三十五章

《算法导论》第三十五章 近似算法许多具有实际意义的问题都是NP完全问题。我们不知道如何在多项式时间内求得最优解。但是,这些问题通常十...

《算法导论》第三十四章(续8)
《算法导论》第三十四章(续8)

34.5.4 旅行商问题旅行商问题与哈密顿回路问题有着密切的联系。在该问题中,一个售货员必须访问n个城市。如果把该问题模型化为一个具有n个...

《算法导论》第三十四章(续7)
《算法导论》第三十四章(续7)

34.5.3哈密顿回路问题现在,我们再回过头来讨论34.2节中定义的哈密顿回路问题。定理34.13 哈密顿回路问题是NP完全问题。证明 先来说明HAM...

《算法导论》第三十四章(续6)
《算法导论》第三十四章(续6)

34.5.2顶点覆盖问题无向图G=(V,E)的顶点覆盖(vertex cover)是一个子集V'cV,满足如果有(u,v)∈E,则u∈V'或v∈V(或两者同时成立...

《算法导论》第三十四章(续5)
《算法导论》第三十四章(续5)

34.5NP完全问题NP完全问题产生于各种不同领域:布尔逻辑,图论,算法,网络设计,集合与划分,存储与检索,排序与调度,数学程序设计,代数...

《算法导论》第三十四章(续4)
《算法导论》第三十四章(续4)

34.4NP完全性的证明通过直接证明对于任意语言L∈NP,都有L≤;CIRCUIT-SAT,我们可以证明电路可满足性问题是NP完全的。在本节中,我们将说明...

19条记录首页上页1下页尾页