Trabalho sobre problema np-completo

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 do Banco 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 banco simplificam 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 o polí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ância apresentada, 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)