Nesse trabalho, o grupo teve que desenvolver um programa que lê um grafo Hamiltoniano ponderado a partir de um arquivo qualquer e através do algoritmo Twice-Around obter 10 soluções diferentes para o problema do caixeiro-viajante.
O problema do caixeiro-viajante consiste na procura de um circuito que possua a menor distância, começando numa qualquer cidade, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial.
Como descrito nas Notas de Aula, “para obter soluções distintas para o problema há algumas heurísticas comumente adotadas na prática: utilizar diferentes inicializações, ou seja, soluções iniciais. Elas podem ser geradas simplesmente aleatoriamente (selecionando vértices quaisquer) ou utilizando alguma heurística, como por exemplo a escolha do vizinho mais próximo. Dessa forma, escolhe-se aleatoriamente apenas o primeiro vértice do ciclo (v0) e depois sempre é escolhido como próximo elemento da sequência o vizinho mais próximo do vértice atual, até que o ciclo Hamiltoniano seja formado (não sobre mais vértices)”
Para desenvolver o trabalho, usamos do algoritmo Twice-around, que consiste de 3 passos principais:
  1. Encontrar uma Minimum Spanning Tree, a fim de ter os menores custos entre os nós (representados pelas cidades)
  2. Encontrar um Tour de Euler, para percorrer todas os nós/cidades
  3. Obter um ciclo Hamiltoniano a partir deste Tour de Euler.
Pseudocódigo Twice-Around
caixeiro_3
No primeiro passo, optamos por utilizar o algoritmo Prim, que já foi utilizado no T3 e está disponível em: Árvores geradoras mínimas e comunidades
Pseudocódigo Prim
pseudo
No segundo passo, usamos o algoritmo de Fleury para encontrar um circuito euliriano:
Entrada: G = (V, E) Euleriano
Saída: Tour de Euler
1. Escolha um vértice inicial v0 qualquer
2. Se Wi=v0 e1 v1 e2v2 … ei vi escolha ei+1 tal que
a) ei+1 é incidente a vi
b) ei+1 não é ponte no subgrafo G – Wi (a menos que seja a única opção)
3. Pare se Wi tiver ∀e∈E . Senão, volta para o passo 2.
No terceiro passo, o ciclo Hamiltoniano é encontrado. A implementação completa pode ser conferida abaixo:
caixeiro_1caixeiro_2caixeiro_3caixeiro_4
Resultado da execução:
Ciclo Hamiltoniano: [2, 23, 10, 5, 1, 3, 27, 29, 13, 8, 28, 14, 21, 12, 0, 16, 19, 7, 26, 11, 24, 9, 18, 15, 20, 25, 4, 22, 6, 17, 2]
Peso: 604.0
Ciclo Hamiltoniano: [4, 22, 6, 25, 20, 15, 18, 7, 26, 11, 24, 9, 19, 16, 0, 12, 21, 2, 23, 10, 5, 1, 3, 27, 29, 13, 8, 28, 14, 17, 4]
Peso: 583.0
Ciclo Hamiltoniano: [6, 22, 4, 25, 20, 15, 18, 7, 26, 11, 24, 9, 19, 16, 0, 12, 21, 2, 23, 10, 5, 1, 3, 27, 29, 13, 8, 28, 14, 17, 6]
Peso: 541.0
Ciclo Hamiltoniano: [8, 13, 27, 29, 3, 1, 5, 10, 23, 2, 21, 12, 0, 16, 19, 7, 26, 11, 24, 9, 18, 15, 20, 25, 4, 22, 6, 17, 28, 14, 8]
Peso: 566.0
Ciclo Hamiltoniano: [10, 23, 2, 21, 12, 0, 16, 19, 7, 26, 11, 24, 9, 18, 15, 20, 25, 4, 22, 6, 17, 5, 1, 3, 27, 29, 13, 8, 28, 14, 10]
Peso: 515.0
Ciclo Hamiltoniano: [12, 21, 2, 23, 10, 5, 1, 3, 27, 29, 13, 8, 28, 14, 17, 0, 16, 19, 7, 26, 11, 24, 9, 18, 15, 20, 25, 4, 22, 6, 12]
Peso: 548.0
Ciclo Hamiltoniano: [14, 28, 8, 13, 27, 29, 3, 1, 5, 10, 23, 2, 21, 12, 0, 16, 19, 7, 26, 11, 24, 9, 18, 15, 20, 25, 4, 22, 6, 17, 14]
Peso: 509.0
Ciclo Hamiltoniano: [16, 19, 7, 26, 11, 24, 9, 18, 15, 20, 25, 4, 22, 6, 0, 12, 21, 2, 23, 10, 5, 1, 3, 27, 29, 13, 8, 28, 14, 17, 16]
Peso: 565.0
Ciclo Hamiltoniano: [18, 7, 26, 11, 24, 9, 19, 16, 0, 12, 21, 2, 23, 10, 5, 1, 3, 27, 29, 13, 8, 28, 14, 17, 15, 20, 25, 4, 22, 6, 18]
Peso: 599.0
Ciclo Hamiltoniano: [20, 15, 18, 7, 26, 11, 24, 9, 19, 16, 0, 12, 21, 2, 23, 10, 5, 1, 3, 27, 29, 13, 8, 28, 14, 17, 25, 4, 22, 6, 20]
Peso: 598.0

Melhores:
Peso: 604.0
Cliclo Hamiltoniano: [2, 23, 10, 5, 1, 3, 27, 29, 13, 8, 28, 14, 21, 12, 0, 16, 19, 7, 26, 11, 24, 9, 18, 15, 20, 25, 4, 22, 6, 17, 2]
Peso: 599.0
Cliclo Hamiltoniano: [18, 7, 26, 11, 24, 9, 19, 16, 0, 12, 21, 2, 23, 10, 5, 1, 3, 27, 29, 13, 8, 28, 14, 17, 15, 20, 25, 4, 22, 6, 18]
Peso: 598.0
Cliclo Hamiltoniano: [20, 15, 18, 7, 26, 11, 24, 9, 19, 16, 0, 12, 21, 2, 23, 10, 5, 1, 3, 27, 29, 13, 8, 28, 14, 17, 25, 4, 22, 6, 20]

Piores:
Peso: 509.0
Cliclo Hamiltoniano: [14, 28, 8, 13, 27, 29, 3, 1, 5, 10, 23, 2, 21, 12, 0, 16, 19, 7, 26, 11, 24, 9, 18, 15, 20, 25, 4, 22, 6, 17, 14]
Peso: 515.0
Cliclo Hamiltoniano: [10, 23, 2, 21, 12, 0, 16, 19, 7, 26, 11, 24, 9, 18, 15, 20, 25, 4, 22, 6, 17, 5, 1, 3, 27, 29, 13, 8, 28, 14, 10]
Peso: 541.0
Cliclo Hamiltoniano: [6, 22, 4, 25, 20, 15, 18, 7, 26, 11, 24, 9, 19, 16, 0, 12, 21, 2, 23, 10, 5, 1, 3, 27, 29, 13, 8, 28, 14, 17, 6]
Como podemos observar, a saída exibe os 3 melhores e os 3 piores caminhos encontrados.

O código fonte e demais arquivos usados nesse trabalho estão disponíveis em: https://github.com/WellitonAlt/Grafos

 

Referências:

Problema do Caixeiro Viajante:

mat.ufrgs.br

Notas de aula da disciplina.

Advertisements