发布网友 发布时间:2023-10-13 16:30
共2个回答
热心网友 时间:2024-10-22 11:19
线性规划不是NP难,它可以用单纯型(simplex)法求解。线性整数规划是NP难问题,但也有一般解法,比如cut plane法,分支界定法。其他NP难问题无一般解法,需要heuristic方法求解。热心网友 时间:2024-10-22 11:20
NP完全(NP Complete,NPC)问题是指这样一类NP问题,所有的NP问题都可以用多项式时间划归到他们中的一个。所以显然NP完全的问题具有如下性质:它可以在多项式时间内求解,当且仅当所有的其他的NP-完全问题也可以在多项式时间内求解。