Grafos e RedesSalesman

Até agora, ignoramos o fato de que algumas cidades podem estar mais afastadas do que outras. Na vida real, no entanto, essa é uma consideração muito importante: não queremos apenas encontrar nenhum caminho, mas queremos encontrar o caminho mais curto. Isso é chamado de Problema do vendedor ambulante. Ele precisa ser resolvido não apenas no transporte e na logística, mas também ao posicionar transistores em microchips, para tornar computadores mais rápidos ou ao analisar a estrutura do DNA.

Um método simples seria tentar todos os caminhos possíveis, encontrar o comprimento de cada um e escolher o menor. No entanto, acabamos de mostrar que, mesmo com apenas ${tsn2} cidades, existem ${tsn2}! = ${factorial(tsn2)} caminhos possíveis. Depois de ter centenas ou milhares de vértices, tentar todos os caminhos possíveis se torna impossível, mesmo usando computadores poderosos.