线性规划问题是一个np-hard问题对吗

答案:2 悬赏:10 手机版

解决时间 2021-01-29 17:49

提问者网友：川水往事
2021-01-28 21:13

最佳答案

五星知识达人网友：夜风逐马
2021-01-28 21:57

NP完全(NP Complete,NPC)问题是指这样一类NP问题，所有的NP问题都可以用多项式时间划归到他们中的一个。所以显然NP完全的问题具有如下性质：它可以在多项式时间内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。
NP完全问题，是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。
NP-hard，其中，NP是指非确定性多项式（non-deterministic polynomial，缩写NP）。所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可解决的问题。

全部回答

1楼网友：一叶十三刺
2021-01-28 22:40

线性规划不是NP难，它可以用单纯型（simplex）法求解。线性整数规划是NP难问题，但也有一般解法，比如cut plane法，分支界定法。其他NP难问题无一般解法，需要heuristic方法求解。

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息