Caixeiro-viajante
Visitar todas as cidades e voltar ao início pelo caminho mais curto. É um problema NP-completo: não se conhece algoritmo rápido que garanta a melhor rota. A força bruta testa todas as ordens, cuja quantidade cresce como o fatorial. A alternativa é uma aproximação gulosa.
Explicação do algoritmo: escolha um nível para ler.
{ }Ver o código
const distancia = (a, b) => Math.hypot(a.x - b.x, a.y - b.y);
function comprimento(cidades, rota) {
let total = 0;
for (let i = 0; i < rota.length; i++) {
total += distancia(cidades[rota[i]], cidades[rota[(i + 1) % rota.length]]); // volta ao início
}
return total;
}
// Aproximação gulosa: sempre vai para a cidade não visitada mais próxima
function vizinhoMaisProximo(cidades) {
const rota = [0];
while (rota.length < cidades.length) {
const atual = cidades[rota[rota.length - 1]];
let proxima = -1;
for (let i = 0; i < cidades.length; i++) {
if (rota.includes(i)) continue;
if (proxima === -1 || distancia(atual, cidades[i]) < distancia(atual, cidades[proxima])) {
proxima = i;
}
}
rota.push(proxima);
}
return rota;
}
// Força bruta: testa todas as (n - 1)! ordens possíveis
function forcaBruta(cidades) {
let melhor = null;
let menor = Infinity;
function permutar(rota, restantes) {
if (restantes.length === 0) {
const c = comprimento(cidades, rota);
if (c < menor) {
menor = c;
melhor = rota;
}
return;
}
for (let i = 0; i < restantes.length; i++) {
permutar([...rota, restantes[i]], restantes.filter((_, j) => j !== i));
}
}
permutar([0], cidades.map((_, i) => i).slice(1));
return melhor;
}Vizinho mais próximo (guloso)
287,2A → E → F → B → C → G → D → A
Melhor rota (força bruta)
248,5A → D → E → F → C → B → G → A
Como reconhecer um problema NP-completo
Provar que um problema é NP-completo é difícil, mas o livro dá pistas práticas para suspeitar. São regras de bolso, não provas.
- Pista 1
Rápido com poucos itens, lento com muitos
Se o seu algoritmo roda bem com 5 itens e fica impraticável com 20, desconfie. Arraste o controle acima de 4 para 9 cidades e veja o número de rotas disparar.
- Pista 2
Pede "todas as combinações de X"
Se a solução óbvia é testar todas as ordens ou todos os subconjuntos, como a força bruta desta página, o problema pode ser NP-completo.
- Pista 3
Envolve uma sequência ou um conjunto
Se a dificuldade está em escolher uma sequência (como a ordem das cidades) ou um conjunto (como as estações de rádio que cobrem todos os estados), suspeite.
- Pista 4
Dá para reformular como um problema conhecido?
Se você consegue reescrever o seu problema como o do caixeiro-viajante ou como a cobertura de conjuntos, ele também é NP-completo.