Tob*_*ias 6 np-complete approximation
或者更确切地说,组合算法和线性算法的定义是什么？
为了说清楚,因为很明显第一响应者误解了这个问题:我不是在寻找在线性时间与非线性时间运行的算法的定义.线性算法以某种方式与线性编程相关,线性编程是用于查找或近似线性优化问题的解决方案的技术.
由于NP难问题是如此困难,有一个完整的领域试图找到近似的解决方案.例如,旅行商问题具有几个近似解,其在多项式时间内运行并产生在最佳解的给定界限内的解.
这些近似算法中的一些称为线性算法,其他算法称为组合算法; 而后者似乎更受欢迎(为什么？).这些是我想要理解的两个概念.
小智 4
该问题是问题表述之一。
正如您所说，旅行推销员问题（TSP）是NP 难的，正是因为它有一个离散的问题表述（推销员在特定时间要么访问某个城市，要么不访问）。这种离散的公式使问题及其算法成为组合的。（请注意，并非所有组合问题都是 NP 困难问题；考虑排序算法。）
然而，TSP 的线性规划 (LP) 松弛会产生线性算法。这是因为问题已被重新表述，使得销售人员在一定比例的时间内访问某个城市。使用 LP 松弛的主要原因是松弛版本可以在多项式时间内求解。然而，LP松弛的解不一定是原始问题的解。