O problema
O problema do caixeiro viajante é a representação de um problema de minimizar o custo de um ciclo hamiltoniano. Esta representação consiste em um caixeiro que tem que visitar n diferentes cidades levando seus produtos para vender. No entanto, este caminho deve passar somente uma vez por cada cidade e deve começar e terminar no mesma cidade (que pode ser tanto sua casa, quanto a empresa em que trabalha). Assim, para minimizar o custo de visitar estas cidades, devemos responder a seguinte pergunta: qual é a rota mínima para a viagem?
Pensando neste problema, logo vem à nossa cabeça: devemos verificar todas as possíveis rotas e assim identificar a menor delas. Contudo, o cálculo das rotas pode, muitas vezes, ser muito custoso e inviável computa-los. Vejamos:
Se tivermos 3 cidades para visitar, temos 3 opções iniciais para começar, depois 2 para visitar e depois somente 1 para visitar. Ou seja, este problema cresce em tempo exponencial. Para este caso, temos 3! (= 6) possíveis rotas.
Se pegarmos 4 cidades, temos 5! (= 120) possíveis rotas.
No entanto, se tivermos 30 cidades, nosso problema terá um cálculo muito mais custoso e difícil, pois temos 30! ou 2.10^32 (!!!!) possíveis rotas. Além disso, se adicionarmos apenas mais uma cidade, teremos 31! ou 8.10^33 (!!!!) possíveis rotas. Logo, a adição de apenas uma cidade em instâncias grandes, o problema cresce muito em questão de custo de computação.
Complexidade computacional
Por todos estes motivos descritos anteriormente, este problema é considerado da classe NP_Hard.
Logo, pode-se perceber, por termos diferentes escolhas de cidades em todos os momentos do problema (exceto a última iteração), que este é um problema de otimização combinatória.
Para facilitar o cálculo, devemos reduzi-lo a um problema de enumeração e, para isto, devemos:
- acharmos todas as rotas possíveis
- calcularmos o comprimento
- verificarmos qual é a menor rota
Como resolver?
Para resolver este problema, podemos seguir algumas técnicas, como:
- Métodos de busca heurística (algoritmo guloso)
- Métodos de computação bioinspirada
- Algoritmos genéticos
- Colônia de formigas
Porém, para fins de apresentar mais facilmente uma solução deste problema, iremos usar a abordagem de busca heurística, como o Twice Around e o algoritmo 2-optimal.
Ainda mais, para resolver este problema devemos responder a 2 questões:
- G é hamiltoniano?
- Se sim, como obter ciclo Hamiltoniano de custo mínimo? -> Não trivial
Algoritmo Twice Around
Este algoritmo consiste de 3 passos principais:
- Encontrar uma Minimum Spanning Tree, a fim de ter os menores custos entre os nós (representados pelas cidades)
- Encontrar um Tour de Euler, para percorrer todas os nós/cidades
- Obter um ciclo Hamiltoniano a partir deste Tour de Euler, pois devemos passar uma única vez por cada nó/cidade
MST - Algoritmo de Prim
Para encontrarmos a MST do grafo que representa as cidades em que o caixeiro viajante deve passar usaremos o Algoritmo de Prim. Vejamos o exemplo:
Em relação ao nosso trabalho, fizemos a seguinte implementação para descobrir o MST pelo algoritmo de Prim:
Tour de Euler - Algoritmo de Fleury
O tour de Euler significa que é possível percorrer todas arestas de G sem repetí-las, começando e terminando em um mesmo vértice v qualquer.
Assim, usaremos o Algoritmo de Fleury para identificar este tour que passa por todas as arestas uma única vez.
Ciclo Hamiltoniano
Um ciclo Hamiltoniano significa que é possível percorrer todos os vértices de G uma única vez, começando e terminando em um mesmo vértice v qualquer, que é exatamente o que procuramos para solucionar o problema do caixeiro viajante.
Para encontrarmos este ciclo, basta tomarmos o tour de Euler como base e tirarmos as repetições.
O seguinte trecho de código, representa a obtenção do tour de Euler e em seguida o ciclo Hamiltoniano:
Já para executar todo o algoritmo, criamos um grafo, inicializamos todas suas arestas e depois mostramos o resultado, como pode ser observado a seguir:
Nenhum comentário:
Postar um comentário