Cód. Trabalho: 1256 | Palavras-chave: Caixeiro viajante, Ciclo Hamiltoniano, R.
Título: O problema do caixeiro viajante
Autor(es): Aline Edlaine de Medeiros, Mônica Marin de Souza.
Resumo: Resumo– Problemas de otimização percorrem diversas áreas, tais como a Matemática, a Estatística, a Computação, e Engenharias. Entre eles, há a classe dos problemas NP, que compreende todos os problemas de decisão cujas soluções podem ser verificadas em tempo polinomial. Dentro desse conjunto, um dos problemas que mais se destacam é o problema do caixeiro viajante, que busca responder à seguinte questão: Dada uma lista de cidades e as distâncias entre cada par de cidades, qual a menor rota que possibilita visitar todos os municípios apenas uma vez e voltar ao ponto de partida? Esse problema pode ser interpretado como um ciclo Hamiltoniano, que consiste em um grafo que descreve em seus vértices um conjunto de cidades que devem ser visitadas uma única vez, e cujas arestas só podem ser atravessadas em uma única direção. Para cada vértice no grafo pode-se determinar um novo caminho de modo a visitar todas as cidades, por exemplo, se o objetivo for passar por 10 cidades, haverá 10! modos de visitar cada uma das cidades somente uma vez. Consequentemente, a medida em que o número de cidades aumenta, o número de caminhos Hamiltonianos distintos que podem ser percorridos crescem, de modo que a otimização manualmente se torna inviável. Para isso, existem métodos de calcular esses caminhos em várias linguagens computacionais. Esse trabalho consiste em utilizar pacotes da linguagem R para obter o melhor caminho em um problema que consiste em percorrer 20 cidades do estado do Paraná passando por cada uma única vez.