José é caixeiro-viajante: ele desloca-se da fábrica até as lojas dos clientes, para entregar a mercadoria e receber novas encomendas, e volta à fábrica ao final. E gostaria de saber qual é o itinerário mais curto que pode tomar passando por todas as lojas.

Questões semelhantes surgem em muitas áreas, da logística ao design de chips. Por isso, o "problema do caixeiro-viajante" –dado um conjunto finito de pontos cujas distâncias são conhecidas, encontrar a rota mais curta que conecta todos os pontos e volta ao ponto de partida– é um dos mais importantes na área das aplicações da matemática.

A primeira menção conhecida a esta questão foi num manual de instruções para caixeiros-viajantes datado de 1832. Mas o seu estudo matemático só começou um século depois, tornando-se muito popular nos anos 1950, com o advento do computador.

Quando o número N de pontos ("cidades") é pequeno, o problema pode ser resolvido por meio de força bruta, listando todas as rotas possíveis para conferir qual é a mais curta. Mas isso logo se torna inviável quando N aumenta, mesmo com computadores poderosos, porque o número de rotas possíveis é dado pelo fatorial N! = 1 x 2 x … x N, o qual cresce muito rapidamente.

Talvez o leitor esteja achando que há uma estratégia simples: começar pela loja mais próxima da fábrica, em seguida visitar a loja mais perto dessa, e assim sucessivamente, sempre escolhendo a loja mais próxima ainda não visitada. Mas não, em geral essa estratégia "natural" não dá a rota mais curta!

Métodos mais sofisticados foram desenvolvidos ao longo dos anos. Em 1954, os pesquisadores G. B. Dantzig, R. Fulkerson e S. M. Johnson expressaram a questão na linguagem da programação linear, ou seja, na forma de um conjunto de equações lineares. Programação linear é uma das áreas mais desenvolvidas e poderosas da análise numérica: nessa linguagem, um computador pode analisar metodicamente as diferentes combinações para encontrar a melhor solução do problema.

O método de Dantzig, Fulkerson e Johnson foi melhorado e, tirando proveito também de computadores mais potentes, hoje já resolve problemas com 1 milhão de cidades ou mais. Mas, em todos os métodos conhecidos, o tempo para obter a solução do problema do caixeiro-viajante cresce pelo menos exponencialmente com N. Isso é muito melhor do que o fatorial N!, mas ainda assim é demasiado para certas aplicações. Na verdade, sabemos que, num sentido computacional preciso, este problema está entre os mais difíceis que existem.