Algoritmos para resolução do problema do corte máximo : abordagem exata e meta-heurísticas

Abstract

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 G = (V, A), 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, 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 o método exato proposto é eficaz e preferível em casos de pequeno porte, já os métodos meta-heurísticos existentes, em casos de grande porte, 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), a complexidade ainda é muito elevada 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.