Trabalho sobre problema np-completo

1527 palavras 7 páginas
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)

Relacionados

  • o bovino
    3298 palavras | 14 páginas
  • Trabalho Analise De Algoritimos
    1655 palavras | 7 páginas
  • Problemas NP Completo
    2315 palavras | 10 páginas
  • NP - Completo
    3806 palavras | 16 páginas
  • Computabilidade
    3840 palavras | 16 páginas
  • np-complexo
    7876 palavras | 32 páginas
  • Teoria da computação
    2482 palavras | 10 páginas
  • EAD 2014
    3904 palavras | 16 páginas
  • Problemas Intrataveis
    4258 palavras | 18 páginas
  • Complexidade de Algotmo
    11772 palavras | 48 páginas