Abrir menu principal

Desciclopédia β

Problema do caixeiro viajante

Numerosdes.jpg Este artigo é relacionado à matemática.

Use para resolver as equações deste artigo.


NewBouncywikilogo.gif
Para aqueles sem senso de humor, os espertalhões da Wikipédia têm um artigo (pouco confiável) sobre: Problema do caixeiro viajante.

Cquote1.png Bater perna é comigo mesmo Cquote2.png
Caixeiro viajante sobre Problema do caixeiro viajante
Cquote1.png A TAM até me ofereceu patrocínio para as viagens, mas preferi ir a pé Cquote2.png
Caixeiro viajante sobre seu medo de voar

O Problema do caixeiro viajante é um problema de cunho econômico-social para o Caixeiro, mas um problema do caramba para a Computação.

Índice

IntroduçãoEditar

Basicamente, o caixeiro olho gordo quer ir a todas as cidades vender suas bugigangas utilizando para isto o menor caminho, pois além de olho gordo é preguiçoso.

Ele deve voltar à cidade origem ao final de sua jornada, mas ninguém sabe o porquê.

A soluçãoEditar

 
O Problema do caixeiro viajante para iniciantes. O belo ator neste cena é o boneco palito, tendo que escolher o menor caminho de ida e volta para a cidade A

Para um número pequeno de cidades é fácil, mas as coisas começam a ficar complicadas em lugares como São Paulo, em que há diversos amontoados de favelas cidades formando uma megalópole.

Um Algoritmo Guloso é a solução mais indicada para este problema, pois provê sempre uma solução ótima. O Algoritmo Guloso sugere que o caixeiro viajante coma todas as mercadorias, e a partir daí, não precisará mais ir a cidade alguma, nem voltar à cidade inicial, pois já estará nela.

A solução para um número grande de cidadesEditar


Ver tambémEditar



Rugal mandou uma cartinha para este artigo.
Gaste todas suas fichas para tentar derrotá-lo!