Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver o Travelling Salesman para dez capitais brasileiras?

0 votos
27 visitas
perguntada Set 22 em Ciência da Computação por Sergio Costa (11 pontos)  
editado Set 22 por Sergio Costa

Aplicação de algoritmos para encontrar conector mínimo e para resolver o problema do Travelling Salesman. Questão 11.8 do livro "Combinatorics: Topics, Techniques, Algorithms", por Peter J. Cameron (Capítulo 11, pág 185).

Compartilhe

1 Resposta

0 votos
respondida Set 22 por Sergio Costa (11 pontos)  
editado Set 22 por Sergio Costa

Olá, amigos,

Trata-se da resolução da questão 11.8 do livro "Combinatorics: Topics, Techniques, Algorithms", por Peter J. Cameron".

A questão solicita escolher 10 cidades, e as respectivas distâncias entre elas, para:

1. Encontrar o conector mínimo;
2. Implementar o algoritmo 'twice-round-the-tree' para achar um caminho par ao Travelling Salesman; e
3. Comparar o resultado do item anterior com a rota mais curta o possível.


As 10 cidades escolhidas foram as maiores capitais em ordem decrescente de população municipal, enquanto as respectivas distâncias foram definidas como as distâncias rodoviárias entre cada par de cidade.

Utilizou-se o pacote networkx em Python para a resolução do exercício.


1. Conector mínimo

Basicamente, procura-se aqui ligar todas as cidades com o menor fio possível. O pacote networkx oferece a solução pronta. No exercício, apresentarei tanto o pacote pronto do algoritmo de Prim (mais limpo), como um código feito para o exercício baseado no algoritmo ganancioso apresentado no livro (seção 11.3.1).

import itertools as it
import networkx as nx

#minimum connector
def conector_minimo(theGraph):
    arvore = nx.minimum_spanning_tree(theGraph, algorithm = "prim")
    nx.draw(arvore, with_labels=True)
    return arvore


#minimum conncetor algoritmo alternativo
def conector_alternativo(theGraph):
    arvore=nx.Graph()
    procura=nx.Graph()
    exclusao=nx.Graph()
    minimo = min(theGraph.edges(data=True), key=lambda x: theGraph.get_edge_data(x[0], x[1])["weight"])

    while arvore.nodes != grafo.nodes:
        arvore.add_edges_from([minimo])
        procura.add_edges_from(theGraph.edges(arvore.nodes, data=True))
        exclusao.add_edges_from([minimo])
        procura.remove_edges_from(exclusao.edges(data=True))
        procura.remove_edges_from(list(it.combinations(arvore.nodes,2)))
        try:
            minimo = min(procura.edges(data=True), key=lambda x: procura.get_edge_data(x[0], x[1])["weight"])
        except:
            minimo = minimo

    nx.draw(arvore, with_labels=True)
    return arvore

if __name__ == '__main__':
    #montando rede
    grafo = nx.Graph()
    cidades = ["São Paulo", "Rio de Janeiro", "Brasília", "Salvador", "Fortaleza",
               "Belo Horizonte", "Manaus", "Curitiba", "Recife", "Goiânia"]
    combinacoes=list(it.combinations(cidades,2))
    weights = [429,1015,1962,3127,586,3971,408,2660,926,1148,1649,2805,434,
                   4374,852,2338,1338,1446,2200,716,3490,1366,2135,209,1389,1372,
                   5009,2385,839,1643,2528,5763,3541,800,2482,3951,1004,2061,906,
                   4036,5698,3291,3078,1186,2332]

    for combinacao in combinacoes:
        grafo.add_edge(str(combinacao[0]), str(combinacao[1]),
                       weight=weights[combinacoes.index(combinacao)])

    #conector mínimo Prim
    conector_minimo(grafo)
    #conector mínimo alternativo
    conector_alternativo(grafo)

Abaixo, segue resultado do conector mínimo.

A imagem será apresentada aqui.


2. Algoritmo 'twice-round-the-tree'

O algoritmo referido consiste em:

  • Encontrar um conector mínimo;
  • No grafo do conector mínimo, duplicar as arestas e achar um caminho que visita cada aresta apenas uma vez, mas podendo repetir os vértices e terminando no vértice inicial (closed Eulerian trail);
  • Seguindo esse caminho, pular o vértice seguinte se ele for repetido. Quando todos os vértices forem visitados, voltar ao início.

A resolução partiu encontrando um conector mínimo por qualquer um dos algoritmos acima. Posteriormente, encontrou-se um caminho pelo algoritmo DFS (Depth-First Search) e, por último, realizou-se o terceiro passo do algoritmo. No exemplo, utilizou-se São Paulo como origem.

import itertools as it
import networkx as nx

#twice-round-the-tree algorithm
def twice_round(theGraph, conector, inicio):
    T = list(nx.dfs_edges(conector, source= inicio))
    way=[]
    for aresta in T:
        way.append(aresta[1])
    way=list(dict.fromkeys(way))
    way.insert(0, inicio), way.append(inicio)
    res = str(way)[1:-1]
    print("O caminho tsp aproximado é:", res,".")
    print("Distância em km do tsp aproximado é %d km."% (nx.path_weight(theGraph, way, "weight")))

def conector_minimo(theGraph):
    arvore = nx.minimum_spanning_tree(theGraph, algorithm = "prim")
    nx.draw(arvore, with_labels=True)
    return arvore

