A data structure for spanning tree optimization problems (2019)
- Authors:
- Autor USP: BARBOSA, MARCO AURÉLIO LOPES - ICMC
- Unidade: ICMC
- Sigla do Departamento: SSC
- DOI: 10.11606/T.55.2019.tde-29082019-141240
- Subjects: COMPUTAÇÃO EVOLUTIVA; DADOS CINÉTICOS; OTIMIZAÇÃO GLOBAL
- Keywords: Algoritmos de busca local; Algoritmos evolutivos; Árvores geradoras; Dynamic tree data structures; Estrutura de dados de árvores dinâmicas; Evolutionary algorithms; Local search algorithms; Spanning trees
- Language: Inglês
- Abstract: Os problemas de otimização de árvores geradoras estão relacionados a muitas aplicações práticas. Vários desses problemas são NP-difícies, o que limita a utilidade de métodos exatos e pode exigir abordagens alternativas, como metaheurísticas. Um questão relevante para muitas metaheurísticas é a estrutura de dados usada para representar e manipular as soluções. Uma estrutura de dados com operações eficientes pode aumentar a utilidade de um método, permitindo que instâncias maiores sejam resolvidas em um período de tempo razoável. Propomos a estrutura de dados 2LETT e a usamos para representar árvores geradoras em duas metaheurísticas: algoritmos evolutivos baseados em mutações e algoritmos de busca local. A operação principal da 2LETT é a troca de uma aresta na árvore representada por outra aresta. Esta operação tem tempo de O(√n), onde n é o número de vértices na árvore. Conduzimos avaliações qualitativas e quantitativas para 2LETT e outras estruturas na literatura. Para a principal operação de troca de arestas em algoritmos evolutivos, os experimentos computacionais mostram que a 2LETT possui o melhor desempenho para árvores com mais de 10.000 vértices. Para algoritmos de busca local, o 2LETT é a melhor opção para lidar com árvores grandes com grandes diâmetros.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2019
- Data da defesa: 17.06.2019
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
BARBOSA, Marco Aurélio Lopes. A data structure for spanning tree optimization problems. 2019. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2019. Disponível em: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29082019-141240/. Acesso em: 30 abr. 2024. -
APA
Barbosa, M. A. L. (2019). A data structure for spanning tree optimization problems (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29082019-141240/ -
NLM
Barbosa MAL. A data structure for spanning tree optimization problems [Internet]. 2019 ;[citado 2024 abr. 30 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29082019-141240/ -
Vancouver
Barbosa MAL. A data structure for spanning tree optimization problems [Internet]. 2019 ;[citado 2024 abr. 30 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29082019-141240/
Informações sobre o DOI: 10.11606/T.55.2019.tde-29082019-141240 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
