PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Horário: 2as-feiras e 4as-feiras de 9 às 11 horas - Sala 546L
25 de junho de 2008
Data da Entrega: 10 de julho de 2008
Período: 2008.1
ANÁLISE DE ALGORITMOS (INF 1721)

2o Trabalho de Implementação

Descrição

Este trabalho prático consiste em desenvolver um algoritmo de enumeração (implícita) e o código correspondente. O objetivo é verificar as limitações computacionais na resolução de problemas onde algoritmos com complexidade menor são desconhecidos. Para isso o desempenho das implementações destes algoritmos deverá ser analisado com respeito ao tempo de CPU.

O desenvolvimento do códigos e a análise deve seguir o seguinte roteiro: A corretude código será testada sobre os conjuntos de instâncias distribuidos. O trabalho entregue deve conter: 1. O problema

O problema que o algoritmo deve resolver é:

2. O algoritmo

O algoritmo deve apresentar uma atribuição que verifica que a instância dada pode ser ``colorida'' com K cores ou demonstrar que tal atribuição não existe.

Para esta segunda parte é necessário testar todas as possibilidades de atribuir K valores aos vértices do grafo o que, entretanto, não obriga que todas as possíveis atribuições sejam testadas. Veja, por exemplo, o algoritmo de BackTrack apresentado no capítulo 9 do livro por Dasgupta, Papadimitiriou e Vazirani, ``Algorithms'' (citado na ementa do curso).

Um algoritmo deste tipo funciona da seguinte forma: para cada vértice armazena-se o conjunto das cores que este pode receber (inicialmente {1,...,K}). A cada iteração um vértice recebe uma cor deste conjunto, operação que retira esta cor dos conjuntos de cores possíveis de todos os vértices a ele adjacentes. Esta operação se repete até que todos os vértices tenham recebido uma cor e o algoritmo termina (visto que nesse momento uma atribuição válida foi encontrada), ou até que todos os vértices ainda sem cor atribuída tenham seu conjunto de cores possíveis vazio. Neste, faz-se um backtrack. Ou seja, o último vértice que recebeu uma cor troca sua cor por outra do seu conjunto de cores possíveis que ainda não recebeu. Observe que esta troca de cor modifica os conjuntos de cores possíveis de todos os seus vizinhos. Caso todas as cores do seu conjunto tenham sido testadas, faz-se mais um nível de backtrack deixando este vértice sem cor atribuída (e atualizando os conjuntos de cores possíveis dos vizinhos) e refazendo esta mesma operação para o vértice que havia sido colorido imediatamente antes.

Observe, que a atribuição de cores é arbitrária, isto é, existem K! atribuições equivalentes. Isto implica que o primeiro vértice a ser colorido pode receber somente a cor 1. A segunda cor a ser usada pode ser a 2 sem precisar testar com outra cor, e assim por diante até a cor K ser usada. Com isso, o número de atribuições testadas é dividido por K!.

Sugere-se que esta implementação seja feita utilizando recursão, para reduzir o esforço de codificação.

Finalmente, caso se aposte que existe uma atribuição válida, pode-se tentar encontrá-la por métodos heurísticos, isto é, sem garantia de sucesso e que quando não encontram uma atribuição válida, não geram nenhuma informação com relação a sua existência.

Uma heurística simples e frequentemente eficaz é aplicar uma busca em profundidade que atribui aos vértices visitados sempre a menor cor possível. Muitas outras heurísticas (ou meta-heurísticas) menos eficientes mas mais eficazes existem na literatura.

3. Aplicação e Testes

Uma aplicação do algoritmo proposto acima é jogo conhecido como SUDOKU. Neste jogo um mesmo grafo aparece com alguns vértices já coloridos e o objetivo é encontrar uma atribuição de 9 cores aos vértices ainda sem cor atribuída.

Os testes devem ser feitos sobre um conjunto de instâncias de grafos com valores de K indicados e um subconjunto dos vértices com as respectivas cores atribuídas. Em particular haverá uma série de instâncias do SUDOKU. Nestes caso, como sabe-se que existe uma atribuição deve-se explicitar quando foi usada uma heurística e quando não.

As instâncias estão disponíveis na página do curso.


This document was translated from LATEX by HEVEA.