E não, eu não estou me referindo ao caderudo.
Era uma vez um caixeiro que viajava, logo ele é o caixeiro viajante. O que ele faz é vender coisas para as outras pessoas. Se você viu Chaves na sua vida, sabe que o Jaiminho gosta de evitar a fadiga, pois saiba que o caixeiro também gosta, e se ele tem que ir em todas as cidades vizinhas, existe uma forma de viajar na qual ele não repita as cidades pelas quais ele passa?
Note que ele não está necessariamente evitando a fadiga. Ele só não quer olhar pra cara das mesmas pessoas duas vezes, então ele não é o Jaiminho, mas certamente tem que ir de ponto a ponto. O problema continua. Como passar por todos os lugares que ele tem que visitar sem repetir ?
Pra isso a gente vai precisar de duas coisas. Digamos que ele tem que passar por cidades, então vamos colocar aqui o conjunto de cidades:
{Rio de Janeiro, Angra dos Reis, Cabo Frio, ...}
E bom, tem que existir rotas entre uma cidade e outra, então, você tem rotas:
{(Rio de Janeiro, Angra), (Rio de Janeiro, Cabo Frio), (Cabo Frio, Búzios), ...}
Isso tudo em forma de exemplo, estamos olhando para a coisa de um jeito mais abstrato. A pergunta continua, e o caixeiro continua andando. Ele não está nem aí pra você.
Se você é um cara que já estuda computação, sabe que esses dois conjuntos descrevem muito bem um grafo, e provavelmente sabe que esse problema nem sempre tem uma solução. Dependendo da forma na qual as cidades estão distribuídas, você não consegue satisfazer o problema. Algumas são bem triviais. Fica difícil fazer isso com cidades, então vamos supor que não tem as cidades do norte, e que pra chegar em Niterói você tem que cruzar a maldita ponte.
Aí vem o problema. Você não consegue realizar o caixeiro viajante por causa dessa ponte maldita. Se você está de um lado da ponte e cruza, não vai conseguir voltar. Se você tiver duas pontes passando pela mesma cidade, aí que danou de vez. Aí nem começando do lugar certo.
Na verdade a gente usa esse problema todo o dia porque a gente não gosta de passar duas vezes pelo mesmo lugar. Por exemplo, se você quer ir no subway, mas também que voltar pra casa, você não vai passar no restaurante se ele fica para o outro lado e daí você tem que voltar tudo de novo.
Nós estamos o dia todo executando algoritmos de roteamento para planejar nossas viagens, e existem muitos desse tipo. O problema é que no mundo real as coisas são mais complicadas porque nunca dá pra saber quanto tempo você vai ficar na mesma estrada.
Imagens:
http://www.sciencebuzz.org
https://pbs.twimg.com/profile_images/646084472694149120/-akRiVfV.jpg
Nenhum comentário:
Postar um comentário