Pular para o conteúdo
</> Entendendo Algoritmos

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;
}
Rotas testadas (força bruta)
720
Rotas testadas (guloso)
1
Guloso é mais longo em
15,6%

Vizinho mais próximo (guloso)

287,2
ABCDEFG

A → E → F → B → C → G → D → A

Melhor rota (força bruta)

248,5
ABCDEFG

A → D → E → F → C → B → G → A

Com 7 cidades há 720 rotas para testar ((n − 1)!). Com 10 cidades seriam 362.880; com 15, mais de 87 bilhões. Por isso, para problemas NP-completos, o livro recomenda aceitar uma solução aproximada em vez da exata. O guloso nem sempre acha a melhor rota, mas custa quase nada. A cidade A (branca) é o ponto de partida e de chegada.

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.

  1. 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.

  2. 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.

  3. 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.

  4. 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.

E agora? Para um problema NP-completo não se conhece um algoritmo rápido que garanta a melhor solução. A saída recomendada é usar uma aproximação: o vizinho mais próximo aqui e a escolha gulosa das estações na página do algoritmo guloso. Elas são rápidas e chegam perto, mas nem sempre acham o melhor resultado.