Descrição - Grafos

UECE – Curso de Bacharelado em Ciência da Computação – 2015.1
Trabalho em Laboratório de TEORIA DOS GRAFOS

1

– Em 28/08/15 –

Prof. Valdisio Viana

Instruções
• Este trabalho deve ser entregue no início da aula do dia 04-Set-2015.
• Para cada item, a equipe correspondente deverá preparar e entregar no data acima um texto IMPRESSO, de preferência em “.pdf” em forma de artigo no modelo indicado e enviar 1 todo o material (algoritmo, programa etc). Obs.: O não cumprimento deste prazo na entrega do trabalho implica em perda de pontos na nota final.
• A nota desta avaliação levará em consideração os seguintes aspectos: organização, abrangência, clareza, resultados obtidos e facilidade do uso do programa para outros testes.

2

Tópicos

EQUIPE
1
2
3
4
5
6
7
8

3

Algoritmo / Heurística
Vizinho mais próximo com n partidas
Inserção: Critérios mais próximo & randômico
Inserção: Critérios mais distante & randômico
Inserção: Critério melhor
Substituição: 2-OPT
Partição & Path_Link (Dijkstra)
Partição & Cycle_Link (Permutação)
Algoritmo Geométrico - Poligonais Convexas

Componentes
Lucas R. Dutra / Rubens Aguiar / Valcondes Rocha
Caio Gomes / Erick Barros / Renan Alves
João Vitor / Lucas Remigio / Nicolas Cruz
Jefferson Luciano / Pedro Jorge / Tiago Linhares
Maria Gleicielly / Jerfferson Gomes / Paulo Henrique
Igor Brasil / Kellton Leitão / Saulo Hachem
Fernando Igor / Lucas Freire / Lucas R. Rebelo
Thiago Araújo

Modelo da Tabela dos Experimentos Computacionais
Tabela 1: Resultados obtidos – PCV∗
No

Instância

n

Início

Máxima

Média

Solução

tempo(s)

1
Tsp16
16
—
————2
Tsp29
29
—
————3
Tsp58
58
—
————4
Tsp280
280
——
———5
Tsp1400
1400
——
———∗ O programa deve permitir de forma facilitada que novos testes possam ser realizados para outras instâncias.
Os arquivos correspondentes às instâncias estarão disponíveis a partir de 31/08/15.
Para encontrar os resultados (máximo ou pior, médio e mínimo ou Solução), executar o programa para cada instância pelo menos 3 vezes

4