[数据结构与算法]线性规划和启发式搜索算法的关系

线性规划不是一个算法，只是一种数学模型，或者说是一类问题，在一些约束式子下求解目标函数的最小值。

线性规划的求解算法可以用单纯型法精确求解，这个算法是多项式时间复杂度的，因此线性规划问题，不是NP-Hard问题，而是多项式时间复杂度问题了。但是整数规划问题是NP难的，可以用下面介绍的启发式搜索算法近似求解。

启发式（heuristic）搜索算法，其实跟数据结构中学的深度优先搜索，广度优先搜索类似的，只是启发式搜索算法会再每次搜索时候结合了之前有用信息，进行偏好路径方向搜索，比如群蚁算法，模拟退火算法，神经网络算法应该也是吧。启发式算法的运行不是多项式时间复杂度的，但是它能快速找到接近最优解的结果，因此它被广泛应用来求解NP-Hard问题。

如今0-1背包问题已经被证明是NP完全问题，而它却有着一个动态规划解法，该解法有着O(n*W)的时间复杂度，其中n是物品的个数，W是背包限制的最大负重。所以时间复杂度对输入n，W来说是多项式时间的，所以说明了NP=P！是不是哪里出错了呢？

其实多项式时间是相对于输入规模来说的，输入规模最直观的理解就是输入到该算法的数据占了多少比特内存。0-1背包的输入有n个物品的价值，n个物品的重量，还有背包的最大负重W。如今假设W占用的比特数为L（也就是说背包的最大负重的输入规模是L），那么log(W)=L，所以O(n*W)=O(n*2^L),由此看到，该算法的时间复杂度对于输入规模L来说是指数级别的，随着输入规模L的增加，运算时间会迅速增长。

实际上，人们把这种动态规划的算法称为伪多项式时间算法（pseudo-polynomial time algorithm），这种算法不能真正意义上实现多项式时间内解决问题

参考博客：

https://blog.csdn.net/jim7424994/article/details/39926459