Uma abordagem heurística construtiva para o problema de maximização do número de legendas

Braga, Vitor Ramos

DSpace Home
→
Centro de Ciências Exatas e Tecnologia (CCET)
→
Informática Aplicada
→
INAP - Dissertações de Mestrado
→
View Item

dc.contributor.advisor	Alvim, Adriana Cesário de Faria
dc.contributor.author	Braga, Vitor Ramos
dc.date.accessioned	2019-06-12T21:13:19Z
dc.date.available	2019-06-12T21:13:19Z
dc.date.issued	2009-08-18
dc.identifier.citation	BRAGA, Vitor Ramos. Uma abordagem heurística construtiva para o problema de maximização do número de legendas. 2009. 120f. Dissertação (Mestrado em Informática) - Universidade Federal do Estado do Rio de Janeiro, Rio de Janeiro, 2009.	pt_BR
dc.identifier.uri	http://hdl.handle.net/unirio/12820
dc.description	Dissertação também disponível em formato impresso, com o número de chamada MI 2009/18.	pt_BR
dc.description.sponsorship	n/a	pt_BR
dc.language.iso	Portuguese	pt_BR
dc.rights	openAccess	pt_BR
dc.title	Uma abordagem heurística construtiva para o problema de maximização do número de legendas	pt_BR
dc.title.alternative	A constructive heuristic approach for the label number maximization	pt_BR
dc.type	masterThesis	pt_BR
dc.contributor.referee	Alvim, Adriana Cesário de Faria
dc.contributor.referee	Ciarlini, Angelo Ernani Maia
dc.contributor.referee	Rosseti, Isabel Cristina Mello
dc.contributor.referee	Barboza, Eduardo Uchoa
dc.degree.department	CCET	pt_BR
dc.degree.grantor	Universidade Federal do Estado do Rio de Janeiro - UNIRIO	pt_BR
dc.degree.level	Mestrado Acadêmico	pt_BR
dc.degree.local	Rio de Janeiro, RJ	pt_BR
dc.degree.program	Programa de Pós-Graduação em Informática	pt_BR
dc.subject.cnpq	CIÊNCIAS EXATAS E DA TERRA	pt_BR
dc.subject.cnpq	CIÊNCIA DA COMPUTAÇÃO	pt_BR
dc.subject.en	Point-Feature Label Placement	pt_BR
dc.subject.en	Pre-processing	pt_BR
dc.subject.en	Constructive Heuristic	pt_BR
dc.subject.en	Slider model	pt_BR
dc.description.abstracten	The Label Number Maximization Problem (LNM) consists in defining label positions for features of a map or graph, in a way to avoid conflicts and maximize the number of features labeled. Each feature has, at most, one label and a conflict is defined as an overlapping between labels or between labels and features. This thesis proposes a new LNM resolution algorithm made of two stages: pre-processing and constructive heuristic. The pre-processing stage is independent of the constructive heuristic and its main advantage over other two-dimension cartographic reduction technics is being able to be fully applied on Slider Model based algorithms. The experimental results shows that both the pre-processing and constructive heuristic overmatch other technics presented in literature in terms of quality and running time, mainly in the resolution of problem instances with a higher difficulty level.	pt_BR
dc.degree.country	Brasil	pt_BR
dc.description.sponsordocumentnumber	n/a	pt_BR
dc.description.abstractpt	O Problema de maximizacão do Número de Legendas (PMNL) consiste em definir ´ posicões de legendas para atributos de um mapa ou gráfico, de modo que não haja conflitos e o número de atributos legendados seja máximo. Cada atributo possui no máximo uma legenda, e um conflito é definido como uma sobreposição entre áreas de legendas ou entre legendas e atributos. Este trabalho propõe um novo algoritmo para resolução do PMNL, que se divide em duas partes: pré-processamento e heurística construtiva. O pré-processamento é independente da heurística construtiva e possui como principal vantagem, em relação a outras técnicas de redução¸ para instâncias de problemas cartográficos ´ em duas dimensões, a possibilidade de ser aplicado em sua totalidade a algoritmos baseados no Slider Model. Os resultados experimentais mostram que tanto o pré-processamento quanto a heurística construtiva, superam outros métodos apresentados na literatura em termos de qualidade e tempo de execucão, principalmente na resolução de instâncias com maior nível de dificuldade.	pt_BR
dc.subject.pt	Rotulação catalográfica de pontos	pt_BR
dc.subject.pt	Pré-processamento	pt_BR
dc.subject.pt	Heurística construtiva	pt_BR
dc.subject.pt	Modelo contínuo	pt_BR