Trabalho sobre problema np-completo

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1527 palavras )
  • Download(s) : 0
  • Publicado : 26 de novembro de 2012
Ler documento completo
Amostra do texto
Algoritmos e Estrutura de Dados 3

Trabalho Prático 2
Bacharelado 1o Semestre de 2012

Este trabalho prático tem por objetivo modelar um problema NP-Completo que envolve estruturas de grafos, elaborar diferentes heurísticas para solucionar um mesmo problema e, por fim, apresentar uma análise comparativa entre essas abordagens.

1

Definição do Problema

Este trabalho aborda o problema doBanco Central que consiste em encontrar o menor número de guardas necessários para vigiar um banco. Esse é um problema de visibilidade da geometria computacional. O layout do banco é representado por um polígono simples de arestas não colineares, isto é, as arestas não adjacentes do polígono não se interceptam e nenhuma aresta está alinhada a outra. Essas restrições impostas ao layout do bancosimplificam o problema e evitam que o aluno tenha que tratar casos mais complexos de interseção de retas. Nesse layout (polígono), um possível guarda do banco é representado por um vértice. Dessa forma, um conjunto S de guardas (vértices) vigia um banco (polígono) se, e somente se, para cada vértice v do polígono, existe algum vértice u ∈ S tal que um segmento de reta entre v e u NÃO abandona opolígono – isto é, esse segmento de reta está totalmente contido dentro do polígono, ou coincide com algum vértice/aresta desse polígono. As funções para interseção de segmentos de reta apresentadas no livro do Sedgewick podem ser utilizadas (ver Referências). A Figura 1 apresenta o layout de uma instância do problema com as coordenadas indicadas para cada vértice que compõe o polígono. Para a instânciaapresentada, apenas dois guardas são suficientes para vigiar o banco (guardas representados por vértices em vermelho). Caso um guarda não seja capaz de vigiar um vértice, foi apresentado um segmento de reta do guarda a esse vértice que deixa o polígono. Apesar de existirem múltiplas soluções para uma dada instância, o número ótimo de vértices que vigia todo o polígono permanece o mesmo.
(5,200)(60,200) (5,200) (60,200)

(60,150)

(100,150) (5,140)

(60,150)

(100,150)

(5,140) (1,120)

(50,140)

(50,140) (50,120) (1,120)

(50,120)

(40,50)

(40,50) (100,50)

(100,50)

(1,1)

(40,1)

(1,1)

(40,1)

(a) O guarda (50,140) não vigia os vértices (1,1), (1,120), (40, 1) e (40,50).

(b) O guarda (1,120) não vigia os vértices (50,140), (5,140), (5,200),(60,200), (60,150) e (100,150).

Figura 1: Dado o layout acima, os guardas (1,120) e (50,140) vigiam todos os vértices do polígono, sendo o número mínimo (ótimo) de guardas necessários para vigiar esse banco igual a dois. Para cada figura, foram incluídos os segmentos de reta entre os guardas e os demais vértices que abandonam o polígono, o que indica os vértices não visíveis para cada guarda.

1 Neste trabalho, o aluno deve elaborar duas heurísticas distintas que solucionem o problema, e apresentar uma análise comparativa entre os resultados obtidos pelas abordagens para uma mesma instância. PONTO EXTRA: apresentar e justificar o fator de aproximação das duas heurísticas em relação a solução ótima do problema para qualquer instância genérica. Dessa forma, pede-se que o aluno apresente oquanto sua solução proposta pode estar distante no máximo da solução ótima. A implementação do algoritmo DEVE utilizar alocação dinâmica de memória.

1.1

Entrada e Saída

O arquivo executável deve ser chamado de tp2 e deve receber como parâmetro o arquivo de entrada input.txt e o arquivo de saída output.txt, conforme demonstrado a seguir: ./tp2 -i input.txt -o output.txt O arquivo input.txtdeve conter as seguintes informações, na ordem indicada abaixo: 1. número de instâncias do problema; 2. número de vértices v de um polígono; 3. v linhas com: coordenadas x e y para cada vértice do polígono. As coordenadas dos vértices de id entre 1 e v são apresentadas em ordem no arquivo input.txt por duas partes inteiras, numerador e denominador. A ordem de apresentação desses vértices segue o...
tracking img