TRABALHO 1:

ÁRVORES E ESTRUTURAS DE PRIORIDADE EM C DRAFT 0

RAUL H.C. LOPES

1. Preliminares

Este trabalho consiste em exercício de programação em uma linguagem imperativa sobre algumas das estruturas do trabalho anterior. Para tal você implementará em linguagem C/C++ duas soluções heurísticas para o problema de encontrar o melhor tour para o problema do TSP. Você implementará as heurística NN e Greedy com fila de prioridade descritas no trabalho anterior^{1} e uma heurística para melhora de tour obtido.

Algumas dicas importantes sobre a execução do trabalho seguem.

(1) Não deixe de ler este documento por completo antes de iniciar o trabalho.

(2) Siga estritamente as especificações deste documento: qualquer desvio delas pode significar a anulação de um exercício ou de todo o trabalho.

O trabalho pode ser executado em grupos, mas, como estabelecido na seção 6, grupos maiores recebem menos créditos. Um elemento importante da avaliação do trabalho trata da deteção de mutualismo parasitário: situação em que um aluno atua de vampiro parasita sugando o resultado do trabalho do grupo. Fato: plágio em qualquer item de um trabalho implica na anulação completa do trabalho do(s) grupo(s) envolvidos. Qualquer elemento de um grupo pode ser, durante a execução do trabalho ou após a entrega do mesmo, avaliado em relação ao conhecimento do que foi feito. Essa avaliação poderá ser feita de forma oral ou por escrito.

2. As heurísticas

2.1. Vizinho mais próximo e guloso. As heurística NN e Greedy estão descritas no documento do Trabalho Prático 0.

1 Para mais detalhes sobre o problema e as heurísticas veja documento do Trabalho Prático 0 e referências nele contidas.

2.2. Busca local. Uma das mais importantes heurísticas para obter o melhor tourpossível para o TSP consiste em usar os seguintes passos:

• construir um tour inicial t_{0} usando heurísticas como NN ou Greedy;

• melhorar o tour t_{0} usando heurísitca de busca local realizam exclusão de algumas arestas, seguida de religação dos nós de grau um para obter um tour.

A heurística de busca local acima referida é implementada a partir de alguma variante do processo de permutação limitada de nós, conhecido na literatura como operação k-opt^{2}.

Um tour t_{1} é obtido de um tour t_{0} por k-opt quando t_{1} é obtido pelos seguintes passos:

• geração de um grafo desconexo t′ pela exclusão de k arestas não consecutivas de t_{0};

• religação de nós de grau um presentes em t′ para obter o tour t_{1}

3. Representação de tour

Escolha para representar seu tour uma das seguintes estruturas^{3}: • array com a seqüência de nós;

• lista duplamente encadeada;

• árvore binária com operações de splay;

• árvore em dois níveis. As seguintes observações são importantes na escolha da representação

do tour:

(1) Você deve escolher obrigatoriamente dentre uma das alternativas acima.

(2) Sua escolha afetará significativamente o desempenho do programa, que é o item mais importante da avaliação deste trabalho.

(3) Implementar as operações descritas na página quatro de [Fredman:tspds] deverá faciltar em muito sua tarefa de implementação. As operações ali descritas são:

• Next(a): Dado nó a, determina o nó que o segue no tour.

• P rev(a): Dado nó a, determina o nó que o precede no tour.

2 Veja artigo, referenciado neste documento como [Fredman:tspds], sobre alternativas para representação de tour, que facilitam a implementação da operação k-opt.

3 Descritas em [Fredman:tspds].

• Between(a, b, c): predicado que determina se b está entre a e c no tour.

• F lip(a, b, c, d): atualiza tour, excluindo as arestas (a, b) e (c, d) e inserindo as arestas (b, c) e (a, d).

Note que está implícito em todas essas operações o parâmetro que representa o tour.

4. Fila de prioridade

A heurística Greedy demanda uma estrutura de prioridade. Escolha sua estrutura de prioridade dentre as seguintes:

(1) Binomial queue^{4}

(2) Árvore auto-ajustável^{5}

(3) Árvores splay^{6}

(4) Árvore 2-3.

Novamente sua escolha está restrita a uma dessas estruturas e ela afetará significativamente o desempenho do seu programa.

5. Os exercícios

Exercício 1. Implemente um programa cálculo de tour, usando a heurística NN e uma estrutura de árvore binária espacial, como descrita no Trabalho Prático 0.

