Terminal de consulta web

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