Nesse post você vai fazer uma viagem tanto na história quanto na complexidade do problema do caixeiro viajante. Esse monstro que “persegue” vários estudantes de ciência da computação (muitas vezes tirando o sono de alguns) e também foi considerado um problema de 1 milhão de dólares. Um único problema mudou a história da computação e como você pode tentar resolvê-lo no seu computador.

O que é um caixeiro viajante?

Quando o problema foi proposto, essa profissão ainda existia por conta de vários problemas que a humanidade foi superando ao longo dos anos. Antes mesmo da internet existir e as telecomunicações serem dominantes no mundo das vendas era necessário que um empregado fosse de cidade em cidade com o mostruário para vender produtos de porta em porta.

Esses personagens únicos da história também eram chamados de “mascates” no Brasil, porém a palavra teve sua origem do árabe “El-Matrac” cujo designava os portugueses auxiliados por libaneses que tomaram a cidade de Mascate (atual omã) em 1507 levando as mercadorias [1]. Além disso, no Brasil estudamos que no Recife houve até uma guerra chamada “guerra dos mascates” que foi causada por uma briga política e econômica entre a nobreza açucareira pernambucana e os novos burgueses do Recife (formado essencialmente de portugueses) [2]. A verdade é que o mascate sempre foi um termo pejorativo na época e até hoje existe um resquício desse preconceito quando falamos essa palavra.

Contextualizando o problema do caixeiro viajante

Imagine nosso amigo abaixo, caixeiro viajante que está na estrada e precisa passar em diversas cidades para apresentar suas mercadorias e vender aos habitantes. O problema acontece quando esse nosso amigo precisa escolher a melhor rota para economizar tempo em suas desgastantes viagens, assim, existem basicamente dois fatores que precisam ser considerados: distância entre as cidades e a ordem que elas são visitadas.

Para abstrair esse problema, geralmente representamos as cidades usando um grafo (veja abaixo uma abstração dessas rotas). Perceba que algumas cidades possuem saída para duas outras como em Helge você poderia ir para Bulge ou então para Dax. No entanto, existem cidades possuem saídas para apenas uma outra cidade, por exemplo em Dax você pode ir apenas para Uran ou então em Bulge você pode ir apenas para Dax.

Se você quisesse apenas um caminho válido para percorrer TODAS as cidades, poderiamos citar:

Dax, Uran, Helge e Bulge.

Um caminho inválido seria:

Helge, Dax, Uran, Helge e Bulge.

Geralmente esse problema limita que não é possível passar em uma mesma cidade duas vezes. Mas agora vamos inserir um pouco mais de informações em nosso problema…

Imagine o primeiro caminho:

Bulge, Dax, Uran, Helge → Peso: 70 km

Agora se percorrermos:

Uran, Helge, Dax, Bulge → Peso: 90 km

Veja que claramente o segundo caminho é válido, porém, mais custoso.

Para contextualizar o mesmo problema em um cenário atual, veja um exemplo bem simples: considere que você é simples turista e quer visitar vários pontos turísticos de Curitiba, portanto, para isso você deverá escolher a melhor rota possível para economizar combustível e economizar tempo.

E ai, será que você conseguiria dizer qual é o melhor caminho para percorrer esses pontos turísticos? Bom, esse é o problema do caixeiro viajante que inspirou cientistas da computação por vários anos a criar formas otimizadas de resolver esse problema.

Ué mas por que é tão complexo assim?

Boa pergunta meu amigo… na verdade, esse problema pode ser resolvido facilmente por um algoritmo quando existem poucas cidades, poucas rotas, poucos pesos. No entanto, a medida que a quantidade de cidades aumenta mais difícil de encontrar soluções ótimas. Verificar qual é a solução ótima para a viagem tornou-se um desafio para muitos matemáticos e cientistas da computação.

Um problema que entrou pra história da computação

O problema do caixeiro viajante possui seus registros mais antigos em 1832, porém, não havia nenhuma indicação de preocupação matemática com a resolução desse problema. Apenas em 1930 ele foi formulado por W.R. Hamilton e Thomas Kirkman e além desses cientistas muitos outros contribuiram para formulação desse problema. Karl Menger definiu que a força bruta como a solução mais óbvia, porém, era necessário inserir heurísticas para otimizar a solução [3].

