Para aprender a resolver o problema do Caixeiro Viajante de maneira prática e gradual, aqui vão três versões, que vão desde o básico até o avançado:
### Versão 1: Algoritmo de Vizinho Mais Próximo (Fácil)
Este é o algoritmo mais simples para resolver o problema, que consiste em começar de uma cidade qualquer e, a cada passo, ir para a cidade mais próxima ainda não visitada.
#### Passo a Passo:
1. Escolha uma cidade inicial.
2. Vá para a cidade mais próxima que ainda não foi visitada.
3. Repita até que todas as cidades tenham sido visitadas.
4. Retorne à cidade inicial.
**Código Básico em Python**:
```python
import numpy as np
# Defina as coordenadas das cidades (x, y)
cidades = np.array([
[0, 0], [2, 6], [3, 2], [5, 8], [6, 3], [8, 8]
])
# Função para calcular a distância entre duas cidades
def distancia(cidade1, cidade2):
return np.sqrt(np.sum((cidade1 - cidade2) ** 2))
# Algoritmo do Vizinho Mais Próximo
def vizinho_mais_proximo(cidades):
cidade_atual = 0
caminho = [cidade_atual]
total_distancia = 0
while len(caminho) < len(cidades):
distancias = [distancia(cidades[cidade_atual], cidades[i]) if i not in caminho else float('inf') for i in range(len(cidades))]
cidade_mais_proxima = np.argmin(distancias)
total_distancia += distancias[cidade_mais_proxima]
caminho.append(cidade_mais_proxima)
cidade_atual = cidade_mais_proxima
# Volta para a cidade inicial
total_distancia += distancia(cidades[cidade_atual], cidades[caminho[0]])
caminho.append(caminho[0])
return caminho, total_distancia
caminho, distancia_total = vizinho_mais_proximo(cidades)
print("Caminho encontrado:", caminho)
print("Distância total:", distancia_total)
```
---
### Versão 2: Algoritmo Genético (Intermediário)
Este método utiliza a teoria de seleção natural para encontrar uma solução aproximada para o problema. Cada "geração" gera um novo conjunto de soluções (ou rotas), e as melhores soluções sobrevivem e "cruzam" para criar novas gerações.
#### Passo a Passo:
1. Crie uma população inicial de rotas aleatórias.
2. Avalie o "fitness" de cada rota, que é a distância total percorrida.
3. Selecione as rotas mais curtas para cruzamento.
4. Realize o cruzamento e aplique mutações para criar uma nova geração.
5. Repita por várias gerações.
**Código Básico em Python**:
```python
import random
# Define a população inicial
def gerar_populacao(cidades, tamanho_populacao):
return [random.sample(range(len(cidades)), len(cidades)) for _ in range(tamanho_populacao)]
# Calcula a distância total de uma rota
def distancia_total(rota, cidades):
return sum(distancia(cidades[rota[i]], cidades[rota[(i + 1) % len(rota)]]) for i in range(len(rota)))
# Seleciona os melhores indivíduos
def selecao(populacao, cidades, num_selecionados):
fitness_pop = sorted([(distancia_total(rota, cidades), rota) for rota in populacao])
return [rota for _, rota in fitness_pop[:num_selecionados]]
# Função de cruzamento
def cruzamento(pai1, pai2):
ponto = random.randint(1, len(pai1) - 2)
filho = pai1[:ponto] + [gene for gene in pai2 if gene not in pai1[:ponto]]
return filho
# Função de mutação
def mutacao(rota, taxa_mutacao=0.1):
if random.random() < taxa_mutacao:
i, j = random.sample(range(len(rota)), 2)
rota[i], rota[j] = rota[j], rota[i]
return rota
# Algoritmo Genético Completo
def algoritmo_genetico(cidades, tamanho_populacao, num_geracoes, num_selecionados):
populacao = gerar_populacao(cidades, tamanho_populacao)
for _ in range(num_geracoes):
selecionados = selecao(populacao, cidades, num_selecionados)
filhos = [cruzamento(random.choice(selecionados), random.choice(selecionados)) for _ in range(tamanho_populacao)]
populacao = [mutacao(filho) for filho in filhos]
melhor_rota = min(populacao, key=lambda rota: distancia_total(rota, cidades))
return melhor_rota, distancia_total(melhor_rota, cidades)
melhor_rota, distancia_minima = algoritmo_genetico(cidades, tamanho_populacao=100, num_geracoes=500, num_selecionados=20)
print("Melhor rota encontrada:", melhor_rota)
print("Distância mínima:", distancia_minima)
```
---
### Versão 3: Algoritmo de Simulated Annealing (Avançado)
Esse algoritmo é inspirado no processo de recozimento em metalurgia. Ele busca soluções boas, mas permite que soluções piores sejam aceitas no início para escapar de mínimos locais. Com o tempo, as chances de aceitar soluções piores diminuem.
#### Passo a Passo:
1. Comece com uma rota aleatória e uma "temperatura" inicial.
2. Em cada passo, faça uma pequena alteração na rota.
3. Se a nova rota for melhor, aceite-a. Se for pior, aceite com uma probabilidade baseada na temperatura.
4. Reduza a temperatura gradualmente.
**Código Básico em Python**:
```python
import math
# Troca duas cidades para criar uma nova rota
def nova_rota_perturbada(rota):
i, j = random.sample(range(len(rota)), 2)
rota[i], rota[j] = rota[j], rota[i]
return rota
# Simulated Annealing
def simulated_annealing(cidades, temperatura_inicial=100, taxa_resfriamento=0.99, iteracoes=1000):
rota_atual = list(range(len(cidades)))
random.shuffle(rota_atual)
melhor_rota = rota_atual
distancia_atual = distancia_total(rota_atual, cidades)
menor_distancia = distancia_atual
temperatura = temperatura_inicial
for _ in range(iteracoes):
nova_rota = nova_rota_perturbada(rota_atual[:])
nova_distancia = distancia_total(nova_rota, cidades)
# Aceita a nova rota se ela for melhor ou com base na temperatura
if nova_distancia < distancia_atual or math.exp((distancia_atual - nova_distancia) / temperatura) > random.random():
rota_atual, distancia_atual = nova_rota, nova_distancia
if distancia_atual < menor_distancia:
melhor_rota, menor_distancia = rota_atual, distancia_atual
# Resfria a temperatura
temperatura *= taxa_resfriamento
return melhor_rota, menor_distancia
melhor_rota, menor_distancia = simulated_annealing(cidades)
print("Melhor rota encontrada:", melhor_rota)
print("Menor distância:", menor_distancia)
```
---
Essas três abordagens apresentam soluções práticas e crescentes para resolver o problema do Caixeiro Viajante, desde o básico até o avançado.
Comentários
Postar um comentário