Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo /

Mostrar outras versões (1)

Resumo: O Problema da Árvore Geradora Multiobjetivo é NP-árduo e modela aplicações em diversas áreas. Esta pesquisa apresenta uma análise experimental de diferentes estratégias utilizadas na literatura para desenvolver algoritmos exatos para resolver o problema. Inicialmente, os algoritmos são class...

ver descrição completa

Na minha lista:

Detalhes bibliográficos
Principais autores:	Drumond, Patricia Medyna Lauritzen de Lucena., Goldbarg, Elizabeth Ferreira Gouvêa., Universidade Federal do Rio Grande do Norte.
Formato:	Dissertação
Publicado em:
Assuntos:	Algoritmos experimentais - Dissertação. Algoritmos exatos - Árvore geradora multiobjetivo - Análise experimental - Experimental algorithms. Exact algorithms. Multiobjective spanning tree.
Endereço do item:	https://repositorio.ufrn.br/jspui/bitstream/123456789/18047/1/PatriciaMLLD_DISSERT.pdf
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	oai:localhost:123456789-119688
record_format	dspace
spelling	oai:localhost:123456789-1196882022-11-30T21:40:21Z Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo / Drumond, Patricia Medyna Lauritzen de Lucena. Goldbarg, Elizabeth Ferreira Gouvêa. Universidade Federal do Rio Grande do Norte. Algoritmos experimentais - Dissertação. Algoritmos exatos - Dissertação. Árvore geradora multiobjetivo - Dissertação. Análise experimental - Dissertação. Experimental algorithms. Exact algorithms. Multiobjective spanning tree. Resumo: O Problema da Árvore Geradora Multiobjetivo é NP-árduo e modela aplicações em diversas áreas. Esta pesquisa apresenta uma análise experimental de diferentes estratégias utilizadas na literatura para desenvolver algoritmos exatos para resolver o problema. Inicialmente, os algoritmos são classificados de acordo com as abordagens utilizadas para resolver o problema. Características de duas ou mais abordagens podem ser encontradas em alguns desses algoritmos. As abordagens aqui investigadas são: o método duas fases, branch-and-bound, k-best e a abordagem baseada em preferência. A principal contribuição deste trabalho está no fato de que nenhuma pesquisa desenvolvida até o momento relata uma análise sistemática experimental de algoritmos exatos para o problema da Árvore Geradora Multiobjetivo. Portanto, este trabalho pode ser uma base para outras pesquisas que lidam com o mesmo problema. Os experimentos computacionais comparam o desempenho de algoritmos em relação ao tempo de processamento, à eficiência com base no número de objetivos e no número de soluções encontradas em um intervalo de tempo controlado. A análise dos algoritmos foi realizada para instâncias conhecidas do problema, bem como para instâncias obtidas a partir de um gerador bastante utilizado na literatura.#$&Abstract: The Multiobjective Spanning Tree Problem is NP-hard and models applications in several areas. This research presents an experimental analysis of different strategies used in the literature to develop exact algorithms to solve the problem. Initially, the algorithms are classified according to the approaches used to solve the problem. Features of two or more approaches can be found in some of those algorithms. The approaches investigated here are: the two-stage method, branch-and-bound, k-best and the preference-based approach. The main contribution of this research lies in the fact that no research was presented to date reporting a systematic experimental analysis of exact algorithms for the Multiobjective Spanning Tree Problem. Therefore, this work can be a basis for other research that deal with the same problem. The computational experiments compare the performance of algorithms regarding processing time, efficiency based on the number of objectives and number of solutions found in a controlled time interval. The analysis of the algorithms was performed for known instances of the problem, as well as instances obtained from a generator commonly used in the literature. 1 2022-10-06T04:55:27Z 2022-10-06T04:55:27Z 2012. Dissertação 004.021 D795a DISSERT 182810 https://repositorio.ufrn.br/jspui/bitstream/123456789/18047/1/PatriciaMLLD_DISSERT.pdf https://repositorio.ufrn.br/jspui/bitstream/123456789/18047/1/PatriciaMLLD_DISSERT.pdf
institution	Acervo SISBI
collection	SIGAA
topic	Algoritmos experimentais - Dissertação. Algoritmos exatos - Dissertação. Árvore geradora multiobjetivo - Dissertação. Análise experimental - Dissertação. Experimental algorithms. Exact algorithms. Multiobjective spanning tree.
spellingShingle	Algoritmos experimentais - Dissertação. Algoritmos exatos - Dissertação. Árvore geradora multiobjetivo - Dissertação. Análise experimental - Dissertação. Experimental algorithms. Exact algorithms. Multiobjective spanning tree. Drumond, Patricia Medyna Lauritzen de Lucena. Goldbarg, Elizabeth Ferreira Gouvêa. Universidade Federal do Rio Grande do Norte. Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo /
description	Resumo: O Problema da Árvore Geradora Multiobjetivo é NP-árduo e modela aplicações em diversas áreas. Esta pesquisa apresenta uma análise experimental de diferentes estratégias utilizadas na literatura para desenvolver algoritmos exatos para resolver o problema. Inicialmente, os algoritmos são classificados de acordo com as abordagens utilizadas para resolver o problema. Características de duas ou mais abordagens podem ser encontradas em alguns desses algoritmos. As abordagens aqui investigadas são: o método duas fases, branch-and-bound, k-best e a abordagem baseada em preferência. A principal contribuição deste trabalho está no fato de que nenhuma pesquisa desenvolvida até o momento relata uma análise sistemática experimental de algoritmos exatos para o problema da Árvore Geradora Multiobjetivo. Portanto, este trabalho pode ser uma base para outras pesquisas que lidam com o mesmo problema. Os experimentos computacionais comparam o desempenho de algoritmos em relação ao tempo de processamento, à eficiência com base no número de objetivos e no número de soluções encontradas em um intervalo de tempo controlado. A análise dos algoritmos foi realizada para instâncias conhecidas do problema, bem como para instâncias obtidas a partir de um gerador bastante utilizado na literatura.#$&Abstract: The Multiobjective Spanning Tree Problem is NP-hard and models applications in several areas. This research presents an experimental analysis of different strategies used in the literature to develop exact algorithms to solve the problem. Initially, the algorithms are classified according to the approaches used to solve the problem. Features of two or more approaches can be found in some of those algorithms. The approaches investigated here are: the two-stage method, branch-and-bound, k-best and the preference-based approach. The main contribution of this research lies in the fact that no research was presented to date reporting a systematic experimental analysis of exact algorithms for the Multiobjective Spanning Tree Problem. Therefore, this work can be a basis for other research that deal with the same problem. The computational experiments compare the performance of algorithms regarding processing time, efficiency based on the number of objectives and number of solutions found in a controlled time interval. The analysis of the algorithms was performed for known instances of the problem, as well as instances obtained from a generator commonly used in the literature.
format	Dissertação
author	Drumond, Patricia Medyna Lauritzen de Lucena. Goldbarg, Elizabeth Ferreira Gouvêa. Universidade Federal do Rio Grande do Norte.
author_facet	Drumond, Patricia Medyna Lauritzen de Lucena. Goldbarg, Elizabeth Ferreira Gouvêa. Universidade Federal do Rio Grande do Norte.
author_sort	Drumond, Patricia Medyna Lauritzen de Lucena.
title	Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo /
title_short	Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo /
title_full	Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo /
title_fullStr	Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo /
title_full_unstemmed	Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo /
title_sort	uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo /
publishDate	2022
url	https://repositorio.ufrn.br/jspui/bitstream/123456789/18047/1/PatriciaMLLD_DISSERT.pdf
work_keys_str_mv	AT drumondpatriciamedynalauritzendelucena umaanaliseexperimentaldealgoritmosexatosaplicadosaoproblemadaarvoregeradoramultiobjetivo AT goldbargelizabethferreiragouvea umaanaliseexperimentaldealgoritmosexatosaplicadosaoproblemadaarvoregeradoramultiobjetivo AT universidadefederaldoriograndedonorte umaanaliseexperimentaldealgoritmosexatosaplicadosaoproblemadaarvoregeradoramultiobjetivo
_version_	1766846660848123904

Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo /

Registros relacionados