Na verdade, o problema desde o início sempre foi definido como um problema de otimização e foi adaptado para diversas áreas. O caixeiro viajante é considerado uma base para criar soluções para problemas modernos como a logística (Ifood, Uber, etc), otimização de processos fabricação, sequenciamento de DNA e até mesmo minimizar o tempo gasto na movimentação de telescópios na astronomia. Tudo isso começou com Marril M. Flood que estava procurando uma forma de resolver um problema de roteamento de ônibus escolar, mas a verdade é que esse problema é tão antigo e tantos já quebraram a cabeça com ele que ao longo do tempo ele ganhou várias soluções bastante robustas [3].

O nome caixeiro viajante foi usado pela primeira vez por Júlia Robinson em sua publicação de um relatório da RAND corporation. Outro problema que devemos considerar é que na década de 30, 40 ou 50 os computadores e o poder computacional era apenas uma fração do que os computadores são atualmente. Porém, o problema é tão complexo que permaneceu vivo por muitos anos até ser solucionado de forma razoavelmente satisfatória. Em 1970 e 1980, Grötschel, Padberg, Rinaldi e outros conseguiram resolver o problema com até 2392 cidades e apenas em 2006 que Cook e outros cientistas calcularam um passeio ótimo por uma instância com 85900 cidades (no contexto de um microchip e não de uma cidade real) [3].

Muitos dizem que a solução para os problemas computacionais atuais seria a evolução do hardware ao ponto que não é necessário precupação com otimização. Porém, observando a história podemos entender que problemas como o caixeiro viajante e sua discussão ao longo dos anos trouxeram soluções que foram extrapoladas e foram aplicadas em muitas áreas diferentes, portanto, mesmo que a evolução do hardware seja um grande avanço, a construção de soluções inteligentes para problemas da área são igualmente importantes nesse contexto [3].

Soluções do problema

Como dissemos anteriormente existem diversas soluções para esse problema e mesmo aquela que é considerada a mais óbvia (força bruta) por ser a mais ineficiente pode ser um excelente método para treinar seus conhecimentos. Porém, antes de mais nada precisamos criar uma forma de representar nossas cidades e também o caminho até elas.

Se você não entende muito sobre grafos, sugiro que você acesse algum material sobre isso. Por exemplo, esse material do IME-USP é excelente.

Veja abaixo uma sugestão de como representar um grafo com cidades em seus nós:

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

int index = 0;

struct edge{
    char start;
    char end;
    int weight;
    int checked;
};
typedef struct edge Edge;

struct graph{
    Edge edges[MAX];
    int numberOfEdges;
};
typedef struct graph Graph;

Graph initialize(Graph g){
    for (int x = 0; x < MAX; x++){
        g.edges[x].start = 0;
    }
    g.numberOfEdges = 0;
    return g;
}

void addEdge(Graph* g, char start, char end, int weight){
    if (index >= 100){
        printf("O Grafo está cheio");
    } else {
        Edge edge;
        edge.start = start;
        edge.checked = 0;
        edge.end = end;
        edge.weight = weight;
        g->edges[index] = edge;
        index++;
        g->numberOfEdges += 1;
    }
}

void showGraph(Graph g){
    ///imprimir todos os nós
    for (int x = 65; x < 90; x++){
        for (int y = 0; y < MAX; y++){
            if (g.edges[y].start == x){
                printf("%c - %d -  %c\n", g.edges[y].start, g.edges[y].weight, g.edges[y].end );
            }
        }
    }
}

A validação das rotas e a realização da soma dos pesos são funções auxiliares importantíssimas para esse algoritmo:

int validarRota(char rota[], int tamanho, Graph g){
    for (int y = 0; y < tamanho; y++) {
        int check = 0;
        for (int x = 0; x < g.numberOfEdges; x++){
            if (g.edges[x].start == rota[y] && g.edges[x].end == rota[y + 1] && g.edges[x].checked == 0) {
                check = 1;
                g.edges[x].checked = 1;
                break;
            }
            if (g.edges[x].end == rota[y] && g.edges[x].start == rota[y + 1] && g.edges[x].checked == 0) {
                check = 1;
                g.edges[x].checked = 1;
                break;
            }
        }
        if (check == 0){
            return 0;
        }
    }
    return 1;
}

