Um pouco sobre o Salesman Problem

O Salesman Problem, também conhecido como o Problema do Caixeiro Viajante, é um dos problemas mais estudados no campo da Matemática e Ciência da Computação.

Neste humilde post eu pretendo fazer uma breve introdução ao tópico, e apresentar um algoritmo que utiliza o paradigma de Programação Dinâmica para resolver o problema.

Clique no link abaixo para ler mais.

Salesman Problem – Descrição

O Salesman Problem foi inspirado na vida de um vendedor viajante que pretendia vender seus produtos em N cidades diferentes. Para isso ele deveria visitar todas as N cidades uma vez, e terminar seu percurso na mesma cidade em que iniciou.

Como existiam muitas maneiras de se fazer este percurso, ele decidiu escolher o percurso que o fizesse andar o mínimo possível.

É intuitivo fazermos a conversão deste problema para um estrutura de grafos, onde cada cidade representa um vértice, e cada estrada entre duas cidades representa uma aresta entre dois vértices, sendo o peso de tal vértice igual ao comprimento de tal estrada.

Abordagem padrão

A abordagem mais trivial para a resolução deste problema é a força bruta, onde todos os possíveis trajetos são testados, e temos como resultado aquele que tiver o menor custo de percurso.

Por exemplo, considere o grafo da imagem abaixo, com N = 4 vértices, sendo 1 o vértice inicial.

 

Temos um total de 6 possíveis percursos, sendo o percurso 1 – 2 – 3 – 4 – 1 um dos percursos de menor custo (11).

O problema desta abordagem é que o número de possíveis percursos cresce perigosamente em relação ao número de vértices no grafo. Levando em consideração o exemplo acima, temos 3 opções de visita para o primeiro vértice, 2 opções para o segundo vértice, e 1 opção para o terceiro. Logo, 3*2*1 = 6 percursos.

É possível generalizar essa contagem para uma fórmula: seja f(N) uma função que calcular o número de possíveis trajetos a serem feitos em um grafo completo de N vértices. Temos:

f(2) = 1 = 1!
f(3) = 2*1 = 2 = 2!
f(4) = 3*2*1 = 6 = 3!
Logo, f(N) = (N-1) * (N-2) * … * 2 * 1 = (N-1)!

Conforme o número de vértices sobe o número de percursos também sobe absurdamente. Para N = 14 já temos mais de 6 bilhões de possíveis percursos.

Outros algoritmos e heurísticas foram estudados e apresentados para se tentar resolver tal problema, mas como o Salesman Problem pertence à classe de problemas NP-Hard nenhuma das atuais soluções ótimas tem complexidade menor que polinomial. O desafio permanece em aberto.

No restante deste post pretendo demonstrar como utilizar Programação Dinâmica para melhorar a complexidade da abordagem acima. Tal algoritmo tem complexidade igual a O(N^2 * 2^N), é muito utilizado em competições de programação e consegue resolver com um tempo razoável problemas com N <= 20.

Salesman + Programação Dinâmica

Em resumo é possível dizer que programação dinâmica procura dividir o problema em sub-problemas menores, de tal modo que as soluções de tais sub-problemas contribuam para a solução do problema original. No nosso caso, pretendemos resolver o problema para pequenos percursos do grafo, armazenar tais soluções, e utilizá-las para resolver percursos cada vez maiores.

Vejamos, para aplicarmos programação dinâmica precisamos definir o seguinte:

(1) qual o problema.
(2) quais são os sub-problemas.
(3) quais são os relacionamentos entre os problemas e sub-problemas.

Para o caso do Salesman Problem temos o seguinte:

(1) descobrir o menor custo de se visitar todos os N vértices do grafo, iniciando e terminando o percurso no vértice 1.
(2) descobrir o menor custo de se visitar um determinado conjunto de vértices do grafo, terminando o percurso no vértice 1.
(3) o relacionamento entre os sub-problemas se baseia no seguinte conceito:

todo sub-percurso de um percurso de custo mínimo tem, por si só, custo mínimo

Logo, a solução de um sub-problema B pode ser útil para a solução de um sub-problema A, caso B seja um sub-percurso de A.

Definição formal

Antes que possamos montar o quebra-cabeça precisamos definir as peças.

Seja v o vértice em que o vendedor está atualmente.
Seja S um conjunto de vértices já visitados pelo vendedor. Note que v ∈ S.
Seja P um conjunto de vértices ainda não visitado pelo vendedor. Note que S ∪ P = {1, 2, …, N}, e S ∩ P = {∅}.
Seja c(a, b) o custo da aresta entre os vértices a e b.

Seja agora sp(v, S) uma função que calcula o custo mínimo de se visitar todos os vértices em P, iniciando o percurso no vértice v e terminando no vértice 1.

Temos como caso base sp(v, {1, 2, …, N}) = c(v, 1). Visitamos aqui todos os vértices do grafo e estamos atualmente no vértice v. O custo de se visitar os vértices ainda não visitados (nenhum) é zero, logo a resposta é igual ao custo da aresta entre v e 1 (sempre terminamos no vértice 1).

Por fim, nossa relação entre os sub-problemas é:

sp(v, S) = min( sp(u, S+u) + c(v, u) ),
para todo u em P.

É possível interpretar tal procedimento como uma busca em profundidade, como pode ser visualizado na imagem abaixo.

A vantagem desta abordagem para a busca em profundidade está no armazenamento e reuso do resultado de sub-problemas. Por exemplo, em um grafo com N = 10 vértices, note que ao fazermos os dois seguintes percursos, A = 1 – 2 – 5 – 4, e B = 1 – 5 – 2 – 4, chegamos ao mesmo sub-problema: sp(4, {1, 2, 4, 5}). Logo, se resolvermos tal sub-problema da primeira vez (no restante do percurso A), não precisaremos resolvê-lo da segunda (no restante do percurso B).

Algoritmo

Agora que temos tudo definido podemos escrever nosso algoritmo. Segue abaixo uma implementação em C++:

int dfs(int v, int S) {
    // caso base
    if(completo(S)) return adj[v][1];
    
    // sub-problema ja resolvido
    if(sp[v][S] != -1) return sp[v][S];
    
    int resposta = INF;
    for(int u=1; u<=n; u++) {
        if(!pertence(u, S)) {
            resposta = min(
                resposta, 
                dfs(u, inclua(u, S)) + adj[v][u]
            );
        }
    }
    
    sp[v][S] = resposta;
    return sp[v][S];
}

Para que o conjunto de vértices S fosse representando por um único inteiro acima, foi-se utilizada uma técnica chamada Bitmask. Leia mais a respeito dela [por aqui] (inglês).

Segue o link com o código completo: [github]

Conclusão

A complexidade do algoritmo acima pode ser calculado se multiplicarmos o número de sub-problemas pelo número de operações realizados para se resolver cada sub-problema, que são, respectivamente, N * 2^N e N. Logo, o algoritmo acima tem complexidade O(N^2 * 2^N).

O Salesman Problem permanece como um problema aberto no campo da ciência da computação, e esta foi apenas uma abordagem que otimiza a complexidade nada atrativa da força bruta trivial (N!).

 

 

Qualquer dúvida, sugestão ou crítica, peço deixem um comentário abaixo 😉