English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGrafos e RedesO Problema do Vendedor Viajante
Vamos pensar, mais uma vez, em redes e mapas. Imagine que um serviço de entrega precise visitar
O caminhão de entrega deve visitar todas as cidades, em qualquer ordem. No problema das pontes de Königsberg, queríamos encontrar caminhos que percorrem todas as margens exatamente um. Agora, queremos encontrar caminhos que visitam todos os vértices exatamente uma vez. Esses caminhos são chamados ciclos hamiltonianos.
Existem inúmeras possibilidades diferentes para ciclos hamiltonianos em gráficos completos. De fato, podemos escolher qualquer vértice como vértice inicial e, em seguida, qualquer uma das cidades restantes em qualquer ordem:
Diagram coming soon…
Diagram Coming Soon…
Em um gráfico com
Isso significa que, no total, existem ${tsnPaths(tsn1)} caminhos possíveis. Uma abreviação para este produto é ${tsn1}! ou ${tsn1} fatorial.
Você pode imaginar que talvez não seja possível viajar diretamente entre duas cidades - sem passar por outra cidade. Nesse caso, não temos mais um gráfico completo, e encontrar o número de ciclos hamiltonianos, se é que existem, se torna muito mais difícil.
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
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
Infelizmente, não existe um algoritmo mais eficiente para resolver o problema do vendedor ambulante. Em vez disso, matemáticos e cientistas da computação desenvolveram vários algoritmos que encontram boas soluções, mesmo que elas não sejam as melhores. Esses algoritmos, que fornecem apenas soluções aproximadas, são chamados Heurísticas.
Tente reorganizar as cidades neste mapa e observe como o caminho mais curto entre elas muda. Você pode remover cidades tocando nelas e pode adicionar cidades clicando em qualquer lugar do mapa (até 8):
O Greedy Algorithm (ou Algoritmo do vizinho mais próximo) é muito simples: você começa em uma cidade aleatória e se move consecutivamente para a cidade mais próxima que você nunca visitou antes. Depois de visitar todas as cidades, você para.
Animação em breve ...
Você pode mostrar que, em média, os caminhos encontrados usando o algoritmo guloso são 25% mais longos que o menor caminho possível.
O Algoritmo 2-Opt começa com um caminho possível aleatório. Em seguida, você escolhe duas arestas repetidamente e as troca, se isso reduziria o comprimento do caminho. Você para quando não pode reduzir ainda mais o comprimento trocando quaisquer pares de arestas.
Animação em breve ...
Acontece que, muito antes dos computadores existirem, a Natureza havia encontrado uma maneira inteligente de encontrar caminhos ótimos entre diferentes locais: nas colônias de formigas.
As formigas querem encontrar as rotas mais curtas possíveis entre o ninho e as possíveis fontes de alimento. Eles podem se comunicar através de produtos químicos que deixam ao longo de sua trilha e que outras formigas podem seguir.
- A colônia de formigas envia muitos batedores que inicialmente viajam em direções aleatórias. Uma vez que encontram comida, eles retornam, deixando para trás um rastro de feromônio.
- Outras formigas tendem a seguir uma trilha quando encontram uma, o que as leva à comida. Na viagem de volta, depositam mais feromônios, reforçando a trilha.
- Com o tempo, o feromônio evapora. Quanto mais longo o caminho, mais tempo leva para as formigas viajarem, e assim o feromônio tem mais tempo para evaporar. Caminhos curtos, por outro lado, podem ser reforçados mais rapidamente, portanto sua força aumenta mais rapidamente.
Diagrama em breve ...
Os algoritmos do Sistema de Colônia de Formigas (ACS) tentam replicar esse comportamento nos computadores, usando muitas formigas "virtuais". Eles podem encontrar rapidamente soluções muito boas para o problema do vendedor ambulante.
Uma propriedade particularmente útil dos algoritmos do ACS é que eles podem ser executados continuamente e se adaptar em tempo real às mudanças no gráfico. Essas alterações podem ser causadas por acidentes de carro e fechamento de estradas nas redes de ruas ou por picos de tráfego nos servidores da Web nas redes de computadores.
O problema do Vendedor ambulante é
Encontrar um algoritmo rápido e exato teria implicações sérias no campo da ciência da computação: significaria que existem algoritmos rápidos para todos os problemas difíceis de NP. Isso também tornaria inútil a maior parte da segurança da Internet, que se baseia no fato de que certos problemas são considerados muito difíceis para os computadores.
Encontrar um algoritmo rápido para resolver o problema do vendedor ambulante também resolveria um dos problemas abertos mais famosos da matemática e da ciência da computação, o problema de P vs NP. É um dos sete