Um algoritmo exato para um problema de Galeria de Arte / An exact algorithm for an Art Gallery problem
AUTOR(ES)
Marcelo Castilho Couto
DATA DE PUBLICAÇÃO
2010
RESUMO
Nesta dissertação, faz-se um amplo estudo multidisciplinar sobre duas variantes de um problema geométrico NP-DIFÍCIL, o Problema da Galeria de Arte, que é analisado tanto pela ótica geométrica quanto combinatória. O objetivo consiste em minimizar o número de guardas suficientes para cobrir todo o interior de uma galeria de arte, representada por um polígono simples. Dentre as muitas variantes desse problema, o foco foi dado àquela onde os guardas são estacionários e restritos aos vértices do polígono, ortogonal ou simples, sem obstáculos. Propõe-se neste trabalho um algoritmo iterativo exato que é capaz de resolver ambas as variantes do problema. Nesse algoritmo, o problema original é discretizado, reduzido a um problema combinatório, o Problema da Cobertura de Conjuntos, e modelado por programação linear inteira. A redução entre os problemas que assegura a corretude do algoritmo e as provas de exatidão e convergência para uma solução ótima do problema original são detalhadas. Apresenta-se também uma extensa experimentação de uma implementação desse algoritmo com o intuito de validar seu uso prático e analisar as várias estratégias propostas aqui para a discretização inicial da galeria. São dados resultados para instâncias com até 2500 vértices, mais de dez vezes o tamanho das maiores instâncias resolvidas exatamente na literatura pré-existente. Mostra-se que o número de iterações executadas pelo algoritmo está extremamente relacionada com o modo como a galeria é inicialmente discretizada. Considerando a estratégia de discretização com o melhor desempenho geral, tem-se que, na prática, o algoritmo converge para uma solução ótima para o problema original em um baixo tempo computacional e em um número de iterações que é ordens de grandeza aquém do limite teórico resultante da análise de pior caso
ASSUNTO(S)
algorítimos combinatorial geometry combinatorial optimization integer programming otimização combinatória programação inteira geometria combinatória algorithms
ACESSO AO ARTIGO
http://libdigi.unicamp.br/document/?code=000779213Documentos Relacionados
- Um algoritmo exato para problemas das P-medianas
- Implementação paralela de um algoritmo exato para a resolução de um problema de seqüenciamento de padrões de corte
- Parallel implementation of an exact algorithm to solve a cutting pattern sequencing problem
- Um algoritmo exato para o problema de empacotamento bidimensional em faixas
- Um algoritmo exato para a otimização de carteiras de investimento com restrições de cardinalidade