Caixeiro Viajante

É um problema de otimização combinatória no qual um caixeiro viajante tem a tarefa de passar por um conjunto de cidades apenas uma vez por cada uma de forma que o caminho percorrido seja o menor possível. Na teoria de complexidades computacionais esse problema se enquadra em NP-Hard, ou seja, seu espaço de soluções cresce de forma não polinomial. Métodos de busca extensiva (força bruta) resolvem o problema em tempo fatorial.