Exercício 2. Implemente um programa para cálculo de tour, usando a heurística Greedy, combinada com árvore binária espacial e árvore de prioridade.

Exercício 3. Implemente um programa que gere um tour inicial usando a heurística NN, como no exercício 1, melhore o tourusando k-opt.

Exercício 4. Implemente um programa que gere um tour inicial usando a heurística Greedy, como no exercício 2, melhore o tourusando k-opt.

6. Créditos

A definição dos critérios de avaliação A atribuição de nota para o trabalho ocorrerá em duas fases:

(1) Atribuição de créditos pelo trabalho submetido, de acordo com a tabela 1.

(2) Definição do multiplicador de acordo com a tabela 2.

4Descrita no artigo vuillemin.

5 Descritas em [sleator83] e no Trabalho Prático 0.

6Descritas em [sleator85].

Critério Créditos
Seção 1  10
Seção 2  10
Seção 3  10
Seção 4  10
Seção 6.4  10
Seção 6.6  10
Seção 6.7  10
Seção 6.8  10
Secão 6.5  10
Seção 6.9  10

Tabela 1. Tabela de atribuição de créditos

6.1. Definição do número de créditos. Cada trabalho submetido será avaliado para receber de zero a cem créditos de acordo com a tabela 1.

6.2. Critério fundamental da atribuição de créditos. Os critérios que definem atribuição de créditos colocam uma ênfase especial na eficiência (50% dos créditos vão para desempenho) e correção: programas que apresentam qualquer erro não podem participar de nenhuma competição de desempenho.

6.3. A avaliação não comparativa. Os itens das seções 1,2,3 e 4 serão avaliados em relação:

• Correção do tour;

• Correção do uso de memória;

• Melhoria no tour no caso das seçoes 3 e 4.

6.4. Estudo de qualidade. Escreva um artigo curto (duas ou três páginas em L^{A}TEX) comparando os programas implementados com respeito a:

• qualidade do tour;

• tempo de execução;

• demanda de memória.

6.5. O melhor tour. Neste item os tours de todos programas serão comparados para definir o melhor. Em cada teste realizado, o grupo com o melhor programa receberá dez créditos e os outros grupos receberão créditos razão inversa da piora da qualidade do tour, quando comparado com o melhor grupo.

Fator  Multiplicador
Grupos de 1 aluno  11/100
Grupos de 2 alunos  10/100
Grupos de 3 alunos  75/100
Grupos de 4 alunos  60/100
Grupos de mais 4 alunos  0
Plágio  0

Tabela 2. Tabela de multiplicadores

A nota de cada grupo neste item será a média das notas dos diversos testes.

6.6. O mais rápido NN. Usando a mesma metodologia de atribuição de créditos da seção 6.5, buscar-se-á aqui a implementação mais rápida para o exercício 1.

6.7. O mais rápido Greedy. Usando a mesma metodologia de atribuição de créditos da seção 6.5, buscar-se-á aqui a implementação mais rápida para o exercício 2.

6.8. O mais rápido k-opt. Usando a mesma metodologia de atribuição de créditos da seção 6.5, buscar-se-á aqui a implementação mais rápida para os exercício 3 e 4, obedecendo à seguinte restrição:

• Só podem participar programas que tenham produzido tour que seja no máximo 10% pior que o vencedor do teste da seção 6.5. Eliminam-se aqui programas que são rápidos porque não produzem um tour minimamente respeitável.

6.9. O mais econômico k-opt. Usando a mesma metodologia de atribuição de créditos da seção 6.5, buscar-se-á aqui a implementação com menor uso de memória para os exercício 3 e 4, obedecendo à seguinte restrição:

• Só podem participar programas que tenham produzido tour que seja no máximo 10% pior que o vencedor do teste da seção 6.5. Eliminam-se aqui programas que são rápidos porque não produzem um tour minimamente respeitável.

6.10. Definição de multiplicador. O nota de cada trabalho é dada pelo número de créditos obtidos pelo trabalho multiplicado pelo fator da tabela 2.

Em caso de plágio todos os trabalhos de grupos envolvidos são anulados. Poderá ser enquadrado como plágio qualquer trabalho em que um mais alunos do grupo não tenham conhecimento de qualquer item do trabalho. Esse conhecimento deverá ser demonstrado em prova e/ou enttrevista.

7. A submissão para correção

A definição do formato de submissão do trabalho estará na versão deste documento do dia 20/01/05.

A data provisória de entrega deste trabalho é 25/02/05.