Qual é a diferença entre um 'combinatória algoritmo' e um 'linear algoritmo'?

Question

Ou melhor, qual é a definição de um algoritmo de combinatória e um algoritmo linear, resp.?

Para deixar claro porque, obviamente, os socorristas entendido mal a pergunta: Eu não estou à procura de uma definição de um algoritmo rodando em tempo linear vs tempo não-linear. Um algoritmo linear é de alguma forma relacionado à programação linear, que é uma técnica para encontrar ou aproximar soluções para problemas de otimização lineares.

Uma vez que os problemas NP-hard são tão difíceis, há todo um campo tentando encontrar soluções aproximadas. O problema do caixeiro viajante, por exemplo, tem várias soluções aproximadas que rodam em tempo polinomial e produzir uma solução que seja dentro de um determinado limite ao melhor solução.

Alguns destes algoritmos aproximam são chamados um algoritmo linear, outros um algoritmo combinatória; eo último parece ser preferido (Por quê?). Estes são os dois conceitos que eu gostaria de entender.

Answer 1

A questão é um dos formulação do problema.

Assim como você disse Viajando vendedor Problem (TSP) é NP-hard precisamente porque tem uma formulação do problema discreto (o vendedor quer visitas uma cidade ou não em um determinado momento). Esta formulação discreta torna o problema, e é algoritmo, combinatória . (Note-se que nem todos os problemas combinatórios são NP-hard;. Considerar algoritmos de ordenação)

No entanto, o relaxamento Linear-Programming (LP) de resultados TSP em um linear algoritmo. Isso ocorre porque o problema foi reformulado de tal forma que as visitas vendedor uma cidade uma certa proporção do tempo. A principal razão para usar um relaxamento LP é porque a versão relaxada pode ser resolvido em polinomial tempo. No entanto, a solução para o relaxamento LP não é necessariamente uma solução para o problema original.

Answer 2

Um linear algoritmo tende a trabalhar com apenas um conjunto de dados - 'Toma todos os números em conjunto um, dobrá-los, e colocar o resultado em conjunto b'. O número de operações é igual à contagem de itens em definir um

A combinatória um trabalhos sobre combinações de conjuntos - 'para cada número em conjunto um, o trabalho fora a soma desse número e cada número no conjunto b e imprimir a tela'. O número de operações é o produto do tamanho de um conjunto e o tamanho do conjunto b.

Answer 3

algoritmos combinatórios "explodir" como sua entrada cresce. algoritmos lineares cresce proporcional à sua entrada, enquanto algoritmos combinatórios cresce proporcional a um expoente (ou pior) ou a sua entrada:. enumerar todos os caminhos possíveis através de um gráfico, por exemplo