“组合算法”和“组合算法”有什么区别？ 和“线性算法”？
或者更确切地说，组合算法和线性算法的定义分别是什么？
明确地说，因为显然第一批响应者误解了这个问题：我并不是在寻找线性时间与非线性时间运行的算法的定义。 线性算法在某种程度上与线性规划有关，线性规划是一种寻找或近似线性优化问题的解决方案的技术。
由于 NP 难题非常困难，因此整个领域都在尝试寻找近似解。 例如，旅行商问题有几个近似解，它们在多项式时间内运行并产生在最佳解的给定范围内的解。
这些近似算法中的一些称为线性算法，另一些称为组合算法； 后者似乎是首选（为什么？）。 这是我想了解的两个概念。
Or rather, what is the definition of a combinatorial algorithm and a linear algorithm, resp.?
To make it clear because obviously the first responders misunderstood the question: I am not looking for a definition of an algorithm running in linear time vs non-linear time. A linear algorithm is somehow related to linear programming, which is a technique for finding or approximating solutions to linear optimization problems.
Since NP-hard problems are so hard, there is a whole field trying to find approximate solutions. The traveling salesman problem for instance has several approximate solutions which run in polynomial time and produce a solution which is within a given bound of the best solution.
Some of these approximating algorithms are called a linear algorithm, others a combinatorial algorithm; and the latter seems to be preferred (Why?). These are the two concepts I would like to understand.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
该问题是问题表述之一。
正如您所说，旅行推销员问题（TSP）是NP-hard，正是因为它有一个离散的问题表述（推销员在特定时间要么访问一个城市，要么不访问）。 这种离散公式使问题及其算法成为组合。 （请注意，并非所有组合问题都是 NP 难问题；请考虑排序算法。）
但是，TSP 的线性规划 (LP) 松弛会产生线性算法。 这是因为问题已被重新表述，使得销售人员在一定比例的时间内访问某个城市。 使用 LP 松弛的主要原因是松弛版本可以在多项式时间内求解。 然而，LP松弛的解不一定是原始问题的解。
The issue is one of problem formulation.
Just as you said Traveling Salesperson Problem (TSP) is NP-hard precisely because it has a discrete problem formulation (the salesperson either visits a city or not at a particular time). This discrete formulation makes the problem, and it's algorithm, combinatorial. (Note that not all combinatorial problems are NP-hard; consider sorting algorithms.)
However, the Linear-Programming (LP) relaxation of TSP results in a linear algorithm. This is because the problem has been reformulated such that the salesperson visits a city a certain proportion of the time. The main reason for using an LP relaxation is because the relaxed version can be solved in polynomial time. However, the solution to the LP relaxation is not necessarily a solution to the original problem.
线性算法往往只处理一组数据 - “将 a 组中的所有数字加倍，然后将结果放入 b 组”。 运算次数等于集合 a 中的项目数
组合运算适用于集合的组合 - “对于集合 a 中的每个数字，计算出该数字与集合 b 中的每个数字的总和并打印到屏幕”。 操作次数是集合 a 的大小和集合 b 的大小的乘积。
A linear algorithm tends to work with just one set of data - 'Take all the numbers in set a, double them, and put the result in set b'. The number of operations is equal to the count of items in set a
A combinatorial one works on combinations of sets - 'For each number in set a, work out the sum of that number and each number in set b and print to screen'. The number of operations is the product of the size of set a and the size of set b.
组合算法随着输入的增加而“爆炸”。 线性算法的增长与其输入成正比，而组合算法的增长则与指数（或更糟）或其输入成正比：例如，枚举图表中所有可能的路径。
Combinatorial algorithms "explode" as their input grows. Linear algorithms grows proportional to their input, while combinatorial algorithms grows proportional to an exponent (or worse) or their input: enumerating all possible paths through a graph, for example.