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........

© UOL