O Problema do Caixeiro Viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem. Ele é um problema de otimização NP-difícil inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível.
Cada cidade foi representada pela sua posição no vetor.
Para as cidades: "A", "B", "C", "D", "E" teremos um vetor com 5 elementos.
["A", "B", "C", "D", "E"]
[ 0, 1, 2, 3, 4 ]As distâncias são posicionadas de acordo com o índice do array de cada cidade.
A B C D E
A [0, 10, 15, 5, 12],
B [10, 0, 70, 52, 27],
C [15, 70, 0, 120, 14],
D [5, 52, 120, 0, 38],
E [12, 27, 14, 38, 0]Sistema desenvolvido utilizando Javascript.
Igor Brown, Matheus Telles, Davi Bernardo, Breno Cocheto, João Vitor, João Marcos, Vinicius Almeida, Rai Menezes.
Análise e Complexidade de Algoritmos - Tassio Sirqueira