我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:六合报码室 > 多项式时间 >

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

归档日期:07-01       文本归类:多项式时间      文章编辑:爱尚语录

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

  2017-09-23展开全部NP完全(NP Complete,NPC)问题是指这样一类NP问题,所有的NP问题都可以用多项式时间划归到他们中的一个。所以显然NP完全的问题具有如下性质:它可以在多项式时间内求解,当且仅当所有的其他的NP-完全问题也可以在多项式时间内求解。

  NP完全问题,是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题,即多项式复杂程度的非确定性问题。简单的写法是 NP=P?,问题就在这个问号上,到底是NP等于P,还是NP不等于P。

本文链接:http://barstaffuk.com/duoxiangshishijian/796.html