O problema do corte-máximo (Max-Cut) é um problema NP-difícil que consiste em dividir um grafo em dois subconjuntos, com o objetivo de maximizar o peso das arestas cortadas entre eles. Este projeto foca-se na resolução do problema utilizando tanto algoritmos determinísticos como estocásticos, incluindo o Simulated Annealing.
O trabalho está dividido em duas vertentes principais:
Algoritmos determinísticos:
com implementação de pesquisa exaustiva e pesquisa gulosa para solução exata ou aproximada.Algoritmos estocásticos:
com métodos como Corte Aleatório, Simulated Annealing e Guloso Aleatório, que buscam soluções aproximadas de forma eficiente.
Foram avaliados os algoritmos em termos de complexidade, precisão, número de soluções testadas e trade-offs entre precisão e eficiência computacional, além da previsão de tempos de execução em função do tamanho do grafo.
Inclui ainda pseudocódigos para melhor compreensão dos métodos aplicados.