O Caso do Vendedor Viajante

ilustração de thomas fuchs

É impossível tentar computar a rota mais curta para visitar um grande número de cidades? Não só uma boa rota, mas a menor. Essa missão é o antigo desafio conhecido como “problema do vendedor viajante”, ou PVV.

Encontrar um método que possa resolver todos os exemplos do PVV seria uma conquista fenomenal para a matemática. Usando a teoria da complexidade, um método assim nos permitiria resolver eficientemente qualquer problema computacional para o qual as respostas podem ser facilmente verificadas. A maioria dos matemáticos acredita que isso seja impossível.

Mas suponha que você receba a localização de 100 mil cidades. É realmente impossível encontrar a rota mais curta? Não estamos pedindo uma solução para todas as versões do PVV, apenas uma maneira rápida de passar por esses locais específicos.

Para aceitar o desafio, sua melhor opção é escutar o conselho de Yogi Berra, algo como: “Quando encontrar uma encruzilhada, vá por ela”. Uma ferramenta chamada programação linear nos permite fazer exatamente isso ao atribuir frações a estradas que conectam pares de cidades, em vez de decidir imediatamente se devemos usá-las ou não. Nesse modelo, é perfeitamente normal mandar metade do vendedor para cada lado da encruzilhada. O processo começa pedindo que, para cada cidade, as frações designadas às estradas de saída e de chegada somem 1. Então, passo a passo, mais restrições são adicionadas, cada uma envolvendo somas de frações atribuídas a estradas. A programação linear acaba apontando a melhor decisão para cada estrada e assim a rota mais curta possível.

Devo acrescentar que 100 mil cidades não é um desafio hipotético. As computações atuais estão chegando à solução de um belo conjunto de 100 mil pontos, criado por Robert Bosch, do Oberlin College, trajeto que desenha a Mona Lisa. Podemos não ser capazes de derrubar todos os exemplos do PVV, mas novas ideias podem aumentar as fronteiras de sua solubilidade.

Essa é a ideia geral: a teoria da complexidade sugere que existem limites para a capacidade de técnicas computacionais na ciência e em outros lugares. Quais são esses limites e quanto eles restringem nossa busca por conhecimento? É isso que a pesquisa sobre o PVV quer saber.