PUC-Rio
Departamento de Informática
Profs. Marcus Vinicius S. Poggi de Aragão
Período: 2003.1
16 de junho de 2003
Horário: 2as-feiras e 4as-feiras de 16 às 18 horas
ANÁLISE DE ALGORITMOS (INF 1721)
2o Trabalho Prático (T2)
- O objetivo do 2o Trabalho é a implementação de um algoritmo de
branch-and-bound para um problema NP-difícil. Isto é, um
problema de otimização cuja versão de decisão é um problema
NP-completo.
Este trabalho deve ser feito em grupos de no MÁXIMO 2(DOIS). Caso
contrário não será considerado.
A apresentação do seu algoritmo deve conter uma descrição de cada um
dos elementos em um branch-and-bound, são eles:
-
Critério de particionamento do espaço de soluções;
- Uma relaxação do problema (um majorante se o problema é de
maximização, minorante caso contrário). Neste item, mostre como a
sua relaxação é modificada quando se considera apenas um subconjunto
do espaço de soluções (ou seja, quando um elemento tem seu valor
fixado ou passa a não poder receber alguns valores).
- Um método para obter uma "boa" solução viável (um minorante se o problema é de
maximização, majorante caso contrário). Esta solução pode ser obtida
por um método guloso e refinada por uma busca local. (Para obter uma
solução ainda melhor, utilize uma metaeurística, como GRASP, Busca Tabu,
Algoritmo Genético, etc. NÃO é obrigatório).
- Critério de seleção do particionamento a ser feito em cada
nó da árvore de busca.
- Critério de percorrimento da árvore de busca (sugere-se que
seja busca em profundidade, permitindo uma implementação recursiva e
mais simples de ser feita).
- O problema sobre o qual deve-se aplicar o algoritmo de
branch-and-bound segue:
- Problema da Árvore Geradora com Restrições de Capacidade (CAP-MST):
Dado um grafo G=(V È { r }, E), custos c(i,j) ³ 0 associadas às arestas (i,j) em E,
demandas q(v) associados aos vértices v em V, e uma capacidade Q. Deseja-se encontrar
uma árvore geradora de G, cujas sub-árvores enraizadas no vértice r possuam a soma das demandas
dos seus vértices inferiores ou iguais à Q, cujo custo total de suas arestas seja mínimo.
As instâncias estão no link CAP-MST da página de Análise de Algoritmos 03.1.
Apresente sempre a sua melhor solução (lista das arestas com seus respectivos valores)
e o seu valor total. Caso o tempo de CPU ultrapasse 1 hora, faça com que seu algoritmo termine
imprima a melhor solução encontrada até então.
Deverá ser apresentado um relatório sobre as experiências computacionais comentando
os resultados obritdos. Este relatório deverá conter uma tabela com o valor da melhor solução
obtida, indicando se é ótima (provado pelo seu algoritmo) ou não, o tempo de cpu total utilizado
na resolução, o valor do limite inferior obtido no nó raiz, e o valor da solução ótima (ou melhor
conhecida) que serão fornecidos. A tabela deverá ter uma linha para cada uma das 39 instâncias
contidas no arquivo no link.
Os códigos (comentados) devem ser entregues eletronicamente apenas.
This document was translated from LATEX by HEVEA.