¿Cuál es la diferencia entre un 'algoritmo combinatorio' y un 'algoritmo lineal'?

Question

O mejor dicho, ¿cuál es la definición de un algoritmo combinatorio y un algoritmo lineal, resp.?

Para dejarlo claro porque, obviamente, los primeros respondedores entendieron mal la pregunta: no estoy buscando una definición de un algoritmo que se ejecute en tiempo lineal frente a tiempo no lineal. Un algoritmo lineal está relacionado de alguna manera con la programación lineal, que es una técnica para encontrar o aproximar soluciones a problemas de optimización lineal.

Dado que los problemas de NP-difícil son tan difíciles, hay un campo completo que trata de encontrar soluciones aproximadas. El problema de los vendedores ambulantes, por ejemplo, tiene varias soluciones aproximadas que se ejecutan en tiempo polinomial y producen una solución que está dentro de un límite dado de la mejor solución.

Algunos de estos algoritmos de aproximación se denominan algoritmos lineales, otros algoritmos combinatorios; y este último parece ser el preferido (¿por qué?). Estos son los dos conceptos que me gustaría entender.

Answer 1

El problema es uno de la formulación del problema.

Tal como usted dijo, el Problema del Vendedor Viajero (TSP) es NP-hard precisamente porque tiene una formulación de problema discreta (el vendedor visita una ciudad o no en un momento determinado). Esta formulación discreta hace que el problema, y ??su algoritmo, combinatorial . (Tenga en cuenta que no todos los problemas combinatorios son NP-duros; considere la posibilidad de clasificar los algoritmos).

Sin embargo, la relajación de Programación Lineal (LP) de TSP da como resultado un algoritmo lineal . Esto se debe a que el problema se ha reformulado de tal manera que el vendedor visita una ciudad una cierta parte del tiempo. La razón principal para usar una relajación LP es porque la versión relajada se puede resolver en polinomio . Sin embargo, la solución a la relajación de LP no es necesariamente una solución al problema original.

Answer 2

Un algoritmo lineal tiende a funcionar con un solo conjunto de datos: 'Tome todos los números en el conjunto a, duplíquelos y ponga el resultado en el conjunto b'. El número de operaciones es igual al recuento de elementos en el conjunto a

Una combinatoria funciona en combinaciones de conjuntos: 'Para cada número en el conjunto a, calcule la suma de ese número y cada número en el conjunto b e imprima en pantalla'. El número de operaciones es el producto del tamaño del conjunto a y el tamaño del conjunto b.

Answer 3

Algoritmos combinatorios " explotar " como su entrada crece. Los algoritmos lineales crecen proporcionalmente a su entrada, mientras que los algoritmos combinatorios crecen proporcionalmente a un exponente (o peor) o su entrada: enumerar todas las rutas posibles a través de una gráfica, por ejemplo.