int somaPesos(char rota[], int tamanho, Graph g){
    int soma = 0;
    for (int y = 0; y < tamanho; y++) {
        for (int x = 0; x < g.numberOfEdges; x++){
            if (g.edges[x].start == rota[y] && g.edges[x].end == rota[y + 1]) {
                soma += g.edges[x].weight;
                break;
            }
            if (g.edges[x].end == rota[y] && g.edges[x].start == rota[y + 1]) {
                soma += g.edges[x].weight;
                break;
            }
        }
    }
    return soma;
}

Força bruta

A solução da força bruta se resume em: deixe o computador testar todas as combinações e verificar qual é a melhor. Para isso, podemos codificar um algoritmo desses assim:

void mostrarRotasValidas(Graph g, char first, char last){
    for (int j = 66; j <= 67; j++){
        char letra1 = j;
        for (int k = 66; k <= 67; k++){
            char letra2 = k;
            char rota[] = {first, letra1, letra2, last};
            if (validarRota(rota, 3, g)){
                int soma = somaPesos(rota, 3, g);
                printf("\n%c-%c-%c-%c => Peso: %d\n", first,letra1,letra2,last,soma);
            }
        }
    }
}

O grande problema é a quantidade de possibilidades para ser verificada. Veja essa tabela:

Cidades	Combinações possíveis
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	362880
10	3628800
11	39916800
12	479001600
13	6227020800
14	87178291200
15	1307674368000
16	20922789888000
17	355687428096000

Perceba que com apenas 17 cidades a quantidade de possibilidades para avaliar são incrivelmente grandes. Portanto, na maioria dos casos seu processador vai fritar por horas e não vai chegar em uma solução.

Criando uma heurística para melhorar o desempenho do algorítmo

Uma heurística é uma “pista” que você dá ao algorítmo para que a solução seja otimizada e encontre o caminho ótimo mais facilmente. Por exemplo, imagine que você está desenvolvendo um algoritmo para fazer um bolo e ele precisa selecionar os ingredientes, consequentemente, para esse algorítmo temos algumas heurísticas possíveis:

• Ingredientes fora do prazo de validade são ruins
• Ingredientes salgados tendem a ser menos usados
• Ingredientes picantes tendem a ser menos usados
• Frutas são muito usadas
• Ingredientes doces são mais usados

Mas pera aí, o que isso tem a ver com nosso caixeiro?

Calma… eu explico…

Uma heurística pode ser aplicada nesse algorítmo dizendo:

• Se eu estou em uma cidade, vou para próxima cidade que possui o menor custo de caminhada

Assim, com essa heuristica eu posso escolher mais inteligentemente qual caminho vou seguir antes de realizar a ação. Podemos dizer que antes a filosofia do nosso “algorítmo marombado” era apenas seguir em frente e avaliar depois, agora você pensa antes de ir.

Implementação do caixeiro viajante em C e Python

Os exemplos criados e mostrados aqui nesse post seguiram duas abordagens bastante diferentes. Uma delas usando uma representação de grafo mais livre (fora dos padrões tradicionais) e outra usando uma representação mais tradicional (usando listas ligadas).

A implementação tradicional é bastante complexa quando usamos a linguagem C, isso acontece visto que é necessário criar e manipular listas ligadas (o que não é muito simples). No entanto, quando estamos usando a linguagem Python isso fica MUITO mais tranquilo. Sendo assim, nós escolhemos implementar duas versões desse mesmo algorítmo:

1. Usando a linguagem C e uma representação não convencional (não usando listas ligadas).
2. Usando Python e uma representação mais tradicional (com listas ligadas).

Ambas representações estão disponíveis aqui.

Agora se você está interessado em compreender melhor como representar grafos usando linguagens de programação, não se esqueça de visitar nossa seção onde armazenamos representações de grafos.

Além disso, é possível você elevar o nível das suas representações usando a biblioteca IGraph feita para o Python. Se você quiser entender mais sobre isso, veja nosso breve tutorial de introdução ao Igraph.

Visite também nosso repositório de estrutura de dados: