Banca de DEFESA: GABRIEL LOPES LIMA

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : GABRIEL LOPES LIMA
DATA : 03/03/2022
HORA: 14:00
LOCAL: Online
TÍTULO:

ALGORITMOS PARA RESOLUÇÃO DO PROBLEMA DO CORTE MÁXIMO: ABORDAGEM EXATA E META-HEURÍSTICAS


PALAVRAS-CHAVES:

Problema do Max-Cut. Abordagem exata. Árvore de busca binária. Meta-heurísticas.


PÁGINAS: 81
RESUMO:

O problema do corte máximo é um dos problemas de natureza combinatória amplamente abordados na literatura. Neste problema dado um grafo não direcionado e ponderado 𝐺 = (𝑉,𝐴), busca-se particionar o conjunto de vértices em dois subconjuntos, tal que a soma dos pesos das arestas que conectam os dois subconjuntos seja maximizada. Apesar da simplicidade da sua definição, o problema do corte máximo é NP-Completo, sendo classificado também como NP- Difícil, ou seja, uma classe de problemas para a qual, até o momento, não foi definido um método para encontrar uma solução ótima em tempo polinomial de maneira determinística. Para resolver esses problemas com alta complexidade são usadas, na maioria das vezes, abordagens meta-heurísticas. Desta forma, diferente dos algoritmos já propostos na literatura e visando explorar a possibilidade de uma nova abordagem exata, que seja matematicamente interligada, capaz de explorar o espaço de soluções e encontrar a solução ótima para o problema, este estudo propõe um algoritmo de árvore de busca e desenvolve cinco algoritmos meta-heurísticos para solução do problema do max-cut. Esta pesquisa foi dividida em quatro fases: (i) desenvolvimento e implementação da abordagem exata para a solução do problema; (ii) implementação de cinco meta-heurísticas; (iii) execução de experimentos computacionais com diferentes tipos de instâncias de grafos; (iv) realização de análises estatísticas. Os resultados mostraram que para a solução do max-cut os métodos meta-heurísticos já existentes ainda apresentam um melhor trade-off entre encontrar uma boa solução e o tempo necessário para tal, pois, nessa primeira versão do algoritmo Árvore de Busca Binária (ABB), as complexidades ainda são muito elevadas para solucionar instâncias de grafos mais densos. A fim de resolver esse desafio da complexidade são necessárias explorações mais aprofundadas no algoritmo para encontrar um novo critério de contradição, para assim ser viável encontrar a solução ótima do problema em tempos aceitáveis para qualquer grafo.


MEMBROS DA BANCA:
Presidente - 2732514 - ISIS DIDIER LINS
Interno - 1078937 - RAPHAEL HARRY FREDERICO RIBEIRO KRAMER
Externo à Instituição - REINALDO MORABITO NETO
Notícia cadastrada em: 24/02/2022 09:15
SIGAA | Superintendência de Tecnologia da Informação (STI-UFPE) - (81) 2126-7777 | Copyright © 2006-2024 - UFRN - sigaa07.ufpe.br.sigaa07