if __name__ == '__main__':
    #montando rede
    grafo = nx.Graph()
    cidades = ["São Paulo", "Rio de Janeiro", "Brasília", "Salvador", "Fortaleza",
               "Belo Horizonte", "Manaus", "Curitiba", "Recife", "Goiânia"]
    combinacoes=list(it.combinations(cidades,2))
    weights = [429,1015,1962,3127,586,3971,408,2660,926,1148,1649,2805,434,
                   4374,852,2338,1338,1446,2200,716,3490,1366,2135,209,1389,1372,
                   5009,2385,839,1643,2528,5763,3541,800,2482,3951,1004,2061,906,
                   4036,5698,3291,3078,1186,2332]

    for combinacao in combinacoes:
        grafo.add_edge(str(combinacao[0]), str(combinacao[1]),
                       weight=weights[combinacoes.index(combinacao)])


    #twice-round-the-tree para o Travelling Salesman
    twice_round(grafo, conector_minimo(grafo), "São Paulo")

Resultado:

O caminho tsp aproximado é: 'São Paulo', 'Rio de Janeiro', 'Belo Horizonte', 'Brasília', 'Goiânia', 'Manaus', 'Salvador', 'Recife', 'Fortaleza', 'Curitiba', 'São Paulo' .
Distância em km do tsp aproximado é 15676 km.

3. Comparar resultado do item anterior com a rota mais curta o possível

Para encontrar a rota mais curta o possível, calculou-se as permutações partindo de uma cidade específica. Desse modo, as possibilidades de caminho saíram de \(10!\) para \(9!\), facilitando bastante os cálculos.

import itertools as it
import networkx as nx

#shortest path from inicio
def shortest_path(theGraph, lista, inicio):    
    l = len(lista)
    cities=lista[1:l+1]
    permutacoes = list(it.permutations(cities,l-1))
    minimo = float('inf')

    for permutacao in permutacoes:
        caminho = list(permutacao)
        caminho.insert(0, inicio), caminho.append(inicio)
        dist = nx.path_weight(grafo, caminho, "weight")
        if dist < minimo:
            trilha = caminho
            minimo = dist   

    trail = str(trilha)[1:-1]
    print("O Caminho mais curto é:",trail,".")
    print("A distância mínima é %d km." % (minimo))

if __name__ == '__main__':
    #montando rede
    grafo = nx.Graph()
    cidades = ["São Paulo", "Rio de Janeiro", "Brasília", "Salvador", "Fortaleza",
               "Belo Horizonte", "Manaus", "Curitiba", "Recife", "Goiânia"]
    combinacoes=list(it.combinations(cidades,2))
    weights = [429,1015,1962,3127,586,3971,408,2660,926,1148,1649,2805,434,
                   4374,852,2338,1338,1446,2200,716,3490,1366,2135,209,1389,1372,
                   5009,2385,839,1643,2528,5763,3541,800,2482,3951,1004,2061,906,
                   4036,5698,3291,3078,1186,2332]

    for combinacao in combinacoes:
        grafo.add_edge(str(combinacao[0]), str(combinacao[1]),
                       weight=weights[combinacoes.index(combinacao)])


    #caminho mais curto o possível para o Travelling Salesman
    shortest_path(grafo, cidades, "São Paulo")

Resultado:

O Caminho mais curto é: 'São Paulo', 'Rio de Janeiro', 'Belo Horizonte', 'Salvador', 'Recife', 'Fortaleza', 'Brasília', 'Goiânia', 'Manaus', 'Curitiba', 'São Paulo' .
A distância mínima é 14018 km.

De acordo com o resultado, o algoritmo em 3 de força bruta economizou mais de 1658km. No entanto, caso houvesse apenas uma cidade a mais no caminho, haveria mais de 3,6 milhões de permutações possíveis. Portanto, a depender do número de nós no problema, um algoritmo de aproximação é desejável.

comentou Nov 6 por bonfim_tiago (6 pontos)  
Em primeiro lugar, gostaria de te parabenizar pelos códigos gerados! Os códigos são extremamente intuitivos, modularizados e concisos.
   Em primeiro lugar, acabei ficando com uma dúvida na implementação do laço "while arvore.nodes != grafo.nodes:". Pergunto: não seria possível a ocorrência de um loop infinito aqui? seria o caso de, talvez, considerar um contador como critério de saída para a identificação desses loops... fica aqui a reflexão porque já tive alguns problemas com esse tipo de coisa...
   Além disso, uma prática que eu venho adotando no Python há algum tempo consiste em apresentar o tipo esperado do dado quando da declaração dos parâmetros de entrada de uma função. Por exemplo, poderia ser a declaração de uma variável do tipo int como "a: int" ao invés de somente "a". Isso pode não fazer nenhuma diferença para o Python, mas confere um nível muito interessante de legibilidade aos códigos. Por isso, a recomendação.

   No mais, parabéns e um grande abraço!
comentou Nov 6 por Sergio Costa (11 pontos)  
Obrigado, Tiago, excelentes observações. Também gostaria de parabenizá-lo pelo paper sobre detecção de cartéis com base em redes.

Sobre o uso do while, essa estrutura sempre tem esse perigo quando não se abrange as possíveis exceções, embora ache que não seria o caso para a solução pois a procura é sobre o conjunto de arestas. Quando não há mais arestas a serem procuradas, o 'try/except" salva. Não fica bonito, mas resolve.

Abraço!!!
...